Buchberger's algorithm: Difference between revisions

Revision as of 11:26, 17 September 2015

Revision as of 23:32, 13 November 2015

Line 7:

:# ''G'' := ''F''

:# For every ''f_i'', ''f_j'' in ''G'', denote by ''g_i'' the leading term of ''f_i'' with respect to the given ordering, and by ''a_ij'' the [[least common multiple]] of ''g_i'' and ''g_j''.

:# Choose two polynomials in ''G'' and 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)''.

:# Reduce ''S''_''ij'', 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''.

:# Repeat steps 1-4 until all possible pairs are considered, including those involving the new polynomials added in step 4.

Line 16:

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 ''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.

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 doijournal|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>,

where {{math|''n''}} is the number of variables, and {{math|''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

<math>d^{2^{n+o(1)}}</math>.

On the other hand, there are examples<ref>{{cite doijournal|doi=10.1016/0001-8708(82)90048-2|title=The complexity of the word problems for commutative semigroups and polynomial ideals|journal=Advances in Mathematics|volume=46|issue=3|pages=305|year=1982|last1=Mayr|first1=Ernst W|last2=Meyer|first2=Albert R}}</ref> where the Gröbner basis contains elements of degree

:<math>d^{2^{\Omega(n)}}</math>,

and above upper bound of complexity is almost optimal, up to a constant factor in the second exponent). Nevertheless, such examples are extremely rare.

Line 29:

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 ==

* [[Quine-McCluskey algorithm]] (analogous algorithm for Boolean algebra)

* [http://www.scholarpedia.org/article/Buchberger%27s_algorithm Buchberger's algorithm] discussed more extensively on Scholarpedia

== References ==

* {{cite journal

| last = Buchberger

Line 53:

{{reflist}}

== External links ==

* {{springer|title=Buchberger algorithm|id=p/b110980}}

* {{MathWorld | urlname=BuchbergersAlgorithm | title=Buchberger's Algorithm}}