Buchberger's algorithm

Template:Short description 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 extracting information on these common zeros. It was introduced by Bruno Buchberger simultaneously with the definition of Gröbner bases.

The Euclidean algorithm for computing the polynomial greatest common divisor is a special case of Buchberger's algorithm restricted to polynomials of a single variable. Gaussian elimination of a system of linear equations is another special case where the degree of all polynomials equals one.

For other Gröbner basis algorithms, see Template:Slink.

Algorithm

A crude version of this algorithm to find a basis for an ideal Template:Mvar of a polynomial ring R proceeds as follows:

Input A set of polynomials F that generates Template:Mvar

Output A Gröbner basis G for Template:Mvar

1. G := F
2. For every f_i, f_j in G, denote by g_i the leading term of f_i with respect to the given monomial ordering, and by a_ij the least common multiple of g_i and g_j.
3. Choose two polynomials in G and let Template:Math (Note that the leading terms here will cancel by construction).
4. Reduce S_ij, with the multivariate division algorithm relative to the set G until the result is not further reducible. If the result is non-zero, add it to G.
5. Repeat steps 2-4 until all possible pairs are considered, including those involving the new polynomials added in step 4.
6. Output G

The polynomial S_ij is commonly referred to as the S-polynomial, where S refers to subtraction (Buchberger) or syzygy (others). The pair of polynomials with which it is associated is commonly referred to as critical pair.

There are numerous ways to improve this algorithm beyond what has been stated above. For example, one could reduce all the new elements of F relative to each other before adding them. If the leading terms of f_i and f_j share no variables in common, then S_ij will always reduce to 0 (if we use only Template:Mvar and Template:Mvar for reduction), so we needn't calculate it at all.

The algorithm terminates because it is consistently increasing the size of the monomial ideal generated by the leading terms of our set F, and Dickson's lemma (or the Hilbert basis theorem) guarantees that any such ascending chain must eventually become constant.

Complexity

The computational complexity of Buchberger's algorithm is very difficult to estimate, because of the number of choices that may dramatically change the computation time. Nevertheless, T. W. Dubé has proved that the degrees of the elements of a reduced Gröbner basis are always bounded by

$2{(\frac{d^2}{2}+d)}^{2^{n-2}}$,

where Template:Math is the number of variables, and Template:Math the maximal total degree of the input polynomials. This allows, in theory, to use linear algebra over the vector space of the polynomials of degree bounded by this value, for getting an algorithm of complexity $d^{2^{n+o(1)}}$.

On the other hand, there are examples where the Gröbner basis contains elements of degree

$d^{2^{\mathrm{\Omega }(n)}}$,

and the above upper bound of complexity is optimal. Nevertheless, such examples are extremely rare.

Since its discovery, many variants of Buchberger's have been introduced to improve its efficiency. Faugère's F4 and F5 algorithms are presently the most efficient algorithms for computing Gröbner bases, and allow to compute routinely Gröbner bases consisting of several hundreds of polynomials, having each several hundreds of terms and coefficients of several hundreds of digits.

See also

• Knuth–Bendix completion algorithm
• Quine–McCluskey algorithm – analogous algorithm for Boolean algebra

Further reading

• Template:Cite journal
• David Cox, John Little, and Donald O'Shea (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer. Template:ISBN.
• Vladimir P. Gerdt, Yuri A. Blinkov (1998). Involutive Bases of Polynomial Ideals, Mathematics and Computers in Simulation, 45:519ff

External links

• Template:Springer
• Buchberger's algorithm on Scholarpedia
• Template:MathWorld