Skip to content

GroebnerBasis

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

GroebnerBasis[{p1, p2, ...}, {x1, x2, ...}]
    gives a list of polynomials that form a Gröbner basis for the
    ideal generated by the pi over Q[x1, x2, ...].
GroebnerBasis[{p1, ...}, {x1, ...}, {y1, ...}]
    eliminates the yi and returns a Gröbner basis of the elimination
    ideal in {x1, ...}.
Free symbols in pi that are not in vars (and not a known constant
    like Pi, E, EulerGamma, ...) are auto-promoted to coefficient-ring
    parameters and survive in the basis polynomials.
Options: MonomialOrder -> Lexicographic (default) |
    DegreeReverseLexicographic | EliminationOrder | a weight matrix
    {{...}, ...} of integers (one column per variable, defining a
    custom term order); CoefficientDomain -> Rationals (default);
    Method -> "Buchberger" (default) | "GroebnerWalk"; Sort
    -> True reverses the main-variable list; ParameterVariables -> p
    or {p1, ...} marks parameters explicitly (the main-variable list
    is then optional and is auto-derived from the polys).  Other
    settings emit GroebnerBasis::nimpl and fall back; Modulus emits
    GroebnerBasis::modnotimpl and falls back to the rational basis.
Polynomial equations (Equal[a, b]) are accepted in place of
    polynomials; each is rewritten as a - b before computation.
TimeConstrained[GroebnerBasis[...], t] aborts cleanly via the
    cooperative deadline hook.  Lex order can be exponentially slow
    on systems with 3+ variables; switch to MonomialOrder ->
    DegreeReverseLexicographic for hard inputs.

Examples

No verified examples yet for this function.

Implementation notes

Algorithm. builtin_groebner_basis (in src/poly/groebnerbasis.c) is the front end; the engine is in groebner.c and the order conversion in groebnerwalk.c. The front end parses GroebnerBasis[polys, vars] (and the 3-arg elimination form GroebnerBasis[polys, mainVars, elimVars]), reads the MonomialOrder (Lexicographic default, DegreeReverseLexicographic, or EliminationOrder — forced by the 3-arg form), CoefficientDomain and Method options, converts each polynomial to the internal GBPoly via gb_from_expr, runs the core, and renders the basis back to expressions.

The core gb_buchberger is textbook Buchberger with Gebauer–Möller pair management: each new basis element is folded in with gm_update, which applies Buchberger criterion 1 (coprime leading monomials) and the Gebauer–Möller M/F/B criteria to discard provably useless pairs without re-walking exponents. The main loop picks the next pair by the normal strategy (gm_pick_pair), forms the S-polynomial (gb_spoly, using the pointwise-max lcm of the two leading exponent vectors), fully reduces it against the current basis (gb_reduce, multivariate division to a normal form), and adds any non-zero remainder (made monic). After saturation, gb_finalize_basis inter-reduces and normalises to the unique reduced Gröbner basis. A tc_check_deadline hook lets TimeConstrained abort between pairs.

For expensive target orders the front end can route through the Gröbner walk (gb_groebner_walk, the Collart–Kalkbrener–Mall algorithm): compute the basis under the cheap DegreeReverseLexicographic order, then walk along the weight path w(t) = (1−t)·(1,…,1) + t·σ across the Gröbner fan, rewriting through initial-form ideals at each cone wall, with a guaranteed fall-back to a direct gb_buchberger run under the target order on any overflow or degenerate lift.

Data structures. GBPoly holds rational coefficients as a parallel array of GMP mpq_t alongside a row-major int* exps (n_terms × n_vars) exponent matrix, with a borrowed GBWeightMatrix defining the order and an elim_pivot for elimination blocks. Pairs are GMPair records carrying a precomputed lcm and a dead flag.

Complexity / limits. Buchberger's algorithm is doubly-exponential in the worst case; lexicographic bases especially can blow up, which is why grevlex-then-walk is offered. Arithmetic is exact (mpq_t/mpz-guarded int64 weights). Unsupported option values emit a GroebnerBasis::nimpl diagnostic.

  • Protected.
  • Computes the reduced Gröbner basis under the requested monomial order

Attributes: Protected.

Implementation status

Stable — documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

References

  • Cox, Little & O'Shea, "Ideals, Varieties, and Algorithms" (Springer) — Buchberger's algorithm, monomial orders, and elimination.
  • von zur Gathen & Gerhard, "Modern Computer Algebra" (3rd ed.), Ch. 21 (Gröbner bases).
  • B. Buchberger, "An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal" (PhD thesis, 1965).
  • R. Gebauer, H. M. Möller, "On an installation of Buchberger's algorithm", J. Symbolic Computation 1988.
  • S. Collart, M. Kalkbrener, D. Mall, "Converting bases with the Gröbner walk", J. Symbolic Computation 1997.
  • T. Becker, V. Weispfenning, Gröbner Bases (Springer, 1993).
  • Source: src/poly/groebnerbasis.c
  • Specification: docs/spec/builtins/structural-manipulation.md

Notes & additional examples

Worked examples

In[1]:= GroebnerBasis[{x^2 + y^2 - 1, x - y}, {x, y}]
Out[1]= {-1 + 2 y^2, x - y}

In[1]:= GroebnerBasis[{x y - 1, x - y}, {x, y}]
Out[1]= {-1 + y^2, x - y}

In[1]:= GroebnerBasis[{x^2 - y, x^3 - z}, {x, y, z}]
Out[1]= {y^3 - z^2, -y^2 + x z, x y - z, x^2 - y}

In[1]:= GroebnerBasis[{x + y + z, x y + y z + z x, x y z - 1}, {x, y, z}]
Out[1]= {-1 + z^3, y^2 + y z + z^2, x + y + z}

Notes

GroebnerBasis[polys, vars] computes a Gröbner basis of the ideal under the default Lexicographic monomial order via Buchberger's algorithm. The lex order triangularizes the system: in the circle-meets-line example the basis isolates -1 + 2 y^2 (a univariate consequence in the last variable) plus the linear relation. The symmetric-functions system reduces to z^3 = 1, exposing the roots of unity, while the implicitization example returns the full reduced basis describing the twisted cubic. Set MonomialOrder -> DegreeReverseLexicographic for systems with three or more variables, where lex order can be exponentially slow; a third argument selects elimination variables, and Equal equations are accepted in place of bare polynomials.