Faugère F4 algorithm

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"2, …, "f""m") and we want to compute a Gröbner basis of ("f"1)+"G"prev then we will construct matrices whose rows are "m" "f"1 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 (F4)
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 (F5)
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 F5 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.]


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Buchberger's algorithm — In computational algebraic geometry and computational commutative algebra, Buchberger s algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gröbner basis with respect to some monomial order. It was… …   Wikipedia

  • Gröbner basis — In computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring R. One can view it as a multivariate, non linear… …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • F5 — F5, F.V, F 5, F05, F 5 may refer to :Music* F5 (band), hard rock band of former Megadeth bassist David Ellefson * F5 Records, a record label * An F roughly one and a half octaves above middle CPublications* F5 (comics), a comics created by Tony… …   Wikipedia

  • Magma computer algebra system — Magma Developer(s) Computational Algebra Group, School of Mathematics and Statistics, University of Sydney Stable release 2.17 8 / May 27, 2011 Operating system …   Wikipedia

  • F4 — F4, F.IV, F04, F 4, F.4 or F 4 may refer to: * F4 (band) or JVKV, a Taiwanese band * F4 (corporation), a video game developer * F 4 Frösön, a former Swedish Air Force wing * F4 layout, a front engine, four wheel drive auto layout * F₄, one of the …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”