Faugère F4 algorithm

In computer algebra, the Faugère F4 algorithm, by Jean-Charles Faugère, computes the Gröbner basis of an ideal of a multivariate polynomial ring. The algorithm uses the same mathematical principles as the Buchberger algorithm, but computes many normal forms in one go by forming a generally sparse matrix and using fast linear algebra to do the reductions in parallel. The Faugère F4 algorithm is implemented

• as a package FGb for the Maple computer algebra system
• in the Magma computer algebra system

The Faugère F5 algorithm first calculates the Gröbner basis of a pair of generator polynomials of the ideal. Then it uses this basis to reduce the size of the initial matrices of generators for the next larger basis:

If G_prev is an already computed Gröbner basis (f₂, …, f_m) and we want to compute a Gröbner basis of (f₁)+G_prev then we will construct matrices whose rows are m f₁ such that m is a monomial not divisible by the leading term of an element of G_prev.[1]

The previously intractable "cyclic 10" problem was solved by F5 [2].

References

• Faugère, J.-C. (June 1999). "A new efficient algorithm for computing Gröbner bases (F₄)". Journal of Pure and Applied Algebra 139 (1): 61–88. Elsevier Science. doi:10.1016/S0022-4049(99)00005-5. ISSN 0022-4049.
• Faugère, J.-C. (July 2002). "A new efficient algorithm for computing Gröbner bases without reduction to zero (F₅)". Proceedings of the 2002 international symposium on Symbolic and algebraic computation (ISSAC): 75–83. ACM Press. doi:10.1145/780506.780516. ISSN 1-58113-484-3.
  • Corrected version 1.2 of the F₅ paper.
• Till Stegers Faugere's F5 Algorithm Revisited (alternative link). Diplom-Mathematiker Thesis, advisor Johannes Buchmann, Technische Universität Darmstadt, September 2005 (revised April 27, 2007). Many references, including links to available implementations.

External links

Faugère's home page, including pdf reprints of additional papers.