Buchberger's algorithm
| Bruno Buchberger and Manuel Kauers (2011), Scholarpedia, 6(10):7764. | doi:10.4249/scholarpedia.7764 | revision #126537 [link to/cite this article] |
Buchberger's Algorithm solves the following problem:
Input: A finite set \(B\) of polynomials.Output: A finite Gröbner basis \(G\) such that the linear combinations of elements of \(B\) are precisely the same as the linear combinations of elements of \(G\ .\) We call such a \(G\) equivalent to \(B\ .\)
Contents |
Motivation
Why is this problem interesting?
A variety of frequently arising questions about sets of polynomial equations can be answered easily when the sets are "Gröbner bases" while they are not easy to answer for an arbitrary set of polynomials (see the article on Gröbner bases). Buchberger's algorithm provides a means to transform an arbitrary set of polynomials into an equivalent Gröbner basis. Therefore, questions about some set of polynomials arising in an application can be answered by first using Buchberger's algorithm to compute an equivalent Gröbner basis and then answering the question for the Gröbner basis.
Why is this problem difficult?
Gröbner bases can be used for solving problems which are commonly considered as computationally hard. Using Gröbner bases, it is possible for example to decide the solvability of a set of polynomial equations over the complex numbers, which is remarkable in view of the fact that it was shown in 1970 that there cannot be an algorithm for deciding the solvability of a set of polynomial equations over the integers (Hilbert's 10th problem posed in 1900).
Another indication for the difficulty of constructing Gröbner bases is that this question has remained open for at least 65 years, counting from Gordan's work of 1899 [ 16 ], where Gröbner bases were implicitly introduced for the first time, but no algorithm was given for computing them.
Buchberger's Algorithm
We recall from the article on Gröbner bases that a reduction step of a polynomial \(p\) with respect to a fixed set \(B\) of polynomials consists of subtracting some multiple of an element of \(B\) from \(p\) in such a way that some power product in \(p\) is replaced by power products which are smaller (w.r.t. a fixed order imposed on the power products).
Repeated reduction steps, after finitely many steps, will always lead to some polynomial which cannot be reduced any further. Such a polynomial is called a reduced form of \(p\) with respect to \(B\ .\) Reduced forms are in general not unique. However, one can give an algorithm which for given \(p\) and \(B\) computes some reduced form of \(p\) with respect to \(B\ .\) By \(\mathrm{RED}\) we denote such a function, i.e., \(\mathrm{RED}(p,B)\) is a reduced form of \(p\) with respect to \(B\) obtained by repeated reduction steps.
We also recall from the Gröbner bases article that the S-polynomial of two polynomials \(p\) and \(q\) is defined as
\[ \mathrm{SPOL}(f,g):=\mathrm{LCM}(\mathrm{LT}(f),\mathrm{LT}(g))\Bigl(\frac{f}{\mathrm{LM}(f)}-\frac{g}{\mathrm{LM}(g)}\Bigr), \]
where the symbols \(\mathrm{LT}\) and \(\mathrm{LM}\) refer to the leading power product and the leading monomial (w.r.t. a fixed order imposed on the power products), and \(\mathrm{LCM}\) to the least common multiple.
Using these notions, Buchberger's algorithm [ 1 ] can be formulated as follows:
Input: A finite set \(B\) of polynomials
Output: A finite Gröbner basis \(G\) equivalent to \(B\)
1 \(G := B\)
2 \(C := G \times G\)
3 while \(C\neq\emptyset\) do
4 Choose a pair \((f,g)\) from \(C\)
5 \(C := C \setminus \{(f,g)\}\)
6 \(h := \mathrm{RED}(\mathrm{SPOL}(f,g), G)\)
7 if \(h\neq0\) then
8 \(C := C \cup (G \times \{h\})\)
9 \(G := G \cup \{h\}\)
10 return \(G\)
Correctness
The correctness of Buchberger's algorithm is an immediate consequence of Buchberger's theorem [ 1 ]:
A set \(G\) is a Gröbner basis if and only if for all \(f,g\in G\) the S-polynomial \(\mathrm{SPOL}(f,g)\ ,\) by repeated reduction with respect to \(G\ ,\) can be brought to zero.
Termination
Termination of the algorithm is shown by considering the leading power products of the polynomials in \(G\ .\) A leading power product of some new polynomial \(h\) cannot be a multiple of a leading power product of a polynomial in \(G\ ,\) because the polynomials \(h\) are completely reduced with respect to \(G\ .\) If on some input the algorithm did not terminate, this would give rise to an infinite sequence of power products in which none is a multiple of any power product appearing earlier in the sequence. Dickson's lemma [ 10 ] says that such a sequence cannot exist.
Complexity
The output \(G\) can be much larger than the input \(B\ .\) It was shown [ 11 ] that when there are \(n\) variables and the polynomials in \(B\) have a total degree not exceeding \(d\ ,\) then the degree of the polynomials in \(G\) is bounded by \(2(\tfrac12 d^2+d)^{2^{n-1}}\ .\) This bound is doubly exponential with respect to \(n\) but only polynomial in \(d\ .\)
The double exponential growth with respect to the number \(n\) of variables is sharp in the following sense. It can be shown [ 24 ] that there exists some constant \(c\) such that for all sufficiently large \(n\) there is a basis \(B\) of polynomials whose degree does not exceed five, such that every Gröbner basis \(G\) of \(B\) contains at least one element whose degree exceeds \(2^{2^{cn}}\ .\)
These estimates on the size of the output directly imply estimates on the memory requirements and the runtime of the Buchberger algorithm. They describe however the complexity of the problem rather than the complexity of a particular algorithm, in the sense that no other (hypothetical) algorithm for computing Gröbner bases can possibly be faster in the worst case.
Despite this unavoidable worst case behaviour, in many cases of practical relevance it is possible to obtain Gröbner bases in a reasonable time. The algorithm tends to perform far more efficiently on input coming from applications than in the worst case. For this reason, it has been suggested that the expected runtime may be more closely related to certain intrinsic algebraic quantities of the input (such as, for example, the so-called Castelnuvo-Mumford regularity) rather than on its degree and the number of variables.
It should also be taken into account that in practice, the ordering of the power products can have a significant impact on the efficiency. As a rule, degree orders show a better performance than elimination orders. (See Gröbner bases for an explanation of the notions "degree order" and "elimination order".)
Refinements
Deletion Criteria
The set \(C\) is typically larger than needed. In [ 3 ], the technique of "criteria" was introduced by which certain elements from \(C\) can be deleted without losing correctness or termination. We mention two criteria due to Buchberger [ 3 ]:
Product Criterion: If \((f,g)\) in \(C\) is such that the leading power products of \(f\) and \(g\) have no variables in common, then \((f,g)\) can be removed from \(C\ .\)
Chain Criterion: During the execution of the algorithm, a pair \((f,g)\) can be removed from \(C\) if there is some \(h\) in the current \(G\) such that \(\mathrm{LT}(h)\) divides \(\mathrm{LCM}(\mathrm{LT}(f),\mathrm{LT}(g))\) and both \((f,h)\) and \((h,g)\) have been removed from \(C\) before (by zero reduction or application of a criterion).
The effect of the chain criterion is illustrated in the figure below. A black point at position \((i,j)\) represents a basis element with leading power product \(x^i y^j\ .\) White dots indicate the leading power products of pairs. On the left, all pairs generated from the five basis elements are indicated. The situation on the right was obtained from the situation on the left by applying the chain criterion. Only four of the 10 pairs remain.
Selection Strategies
After unnecessary pairs have been removed from \(C\ ,\) there is still the choice in line 4 which pair from \(C\) to select. The choice does not matter for the correctness or the termination of the algorithm, but it may well happen that some choices lead to much earlier termination than others. It is desirable to choose pairs which lead to earlier termination, but it is hard to decide during the execution algorithm whether one pair is better than another. For making a reasonable choice, several heuristic selection strategies have been proposed.
Typical selection strategies take into account the least common multiple of the leading power products (preferring lower ones), the total size of the polynomials in the pair (preferring smaller ones), the age of the pair (preferring older ones), or some combination of these measures. For a recent discussion of advantages and disadvantages, see Chapter 25 of [ 25 ].
Variations
In addition to the freedom in selecting the next pair during the main loop of Buchberger's algorithm, there are other means of improving the performance. One variation, suggested in [ 5 ], is to interrupt the main loop from time to time in order to remove redundancies among the current elements of \(G\ .\) For some examples, this leads to a drastic speed-up, while for others, it does not. A similar variation consists of reducing not only a single S-polynomial at a time, but several (or even all) at once. The simultaneous reduction of a set of S-polynomials with respect to the current basis can be reformulated as the computation of the reduced echelon form of a certain matrix. As this matrix turns out to be sparse, techniques from numerical analysis can be used for handling it efficiently. One particularly efficient variant of Buchberger's algorithm, which proceeds along these lines, was proposed by Faugere [ 13 ] under the name F4.
Related Algorithms
Specializations
Buchberger's algorithm includes two fundamental algorithms as special case. In the case of a single variable, Buchberger's algorithm reduces to Euclid's algorithm for computing the greatest common divisor of polynomials. In the case where all polynomials in the input basis have degree one, Buchberger's algorithm reduces to Gauss' algorithm for bringing a matrix into triangular form. The reduced Gröbner basis, see the Gröbner bases article for a definition, gives the row echelon form of the matrix.
Generalizations
There are other algorithms which share with Buchberger's algorithm the principle of repeatedly adding the reduced from of an analogue of the S-polynomial of pairs of elements to an initial set until an analogue to a Gröbner basis is obtained. In general, this algorithm pattern is called critical pair completion. Other well-known examples of critical pair completion are Robinson's resolution in automated theorem proving [ 26 ] and the Knuth-Bendix algorithm for term rewriting [ 20 ]. For details on this general view on Gröbner bases, see [ 4, 6 ].
Forerunners
Very early forerunners of the Buchberger algorithm are Euclid's algorithm and Gaussian elimination. Gordan in 1899 gave a new proof of Hilbert's basis theorem in which he showed the existence of what we now call finite Gröbner bases [ 16 ]. However, his proof is not constructive in the sense that it would indicate any algorithm for computing Gröbner bases. Also Hironaka [ 18 ] in 1964 used the concept of Gröbner bases in a different context, namely in the domain of formal power series (he calls them "standard bases"), without providing an algorithm for computing them.
In the 1920s, Janet [ 19 ] gave an algorithm for computing so-called "involutive bases" of a system of partial differential equations. When translated to the case of systems of polynomial equations, this algorithm amounts to Buchberger's algorithm with a certain particular choice in step 4 [ 15 ]. Similarly, in 1962, Shirshov [ 28 ] gave an algorithm for Lie algebras which when translated to polynomial systems resembles the Buchberger algorithm.
Gröbner himself proposed in 1950 [ 17 ] a forerunner of today's Buchberger algorithm which does not yet use S-polynomials but instead computes all possible reduced forms of all power products. Gröbner's question given to Buchberger as PhD topic was to find a termination criterion for this method. In his thesis from 1965 [ 1 ], Buchberger settled the question by introducing the Buchberger algorithm.
Change of Ordering
Some applications require Gröbner bases with respect to a particular ordering of the power products for which Buchberger's algorithm is not as efficient as for other orderings. In such situations it may be advantageous to first compute a Gröbner basis with respect to some ordering where Buchberger's algorithm runs faster and in a second step transform this Gröbner basis to a Gröbner basis for the desired ordering.
Gröbner Walk
Two different techniques for performing such a change of ordering are known. One is known as Gröbner walk. It is based on an interpretation of orderings as regions in a space. If two orderings correspond to regions which overlap, then a Gröbner basis for one of the orderings can be turned into a Gröbner basis for the other by calling Buchberger's algorithm on a small auxiliary problem for which it usually terminates quickly. When the regions for two orderings do not overlap, it is always possible to connect them by a path consisting of orderings where the regions of any two consecutive ones have an overlap. The transformation can then be done step by step, switching in each step to the next ordering on the path. For a detailed explanation we refer to [ 8, 9 ].
Linear Algebra
The second technique uses linear algebra. If \(G\) is a Gröbner basis for some ordering, then we have
\[ \begin{array}{rl} &\mathrm{RED}(\alpha_1 p_1+\alpha_2 p_2 + \cdots + \alpha_m p_m, G) = 0\\ \iff\quad&\alpha_1\mathrm{RED}(p_1, G)+\alpha_2\mathrm{RED}(p_2,G) + \cdots + \alpha_m\mathrm{RED}(p_m, G)=0 \end{array} \]
for any constants \(\alpha_1,\dots,\alpha_m\) and any polynomials \(p_1,\dots,p_m\ .\) This fact can be used to systematically search for polynomials which reduce to zero with respect to \(G\) and only contain power products from a prescribed set.
As an example, suppose we want to find a polynomial containing only the power products \(1,x,x^2\) which reduces to zero with respect to the Gröbner basis \(G=\{x-2y-2,z^2-2y-1,2y^2-1\}\ .\) This means we are looking for coefficients \(\alpha_0,\alpha_1,\alpha_2\) such that \(p=\alpha_0+\alpha_1x+\alpha_2x^2\) reduces to zero with respect to \(G\ .\) We have
\[ \begin{array}{rl} &\mathrm{RED}(\alpha_0+\alpha_1x+\alpha_2x^2, G)=0\\ \iff\quad &\alpha_0\mathrm{RED}(1,G)+\alpha_1\mathrm{RED}(x,G)+\alpha_2\mathrm{RED}(x^2,G)=0\\ \iff\quad &\alpha_0+\alpha_1(2y+2)+\alpha_3(8y+6)=0\\ \iff\quad &(\alpha_0+2\alpha_1+6\alpha_2)+(2\alpha_1+8\alpha_2)y=0\\ \iff\quad &\alpha_0+2\alpha_1+6\alpha_2=0\land 2\alpha_1+8\alpha_2=0. \end{array} \]
The latter is a homogeneous linear system of equations with \((\alpha_0,\alpha_1,\alpha_2)=(2,-4,1)\) as a solution. It follows that the polynomial \(x^2-4x+2\) reduces to zero with respect to \(G\ .\)
Using this technique, which was already sketched in [ 2 ], one can determine the elements of a Gröbner basis with respect to an ordering different from the ordering of \(G\ .\) A detailed description can be found in [ 30, 12, 9 ].
Implementations
Every general purpose computer algebra system includes some variant of Buchberger's algorithm for computing Gröbner bases. In addition, there are also several special purpose software systems with particularly efficient code for Gröbner basis computations, for example CoCoA [ 7 ], FGb [ 14 ], Macaulay2 [ 21 ], Magma [ 22 ], and Singular [ 29 ]. Sage [ 27 ] computes Gröbner bases using Singular, and recent versions of Maple [ 23 ] use FGb.
References
- B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal (An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal). PhD thesis, Universität Innsbruck, 1965. English translation in J. of Symbolic Computation, Special Issue on Logic, Mathematics, and Computer Science: Interactions. 41(3/4):475--511, 2006.
- B. Buchberger. Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems (An Algorithmic Criterion for the Solvability of Algebraic Systems of Equations). Aequationes mathematicae 3:374--383. 1970. English translation in: B. Buchberger, F. Winkler: Groebner Bases and Applications, Proc. of the International Conference "33 Years of Groebner Bases", 1998, RISC, Austria, London Math. Society Lecture Note Series 251, Cambridge Univ. Press, 1998, pages 535--545.
- B. Buchberger. A criterion for detecting unnecessary reductions in the construction of Gröbner bases. In Proceedings of EUROSAM'79, pages 3--21, 1979.
- B. Buchberger. A critical-pair/completion algorithm for finitely generated ideals in rings. In Lecture Notes in Computer Science, volume 171, pages 137--161, 1984.
- B. Buchberger. Groebner-bases: An algorithmic method in polynomial ideal theory. In Multidimensional Systems Theory - Progress, Directions and Open Problems in Multidimensional Systems, pages 184--232, 1985.
- B. Buchberger. History and basic features of the critical-pair/completion procedure. Journal of Symbolic Computation, 3(1/2):3--38, 1987.
- Cocoa. http://cocoa.dima.unige.it
- S. Collart, M. Kalkbrenner, and D. Mall. Converting bases with the Gröbner walk. Journal of Symbolic Computation, 24(3/4):465--469, 1997.
- D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry. Springer, 2nd edition, 2005.
- L. E. Dickson. Finiteness of the odd perfect and primitive abundant numbers with \(n\) distinct prime factors. American Journal of Mathematics, 35:413--422, 1913.
- T.W. Dube. The Structure of Polynomial Ideals and Gröbner Bases. SIAM Journal of Computing, 19(4):750--773, 1990.
- J.-Ch. Faugere, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zero dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation, 16(4):329--344, 1993.
- J.-Ch. Faugere. A new efficient algorithm for computing Gröbner bases. Journal of Pure and Applied Algebra, 139(1/3):61--88, 1999.
- FGb. http://www-salsa.lip6.fr/~jcf/Software/index.html
- V. P. Gerdt and Y. A. Blinkow. Involutive bases for polynomial ideals. Mathematics and Computers in Simulation, 45:519--541, 1998.
- P. Gordan. Neuer Beweis des Hilbertschen Satzes über homogene Funktionen. Göttinger Nachrichten, pages 240--284, 1899.
- W. Gröbner. Über die Eliminationstheorie Monatshefte für Mathematik, 54:71--78, 1950.
- H. Hironaka. Resolution of singularities of an algebraic variety over a field of characteristic zero: I, II. Annals of Mathematics, 79:109--326, 1964.
- M. Janet. Les systemes d'equations aux derivees partielles. Journal de Mathematique, 3:65--151, 1920.
- D. Knuth and P. Bendix. Simple word problems in universal algebras. In Computational Problems in Abstract Algebra, pages 263--297, 1970.
- Macaulay2. http://www.math.uiuc.edu/Macaulay2/
- Magma. http://magma.maths.usyd.edu.au/magma/
- Maple. http://www.maplesoft.com/products/maple/
- E.W. Mayr and A.R. Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics, 46(3):305--329, 1982.
- T. Mora. Solving Polynomial Equation Systems II. Cambridge, 2005.
- J. Alan Robinson. A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1):23--41, 1965.
- Sage. http://www.sagemath.org
- A. I. Shirshov. Certain algorithmic problems for Lie algebras. Siberian Mathematics Journal, 3:292--296, 1962.
- Singular. http://www.singular.uni-kl.de
- W. Trinks. Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen. Journal of Number Theory, 10(4), 1978.
For further references, including text books and survey articles on the subject, see the article on Gröbner bases.
