Buchberger's algorithm: Difference between revisions

Revision as of 17:41, 19 June 2015

Revision as of 05:23, 28 July 2015

Line 18:

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 been proved<ref>{{cite doi|10.1137/0219053}}</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