Gröbner basis
Encyclopedia
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. One can view it as a multivariate, non-linear generalization of:
The theory of Gröbner bases for polynomial rings was developed by Bruno Buchberger
in 1965, who named them after his advisor Wolfgang Gröbner
. The Association for Computing Machinery awarded him its 2007 Paris Kanellakis Theory and Practice Award for this work. An analogous concept for local ring
s was developed independently by Heisuke Hironaka
in 1964, who named them standard bases. The analogous theory for free Lie algebras was developed by A. I. Shirshov in 1962 but his work remained largely unknown outside the Soviet Union.
I in a polynomial ring R over a field is characterised by any one of the following properties, stated relative to some monomial order:
All these properties are equivalent; different authors use different definitions depending on the topic they choose. The last two properties that allow calculations in the factor ring R/I with the same facility as modular arithmetic. It is a significant fact of commutative algebra
that Gröbner bases always exist, and can be effectively obtained for any ideal starting with a generating subset.
Multivariate division requires a monomial ordering, the basis depends on the monomial ordering chosen, and different orderings can give rise to radically different Gröbner bases. Two of the most commonly used orderings are lexicographic ordering
, and degree reverse lexicographic order (also called graded reverse lexicographic order or simply total degree order). Lexicographic order eliminates variables, however the resulting Gröbner bases are often very large and expensive to compute. Degree reverse lexicographic order typically provides for the fastest Gröbner basis computations. In this order monomials are compared first by total degree, with ties broken by taking the smallest monomial with respect to lexicographic ordering with the variables reversed.
In most cases (polynomials in finitely many variables with complex coefficients or, more generally, coefficients over any field, for example), Gröbner bases exist for any monomial ordering. Buchberger's algorithm
is the oldest and most well-known method for computing them. Other methods are the Faugère F4 algorithm
, based on the same mathematics as the Buchberger algorithm, and involutive approaches, based on ideas from differential algebra
. There are also three algorithms for converting a Gröbner basis with respect to one monomial order to a Gröbner basis with respect to a different monomial order: the FGLM algorithm, the Hilbert Driven Algorithm and the Gröbner walk algorithm. These algorithms are often employed to compute (difficult) lexicographic Gröbner bases from (easier) total degree Gröbner bases.
A Gröbner basis is termed reduced if the leading coefficient of each element of the basis is 1 and no monomial in any element of the basis is in the ideal generated by the leading terms of the other elements of the basis. In the worst case, computation of a Gröbner basis may require time that is exponential or even doubly exponential in the number of solutions of the polynomial system (for degree reverse lexicographic order and lexicographic order, respectively). Despite these complexity bounds, both standard and reduced Gröbner bases are often computable in practice, and most computer algebra systems contain routines to do so.
The concept and algorithms of Gröbner bases have been generalized to modules
over a polynomial ring, to free non-commutative polynomial rings and, by Weispfenning and his school, to solvable polynomial rings such as Weyl algebras.
for an ideal using a Gröbner basis will yield 0 if and only if f is in the ideal. (By contrast, this is generally not true for a non-Gröbner basis with polynomials in more than one variable). This gives a test for determining whether or not a polynomial is in an ideal with a given set of generators.
is computed relative to the lexicographic ordering with
the intersection of I with
is given by the intersection of the Gröbner basis with
In particular a polynomial f lies in
if and only if its leading term lies in this subring. This is known as the elimination property.
we should be able to manipulate these equations to get something of the form
The elimination property says that if we compute a Gröbner basis for the ideal generated by {f1 – a1, ..., fm – am} relative to the right lexicographic ordering, then we can find the polynomial g as one of the elements of our basis. Furthermore, (taking k = n – 1) there will be another polynomial in the basis involving only xn – 1 and xn, so we can take our possible solutions for xn and find corresponding values for xn – 1. This lifting continues all the way up until we've found the values of all the variables.
s of polynomials into nonparametric equations. Given the equations
we compute a Gröbner basis for the ideal generated by
relative to any ordering that places polynomials involving t greater than those that don't: for example, lexicographic ordering with
Taking only the elements of the basis that do not involve the t variables, we get a set of equations describing not the original surface, but the smallest affine variety
containing it.
and J is generated by some
then the intersection of I and J can be found by taking a Gröbner basis for the ideal generated by
relative to any lexicographic ordering that places t first, then taking only those terms not involving t. In particular, this allows us to calculate the least common multiple
(and hence the greatest common divisor
) of two polynomials f and g, since it is the generator of the intersection of the ideals generated by f and by g. This is true even if we do not know how to factor the polynomials! Also, note that for more than one variable the polynomial ring is not a Euclidean domain
, so the Euclidean algorithm doesn't work here.
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...
, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring
Polynomial ring
In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the Hilbert basis theorem, to the construction of...
R. One can view it as a multivariate, non-linear generalization of:
- the Euclidean algorithmEuclidean algorithmIn 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 computation of univariate greatest common divisorGreatest common divisorIn 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...
s, - Gaussian eliminationGaussian eliminationIn 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, and - integer programmingInteger programmingAn integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
problems.
The theory of Gröbner bases for polynomial rings was developed by 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...
in 1965, who named them after his advisor Wolfgang Gröbner
Wolfgang Gröbner
Wolfgang Gröbner was an Austrian mathematician. His name is best known for the Gröbner basis, used for computations in algebraic geometry...
. The Association for Computing Machinery awarded him its 2007 Paris Kanellakis Theory and Practice Award for this work. An analogous concept for local ring
Local ring
In abstract algebra, more particularly in ring theory, local rings are certain rings that are comparatively simple, and serve to describe what is called "local behaviour", in the sense of functions defined on varieties or manifolds, or of algebraic number fields examined at a particular place, or...
s was developed independently by Heisuke Hironaka
Heisuke Hironaka
is a Japanese mathematician. After completing his undergraduate studies at Kyoto University, he received his Ph.D. from Harvard while under the direction of Oscar Zariski. He won the Fields Medal in 1970....
in 1964, who named them standard bases. The analogous theory for free Lie algebras was developed by A. I. Shirshov in 1962 but his work remained largely unknown outside the Soviet Union.
Formal definition
A Gröbner basis G of an idealIdeal (ring theory)
In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. The ideal concept allows the generalization in an appropriate way of some important properties of integers like "even number" or "multiple of 3"....
I in a polynomial ring R over a field is characterised by any one of the following properties, stated relative to some monomial order:
- the ideal given by the leading terms of polynomials in I is itself generated by the leading terms of the basis G;
- the leading term of any polynomial in I is divisible by the leading term of some polynomial in the basis G;
- multivariate divisionMultivariate 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....
of any polynomial in the polynomial ring R by G gives a unique remainder; - multivariate division of any polynomial in the ideal I by G gives 0.
All these properties are equivalent; different authors use different definitions depending on the topic they choose. The last two properties that allow calculations in the factor ring R/I with the same facility as modular arithmetic. It is a significant fact of 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...
that Gröbner bases always exist, and can be effectively obtained for any ideal starting with a generating subset.
Multivariate division requires a monomial ordering, the basis depends on the monomial ordering chosen, and different orderings can give rise to radically different Gröbner bases. Two of the most commonly used orderings are lexicographic ordering
Lexicographical order
In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...
, and degree reverse lexicographic order (also called graded reverse lexicographic order or simply total degree order). Lexicographic order eliminates variables, however the resulting Gröbner bases are often very large and expensive to compute. Degree reverse lexicographic order typically provides for the fastest Gröbner basis computations. In this order monomials are compared first by total degree, with ties broken by taking the smallest monomial with respect to lexicographic ordering with the variables reversed.
In most cases (polynomials in finitely many variables with complex coefficients or, more generally, coefficients over any field, for example), Gröbner bases exist for any monomial ordering. Buchberger's algorithm
Buchberger's algorithm
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...
is the oldest and most well-known method for computing them. Other methods are 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...
. There are also three algorithms for converting a Gröbner basis with respect to one monomial order to a Gröbner basis with respect to a different monomial order: the FGLM algorithm, the Hilbert Driven Algorithm and the Gröbner walk algorithm. These algorithms are often employed to compute (difficult) lexicographic Gröbner bases from (easier) total degree Gröbner bases.
A Gröbner basis is termed reduced if the leading coefficient of each element of the basis is 1 and no monomial in any element of the basis is in the ideal generated by the leading terms of the other elements of the basis. In the worst case, computation of a Gröbner basis may require time that is exponential or even doubly exponential in the number of solutions of the polynomial system (for degree reverse lexicographic order and lexicographic order, respectively). Despite these complexity bounds, both standard and reduced Gröbner bases are often computable in practice, and most computer algebra systems contain routines to do so.
The concept and algorithms of Gröbner bases have been generalized to modules
Module (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
over a polynomial ring, to free non-commutative polynomial rings and, by Weispfenning and his school, to solvable polynomial rings such as Weyl algebras.
Deciding equality of ideals
Reduced Gröbner bases can be shown to be unique for any given ideal and monomial ordering, and are also often computable in practice. Thus one can determine if two ideals are equal by looking at their reduced Gröbner bases.Deciding membership of ideals
The reduction of a polynomial f by the multivariate division algorithmMultivariate division algorithm
In 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....
for an ideal using a Gröbner basis will yield 0 if and only if f is in the ideal. (By contrast, this is generally not true for a non-Gröbner basis with polynomials in more than one variable). This gives a test for determining whether or not a polynomial is in an ideal with a given set of generators.
Elimination property
If a Gröbner basis for an ideal I in- k[x1, x2, ..., xn]
is computed relative to the lexicographic ordering with
- x1 > x2 > ... > xn,
the intersection of I with
- k[xk, xk+1, ..., xn]
is given by the intersection of the Gröbner basis with
- k[xk, xk+1, ..., xn].
In particular a polynomial f lies in
- k[xk, xk+1, ..., xn],
if and only if its leading term lies in this subring. This is known as the elimination property.
Solving equations
In particular, this gives us a method for solving simultaneous polynomial equations. If there are only finitely many solutions (over an algebraic closure of the field in which the coefficients lie) to the system of equations- {f1[x1, ..., xn] = a1, ..., fm[x1, ..., xn] = am},
we should be able to manipulate these equations to get something of the form
- g(xn) = b.
The elimination property says that if we compute a Gröbner basis for the ideal generated by {f1 – a1, ..., fm – am} relative to the right lexicographic ordering, then we can find the polynomial g as one of the elements of our basis. Furthermore, (taking k = n – 1) there will be another polynomial in the basis involving only xn – 1 and xn, so we can take our possible solutions for xn and find corresponding values for xn – 1. This lifting continues all the way up until we've found the values of all the variables.
Conversion of parametric equations
The same elimination property can almost be used to convert parametric equationParametric equation
In mathematics, parametric equation is a method of defining a relation using parameters. A simple kinematic example is when one uses a time parameter to determine the position, velocity, and other information about a body in motion....
s of polynomials into nonparametric equations. Given the equations
- {x1 = f1(t1, ..., tm), ..., xn = fn(t1, ..., tm)},
we compute a Gröbner basis for the ideal generated by
- {x1 – f1, ..., xn – fn}
relative to any ordering that places polynomials involving t greater than those that don't: for example, lexicographic ordering with
- t1 > t2 > ... > tm > x1 > ... > xn.
Taking only the elements of the basis that do not involve the t variables, we get a set of equations describing not the original surface, but the smallest affine variety
Algebraic variety
In mathematics, an algebraic variety is the set of solutions of a system of polynomial equations. Algebraic varieties are one of the central objects of study in algebraic geometry...
containing it.
Intersecting ideals
- If I is generated by
- {f1, ..., fm}
and J is generated by some
- {g1, ..., gk},
then the intersection of I and J can be found by taking a Gröbner basis for the ideal generated by
- {tf1, ..., tfm, (1 – t)g1, ..., (1 – t)gk}
relative to any lexicographic ordering that places t first, then taking only those terms not involving t. In particular, this allows us to calculate the least common multiple
Least common multiple
In 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...
(and hence the greatest common divisor
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...
) of two polynomials f and g, since it is the generator of the intersection of the ideals generated by f and by g. This is true even if we do not know how to factor the polynomials! Also, note that for more than one variable the polynomial ring is not a Euclidean domain
Euclidean domain
In mathematics, more specifically in abstract algebra and ring theory, a Euclidean domain is a ring that can be endowed with a certain structure – namely a Euclidean function, to be described in detail below – which allows a suitable generalization of the Euclidean algorithm...
, so the Euclidean algorithm doesn't work here.
Further reading
- William W. Adams, Philippe Loustaunau (1994). An Introduction to Gröbner Bases. American Mathematical SocietyAmerican Mathematical SocietyThe American Mathematical Society is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, which it does with various publications and conferences as well as annual monetary awards and prizes to mathematicians.The society is one of the...
, Graduate Studies in Mathematics, Volume 3. ISBN 0-8218-3804-0 - Thomas Becker, Volker Weispfenning (1998). Gröbner Bases. Springer Graduate Texts in Mathematics 141. ISBN 0-387-97971-7
- Bruno BuchbergerBruno BuchbergerBruno 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...
(1965). An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal. Ph.D. dissertation, University of Innsbruck. English translation by Michael Abramson in Journal of Symbolic ComputationJournal of Symbolic ComputationThe Journal of Symbolic Computation is a peer-reviewed monthly scientific journal covering all aspects of symbolic computation published by Academic Press. It is targeted to both mathematicians and computer scientists...
41 (2006): 471–511. [This is Buchberger's thesis inventing Gröbner bases.] - Bruno BuchbergerBruno BuchbergerBruno 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...
(1970). An Algorithmic Criterion for the Solvability of a System of Algebraic Equations. Aequationes Mathematicae 4 (1970): 374–383. English translation by Michael Abramson and Robert Lumbert in Gröbner Bases and Applications (B. Buchberger, F. Winkler, eds.). London Mathematical Society Lecture Note Series 251, Cambridge University Press, 1998, 535–545. ISBN 0-521-63298-6 (This is the journal publication of Buchberger's thesis.) (translated from Sibirsk. Mat. Zh. Siberian Mathemaics Journal, 3 (1962), 292–296) - M. Aschenbrenner and C. Hillar, Finite generation of symmetric ideals, Trans. Amer. Math. Soc. 359 (2007), 5171–5192 (on infinite dimensional Gröbner bases for polynomial rings in infinitely many indeterminates).
External links
- B. Buchberger, Groebner Bases: A Short Introduction for Systems Theorists in Proceedings of EUROCAST 2001.
- Buchberger, B. and Zapletal, A. Gröbner Bases Bibliography.
- Comparative Timings Page for Gröbner Bases Software
- ogb Online Gröbner Basis, Galway, Éire
- Java applet for computing Gröbner bases by Fabrizio
- Gröbner Basis Theory Leicester University
- Prof. Bruno Buchberger Bruno Buchberger