In computer algebra, the Faugère F4 algorithm, by Jean-Charles Faugère

Jean-Charles Faugère

Jean-Charles Faugère is the head of the SALSA team of the Laboratoire d'Informatique de Paris 6 and Inria Paris/Rocquencourt. The team was formerly known as SPIRAL....

, computes the Gröbner basis

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...

 of an ideal

Ideal (ring theory)

In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. The ideal concept allows the generalization in an appropriate way of some important properties of integers like "even number" or "multiple of 3"....

 of a multivariate polynomial ring

Polynomial ring

In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the Hilbert basis theorem, to the construction of...

. 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

Sparse matrix

In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....

 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 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.

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

• as a package FGb for the Maple computer algebra system. This package is included in Maple
  Maple (software)
  Maple is a general-purpose commercial computer algebra system. It was first developed in 1980 by the Symbolic Computation Group at the University of Waterloo in Waterloo, Ontario, Canada....
  
   distribution as the option method=fgb of function Groebner[gbasis];
• in the Magma computer algebra system
  Magma computer algebra system
  Magma is a computer algebra system designed to solve problems in algebra, number theory, geometry and combinatorics. It is named after the algebraic structure magma...
  
  .

Study versions of the Faugère F5 algorithm is implemented in

• the SINGULAR
  SINGULAR
  SINGULAR is a computer algebra system for polynomial computations with special emphasis on the needs of commutative algebra, algebraic geometry, and singularity theory. SINGULAR is free software released under the GNU General Public License. Problems in non-commutative algebra can be tackled with...
  
   computer algebra system;
• the Sage computer algebra system.

Applications

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

External links

• Faugère's home page (includes pdf reprints of additional papers)
• An introduction to the F4 algorithm.