Buchberger's algorithm

In computational algebraic geometry and computational commutative algebra, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gröbner basis with respect to some monomial order. It was invented by Austrian mathematician Bruno Buchberger. One can view it as a generalization of the Euclidean algorithm for univariate GCD computation and of Gaussian elimination for linear systems.

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

Input A set of polynomials F that generates I
Output A Gröbner basis G for I
  1. G := F
  2. For every fi, fj in G, denote by gi the leading term of fi with respect to the given ordering, and by aij the least common multiple of gi and gj.
  3. Choose two polynomials in G and let Sij = (aij / gi) fi − (aij / gj) fj (Note that the leading terms here will cancel by construction).
  4. Reduce Sij, 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 1-4 until all possible pairs are considered, including those involving the new polynomials added in step 4.
  6. Output G

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 fi and fj 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(\frac{d^2}{2} +d\right)^{2^{n-1}},

where n is the number of variables, and d 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[2] where the Gröbner basis contains elements of degree

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

and above upper bound of complexity is almost optimal, up to a constant factor in the second exponent). 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

References

  1. ↑ Dubé, Thomas W. (1990). "The Structure of Polynomial Ideals and Gröbner Bases". SIAM Journal on Computing 19 (4): 750. doi:10.1137/0219053.
  2. ↑ Mayr, Ernst W; Meyer, Albert R (1982). "The complexity of the word problems for commutative semigroups and polynomial ideals". Advances in Mathematics 46 (3): 305. doi:10.1016/0001-8708(82)90048-2.

External links

This article is issued from Wikipedia - version of the Saturday, November 14, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.