Gröbner Basis

A Gröbner basis G for a system of polynomials A is an equivalence system that possesses useful properties, for example, that another polynomial f is a combination of those in A iff the remainder of f with respect to G is 0. (Here, the division algorithm requires an order of a certain type on the monomials.) Furthermore, the set of polynomials in a Gröbner basis have the same collection of roots as the original polynomials. For linear functions in any number of variables, a Gröbner basis is equivalent to Gaussian elimination.

The algorithm for computing Gröbner bases is known as Buchberger's algorithm. Calculating a Gröbner basis is typically a very time-consuming process for large polynomial systems (Trott 2006, p. 37).

Gröbner bases are pervasive in the construction of symbolic algebra algorithms, and Gröbner bases with respect to lexicographic order are very useful for solving equations and for elimination of variables. For example, the following Wolfram Language command solves for the onset of the period-4 bifurcation in parameter r the logistic map by eliminating the variables x_1, x_2, x_3, and x_4 from a set of five equations describing the system.

  Factor /@ GroebnerBasis[
      x2 - r x1(1 - x1),
      x3 - r x2(1 - x2),
      x4 - r x3(1 - x3),
      x1 - r x4(1 - x4),
      r^4(1 - 2x1)(1 - 2x2)(1 - 2x3)(1 - 2x4) + 1
    {x1, x2, x3, x4},
    MonomialOrder -> EliminationOrder

Because computing a Gröbner basis can be so computationally expensive, variables can sometimes be eliminated more readily from a system of equations by manually computing the resultant of successive pairs of equations to iteratively eliminate one variable at each step.

The determination of a Gröbner basis is very roughly analogous to computing an orthonormal basis from a set of basis vectors and can be described roughly as a combination of Gaussian elimination (for linear systems) and the Euclidean algorithm (for univariate polynomials over a field).

The time and memory required to calculate a Gröbner basis depend very much on the variable ordering, monomial ordering, and on which variables are regarded as constants. Gröbner bases are used implicitly in many routines in the Wolfram Language, and can be called explicitly with the command GroebnerBasis[{poly1, poly2, ...}, {x1, x2, ...}].

In the common case of computing a Gröbner basis to eliminate trigonometric functions from a system of equations, the Weierstrass substitution


where h=tan(t/2) can be (but are not always) preferable to using c=cost and s=sint with the additional equation c^2+s^2=1 because they reduce the number of variables (Trott 2006, p. 39).

A bibliography about Gröbner bases is maintained by Buchberger and Zapletal.

In the Season 4 opening episode "Trust Metric" (2007) of the television crime drama NUMB3RS, math genius Charlie Eppes mentions that he used Gröbner bases in an attempt to derive an equation describing friendship.

See also

Buchberger's Algorithm, Commutative Algebra, Euclidean Algorithm, Gaussian Elimination, Gröbner Walk, Monomial, Orthonormal Basis

Explore with Wolfram|Alpha


Adams, W. W. and Loustaunau, P. An Introduction to Gröbner Bases. Providence, RI: Amer. Math. Soc., 1994.Becker, T. and Weispfenning, V. Gröbner Bases: A Computational Approach to Commutative Algebra. New York: Springer-Verlag, 1993.Boege, W.; Gebauer, R.; and Kredel, H. "Some Examples for Solving Systems of Algebraic Equations by Calculating Gröbner Bases." J. Symb. Comput. 1, 83-98, 1986.Buchberger, B. "Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory." Ch. 6 in Multidimensional Systems Theory (Ed. N. K. Bose). New York: van Nostrand Reinhold, 1982.Buchberger, B. "A Criterion for Detecting Unnecessary Reductions in the Construction of Groebner Bases." Proceedings of the International Symposium on Symbolic and Algebraic Computation. pp. 3-21, June 1979.Buchberger, B. "Groebner Bases: A Short Introduction for Systems Theorists.", B. and Zapletal, A. "Gröbner Bases Bibliography.", D.; Little, J.; and O'Shea, D. Ideals, Varieties, and Algorithms: An Introduction to Algebraic Geometry and Commutative Algebra, 2nd ed. New York: Springer-Verlag, 1996.Eisenbud, D. Commutative Algebra with a View toward Algebraic Geometry. New York: Springer-Verlag, 1995.Faugere, J. C.; Gianni, P.; Lazard, D.; and Mora, T. "Efficient Computation of Zero-Dimensional Groebner Bases by Change of Ordering." J. Symb. Comput. 16, 329-344, 1993.Giovini, A.; Mora, T.; Niesi, G.; Robbiano, L.; and Traverso, C. "One Sugar Cube, Please?, or Selection Strategies in the Buchberger Algorithm." Proceedings of the International Symposium on Symbolic and Algebraic Computation. pp. 49-54, June 1991.Harris, J. "Rearranging Expressions by Patterns." Mathematica J. 4, 82-85, 1994.Heck, A. "A Bird's-Eye View of Gröbner Bases.", G. "Gröbner Bases." Mathematica J. 5, 67-73, 1995.Nakos, G. and Glinos, M. "Computing Gröbner Bases over the Integers." Mathematica J. 4, 70-75, 1994.Lichtblau, D. "Gröbner Bases in Mathematica 3.0." Mathematica J. 6, 81-88, 1996.McGettrick, M. "Buchberger Algorithm--Gröbner Basis--Sparse Multivariate Polynomials.", B. Algorithmic Algebra. New York: Springer-Verlag, 1993.Robbiano, L. "Term Ordering on the Polynomial Ring." In EUROCAL '85: European Conference on Computer Algebra, 1985 Linz, Austria, Vol. 2: Research Contributions New York: Springer-Verlag, 1986.Stoutemyer, D. "Which Polynomial Representation is Best? Surprises Abound!" In Proceedings of the Third MACSYMA Users' Conference, Schenectady, NY. pp. 221-243, 1984.Trott, M. "Applying GroebnerBasis to Three Problems in Geometry." Mathematica Educ. Res. 6, 15-28, 1997.Trott, M. The Mathematica GuideBook for Symbolics. New York: Springer-Verlag, pp. 32-50, 2006., D. Elimination Methods. Berlin: Springer-Verlag, 1999.

Referenced on Wolfram|Alpha

Gröbner Basis

Cite this as:

Weisstein, Eric W. "Gröbner Basis." From MathWorld--A Wolfram Web Resource.

Subject classifications