A Noetherian ring is called effective if its elements and ring operations can be described effectively as well as the problem of finding all solutions to a linear equation with and unknown (in terms of a particular solution and a finite set of generators for the module of all homogeneous solutions). Examples are the rings of integers and of rational numbers, algebraic number fields, and finite rings. For such a ring , the Buchberger algorithm (cf. [a3], [a4]) solves the following problem concerning the polynomial ring in the variables :
1) Provide algorithms turning into an effective ring.
If is a field, the algorithm also solves the following two problems:
2) Given a finite set of polynomial equations over in the variables , produce an "upper triangular form" of the equations, thus providing solutions by elimination of variables.
3) Given a finite subset of , produce an effectively computable -linear projection mapping onto a complement in of , the ideal of generated by .
An important example is the lexicographical ordering (coming from the identification of with ). Starting from any reduction ordering and a vector , a new reduction ordering can be obtained by demanding that if and only if either or and . If is the all-one vector, the order refines the partial order by total degree.
Termination of the Buchberger algorithm follows from the fact that a reduction ordering on is well founded.
These orderings are used to compare (sets of) polynomials. To single out the highest monomial and coefficient from a non-zero polynomial , set
The letters , , stand for leading monomial, leading coefficient and leading term, respectively.
The Buchberger algorithm in its simplest form.
Let be a field and a finite subset of . Let denote a remainder of with respect to , that is, the result of iteratively replacing by a polynomial of the form with such that as often as possible. This is effective because is well founded. The result is not uniquely determined by . Given , their -polynomial is
The following routine is the Buchberger algorithm in its simplest form.
od; return .
It terminates because the sequence of consecutive sets , produced in the course of the algorithm, descends with respect to .
Note that is an invariant of the algorithm. Consequently, if is the output resulting from input , then . The output has the following characteristic property:
A subset of with this property is called a Gröbner basis. Equivalently, a subset of is a Gröbner basis if and only if, for all , one has .
Suppose that is a Gröbner basis. Then is uniquely determined for each . A monomial is called standard with respect to an ideal if it is not of the form for some . The mapping is an effectively computable projection onto the -span of all standard monomials with respect to , which is a complement as in Problem 3) above.
A reduction ordering with is called an elimination ordering if for and . If is a Gröbner basis with respect to an elimination ordering, then is the ideal of generated by . This is the key to solving Problem 2.
The Buchberger algorithm can be generalized to arbitrary effective rings . By keeping track of intermediate results in the algorithms, it is possible to express the Gröbner basis coming from input as an -linear combination of . Using this, one can find a particular solution, as well as a finite generating set for all homogeneous solutions to an -linear equation, and hence a solution to Problem 1.
General introductions to the Buchberger algorithm can be found in [a1], [a5], [a6]. More advanced applications can be found in [a7], which also contains an indication of the badness of the complexity of finding Gröbner bases. Buchberger algorithms over more general coefficient domains are dealt with in [a8], and generalizations from to particular non-commutative algebras (e.g., the universal enveloping algebra of a Lie algebra) in [a2].
|[a1]||W.W. Adam, P. Loustaunau, "An introduction to Gröbner bases" , Graduate Studies in Math. , 3 , Amer. Math. Soc. and Oxford Univ. Press (1994) MR1287608|
|[a2]||J. Apel, W. Lassner, "An extension of Buchberger's algorithm and calculations in enveloping fields of Lie algebras" J. Symb. Comp. , 6 (1988) pp. 361–370 MR988423|
|[a3]||B. Buchberger, "An algorithmic criterion for the solvability of algebraic systems of equations" Aequationes Math. , 4 (1965) pp. 374–383 (This paper is a published version of the author's Ph.D. Thesis (Innsbruck, 1965) under the advice of Prof. W. Gröbner)|
|[a4]||B. Buchberger, "Gröbner bases: an algorithmic method in polynomial ideal theory" N.K. Bose (ed.) , Recent Trends in Multidimensional System Theory , Reidel (1985) pp. 184–232 Zbl 0587.13009|
|[a5]||D. Cox, J. Little, D. O'Shea, "Ideals, varieties, and algorithms" , Springer (1992) MR1189133 Zbl 0756.13017|
|[a6]||D. Eisenbud, "Commutative algebra with a view toward algebraic geometry" , GTM , 150 , Springer (1995) Zbl 0819.13001|
|[a7]||L. (ed.) Robbiano, "Computational aspects of commutative algebra" J. Symb. Comp. , special issue (1989) MR1262830 Zbl 0796.00017|
|[a8]||W. Trinks, "Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen" J. Number Th. , 10 (1978) pp. 475–488 MR0515056 Zbl 0404.13004|
Buchberger algorithm. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Buchberger_algorithm&oldid=23773