Gröbner Basis

A Gröbner basis for a system of polynomials is an equivalence system that possesses useful properties, for example, that another polynomial is a combination of those in iff the remainder of with respect to 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 the logistic map by eliminating the variables , , , and 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
    },
    r,
    {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

			(1)
			(2)

where can be (but are not always) preferable to using and with the additional equation 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.