Built-in Mathematica Symbol

GroebnerBasis

GroebnerBasis[{poly₁, poly₂, ...}, {x₁, x₂, ...}]
gives a list of polynomials that form a Gröbner basis for the set of polynomials poly_i.

GroebnerBasis[{poly₁, poly₂, ...}, {x₁, x₂, ...}, {y₁, y₂, ...}]
finds a Gröbner basis in which the y_i have been eliminated.

MORE INFORMATION

The set of polynomials in a Gröbner basis have the same collection of roots as the original polynomials.

For polynomials in one variable, GroebnerBasis reduces to PolynomialGCD.

For linear functions in any number of variables, GroebnerBasis is equivalent to Gaussian elimination.

The Gröbner basis in general depends on the ordering assigned to monomials. This ordering is affected by the ordering of the x_i.

The following options can be given:

MonomialOrder	Lexicographic	the criterion used for ordering monomials
CoefficientDomain	Automatic	the type of objects assumed to be coefficients
Method	Automatic	the method to use
Modulus	0	the modulus for numerical coefficients

Possible settings for MonomialOrder are Lexicographic, DegreeLexicographic, DegreeReverseLexicographic or an explicit weight matrix. Monomials are specified for the purpose of MonomialOrder by lists of the exponents with which the x_i appear in them.

The ordering of the x_i and the setting for MonomialOrder can substantially affect the efficiency of GroebnerBasis.

Possible settings for CoefficientDomain are InexactNumbers, Rationals, RationalFunctions and Polynomials[x].

Possible settings for the Method option include "Buchberger" and "GroebnerWalk".

EXAMPLES

CLOSE ALL

Basic Examples (1)

Compute a Gröbner basis:

Prove that polynomials have no common roots:

Compute a Gröbner basis:

In[1]:=

Out[1]=

Prove that polynomials have no common roots:

In[2]:=

Out[2]=

Scope (5)

Polynomials with a finite number of common roots:

Polynomials with an infinite number of common roots:

Polynomials with no common roots:

Eliminate a variable:

A lexicographic Gröbner basis:

A degree reverse lexicographic Gröbner basis:

Generalizations & Extensions (1)

Polynomial equations can be given instead of polynomials:

Options (8)

By default, Gröbner bases are computed over the field of rational numbers:

This computes the strong Gröbner basis over the ring of integers:

This computes the Gröbner basis over the field of rational functions

(a):

This uses approximate arithmetic:

The Automatic method setting uses "GroebnerWalk" for lexicographic bases over the rationals:

In this case the "Buchberger" method is much slower than "GroebnerWalk":

These polynomials are "close" to the lexicographic Gröbner basis:

The "GroebnerWalk" method computes the degree reverse lexicographic basis first:

Computing the lexicographic basis directly with the "Buchberger" method is faster here:

This computes the Gröbner basis over the field of integers modulo 7:

By default, GroebnerBasis uses the Lexicographic monomial order:

This gives the Gröbner basis in the DegreeReverseLexicographic monomial order:

A monomial order may be specified by giving a full rank square rational weight matrix:

For the order to be well-founded the first nonzero entry in each column must be positive:

Eliminate z and return a degree reverse lexicographic basis with respect to {x, y}:

Parameters are ordered lexicographically after all other variables:

This is an equivalent input:

By default, GroebnerBasis is not allowed to reorder the variables:

Reordering the variables may make computations faster; the Gröbner basis may be different:

Find an approximate GCD of a pair of univariate polynomials:

The polynomials are close to polynomials with integer coefficients:

With the default setting Tolerance->0, the approximate GCD has a too low degree:

With a higher setting of Tolerance, GroebnerBasis gives a "better" approximate GCD:

Applications (2)

Solve a system of polynomial equations:

A Gröbner basis has the same set of roots as the input polynomials:

Solve the first polynomial of the Gröbner basis for its only variable x:

Solve the second polynomial of the Gröbner basis for the other variable y:

This method finds all common roots of polys:

Reduce and Solve use Gröbner bases to solve systems of equations:

Get a fuzzy solution to a system of overdetermined equations:

This gives a low-precision approximate solution to this overdetermined set of polynomials:

Properties & Relations (6)

A Gröbner basis generates the same ideal as the input polynomials:

Use PolynomialReduce to show that p1 is in the ideal generated by g1 and g2:

By Hilbert's Nullstellensatz, if the ideal is

then the polynomials have no common zero:

Reduce or Solve proves that there is no common solution:

Conversely, if the ideal is not

, then there is at least one common zero:

Use FindInstance to find a solution instance:

GroebnerBasis of univariate polynomials is equivalent to computing PolynomialGCD:

GroebnerBasis of linear polynomials is equivalent to a Gaussian elimination process:

GroebnerBasis is used to solve systems of polynomial equations:

Use Reduce to directly solve the system:

Solve gives solutions in terms of replacement rules:

Eliminate a variable from a system of polynomial equations:

Eliminate a variable using Resolve:

Eliminate a variable using Eliminate:

Eliminate a variable using Resultant: