Faugère's F4 and F5 algorithms: Difference between revisions

Revision as of 17:03, 5 July 2021

Latest revision as of 09:34, 4 April 2025

(4 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Algorithms for computing Gröbner bases}}

In [[computer algebra]], the '''Faugère F4 algorithm''', by [[Jean-Charles Faugère]], computes the [[Gröbner basis]] of an [[ideal (ring theory)|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.

Line 19 ⟶ 20:

* the [[SINGULAR]] computer algebra system;<ref>{{cite arXiv |last=Eder |first=Christian |eprint=0804.2033 |title=On The Criteria Of The F5 Algorithm |class= math.AC|year=2008 }}</ref>

* the [[SageMath]] computer algebra system.

* in [[SymPy]] [[Python (programming language)|Python]] package.<ref>{{Cite web|url=https://docs.sympy.org/latest/modules/polys/internals.html#groebner-basis-algorithms|title=Internals of the Polynomial Manipulation Module — SymPy 1.9 documentation}}</ref>

== Applications ==

Line 49 ⟶ 50:

| last = Faugère

| first = J.-C.

| journaltitle = Proceedings of the 2002 Internationalinternational Symposiumsymposium on Symbolic and Algebraicalgebraic Computation (ISSAC)computation

| titlechapter = 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

Line 58 ⟶ 59:

| isbn = 978-1-58113-484-1

| citeseerx = 10.1.1.188.651

| s2cid = 15833106

}}

* Till Stegers [https://web.archive.org/web/20081202150316/http://wwwcsif.cs.ucdavis.edu/~stegers/diplom_stegers.pdf Faugère'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://www-polsys.lip6.fr/~jcf/ Faugère's home page] (includes pdf reprints of additional papers)

* [httphttps://www.broune.com/paperss/f4.pdf An introduction to the F4 algorithm.]

{{DEFAULTSORT:Faugere's F4 and F5 algorithms}}