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 ring "R" proceeds as follows:

:Input A set of polynomials "F" = {"f"₁, "f"₂, ..., "f"_"k"} that generate "I":Output A Gröbner basis for "I"

:# Let "g_i" be the leading term of "f_i" with respect to the given ordering, and denote the least common multiple of "g_i" and "g_j" by "a_ij".:# Let "S"_"ij" ← ("a"_"ij" / "g"_"i") "f"_"i" − ("a"_"ij" / "g"_"j") "f"_"j"
"(Note that the leading terms here will cancel by construction)".:# Using the multivariate division algorithm, reduce all the "S_ij" relative to the set "F".:# Add all the nonzero polynomials resulting from step 3 to "F", and repeat steps 1-4 until nothing new is added.

The polynomial "S"_"ij" is commonly referred to as the "S"-polynomial, where "S" refers to "subtraction" (Buchberger) or "syzygy" (others).

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. It also should be noted that 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 f_i and f_j 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. Unfortunately, it may take a very long time to terminate, corresponding to the fact that Gröbner bases can be "extremely" large.

Further methods for computing Gröbner bases include the Faugère F4 algorithm, based on the same mathematics as the Buchberger algorithm, and involutive approaches, based on ideas from Differential algebra.

References

* cite journal
last = Buchberger
first = B.
authorlink = Bruno Buchberger
title = Theoretical Basis for the Reduction of Polynomials to Canonical Forms
journal = ACM SIGSAM Bull.
volume = 10
issue = 3
pages = 19–29
publisher = ACM
month = August
year = 1976
url = http://doi.acm.org/10.1145/1088216.1088219
doi = 10.1145/1088216.1088219
id = ISSN|0163-5824
* David Cox, John Little, and Donal O'Shea (1997). "Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra", Springer. ISBN 0-387-94680-2.
* Vladimir P. Gerdt, Yuri A. Blinkov (1998). "Involutive Bases of Polynomial Ideals", Mathematics and Computers in Simluation, 45:519ff

External links

*