Faugère's F4 and F5 algorithms

From HandWiki

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 F5 algorithm 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 Gprev is an already computed Gröbner basis (f2, …, fm) and we want to compute a Gröbner basis of (f1) + Gprev then we will construct matrices whose rows are m f1 such that m is a monomial not divisible by the leading term of an element of Gprev.

This strategy allows the algorithm to apply two new criteria based on what Faugère calls signatures of polynomials. Thanks to these criteria, the algorithm can compute Gröbner bases for a large class of interesting polynomial systems, called regular sequences, without ever simplifying a single polynomial to zero—the most time-consuming operation in algorithms that compute Gröbner bases. It is also very effective for a large number of non-regular sequences.

Implementations

The Faugère F4 algorithm is implemented

  • in FGb, Faugère's own implementation, which includes interfaces for using it from C/C++ or Maple,
  • in Maple computer algebra system, as the option method=fgb of function Groebner[gbasis]
  • in the Magma computer algebra system,
  • in the SageMath computer algebra system,


Study versions of the Faugère F5 algorithm is implemented in[citation needed]

Applications

The previously intractable "cyclic 10" problem was solved by F5,[citation needed] as were a number of systems related to cryptography; for example HFE and C*.[citation needed]

References

  1. Eder, Christian (2008). "On The Criteria Of The F5 Algorithm". arXiv:0804.2033 [math.AC].
  2. "Internals of the Polynomial Manipulation Module — SymPy 1.9 documentation". https://docs.sympy.org/latest/modules/polys/internals.html#groebner-basis-algorithms. 

External links