Namespaces
Variants
Actions

Difference between revisions of "Buchberger algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (MR/ZBL numbers added)
Line 5: Line 5:
 
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b1109809.png" /> is a [[Field|field]], the algorithm also solves the following two problems:
 
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b1109809.png" /> is a [[Field|field]], the algorithm also solves the following two problems:
  
2) Given a finite set of polynomial equations over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098010.png" /> in the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098011.png" />, produce an "upper triangular form" of the equations, thus providing solutions by elimination of variables.
+
2) Given a finite set of polynomial equations over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098010.png" /> in the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098011.png" />, produce an "upper triangular form" of the equations, thus providing solutions by elimination of variables.
  
 
3) Given a finite subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098012.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098013.png" />, produce an effectively computable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098014.png" />-linear projection mapping onto a complement in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098015.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098016.png" />, the ideal of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098017.png" /> generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098018.png" />.
 
3) Given a finite subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098012.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098013.png" />, produce an effectively computable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098014.png" />-linear projection mapping onto a complement in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098015.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098016.png" />, the ideal of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098017.png" /> generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098018.png" />.
Line 43: Line 43:
 
  while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098066.png" /> do
 
  while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098066.png" /> do
  
  choose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098067.png" />;
+
choose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098067.png" />;
  
  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098068.png" />;
+
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098068.png" />;
  
  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098069.png" />;
+
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098069.png" />;
  
  if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098070.png" /> then
+
if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098070.png" /> then
  
  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098071.png" />;
+
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098071.png" />;
  
  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098072.png" />;
+
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098072.png" />;
  
  fi;
+
fi;
  
 
  od; return <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098073.png" />.
 
  od; return <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110980/b11098073.png" />.
Line 76: Line 76:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> W.W. Adam,   P. Loustaunau,   "An introduction to Gröbner bases" , ''Graduate Studies in Math.'' , '''3''' , Amer. Math. Soc. and Oxford Univ. Press (1994)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> 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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> 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)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> 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</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> D. Cox,   J. Little,   D. O'Shea,   "Ideals, varieties, and algorithms" , Springer (1992)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> D. Eisenbud,   "Commutative algebra with a view toward algebraic geometry" , ''GTM'' , '''150''' , Springer (1995)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> L. (ed.) Robbiano,   "Computational aspects of commutative algebra" ''J. Symb. Comp.'' , '''special issue''' (1989)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> W. Trinks,   "Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen" ''J. Number Th.'' , '''10''' (1978) pp. 475–488</TD></TR></table>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> W.W. Adam, P. Loustaunau, "An introduction to Gröbner bases" , ''Graduate Studies in Math.'' , '''3''' , Amer. Math. Soc. and Oxford Univ. Press (1994) {{MR|1287608}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> 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 {{MR|988423}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> 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)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> 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 {{MR|}} {{ZBL|0587.13009}} </TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> D. Cox, J. Little, D. O'Shea, "Ideals, varieties, and algorithms" , Springer (1992) {{MR|1189133}} {{ZBL|0756.13017}} </TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> D. Eisenbud, "Commutative algebra with a view toward algebraic geometry" , ''GTM'' , '''150''' , Springer (1995) {{MR|}} {{ZBL|0819.13001}} </TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> L. (ed.) Robbiano, "Computational aspects of commutative algebra" ''J. Symb. Comp.'' , '''special issue''' (1989) {{MR|1262830}} {{ZBL|0796.00017}} </TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> W. Trinks, "Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen" ''J. Number Th.'' , '''10''' (1978) pp. 475–488 {{MR|0515056}} {{ZBL|0404.13004}} </TD></TR></table>

Revision as of 21:50, 30 March 2012

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 .

Monomials.

Denote by the monoid of all monomials of . For there is an such that . A total order (cf. also Totally ordered set) on is called a reduction ordering if, for all ,

implies ;

implies .

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.


;
while  do
choose ;
;
;
if  then
;
;
fi;
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].

References

[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
How to Cite This Entry:
Buchberger algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Buchberger_algorithm&oldid=13857
This article was adapted from an original article by A.M. Cohen (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article