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.
malb::blog 