HOME

TheInfoList



OR:

FGLM is one of the main
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s 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 ...
, named after its designers, Faugère,
Gianni Gianni is an Italian name (occasionally a surname), a short form of the Italian Giovanni and a cognate of John meaning God is gracious. Gianni is the most common diminutive of Giovanni in Italian. People with this given name * Gianni Agnelli (i ...
, Lazard and
Mora Mora may refer to: People * Mora (surname) Places Sweden * Mora, Säter, Sweden * Mora, Sweden, the seat of Mora Municipality * Mora Municipality, Sweden United States * Mora, Louisiana, an unincorporated community * Mora, Minnesota, a city * M ...
. They introduced their algorithm in 1993. The input of the algorithm is a Gröbner basis of a zero-dimensional
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 ...
in the ring of
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
s over a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
with respect to a
monomial order In mathematics, a monomial order (sometimes called a term order or an admissible order) is a total order on the set of all ( monic) monomials in a given polynomial ring, satisfying the property of respecting multiplication, i.e., * If u \leq v and ...
and a second
monomial order In mathematics, a monomial order (sometimes called a term order or an admissible order) is a total order on the set of all ( monic) monomials in a given polynomial ring, satisfying the property of respecting multiplication, i.e., * If u \leq v and ...
. As its output, it returns a Gröbner basis of the ideal with respect to the second ordering. The algorithm is a fundamental tool in computer algebra and has been implemented in most of the
computer algebra system A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The de ...
s. The
complexity Complexity characterises the behaviour of a system or model whose components interaction, interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. The term is generall ...
of FGLM is ''O''(''nD''3), where ''n'' is the number of variables of the polynomials and D is the degree of the ideal. There are several generalization and various applications for FGLM.


References

Computer algebra Commutative algebra Polynomials {{commutative-algebra-stub