Buchberger's algorithm
Encyclopedia
In computational algebraic geometry
and computational commutative algebra
, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial 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 GCD
computation and of Gaussian elimination
for linear systems.
A crude version of this algorithm to find a basis for an ideal I of a ring R proceeds as follows:
The polynomial Sij is commonly referred to as the S-polynomial, where S refers to subtraction (Buchberger) or Syzygy
(others).
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. It also should be noted that if the leading terms of fi and fj share no variables in common, then Sij will always reduce to 0 (if we use only fi and fj 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.
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
.
Algebraic geometry
Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...
and computational commutative algebra
Commutative algebra
Commutative algebra is the branch of abstract algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra...
, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gröbner basis
Gröbner basis
In computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring R...
with respect to some monomial order. It was invented by Austrian mathematician Bruno Buchberger
Bruno Buchberger
Bruno Buchberger is Professor of Computer Mathematics at Johannes Kepler University in Linz, Austria. In his 1965 Ph.D. thesis, he created the theory of Gröbner bases, and has developed this theory throughout his career. He named these objects after his advisor Wolfgang Gröbner...
. One can view it as a generalization of the Euclidean algorithm
Euclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
for univariate GCD
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
computation and of Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
for linear systems.
A crude version of this algorithm to find a basis for an ideal I of a ring R proceeds as follows:
- Input A set of polynomials F = {f1, f2, ..., fk} that generate I
- Output A Gröbner basisGröbner basisIn computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring R...
for I
-
- Let gi be the leading term of fi with respect to the given ordering, and denote the least common multipleLeast common multipleIn arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...
of gi and gj by aij. - Let Sij ← (aij / gi) fi − (aij / gj) fj
(Note that the leading terms here will cancel by construction). - Using the multivariate division algorithmMultivariate division algorithmIn mathematics, polynomials in more than one variable do not form a Euclidean domain, so it is not possible to construct a true division algorithm; but an approximate multivariate division algorithm can be constructed....
, reduce all the Sij relative to the set F. - Add all the nonzero polynomials resulting from step 3 to F, and repeat steps 1-4 until nothing new is added.
- Let gi be the leading term of fi with respect to the given ordering, and denote the least common multiple
The polynomial Sij is commonly referred to as the S-polynomial, where S refers to subtraction (Buchberger) or Syzygy
Syzygy (mathematics)
In mathematics, a syzygy is a relation between the generators of a module M. The set of all such relations is called the "first syzygy module of M". A relation between generators of the first syzygy module is called a "second syzygy" of M, and the set of all such relations is called the...
(others).
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. It also should be noted that if the leading terms of fi and fj share no variables in common, then Sij will always reduce to 0 (if we use only fi and fj 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
Dickson's lemma
In mathematics, Dickson's lemma is a finiteness statement applying to n-tuples of natural numbers. It is a simple fact from combinatorics, which has become attributed to the American algebraist L. E. Dickson...
(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
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
of the algorithm is doubly exponential in the input data, which implies that its worst-case behavior can be very slow.
Further methods for computing Gröbner bases include the Faugère F4 algorithm
Faugère F4 algorithm
In computer algebra, the Faugère F4 algorithm, by Jean-Charles Faugère, computes the Gröbner basis of an ideal of a multivariate polynomial ring...
, based on the same mathematics as the Buchberger algorithm, and involutive approaches, based on ideas from Differential algebra
Differential algebra
In mathematics, differential rings, differential fields, and differential algebras are rings, fields, and algebras equipped with a derivation, which is a unary function that is linear and satisfies the Leibniz product law...
.
See also
- Quine-McCluskey algorithm (analogous algorithm for Boolean algebra)
- Buchberger's algorithm discussed more extensively on Scholarpedia