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.
Euclidean algorithm for polynomial greatest common divisor computation and Gaussian elimination of linear systems are special cases of Buchberger's algorithm when the number of variables or the degrees of the polynomials are respectively equal to one.
For other Gröbner basis algorithms, see .
A crude version of this algorithm to find a basis for an ideal of a polynomial ring R proceeds as follows:
Input A set of polynomials F that generates
Output A Gröbner basis G for
The polynomial Sij 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 fi and fj share no variables in common, then Sij will always reduce to 0 (if we use only and 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.
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[1] that the degrees of the elements of a reduced Gröbner basis are always bounded by
2\left( | d2 |
2 |
2n-2 | |
+d\right) |
2n+o(1) | |
d |
On the other hand, there are examples[2] where the Gröbner basis contains elements of degree
2\Omega(n) | |
d |
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.