Buchberger's algorithm: Difference between revisions

Revision as of 18:31, 18 May 2015

Revision as of 17:39, 19 June 2015

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. Unfortunately, it may take a very long time to terminate, corresponding to the fact that [[Gröbner bases]] can be ''extremely'' large. Thus, it has large storage requirements ([[space complexity]]). Also, the [[time complexity]] of the algorithm is doubly exponential in the input data, which implies that its worst-case behavior can be very slow.

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

Further methods for computing Gröbner bases include the [[Faugère F4 algorithm]], based on the same mathematics as the Buchberger algorithm, and involutive approaches, based on ideas from [[differential algebra]].

:<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 doi|10.1016/0001-8708(82)90048-2}}</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 rares.

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