Scholarpedia is supported by Brain Corporation
Groebner basis
Bruno Buchberger and Manuel Kauers (2010), Scholarpedia, 5(10):7763. | doi:10.4249/scholarpedia.7763 | revision #128998 [link to/cite this article] |
A Gröbner basis is a set of multivariate nonlinear polynomials enjoying
certain properties that allow simple algorithmic solutions for many fundamental
problems in mathematics and natural and technical sciences.
Examples of such problems are: the solution of algebraic systems of equations, the representability of polynomials in terms of other polynomials, the analysis and construction of nonlinear cryptosystems, the closed form summation and integration of expressions involving special functions, the closed form solution of linear boundary value problems (differential equations). Amazingly, also problems that seem to be far away form algebra as, for example, the automated proof and discovery of geometrical theorems, the construction of graph colorings and the solution of Sudoku games can be reduced to Gröbner bases computations. Examples of problems in natural and technical sciences that have recently been solved by the Gröbner bases methodology are intelligent control of oil platforms, reverse engineering of software, finding genetic relationship between species, and solving the inverse robotic kinematics.
Here is a typical example of a Gröbner basis consisting of three polynomials in three variables:
\{x^3 - x^2+2, y - 2x^2 +1, z - 3x+5\}.
In this example, we see one of the advantageous properties of Gröbner bases: The equation system
x^3 - x^2+2=0,\quad y - 2x^2 +1=0,\quad z - 3x+5=0
in this Gröbner basis form can be easily solved. Namely, one first will find the three possible solutions x of the first equation and then substitute each of these solutions into the second and third equation to determine the corresponding y and z\ , respectively.
The fundamental insight and contribution of Gröbner bases theory is that every polynomial system, no matter how complicated, can be transformed---by an algorithm---into Gröbner basis form, see Buchberger's algorithm.
In this article, we will explain by examples the general notion of Gröbner basis, the fundamental mathematical properties of Gröbner bases, the algorithm for constructing Gröbner bases, and some example applications of Gröbner bases. The notion of Gröbner basis and the fundamental results of Gröbner bases theory was introduced by Bruno Buchberger [ 5, 6 ]. Further information can be found in the textbooks and survey articles on Gröbner bases given in the list of references [ 2, 3, 4, 7, 8, 9, 11, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 29, 30, 32, 33, 35, 36, 39, 47, 48 ]. For a comprehensive collection of research articles, see [1].
Contents |
The Notion of Gröbner bases
Gröbner bases are sets of multivariate polynomials satisfying certain conditions. There are numerous equivalent conditions by which Gröbner bases can be defined. We give here two of them.
Definition via the Leading Power Product Property
In this article, a "basis" is just a set B of multivariate polynomials, like B=\{x z^2-3 y z+1,x^2-2 y,x y-5 z\}.
all leading power products of linear combinations of polynomials in the basis are multiples of at least one of the leading power products in the set.
By a linear combination of polynomials we mean a sum of polynomial multiples of these polynomials. For example, -2 y^2 z^2+15 y z^2-5 z=(-x y)(x z^2-3 y z+1)+(y z^2)(x^2-2 y)+(-3yz+1) (x y-5 z)
By a power product we mean polynomials that are obtained from the variables only by multiplication. For example, x^3 y^2 is a power product. Every polynomial can be written uniquely as a linear combination of power products with constant coefficients. For example, the polynomial -2 y^2 z^2+15 y z^2-5 z
Multiplicative relations among power products can be visualized by arranging the power products into a grid as shown in Figure Figure 1 for two variables. The multiples of some power product, as for example x^3y^2\ , can then be visualized by the shaded area in Figure Figure 1.
The leading power product of a polynomial is the largest power product appearing in the polynomial. For this, some ordering has to be imposed on the power products, for example (in the case of the three variables x,y,z) 1 \prec x \prec y \prec z \prec x^2 \prec x y \prec x z \prec y^2 \prec y z \prec z^2 \prec x^3 \prec \dots
With the ordering above, the leading power products of x z^2-3 y z+1,\quad x^2-2 y,\quad x y-5 z
The basis B=\{x z^2-3 y z+1,x^2-2 y,x y-5 z\}
The phenomenon that linear combinations of basis elements may have a leading power product that is not a multiple of any of the leading power products in the basis comes from the fact that, by linear combination, multiples of leading polynomials of the basis polynomials may cancel. In our example, the power product x^2yz^2 appears in (-x y)(x z^2-3 y z+1)=-x^2yz^2+3xy^2z-xy
Definition via the Church-Rosser Property
An alternative definition of Gröbner bases is as follows. A basis is called a Gröbner basis if and only if
the division process with respect to the basis has the Church-Rosser property.
The division process for a polynomial with respect to a basis is a repeated subtraction by multiples of basis elements to the effect of replacing a power product in the polynomial by several power products that are smaller in the chosen ordering. This process is also called reduction. As an example, 3x^3z+x^2z^2 \quad\to\quad x^2 z^2+6xyz \quad\to\quad 9xyz-x \quad\to\quad 45z^2-x
A binary relation like \to is said to have the Church-Rosser property if whenever f and g are connected by a path of arrows and reverse arrows, then f and g have some common successor u with respect to the relation (Figure Figure 3).
For example, consider f=3x^3z+3xyz-x and g=x^2z^2+30z^3 and let \to be the reduction with respect to B=\{x z^2-3 y z+1,x^2-2 y,x y-5 z\}\ . Then \begin{array}{rlll} f = 3x^3z+3xyz-x &\quad\leftarrow\quad 3x^3z+x^2 z^2&\qquad&\text{(by }x\text{ times the first basis element)}\\ &\quad\rightarrow\quad x^2z^2+6xyz&\qquad&\text{(by }3xz\text{ times the second basis element)}\\ &\quad\rightarrow\quad x^2z^2+30z^3=g&\qquad&\text{(by }6z\text{ times the third basis element)} \end{array}
It is not hard to see that this definition is equivalent to the previous (and to several other characterizations not mentioned here). These characterizations have in common that they are not constructive in the sense that they involve a statement about infinitely many objects ("all linear combinations" or "all pairs f and g"). Later, we will give another characterization of Gröbner bases by which it can be checked in finitely many steps whether a given basis is a Gröbner basis. The proof of this criterion is not trivial, and it is the corner stone of the Gröbner bases methodology.
Fundamental Properties of Gröbner Bases
The Elimination Property
For solving a system of multivariate polynomial equations, it is interesting to know linear combinations of the given polynomials that contain as few variables as possible. For example, it is not obvious at first glance how to find the solutions of the system x z^2-3 y z+1=0,\quad x^2-2 y=0,\quad x y-5 z=0
Linear combinations only containing some of the variables are hard to find for arbitrary bases, but easy to find for Gröbner bases: it can be proved that if the ordering of the power products is such that all power products containing unwanted ("bad") variables are greater than any power product only containing wanted ("good") variables, then
the linear combinations containing only good variables of all Gröbner basis elements are precisely the linear combinations of the Gröbner basis elements containing only good variables.
In particular, a linear combination only with good variables exists if and only if already the Gröbner basis contains some polynomial with only good variables.
The prototypical example for an ordering supporting the elimination property is the lexicographic order, which for three variables looks as follows (cf. Figure Figure 4 for two variables): \begin{array}{rl} & 1 \prec x \prec x^2 \prec x^3 \prec x^4 \prec \cdots \\ \prec& y \prec xy \prec x^2y \prec x^3y \prec x^4y \prec \cdots \\ \prec& y^2 \prec xy^2 \prec x^2y^2 \prec x^3y^2 \prec x^4y^2 \prec \cdots\\ & \cdots\cdots\cdots\cdots\\ \prec& z \prec xz \prec x^2z \prec x^3z \prec x^4z \prec \cdots \\ \prec& yz \prec xyz \prec x^2yz \prec x^3yz \prec x^4yz \prec \cdots \\ \prec& y^2z \prec xy^2z \prec x^2y^2z \prec x^3y^2z \prec x^4y^2z \prec \cdots\\ & \cdots\cdots\cdots\cdots \end{array}
Here is a Gröbner basis with respect to that ordering: \left. \begin{array}{ll} &\left. \begin{array}{ll} &\{x^2-5x+6,\qquad\qquad\qquad\bigr\}\quad x \text{ only}\\ &\,\,2 x y-4 y-x+2,\\ &\,\,4 y^2+3 x-10, \end{array}\right\}\quad x,y\text{ only}\\ &\qquad x z^2-2 z^2-4 x+8,\\ &\qquad z^3-4 x z+8 z+2 x-6\}. \end{array}\right\}\text{all variables}
In analogy to systems of linear equations, a Gröbner basis with respect to lexicographic ordering is also called a triangular system. The solutions of such a system can be easily determined. In the example:
- First solve x^2-5x+6=0\ , yielding x=2 and x=3\ .
- Setting x=2\ , the system simplifies to
\{0,0,4 y^2-4,0,z^3-2\}\ :
- Setting x=3\ , the system simplifies to
\{0,2 y-1,4 y^2-1,z^2-4,z^3-4 z\} \ :
- Together, the solutions of the system are precisely the eight points
\begin{array}{rl} &(2,1,\sqrt[3]{2}), \,\, (2,-1,\sqrt[3]{2}), \,\, (2,1,\omega\sqrt[3]{2}), \,\, (2,-1,\omega\sqrt[3]{2}), \\ &(2,1,\omega^2\sqrt[3]{2}), \,\, (2,-1,\omega^2\sqrt[3]{2}), \,\, (3,\tfrac12,-\sqrt2), \,\, (3,\tfrac12,\sqrt2). \end{array}
For Gröbner bases, unlike for arbitrary triangular systems, it is guaranteed that each partial solution can be extended to a full solution of the system. This means that every solution x of the first polynomial can be extended to a solution (x,y) of the polynomials in x and y\ , and each of these solutions can be further extended to a solution (x,y,z) of the polynomials in x,y,z\ , etc.
The Canonicality Property
Call two polynomials f and g congruent modulo a basis B if f can be obtained from g by adding a linear combination of elements from B\ .
In general, given some f\ , g and B\ , it is hard to decide whether or not f and g are congruent modulo B because for deciding this, in general one has to check infinitely many linear combinations. But if B is a Gröbner basis, congruence of two polynomials modulo B can be decided easily, because it can be proved for Gröbner bases B that
f is congruent to g modulo B if and only if R(f,B)=R(g,B)\ .
Here, R(f,B) denotes the remainder of the polynomial f upon multivariate division by the polynomials in B\ , i.e., the congruence of f and g modulo B can be decided by computing remainders. This can also be expressed in the following way: For a Gröbner basis G\ , the function R(f,G) is a canonical simplifier for the congruence modulo G\ .
In general, a function S is called a canonical simplifier for an equivalence relation \sim if S maps all elements of an equivalence class to the same representative of that class, i.e., whenever f\sim g\ , then S(f)=S(g)\ . In our case, the equivalence relation is the congruence modulo a fixed basis B\ , sometimes denoted by the symbol \equiv_B\ .
As an example, let f=2z^2-2y^3+2y-4\ , g=z^5-4z^3-y^2+5 and \begin{array}{rl} B=\{&x^2-5 x+6, \,\, 2 x y-4 y-x+2, \,\, 4 y^2+3 x-10, \\ &x z^2-2 z^2-4 x+8, \,\, z^3-4 x z+8 z+2 x-6\}. \end{array}
As an important special case, if B is a Gröbner basis and f is a polynomial, it can be decided whether or not f is a linear combination of the elements of B\ : This is the case if and only if R(f,B)=0\ . For example, the polynomial z^5-4z^3-2z^2+8 is a linear combination of elements of B\ , because
\begin{array}{rlrlrlrlrlrlrlrlrlrlrl} &z^5-4z^3-2z^2+8\\ \to\quad& 4xz^3-12z^3-2xz^2+4z^2+8&\quad&\text{(by }z^2\text{ times the fifth basis element)}\\ \to\quad& -12z^3-2xz^2+4z^2+16x^2z-32xz-8x^2+24x+8&\quad&\text{(by }4x\text{ times the fifth basis element)}\\ \to\quad& -2xz^2+4z^2+16x^2z-80xz+96z-8x^2+48x-64&\quad&\text{(by }-12\text{ times the fifth basis element)}\\ \to\quad& 16x^2z-80xz+96z-8x^2+40x-48&&\text{(by }-2\text{ times the fourth basis element)}\\ \to\quad& -8x^2+40x-48&&\text{(by }16z\text{ times the first basis element)}\\ \to\quad& 0&&\text{(by }-8\text{ times the first basis element)}. \end{array}
It is important to note that the computation of R(f,B) can be done by an algorithm, and therefore, it can be checked by an algorithm whether or not a given polynomial can be written as a linear combination of the polynomials in a given Gröbner basis.
In commutative algebra, the above result is also expressed in the following terminology: if G is a Gröbner basis and f a polynomial, then R(f,G)=0 if and only if "f belongs to the ideal generated by the elements of G".
The Syzygy Property
A representation of zero as a linear combination of some polynomials is called a syzygy. For example, as 0=(-1)(2y^2+x z-y z+4y-2z)+(-x)(x y+2x-z)+(y+2)(x^2+2y-z),
0=(2y^2+x z-y z+4y-2z)P_1+(x y+2x-z)P_2+(x^2+2y-z)P_3
with unknown polynomials P_1,P_2,P_3\ .
In general, given a tuple of polynomials, it is hard to find its infinitely many syzygies. But if the coefficients of the diophantine equation form a Gröbner basis, then the syzygies can be determined easily: It can be shown that
in this case, the syzygies are precisely the linear combinations of the finitely many principal syzygies obtained from cofactors of all S-polynomials.
The S-polynomial of two polynomials f,g is defined as
\mathrm{SPOL}(f,g):=\mathrm{lcm}(\mathrm{LPP}(f),\mathrm{LPP}(g))\Bigl(\frac{f}{\mathrm{LM}(f)}-\frac{g}{\mathrm{LM}(g)}\Bigr),
where \mathrm{LPP}(p) is the leading power product of the polynomial p and \mathrm{LM}(p) is the leading monomial of p\ , i.e., the leading power product together with its coefficient. For example, for f=xy+2x-z\ , g=x^2+2y-z\ , we have
\mathrm{SPOL}(f,g)=\mathrm{lcm}(xy,x^2)\Bigl(\frac{f}{xy}-\frac{g}{x^2}\Bigr)= xf-yg=2x^2-xz-2y^2+yz.
The notion of S-polynomials plays a key role not only for finding syzygies, but also for the construction of Gröbner bases (see below and Buchberger algorithm).
The S-polynomial of two polynomials f and g is, by definition, a particular linear combination of f and g\ , and so its remainder upon division by a Gröbner basis containing f and g must be zero. For the example f=xy+2x-z\ , g=x^2+2y-z with B=\{2y^2+xz-yz+4y-2z,f,g\} (which is a Gröbner basis), we have \begin{array}{rll} \mathrm{SPOL}(f,g)&=2x^2-xz-2y^2+yz\\ &\to -x z-2 y^2+y z-4 y+2 z&\qquad\text{(by }2\text{ times }g)\\ &\to 0&\qquad\text{(by }-1\text{ times the first basis element)}. \end{array}
A principal syzygy is obtained by taking the difference of such a representation of \mathrm{SPOL}(f,g) and the representation \mathrm{SPOL}(f,g)=xf-yg above. In the example, 0 = (-1)(2y^2+xz-yz+4y-2z)+(-x)(xy+2x-z)+(y+2)(x^2+2y-z)
From the S-polynomial of the first and the second element of B\ , we get the principal syzygy (-\tfrac12x,y-\tfrac12z,\tfrac12z)\ , and from the S-polynomial of the first and the third element of B\ , we get the principal syzygy (-\tfrac12x^2-y+2,2x-\tfrac12xz,y^2+\tfrac12xz-4)\ . According to the syzygy property, since B is a Gröbner basis, all the syzygies for (2y^2+x z-y z+4y-2z,x y+2x-z,x^2+2y-z) are linear combinations of (-1,-x,y+2),\quad(-\tfrac12x^2-y+2,2x-\tfrac12xz,y^2+\tfrac12xz-4), \quad\text{and}\quad(-\tfrac12x,y-\tfrac12z,\tfrac12z).
Construction of Gröbner bases
An arbitrary set of polynomials is in general not a Gröbner basis. However, for every basis B there exists a Gröbner basis G which is equivalent to B in the sense that the linear combinations of elements of B are precisely the same as the linear combinations of elements of G\ . For B and G equivalent in this sense, the congruence of polynomials modulo B agrees with the congruence modulo G\ .
Given an arbitrary basis B\ , an equivalent Gröbner basis G can be found constructively by Buchberger's Algorithm. This algorithm relies on Buchberger's Theorem:
A basis is a Gröbner basis if and only if all S-polynomials of any two basis elements reduce to zero.
As an example, B=\{x y+2 x-z,x^2+2 y-z\} is not a Gröbner basis, because \begin{array}{rl} \mathrm{SPOL}(x y+2 x-z,x^2+2 y-z)&=x(x y+2 x-z) - y(x^2+2 y-z)\\ &=2x^2-2y^2-xz+yz\\ &\to\quad -x z-2 y^2+y z-4 y+2 z \end{array}
Buchberger's algorithm for computing a Gröbner basis G equivalent to a given arbitrary basis B is a completion procedure. Starting with G=B\ , the algorithm searches for polynomials f,g\in G whose S-polynomial \mathrm{SPOL}(f,g) does not reduce to zero. If no such pair exists, then G is a Gröbner basis by the above theorem. Otherwise, some \mathrm{SPOL}(f,g) has a nonzero remainder r after division by G\ . In this case, we replace G by G\cup\{r\} and iterate. It is not trivial to prove that this procedure will always terminate after finitely many such extensions of the basis.
In the example above, G:=B\cup\{-x z-2 y^2+y z-4 y+2 z\} is a Gröbner basis, because for this extended basis all S-polynomials reduce to zero.
More on the construction of Gröbner bases can be found in a separate Scholarpedia article on Buchberger's Algorithm. All examples of Gröbner bases in the present article were constructed by using this algorithm, which is implemented in all computer algebra systems like Maple, Mathematica, etc.
Applications of Gröbner Bases
In the following, we will illustrate some of the many applications of Gröbner bases
- in commutative algebra, the field from which Gröbner bases theory originated,
- in other areas of mathematics,
- in science and engineering.
Some of the applications in commutative algebra are immediate consequences of the various (equivalent) definitions of Gröbner bases and were exemplified already above: solving systems of nonlinear equations, solving the congruence problem modulo polynomial systems, and solving linear diophantine polynomial equations.
Other Applications in Commutative Algebra
Intersection of Ideals
Given two bases B\ , B'\ , we can ask for the set of polynomials that can be written as a linear combination of the polynomials in B and also as a linear combination of the polynomials in B'\ . For example, if B=\{x^2-2y+1\} and B'=\{3x-5,3y+1\}\ , then p=x^3+5x^2y-2xy-10y^2+x+5y is such a polynomial, because there are the two representations p=(x+5y)(x^2-2y+1)
It can be shown that, given two bases B and B'\ , the polynomials in the Gröbner basis of tB\cup(1-t)B' (with respect to an elimination ordering ranking t highest) that do not contain the variable t form a basis whose linear combinations form exactly the polynomials that simultaneously are linear combinations of B and linear combinations of B'\ .
Indeed, the two polynomials 3x^2y+x^2-6y^2+y+1 and 3x^3-5x^2-6xy+3x+10y-5 in our example were obtained as precisely those two t-free elements in the Gröbner basis of \{t(x^2-2y+1),(1-t)(3x-5),(1-t)(3y+1)\} with respect to some ordering that ranks t highest: \{3x^2y+x^2-6y^2+y+1, 3x^3-5x^2-6xy+3x+10y-5, 40t + 9x^2 - 18y - 31\}.
Envelopes
Consider a family of curves defined by equations p(x,y,t)=0 depending on a parameter t\ . Under suitable conditions, an equation for the envelope of this family can be found by eliminating t from the equations p=0 and \frac\partial{\partial t}p=0\ . If p is a polynomial, this can be done with Gröbner bases.
For example, the polynomial p=(x-t)^2+y^2-t describes the circles with center (t,0) and radius \sqrt t (Figure Figure 5, red). The Gröbner basis of \{(x-t)^2+y^2-t,-2(x-t)-1\} with respect to the lexicographic order with t>y>x is \{4 y^2-4 x-1,2 t-2 x-1\},
Hilbert Dimension
A collection of multivariate polynomials defines the geometric object in the multidimensional space consisting of those points where all the polynomials in the collection vanish simultaneously. For example, the equation x+y+z-1 defines a plane in \mathbb{R}^3\ , the equation x^2+y^2-1 defines a cylinder with radius 1 parallel to the z-axis, and both equations together define the red curve shown in Figure Figure 6.
One of the possibilities to define the dimension of such a geometric object is via variables that are algebraically independent modulo the defining equations: the dimension is the minimal number d of variables such that no (nonzero) linear combination of the defining polynomials involves only d variables. Except in some degenerate cases, this definition matches the geometric intuition (points have dimension 0, curves have dimension 1, surfaces have dimension 2, etc.)
The dimension of a geometric object can be read off from the leading power products in the Gröbner basis of the defining polynomials: it is the maximum number of variables for which there exists no power product in these variables in the Gröbner basis with respect to a degree order. In the example of the cylinder defined by x^2+y^2-1\ , the dimension is 2\ , because there is no leading power product in y and z alone (so the dimension is at least 2) and there is a leading power product in x\ , y\ , z\ , (so the dimension is less than 3). For the intersection curve of the cylinder with the plane defined by x+y+z-1\ , we have the Gröbner basis \{\,x+y+z-1,2 y^2+2 y z-2 y+z^2-2 z\,\}.
Applications in Other Areas of Mathematics
Geometric Theorem Proving
Gröbner bases can be used for proving theorems in elementary geometry that can be rephrased as quantified formulas involving polynomial equations and inequations. As an example, consider the theorem of Apollonius: If ABC is a right triangle with its right angle at A\ , then the circle through the midpoints of all three sides also contains the foot point H of the altitude drawn from A to the side BC (Figure Figure 7).
(It is also true, and even simpler to prove, that A always lies on the circle.)
In order to prove this theorem, we choose a cartesian coordinate system where A is the origin and B and C are on the axes, so that A=(0,0)\ , B=(x,0) and C=(0,y) for some x,y\ . In terms of these coordinates, we clearly have U=(x/2,0)\ , V=(x/2,y/2)\ , W=(0,y/2) as the midpoints of the three sides. The other relevant points can be described implicitly by equations that must be satisfied by their coordinates. The point H=(h_1,h_2) is determined by the equations \begin{array}{ll} h_1x-h_2y=0&\qquad(AH\text{ is orthogonal to }BC)\\ h_1y+h_2x-xy=0&\qquad(B,H,C\text{ are on one line}). \end{array}
Now, this is equivalent to saying that there do not exist x,y,h_1,h_2,m_1,m_2 and z such that the equations above and 1 - z ((m_1-x/2)^2+m_2^2-( (m_1-h_1)^2+(m_2-h_2)^2 )) = 0
This question about the existence of common solutions of polynomials can now be decided by the Gröbner basis method: A set of polynomials has no common solutions if and only if its Gröbner basis contains 1\ .
In many cases, however, the corresponding Gröbner basis delivers possible solutions which can be considered as "degenerate" cases (in which the validity of the theorem cannot be guaranteed) whereas, for all other cases the theorem is guaranteed to be true.
In our example, the Gröbner basis of \begin{array}{rl} \{&h_1x-h_2y, h_1y+h_2x-xy,\\ &(m_1-x/2)^2+m_2^2 - (m_1-x/2)^2 -(m_2-y/2)^2,\\ &(m_1-x/2)^2+m_2^2-m_1^2-(m_2-y/2)^2,\\ &((m_1-x/2)^2+m_2^2- (m_1-h_1)^2-(m_2-h_1)^2)z-1\} \end{array}
Graph Coloring
A k-coloring of a graph G=(V,E) is an assignment of colors taken from k colors to the vertices of the graph in such a way that any two vertices v_1,v_2\in V connected by an edge have a different color. Figure Figure 8 shows an example for a 3-coloring of a graph.
The problem of finding all k-colorings for a given graph can be reduced to the solution of a system of polynomial equations, and so it can be done by means of Gröbner bases. We use the kth roots of unity as colors, and variables to represent vertices. The condition that a vertex should have a color is then encoded by the polynomials x^k-1\ . The polynomial \frac{x^k-y^k}{x-y}=x^{k-1}+x^{k-2}y+x^{k-3}y^2+\cdots+x y^{k-2}+y^{k-1}
For the example graph in Figure Figure 8, the equation system for finding all 3-colorings is \begin{array}{rllll} \{&x_1^3-1=0,x_2^3-1=0,x_3^3-1=0,x_4^3-1=0,&\quad&\text{(one out of three color per vertex)}\\ &x_1^2+x_2 x_1+x_2^2=0,&&\text{(different colors for vertex 1 and 2)}\\ &x_1^2+x_3 x_1+x_3^2=0,&&\text{(different colors for vertex 1 and 3)}\\ &x_2^2+x_3 x_2+x_3^2=0,&&\text{(different colors for vertex 2 and 3)}\\ &x_2^2+x_4 x_2+x_4^2=0,&&\text{(different colors for vertex 2 and 4)}\\ &x_3^2+x_4 x_3+x_4^2=0\}&&\text{(different colors for vertex 3 and 4)}. \end{array}
Summation and Integration
Gröbner bases can be used for evaluating integrals of special functions. Many analytic functions can be defined by some finite set of initial values and a finite set of differential equations they satisfy. For example, the function f(x,t):=\exp(-t^2 x)
The basic idea is to construct from the given differential equations for f(x,t) by suitable linear combinations and/or applications of partial derivatives a new differential equation for f(x,t) from which a differential equation for F(x) can be obtained. The application of a derivative with respect to a variable x may be rephrased as multiplication with an additional variable D_x\ . In this point of view, differential equations in x and t are polynomials in x,t,D_x,D_t which can be added and multiplied. It must be noted however that multiplication in this setting is no longer commutative: The product rule \frac{d}{dx} x u(x) = u(x) + x \frac{d}{dx} u(x)
Gröbner bases can be generalized to such domains with noncommutative multiplication [ 13, 27, 31, 34, 41 ], and this can be used for solving the integration problem. In order to find a differential equation in x satisfied by the integral F(x)\ , compute a non-commutative Gröbner basis with respect to an ordering that ranks t highest. In the example, this gives \{4x^2 D_x+2x+D_t^2,t D_t-2xD_x,2tx+D_t,t^2+D_x\}.
Linear Integer Optimization
Gröbner bases can be used to solve certain integer optimization problems. For example, consider the question of finding the minimum number of coins (pennies, nickels, dimes, and quarters) that is needed to pay \$1.17.
The key idea is to encode the number of coins as exponents of variables. For example, using variables P,N,D,Q for the various kinds of coins, the power product P^7 N^2 D^5 Q^2 represents seven pennies and two nickles and five dimes and two quarters. The total number of coins is then given by the total degree of the term, 7+2+5+2=16 in the example.
In order to minimize the number of coins, compute a Gröbner basis with respect to a degree ordering of \{P^5-N,P^{10}-D,P^{25}-Q\}.
A general description of this technique applicable to arbitrary linear optimization problems can be found in Section 2.8 of [ 2 ].
Applications in Science and Engineering
Coding Theory
One of the aims of coding theory is to conceive schemes for transmitting information through a communication channel in such a way that errors that may possibly occur during the transmission can be detected and corrected by the receiver. According to a classical coding scheme, instead of transmitting data items a_0,a_1,\dots,a_n directly, we take the polynomial p(x)=a_0+a_1x+\cdots+a_nx^n and transmit the values p(0),p(1),p(2),\dots,p(n),p(n+1),\dots,p(n+5)\ , say. If the transmission was correct, then the coefficients of p can be recovered from these values by interpolation. If not, i.e., if some of the values p(i) were transmitted incorrectly, then we will typically find that there does not exist a polynomial of degree n matching all the transmitted values.
In this case, Gröbner bases can be used to determine a plausible candidate for the correct data vector from an erroneous vector of transmitted data. Continuing the example situation sketched before, assume we have received the data values p_0,p_1,\dots,p_{n+5}\ . Our goal is to construct a polynomial p(x)=a_0+a_1x+\cdots+a_nx^n of degree at most n such that p(i)=p_i for many points i\ . At these points, we will have the equations a_0+a_1i+a_2i^2+\cdots+a_ni^n=p_i.
This solves the error correction problem in principle. However, the method given here is a somewhat oversimplified version of what is actually applied in practice. In order to obtain efficient error correcting algorithms, refined techniques have to be applied which are beyond the scope of this text. (In particular, the appropriate coefficient fields in the context of coding are finite and specific algorithmic techniques available in such fields can be applied. See [ 42 ] for details.)
Robotics
The "general inverse kinematics problem" in robotics asks for determining how the various joints in a robot have to be turned in order to reach a certain position. For example, given a point in 3D space and an orientation, we may ask for the appropriate angles of the joints in order to reach the point with the requested orientation. In general, these problems lead to a system of nonlinear equations, which in principle can be solved by Gröbner bases.
As a simple example, consider the "robot" depicted in Figure Figure 9, consisting of three straight segments of length 1 connected via joints that can independently rotate around angles \phi_1\ , \phi_2\ , and \phi_3\ , respectively. Choosing the foot of the robot as the origin of a coordinate system, we want to access the point (2,0) (cross in Figure Figure 9) from northwest (arrow in Figure Figure 9). By elementary trigonometry, it can be found that the position of the robot's gripper can be expressed in terms of \phi_1,\phi_2,\phi_3 as \binom{-\sin(\phi_1)-\sin(\phi_1+\phi_2)-\sin(\phi_1+\phi_2+\phi_3)} {\cos(\phi_1)+\cos(\phi_1+\phi_2)+\cos(\phi_1+\phi_2+\phi_3)} = \binom 20.
In order to solve these equations via Gröbner bases, it is necessary to transform them into polynomial equations. One way of doing this is to introduce auxiliary variables s_1,s_2,s_3,c_1,c_2,c_3 for \sin(\phi_1),\sin(\phi_2),\sin(\phi_3),\cos(\phi_1),\cos(\phi_2),\cos(\phi_3)\ , respectively, and solve the equations for the auxiliary variables first rather than directly for \phi_1,\phi_2,\phi_3\ . The requirement for (s_i,c_i) to be on the unit circle is accommodated by additional equations s_i^2+c_i^2-1=0 for i=1,2,3\ .
In our example, using trigonometric addition theorems, the requirement on the target position translates into the polynomials \begin{array}{rl} p_1&={-}c_2 s_1-c_2 c_3 s_1-c_1 s_2-c_1 c_3 s_2-c_1 c_2 s_3+s_2 s_3 s_1-s_1-2,\\ p_2&={-}c_1 s_2 s_3-c_3 s_1 s_2-c_2 s_1 s_3+c_2 c_1+c_2 c_3 c_1+c_1-s_1 s_2. \end{array}
It turns out that the equation system p_1=p_2=p_3=p_4=p_5=p_6=p_7=0
Software Engineering
Gröbner bases can be used for finding invariant properties of loops, which are needed in automated program verification. As an example, consider the following program for computing the product of two integers a,b\ :
(x, y, z) := (a, b, 0); while not (y = 0) do if y mod 2 = 0 then (x, y, z) := (2*x, y/2, z) else (x, y, z) := (2*x, (y-1)/2, x+z) end if end while return z
Writing X,Y,Z for the respective values of the program variables x,y,z at the beginning of the loop, a polynomial p is a loop invariant if p(X,Y,Z,x,y,z)=0
We can find all the polynomials which remain fixed under an arbitrary number n of applications of f_1 by eliminating the auxiliary variables u and v from \{F_1(x-X),F_1(y-Y),F_1(z-Z),uv-1\} =\{u x - X, v y - Y, z - Z, u v - 1\}.
Next, we search among these linear combinations for polynomials that are also fixed under f_2^n by eliminating u and v from \{F_2(x - X - z + Z), F_2(X y - X Y + z + y z - Z - y Z), uv-1\}.
Further applications of F_1 or F_2 will leave this basis fixed, and therefore x y - X Y + z - Z = 0
Taking into account the initialization X=a,Y=b,Z=0\ , it follows that x y - a b + z = 0
See [ 28, 40, 44 ] for further information on loop invariant generation using Gröbner bases.
Petroleum Industry
Gröbner bases can be used to analyze and optimize the production of oil in offshore platforms. If an oil field is accessed through several points (Figure Figure 11), then the amount of oil or gas which can be maximally extracted at one point depends on how much oil is extracted at the other points. The oil compartments in a field are not independent from each other but there are geological interactions between them, so that it is possible that reducing the extraction rate at one access point may increase the total production of all points.
These interactions are hard to model as they depend on parameters which are difficult to measure. A pragmatic approach is therefore to directly establish the relations between extraction parameters at the access points and the resulting production gains.
In the oversimplified situation given in Figure Figure 11, we have three access points. Denote by e_1,e_2,e_3 the extraction parameters and let p_1,p_2,p_3 denote the amount of oil obtained at the respective points. We are interested in how p_1,p_2,p_3 are related to e_1,e_2,e_3\ . If we assume that these relations can be described by a system of polynomials f_1,\dots,f_m such that f_i(e_1,e_2,e_3,p_1,p_2,p_3)=0\quad(i=1,\dots,m)
From this Gröbner basis, it is then possible to determine how e_1,e_2,e_3 have to be chosen such that that total production gain p_1+p_2+p_3 is maximal or some other optimality criterion is met.
Other Applications
The Gröbner bases methodology has been applied successfully in literally dozens of other areas [ 12, 23, 26, 37, 38, 41, 43, 45, 46 ]. In all these applications, the general principle is to reformulate a particular problem as a question about sets of multivariate polynomials, then to do one or more Gröbner bases computations, so that finally the key properties of Gröbner bases (the elimination property, the canonicality property, or the syzygy property) can be used to answer the question.
We encourage experts in the various application fields to complement this article by additional subsections describing these applications.
References
- Gröbner Bases Bibliography. Compiled by B. Buchberger and A. Zapletal in the course of the Special Semester on Gröbner Bases at RICAM (Radon Institute for Computational and Applied Mathematics) and RISC (Research Institute for Symbolic Computation), Linz, Austria, 2006: http://www.ricam.oeaw.ac.at/Groebner-Bases-Bibliography/.
- W. Adams and P. Loustaunau. An Introduction to Gröbner Bases. AMS, Providence, 1994.
- T. Becker, V. Weispfenning, and H. Kredel. Gröbner Bases: A Computational Approach to Commutative Algebra. Springer New York, 1993.
- B. Buchberger. Introduction to Gröbner Bases. In [11], pages 3--31.
- B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal). PhD thesis, University of Innsbruck, 1965. English translation in Journal of Symbolic Computation, 41(3--4):475--511, 2006.
- B. Buchberger. Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems (An algorithmic criterion for the solvability of algebraic systems of equations). Aequationes Mathematicae, 4(3):374--383, 1970. English translation in [11], pages 535--545.
- B. Buchberger. Gröbner-bases: An algorithmic method in polynomial ideal theory.In Multidimensional Systems Theory -- Progress, Directions and Open Problems in Multidimensional Systems, pages 184--232. Reidel Publishing Company, Dodrecht--Boston--Lancaster, 1985.
- B. Buchberger. Gröbner bases and systems theory. Multidimensional Systems and Signal Processing, 12(3--4):223--251, 2001.
- B. Buchberger and R. Loos. Algebraic simplification. In Computer Algebra: Symbolic and Algebraic Computation, pages 11--43. Springer, Wien, 1982.
- B. Buchberger and H. M. Möller. The construction of multivariate polynomials with preassigned zeros. In Proceedings of EUROCAM'82, volume 144 of LNCS, pages 24--31. Springer, Berlin/Heidelberg, 1982.
- B. Buchberger and F. Winkler, editors. Gröbner Bases and Applications, London Mathematical Society Lectures Notes Series 251. Cambridge University Press, 1998.
- J. Bueso, J. G. Torrecillas, and A. Verschoren. Algorithmic Methods in Non-Commutative Algebra: Applications to Quantum Groups Kluwer, Dordrecht, 2003.
- F. Chyzak and B. Salvy. Non-commutative elimination in Ore algebras proves multivariate identities. Journal of Symbolic Computation, 26(5--6):187--227, 1998.
- A. Cohen. Gröbner bases, an introduction. In Some Tapas of Computer Algebra, volume 4 of Algorithms and Computation in Mathematics, pages 1--33. Springer, Berlin, 1999.
- D. Cox. Gröbner bases: A sampler of recent developments. In Proceedings of ISSAC'07, pages 387--388, ACM, New York, 2007.
- D. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, New York, 1992.
- D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry. Springer, New York, 1998.
- A. Dickenstein and I.Z. Emiris, editors. Solving Polynomial Equations. Algorithms and Computation in Mathematics. Springer, Berlin/Heidelberg, 2005.
- D. Eisenbud. Gröbner Bases. In Commutative Algebra With a View Toward Algebraic Geometry, chapter 15, pages 321--384. Springer, New York, 1999.
- R. Fröberg. An Introduction to Gröbner Bases. John Wiley & Sons, Chichester, 1998.
- K. Geddes, S. Czapor, and G. Labahn. Gröbner bases for polynomial ideals. In Algorithms for Computer Algebra, chapter 10, pages 429--472. Kluwer, Dordrecht, 1992.
- J. von zur Gathen and J. Gerhard. Gröbner bases. In Modern Computer Algebra, chapter 21, pages 565--596. Cambridge University Press, 1999.
- D. J. Green. Gröbner Bases and the Computation of Group Cohomology, volume 1828 of Lecture Notes in Mathematics. Springer, Berlin/Heidelberg, 2003.
- G. Greuel and G. Pfister. A Singular Introduction to Commutative Algebra. Springer, Berlin/Heidelberg, 2002.
- D. Heldt, M. Kreuzer, S. Pokutta, and H. Poulisse. Approximate computation of zero-dimensional polynomial ideals. Journal of Symbolic Computation, 44(11):1566--1591, 2009.
- M. Klin, G.A. Jones, A. Jurisic, M. Muzychuk, and I. Ponomarenko, editors. Algorithmic Algebraic Combinatorics and Gröbner Bases. Springer, Berlin/Heidelberg, 2009.
- C. Koutschan. Advanced Applications of the Holonomic Systems Approach. PhD thesis, RISC-Linz, Johannes Kepler Universität Linz, 2009.
- L. Kovacs and T. Jebelean. An algorithm for automated generation of invariants for loops with conditionals. In Proceedings of SYNASC'05, pages 245--249. IEEE Computer Society Press, 2005.
- M. Kreuzer and L. Robbiano. Computational Commutative Algebra 1. Springer, Berlin/Heidelberg, 2000.
- M. Kreuzer and L. Robbiano. Computational Commutative Algebra 2. Springer, Berlin/Heidelberg, 2005.
- H. Li. Noncommutative Gröbner Bases and Filtered-Graded Transfer, volume 1795 of Lecture Notes in Mathematics. Springer, Berlin/Heidelberg, 2002.
- M. Maruyama. Gröbner Basis and its Applications. Kyoritsu Shuppan, Tokyo, 2002. (Japanese.)
- B. Mishra. Computational ideal theory. In Algorithmic Algebra, Texts and Monographs in Computer Science, chapter 3, pages 71--132. Springer, New York, 1993.
- F. Mora. An introduction to commutative and non-commutative Gröbner bases. Theoretical Computer Science, 134(1):131--173, 1994.
- F. Mora. Solving Polynomial Equation Systems II: Macaulay's Paradigm and Gröbner Technology. Cambridge University Press, New York, 2005.
- M. Noro and K. Yokoyama. Computational Fundamentals of Gröbner bases. University of Tokyo Press, Tokyo, 2003. (Japanese.)
- L. Pachter and B. Sturmfels. Algebraic Statistics for Computational Biology. Cambridge University Press, Cambridge, 2005.
- H. Park and G. Regensburger, editors. Gröbner Bases in Control Theory and Signal Processing. Radon Series on Computational and Applied Mathematics. De Gruyter, Berlin, 2007.
- V. V. Prasolov. Gröbner bases. In Polynomials, Algorithms and Computation in Mathematics, chapter 6.2. Springer, Berlin/Heidelberg, 2004. English translation of Mnogotchleny, Moscow Center for Continuous Math. Education, 2001.
- E. Rodriguez-Carbonell and D. Kapur. Generating all polynomial invariants in simple loops. Journal of Symbolic Computation, 42(4):443--476, 2007.
- M. Rosenkranz and D. Wang, editors. Gröbner Bases in Symbolic Analysis. Radon Series on Computational and Applied Mathematics. De Gruyter, Berlin, 2007.
- S. Sakata. Gröbner bases in coding theory. In [11], pages 205--220.
- M. Sala, T. Mora, L. Perret, S. Sakata, and C. Traverso, editors. Gröbner Bases, Coding, and Cryptography. Springer, Berlin/Heidelberg, 2009.
- S. Sankaranarayanan, H. B. Sipma, and Z. Manna. Non-linear Loop Invariant Generation using Gröbner Bases. In Proceedings of POPL'04, pages 318--329. ACM, New York, 2004.
- B. Sturmfels. Algorithms for Invariant Theory. Texts and Monographs in Symbolic Computation. Springer, Wien, 1993.
- W. V. Vasconcelos. Computational Methods in Commutative Algebra and Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, Berlin/Heidelberg, 1998.
- D. Wang. Elimination Methods. Texts and Monographs in Symbolic Computation. Springer, Wien, 2001.
- F. Winkler. The method of Gröbner bases. In Polynomial Algorithms in Computer Algebra, Texts and Monographs in Symbolic Computation, chapter 8. Springer, Wien, 1996.
See also
(pending)