Buchberger's algorithm: Difference between revisions

Content deleted Content added
Ruud Koot (talk | contribs)
Ruud Koot (talk | contribs)
section headers
Line 1:
In computational [[algebraic geometry]] and computational [[commutative algebra]], '''Buchberger's algorithm''' is a method of transforming a given set of [[Ideal (ring theory)#Ideal generated by a set|generators]] for a polynomial [[ring ideal|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 [[Greatest common divisor|GCD]] computation and of [[Gaussian elimination]] for [[linear system]]s.
 
== Algorithm ==
A crude version of this algorithm to find a basis for an ideal ''I'' of a polynomial ring ''R'' proceeds as follows:
 
Line 18 ⟶ 19:
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.
 
== Complexity ==
The [[time complexity|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<ref>{{cite journal|doi=10.1137/0219053|title=The Structure of Polynomial Ideals and Gröbner Bases|journal=SIAM Journal on Computing|volume=19|issue=4|pages=750|year=1990|last1=Dubé|first1=Thomas W.}}</ref> that the degrees of the elements of a reduced Gröbner basis are always bounded by
:<math>2\left(\frac{d^2}{2} +d\right)^{2^{n-1}}</math>,
Line 32 ⟶ 34:
* [[Knuth–Bendix completion algorithm]]
* [[Quine–McCluskey algorithm]] &ndash; analogous algorithm for Boolean algebra
 
== Notes ==
{{reflist|2}}
 
== References ==
Line 50 ⟶ 55:
* David Cox, John Little, and Donald 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
 
{{reflist}}
 
== External links ==