Faugère F4 algorithm

From Wikipedia, the free encyclopedia

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[1] 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.

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

[edit] 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.