An MSc thesis on implementing F4

Daniel Cabarcas’ Msc thesis has the title An Implementation of Faugère’s F4 Algorithm for Computing Gröbner Bases and the following abstract:

“Gröbner bases are an important tool for analyzing systems of polynomial equations. They allow the system of equations to be solved exactly and therefore have gained popularity in many areas of science and technology. However, finding Gröbner bases is a computationally intensive task, thus, several algorithms have been developed for this goal. Faugère invented an elaborate algorithm to compute Gröbner bases in 1999 called F4 , which has become a benchmark due to its efficiency.
We have implemented F4 from scratch in C++. In this thesis we revisit the theoretical foundation of the algorithm, provide details of our implementation, and compare it with other software that computes Gröbner bases.”

I probably know about 10 people who tried to implement the algorithm in such a way that it’s performance is reasonable, most didn’t succeed.  It’s nice to see that somebody has succeeded to some extend (see Experimental Results p.46ff) and wrote about it.

PS: Daniel posted about F4 on [sage-devel] before which sparked a short discussion about F4.

One thought on “An MSc thesis on implementing F4

  1. I sometimes wonder why we can’t see the original implementation of F4 by its inventor 😦 In SAT, the field advanced enormously once people could see each others’ ideas implemented.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s