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 [http://fgbrs.lip6.fr/jcf/Software/ package FGb] for the Maple computer algebra system
* in the Magma computer algebra system

The Faugère F5 algorithm [http://www-calfor.lip6.fr/~jcf/Papers/@papers/f5.pdf] 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.

References

* cite journal
last = Faugère
first = J.-C.
title = A new efficient algorithm for computing Gröbner bases (F₄)
journal = Journal of Pure and Applied Algebra
volume = 139
issue = 1
pages = 61–88
publisher = Elsevier Science
date = June 1999
url = http://fgbrs.lip6.fr/@papers/F99a.pdf
doi = 10.1016/S0022-4049(99)00005-5
id = ISSN|0022-4049
* cite journal
last = Faugère
first = J.-C.
title = A new efficient algorithm for computing Gröbner bases without reduction to zero (F₅)
journal = Proceedings of the 2002 international symposium on Symbolic and algebraic computation (ISSAC)
pages = 75–83
publisher = ACM Press
date = July 2002
url = http://fgbrs.lip6.fr/@papers/F02a.pdf
doi = 10.1145/780506.780516
id = ISSN|1-58113-484-3
** [http://www-calfor.lip6.fr/~jcf/Papers/@papers/f5.pdf Corrected version 1.2 of the F₅ paper] .
* Till Stegers [http://wwwcsif.cs.ucdavis.edu/~stegers/diplom_stegers.pdf Faugere's F5 Algorithm Revisited] ( [http://eprint.iacr.org/2006/404 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

[http://fgbrs.lip6.fr/jcf/ Faugère's home page, including pdf reprints of additional papers.]

[http://www.broune.com/papers/f4.pdf An introduction to the F4 algorithm.]