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.
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 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.
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." http://www.risc.uni-linz.ac.at/people/buchberg/papers/2001-02-19-A.pdf.Buchberger,
B. and Zapletal, A. "Gröbner Bases Bibliography." http://www.ricam.oeaw.ac.at/Groebner-Bases-Bibliography/.Cox,
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."
http://www.can.nl/ca_library/groebner/tutorials/heck/aihenp96.html.Helzer,
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."
http://grobner.nuigalway.ie/grobner/basis.html.Mishra,
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. http://www.mathematicaguidebooks.org/.Wang,
D. Elimination
Methods. Berlin: Springer-Verlag, 1999.