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 expressions ...
, the Faugère F4 algorithm, by
Jean-Charles Faugère
Jean-Charles Faugère is the head of the POLSYS project-team (Solvers for Algebraic Systems and Applications) of the Laboratoire d'Informatique de Paris 6 (LIP6) and Paris–Rocquencourt center of INRIA, in Paris. The team was formerly known as SPI ...
, 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öbn ...
of an
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
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 variables) ...
. 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
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 sequence
In commutative algebra, a regular sequence is a sequence of elements of a commutative ring which are as independent as possible, in a precise sense. This is the algebraic analogue of the geometric notion of a complete intersection.
Definitions
Fo ...
s'', 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 thi ...
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 http ...
,
* in
Maple computer algebra system
Maple is a symbolic and numeric computing environment as well as a multi-paradigm programming language. It covers several areas of technical computing, such as symbolic mathematics, numerical analysis, data processing, visualization, and othe ...
, as the option method=fgb of function Groebner
basis
Basis may refer to:
Finance and accounting
* Adjusted basis, the net cost of an asset after adjusting for various tax-related items
*Basis point, 0.01%, often used in the context of interest rates
* Basis trading, a trading strategy consisting ...
''
* 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, numbe ...
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, numbe ...
computer algebra system.
* in
SymPy Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
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