Gröbner basis

In 2007, Buchberger received the Association for Computing Machinery's Paris Kanellakis Theory and Practice Award for this work.

These papers were largely ignored by the mathematical community until their rediscovery in 1987 by Bodo Renschuch et al.[2] An analogous concept for multivariate power series was developed independently by Heisuke Hironaka in 1964, who named them standard bases.

All operations related to Gröbner bases require the choice of a total order on the monomials, with the following properties of compatibility with multiplication.

These conditions imply that the order is a well-order, that is, every strictly decreasing sequence of monomials is finite.

The other polynomial operations involved in Gröbner basis computations are also compatible with the monomial ordering; that is, they can be performed without reordering the result: Let

is the componentwise subtraction of the exponent vectors of N and M. The greatest common divisor gcd(M, N) of M and N is the monomial

In the case of univariate polynomials, if G consists of a single element g, then h is the remainder of the Euclidean division of f by g, and qg is the quotient.

, this translates to: Using the property that relates the lcm and the gcd, the S-polynomial can also be written as: where gcd denotes the greatest common divisor of the leading monomials of f and g. As the monomials that are reducible by both f and g are exactly the multiples of lcm, one can deal with all cases of non-uniqueness of the reduction by considering only the S-polynomials.

be a polynomial ring over a field F. In this section, we suppose that an admissible monomial ordering has been fixed.

For every admissible monomial ordering and every finite set G of polynomials, there is a Gröbner basis that contains G and generates the same ideal.

The algorithm terminates always because of Dickson's lemma or because polynomial rings are Noetherian (Hilbert's basis theorem).

In this case, the uniqueness of reduced Gröbner bases is true only up to the multiplication of polynomials by a nonzero constant.

For every monomial ordering, the empty set of polynomials is the unique Gröbner basis of the zero ideal.

Such a solution, with coordinates in an algebraically closed field containing the coefficients of the polynomials, is called a zero of the ideal.

This solving process is only theoretical, because it implies GCD computation and root-finding of polynomials with approximate coefficients, which are not practicable because of numeric instability.

The degree of the ideal and of its associated algebraic set is the number of points of this finite intersection, counted with multiplicity.

When modeling a problem by polynomial equations, it is often assumed that some quantities are non-zero, so as to avoid degenerate cases.

The important property of the saturation, which ensures that it removes from the algebraic set defined by the ideal I the irreducible components on which the polynomial f is zero, is the following: The primary decomposition of

there are three ways to proceed which give the same result but may have very different computation times (it depends on the problem which is the most efficient).

The first one asserts that a set of polynomials has no common zeros over an algebraic closure of the field of the coefficients, if and only if 1 belongs to the generated ideal.

have a common zero (sometimes called base point), every irreducible component of the non-empty algebraic set defined by the

The main issues are the following ones: For solving 3. many improvements, variants and heuristics have been proposed before the introduction of F4 and F5 algorithms by Jean-Charles Faugère.

This solves partially issue 4., as reductions to zero in Buchberger's algorithm correspond to relations between rows of the matrix to be reduced, and the zero rows of the reduced matrix correspond to a basis of the vector space of these relations.

[4] In its original form, FGLM may be the critical step for solving systems of polynomial equations because FGML does not take into account the sparsity of involved matrices.

[5] Most general-purpose computer algebra systems have implementations of one or several algorithms for Gröbner bases, often also embedded in other functions, such as for solving systems of polynomial equations or for simplifying trigonometric functions; this is the case, for example, of CoCoA, GAP, Macaulay 2, Magma, Maple, Mathematica, SINGULAR, SageMath and SymPy.

The complexity of the Gröbner basis computations is commonly evaluated in term of the number n of variables and the maximal degree d of the input polynomials.

In the worst case, the main parameter of the complexity is the maximal degree of the elements of the resulting reduced Gröbner basis.

As every algorithm for computing a Gröbner basis must write its result, this provides a lower bound of the complexity.

[7] The concept and algorithms of Gröbner bases have been generalized to submodules of free modules over a polynomial ring.

[10] Applying Gröbner basis in algebraic decoding is still a research area of channel coding theory.