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

[edit] References

• Faugère, J.-C. (June 1999). "A new efficient algorithm for computing Grobner bases (F₄)". Journal of Pure and Applied Algebra 139 (1): 61–88. DOI:10.1016/S0022-4049(99)00005-5. ISSN 0022-4049.