In
computer algebra
In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating mathematical expression ...
, the Faugère F4 algorithm, by
Jean-Charles Faugère, computes the
Gröbner basis
In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring over a field . A Grö ...
of an
ideal of a multivariate
polynomial ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variable ...
. The algorithm uses the same mathematical principles as the
Buchberger algorithm
In the theory of multivariate polynomials, Buchberger's algorithm is a method for transforming a given set of polynomials into a Gröbner basis, which is another set of polynomials that have the same common zeros and are more convenient for extract ...
, but computes many normal forms in one go by forming a generally
sparse matrix
In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse b ...
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''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.
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
* i
FGb Faugère's own implementation, which includes interfaces for using it from
C/C++
The C and C++ programming languages are closely related but have many significant differences. C++ began as a fork of an early, pre- standardized C, and was designed to be mostly source-and-link compatible with C compilers of the time. Due to t ...
or
Maple
''Acer'' () is a genus of trees and shrubs commonly known as maples. The genus is placed in the family Sapindaceae.Stevens, P. F. (2001 onwards). Angiosperm Phylogeny Website. Version 9, June 2008 nd more or less continuously updated since ht ...
,
* in
Maple computer algebra system, as the option method=fgb of function Groebner
basis''
* in the
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. It runs on Unix-like operating systems, as well as Windows.
Introduction
Magma ...
,
* in the
SageMath
SageMath (previously Sage or SAGE, "System for Algebra and Geometry Experimentation") is a computer algebra system (CAS) with features covering many aspects of mathematics, including algebra, combinatorics, graph theory, numerical analysis, nu ...
computer algebra system,
Study versions of the Faugère F5 algorithm is implemented in
* the
SINGULAR
Singular may refer to:
* Singular, the grammatical number that denotes a unit quantity, as opposed to the plural and other forms
* Singular homology
* SINGULAR, an open source Computer Algebra System (CAS)
* Singular or sounder, a group of boar ...
computer algebra system;
* the
SageMath
SageMath (previously Sage or SAGE, "System for Algebra and Geometry Experimentation") is a computer algebra system (CAS) with features covering many aspects of mathematics, including algebra, combinatorics, graph theory, numerical analysis, nu ...
computer algebra system.
* in
SymPy Python package.
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
*.
References
*
*
* Till Steger
Faugère's F5 Algorithm Revisitedalternative 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
Faugère's home page
(includes pdf reprints of additional papers)
An introduction to the F4 algorithm.
{{DEFAULTSORT:Faugere's F4 and F5 algorithms
Computer algebra