- Gröbner basis
In
computer algebra , computationalalgebraic geometry , and computationalcommutative algebra , a Gröbner basis is a particular kind of generating subset of an ideal I in apolynomial ring R. One can view it as a multivariate, non-linear generalization of:* the
Euclidean algorithm for computation of univariategreatest common divisor s,
*Gaussian elimination for linear systems, and
*integer programming problems.The theory of Gröbner bases for polynomial rings was developed by
Bruno Buchberger in 1965, who named them after his advisorWolfgang Gröbner . The Association for Computing Machinery awarded him its 2007 Paris Kanellakis Theory and Practice Award for this work. An analogous concept forlocal ring s was developed independently byHeisuke Hironaka in 1964, who named them standard bases.Formal definition
A Gröbner basis G of an ideal I 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 division 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. It is the last two properties which allow calculations in the
factor ring R/I with the same facility as modular arithmetic. It is a significant fact ofcommutative 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. One method for computing them is known as
Buchberger's algorithm . Other methods for computing Gröbner bases are theFaugère F4 algorithm , based on the same mathematics as the Buchberger algorithm, and involutive approaches, based on ideas fromDifferential algebra . [Vladimir P. Gerdt, Yuri A. Blinkov (1998). "Involutive Bases of Polynomial Ideals", Mathematics and Computers in Simluation, 45:519ff] There are also two 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; theFGLM algorithm and theGrö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 and to non-commutative (skew) polynomial rings such as
Weyl algebra s.Properties and applications of Gröbner bases
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 algorithm 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" ["x"1, "x"2, ..., "x""n"]
is computed relative to the lexicographic ordering with
:"x"1 > "x"2 > ... > "x""n",
the intersection of "I" with
:"k" ["x""k", "x""k"+1, ..., "x""n"]
is given by the intersection of the Gröbner basis with
:"k" ["x""k", "x""k"+1, ..., "x""n"] .
In particular a polynomial f lies in
:"k" ["x""k", "x""k"+1, ..., "x""n"] ,
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
:{"f"1 ["x"1, ..., "x""n"] = "a"1, ..., "f""m" ["x"1, ..., "x""n"] = "a""m"},
we should be able to manipulate these equations to get something of the form
:"g"("x""n") = "b".
The elimination property says that if we compute a Gröbner basis for the ideal generated by {"f"1 − "a"1, ..., "f""m" − "a""m"} 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 "x""n"−1 and "x""n", so we can take our possible solutions for "xn" and find corresponding values for "x""n"−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 equation s of polynomials into nonparametric equations. Given the equations:{"x"1 = "f"1("t"1, ..., "t""m"), ..., "x""n" = "f""n"("t"1, ..., "t""m")},
we compute a Gröbner basis for the ideal generated by
:{"x"1 − "f"1, ..., "x""n" − "f""n"}
relative to any ordering which places polynomials involving "t" greater than those which don't: for example, lexicographic ordering with
:"t"1 > "t"2 > ... > "t""m" > "x"1 > ... > "x""n".
Taking only the elements of the basis which do not involve the "t" variables, we get a set of equations describing not the original surface, but the smallest affine variety containing it.
Intersecting ideals
*If "I" is generated by
:{"f"1, ..., "f""m"} and "J" is generated by some
:{"g"1, ..., "g""k"},
then the intersection of "I" and "J" can be found by taking a Gröbner basis for the ideal generated by:{"tf"1, ..., "tf""m", (1 − "t")"g"1, ..., (1 − "t")"g""k"}
relative to any lexicographic ordering which places "t" first, then taking only those terms not involving "t". In particular, this allows us to calculate the
least common multiple (and hence thegreatest 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 aEuclidean domain , so the Euclidean algorithm doesn't work here.See also
*Buchberger's algorithm
*Faugère F4 algorithm
*Gröbner-Shirshov basis
*Mathematica includes an implementation of the Buchberger algorithm, with performance-improving techniques such as the Gröbner walk, Gröbner trace, and an improvement for toric bases
*Maple has implementations of the Buchberger and Faugère F4 algorithms
*SINGULAR free software for computing Gröbner bases
*Macaulay 2 free software for doing polynomial computations, particularly Gröbner bases calculations.
*CoCoA free computer algebra system for computing Gröbner bases.
*SAGE (computer algebra system) a free software package that provides a unified interface to several computer algebra systems (including SINGULAR and Macaulay), and includes a few Gröbner basis algorithms of its own.
*Magma has an very fast implementation of the Faugère F4 algorithm. [ [http://magma.maths.usyd.edu.au/users/allan/gb/ Allan Steel's Gröbner Basis Timings Page ] ]References
Further reading
* William W. Adams, Philippe Loustaunau (1994). "An Introduction to Gröbner Bases".
American Mathematical Society , 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 Buchberger (1965). [http://www.ricam.oeaw.ac.at/Groebner-Bases-Bibliography/gbbib_files/publication_706.pdf "An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal"] . Ph.D. dissertation, University of Innsbruck. [http://www.ricam.oeaw.ac.at/Groebner-Bases-Bibliography/do_search.php?query_option1=&search_title=&search_author=1&search_type=7&search_keywords=&search_on=0&viewoption=0 English translation] by M. Abramson inJournal of Symbolic Computation 41 (2006): 471-511. [This is Buchberger's thesis inventing Gröbner bases.]*
Bruno Buchberger (1970). [http://www.ricam.oeaw.ac.at/Groebner-Bases-Bibliography/gbbib_files/publication_699.pdf "An Algorithmic Criterion for the Solvability of a System of Algebraic Equations"] . Aequationes Mathematicae 4 (1970): 374-383. [http://www.ricam.oeaw.ac.at/Groebner-Bases-Bibliography/gbbib_files/publication_684.pdf English translation] by M. 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.]* David Cox, John Little, and Donal O'Shea (1997). "Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra", Springer. ISBN 0-387-94680-2. "See Chapter 2: Gröbner Bases".
* Ralf Fröberg (1997). "An Introduction to Gröbner Bases". Wiley & Sons. ISBN 0-471-97442-0
External links
* B. Buchberger, [http://www.risc.uni-linz.ac.at/people/buchberg/papers/2001-02-19-A.pdf Groebner Bases: A Short Introduction for Systems Theorists] in "Proceedings of EUROCAST 2001".
*Buchberger, B. and Zapletal, A. [http://www.ricam.oeaw.ac.at/Groebner-Bases-Bibliography/search.php Gröbner Bases Bibliography.]
* [http://magma.maths.usyd.edu.au/users/allan/gb Comparative Timings Page for Gröbner Bases Software]
* [http://grobner.nuigalway.ie/ ogb] Online Gröbner Basis, Galway, Éire
* [http://www.geocities.com/CapeCanaveral/Hall/3131/ Java applet for computing Gröbner bases] by Fabrizio
* [http://www.cs.le.ac.uk/people/ah83/grobner/ Gröbner Basis Theory] Leicester University
*
Wikimedia Foundation. 2010.