Keith Geddes Website > Research > Online Papers

Groebner Bases for Polynomial Systems: A Brief Introduction

K.O. Geddes
Symbolic Computation Group
D.R. Cheriton School of Computer Science
University of Waterloo
Waterloo ON N2L 3G1
CANADA
http://www.uwaterloo.ca/~kogeddes

Abstract

The concept of Groebner bases is introduced using some motivating examples. Two types of applications are considered: (1) canonical forms for polynomials with side relations; and (2) solutions of systems of polynomial equations.

Canonical Forms for Polynomials with Side Relations

Univariate Side Relations

Suppose that we wish to simplify an expression which contains various powers of the symbol , under the assumption that represents the complex number . For example,

> restart;

> e := 4*i^5 - 7*i^4 + i^3 + 3*i^2 - 5*i + 11;

As a naive approach, we could think of applying transformation rules such as:

i^2 --> -1

i^3 --> -i

i^4 --> 1

i^5 --> i

etc.

For the above example, the expression simplifies as follows.

> subs({i^2=-1, i^3=-i, i^4=1, i^5=i}, e);

An algorithmic approach to the problem is as follows.

We wish to simplify the expression with respect to the following side relation which the variable must satisfy: .

The given expression lies in a polynomial domain [] over some coefficient domain but we really want to represent the expression in a canonical form as an element of the quotient ring -- i.e. as a polynomial modulo the ideal generated by .

Question: Is it possible to specify a canonical form for elements of the quotient ring ?

Yes it is possible. Any element of the quotient ring can be represented uniquely in terms of the basis -- i.e. as a polynomial of degree 1 in the variable .

Algorithm to Transform an Expression into Canonical Form

For the quotient ring discussed above, transformation to canonical form can be obtained by applying Euclidean division with remainder:

--> .

Example 1

> e;

> rem(e, i^2+1, i);

Of course, Maple will automatically simplify expressions involving which has the alias in Maple.

> subs(i=I, e);

Example 2

The above discussion applies to any univariate side relation.

As a second example, consider an expression in the symbol which represents .

In this case, the side relation satisfied by the symbol is: .

> f := r^6 - 5/7*r^5 + 23*r^4 + 1/2*r^3 - 35/11*r^2 + r - 1/2;

> rem(f, r^2-2, r);

Again, Maple will automatically simplify expressions involving .

> subs(r=sqrt(2), f);

Multivariate Side Relations

Suppose, for example, that we have a trigonometric expression involving and and we wish to simplify the expression with respect to the following side relation: .

We can choose to think of this as a polynomial side relation and to represent and in the expression by the symbols and , respectively. We are then faced with the problem of simplifying a multivariate polynomial with respect to a multivariate side relation.

Expressing this in the notation of algebra, the original expression lies in a bivariate polynomial domain [] and we wish to express it (in a canonical form, if possible) as an element of the quotient ring .

Question: Is it possible to specify a canonical form for elements of the quotient ring ?

The answer is not obvious.

For example, the following expressions are mathematically equivalent:

> e1 := sin(x)^2 * cos(x)^2;

> e2 := expand( subs(cos(x)^2 = 1-sin(x)^2, e1) );

> e3 := expand( subs(sin(x)^2 = 1-cos(x)^2, e1) );

Which form is "best"? "simplest"? It depends on your point of view.

The more general Question is: Given a multivariate polynomial domain [] and one or more side relations ( ), is it possible to specify a canonical form for elements of the quotient ring [] / where is the ideal generated by the polynomials ?

Until the 1960s it was not known whether this question could be answered in the affirmative. It turns out that the answer is Yes, via the theory of Groebner bases.

Maple syntax for simplification w.r.t. side relations

Before proceeding further, consider a Maple example. For the simplification of expressions modulo side relations in Maple, see the help page ?simplify[siderels] .

The syntax of the command is where is a set of one or more side relations. When the simplify command is invoked in this form, Maple applies the theory of Groebner bases. Specifically, a Groebner basis for is computed and then is reduced modulo this Groebner basis by transformations to be described in a subsequent section.

Note: This yields a canonical form. But which canonical form? It depends on the choice of ordering for the variables. The user can control the ordering by using the 3-argument syntax where is a list of variables in the desired order.

Example 3

> siderels := {sin(x)^2 + cos(x)^2 = 1};

${sin(x)^2+cos(x)^2 = 1}$

> e := sin(x)^3 - 11*sin(x)^2*cos(x) + 3*cos(x)^3 - sin(x)*cos(x) + 2;

The following command indicates that we wish to "favour" transforming cos(x) into sin(x) as much as possible.

> simplify(e, siderels, [cos(x),sin(x)]);

The following command indicates that we wish to "favour" transforming sin(x) into cos(x) as much as possible.

> simplify(e, siderels, [sin(x),cos(x)]);

Try simplifying the following expression .

> f := sin(x)^2 * cos(x)^2;

> simplify(f, siderels, [cos(x),sin(x)]);

> simplify(f, siderels, [sin(x),cos(x)]);

The expression is equivalent to zero, and therefore its canonical form must be 0 (regardless of ordering).

> g := f - sin(x)^2 + sin(x)^4;

> simplify(g, siderels);

Groebner Basis Preliminaries

Consider the polynomial domain Q[] in three variables over the field Q of rational numbers. Suppose that the following three side relations are specified.

> siderels := {x^3*y*z = x*z^2, x*y^2*z = x*y*z, x^2*y^2 = z^2};

${x^3*y*z = x*z^2, x*y^2*z = x*y*z, x^2*y^2 = z^2}$

Consider the following polynomial expression.

> p := x*z^4 - x*y*z^3;

Problem: Express in a canonical form with respect to .

This can be accomplished in Maple as follows.

> simplify(p, siderels);

Offhand, you would not be able to recognize that is equivalent to zero. How would you proceed to try to "reduce" with respect to the given side relations?

The mathematical framework is as follows. In the original polynomial domain Q[] we can specify a "vector space" basis for this domain. There are various orderings of the monomials which can be chosen. For the moment, let us choose a basis corresponding to the total degree ordering with monomials of the same total degree ordered by a particular lexicographical ordering (called inverse lexicographical order), as follows.

> tdegBasis := [1,z,y,x,z^2,y*z,x*z,y^2,x*y,x^2,z^3,y*z^2,x*z^2,y^2*z,x*y*z,x^2*z,y^3,x*y^2,x^2*y,x^3,z^4,` . . . `];

Given the polynomial expression in the domain Q[] , we are required to simplify with respect to ; in other words, we want to express in a canonical form as an element of the quotient ring Q[] / where is the ideal generated by the side relations. For as specified above, the corresponding ideal is

= < > .

Objective: Define a basis for the quotient ring Q[] / and specify an algorithm to express any particular polynomial in terms of that basis.

The basis specified above for the domain Q[] clearly is not a basis for the quotient ring. The monomials are not all independent in the quotient ring; e.g., .

Question: Which monomials should be deleted from in order to obtain a basis for the quotient ring?

To answer this question, we proceed as follows.

Step 1: Compute a Groebner basis for the ideal .

Step 2: Examine each monomial with respect to the Groebner basis for to determine whether, as an element of Q[] / , it can be reduced to a lower-order monomial (with respect to the specified ordering of monomials). (E.g., reduces to .)

Note: The above concept is vague at this moment, but we will make it more precise. Also, it should be noted that what we will do, in practice, is to apply the reductions indicated in Step 2 on each particular term in the polynomial that we wish to simplify.

Some Remarks about Groebner Bases

The terminology "basis" used in the context of a Groebner basis is not the concept of a "vector space" or "polynomial" basis. Specifically, the elements in the basis will not be linearly independent in the sense of a vector space basis. Rather, it is the concept of an "ideal basis" which means a "set of generators for the ideal". Indeed, for the ideal

= < >

the corresponding Groebner basis will have more elements (i.e. more generators) than the three specified in the original definition of . Using Maple, we can determine a Groebner basis for the ideal as seen in the following Example.

(Note that the ideal is represented by specifying the generators in a Maple list. The "angle bracket" notation used above is a common mathematical notation for ideals, but angle brackets in Maple are used for a different purpose.)

Example 4

> Id := [x^3*y*z - x*z^2, x*y^2*z - x*y*z, x^2*y^2 - z^2];

> nops(Id);

> TermOrder := tdeg(x,y,z);

> Gb := Groebner:-Basis(Id, TermOrder);

> nops(Gb);

Note that the original specification of the ideal has 3 generators whereas the Groebner basis has 8 generators.

However, the same ideal is being specified with different sets of generators: .

(See the definition of a Groebner basis in the next section.)

For the polynomial specified above, our task now is to reduce with respect to the Groebner basis . The function NormalForm in the Groebner package performs "reduction to normal form" of a given polynomial with respect to a particular specification of an ideal. (See the next section for details of the reduction process.)

> p;

> Groebner:-NormalForm(p, Gb, TermOrder);

If the original list of generators was used to specify the ideal then the reduction process applied by the NormalForm function would fail to recognize that reduces to zero modulo the ideal.

> Groebner:-NormalForm(p, Id, TermOrder);

Definition of a Groebner Basis

Definition 1

The S-polynomial of two polynomials is defined by

where denotes the "head term" of a polynomial , meaning the leading monomial (with respect to a specified term ordering).

An important property of is that the head term of will be eliminated in the case where | , in which case we have

Example 5

> p;

Let's choose one particular element from the Groebner basis .

> G1 := x*y*z^2 - x*z^2;

With and we see that | . Hence the -polynomial is as follows.

> headp := -x*y*z^3;

> headG1 := x*y*z^2;

> S := (headG1*p - headp*G1) / gcd(headp,headG1):

> S := normal(S,expanded);

or equivalently,

> S := p - (headp/headG1)*G1;

> S := expand(S);

The point to be noted in the above example is that the computation of the -polynomial results in a reduction of in the following sense:

The computed polynomial is equivalent to in the quotient ring Q[] / (equivalently, Q[] / ) because all we did was to subtract from a multiple of , which is an element of the ideal (i.e. ). Moreover, the head term is smaller (in the specified term ordering) than the original head term .

It is precisely this type of reduction of the terms in the polynomial that we wish to perform, and we wish to be guaranteed that will get reduced to a canonical form. The desired guarantee comes from the definition of a Groebner basis for the ideal.

Definition 2

A polynomial is F-reduced modulo the ideal basis if no head term divides , for .

Method of F-reduction: If | then replace by the -polynomial . I.e., perform the reduction --> . Continue performing reductions until Definition 2 is satisfied.

It is clear that if a polynomial -reduces to zero then is in . We would like the converse implication to hold. That is, we would have an effective method to answer the ideal membership question if, for an ideal basis , we would have the property:

is in if and only if -reduces to zero.

This property is precisely what a Groebner basis gives us.

Definition 3

A set of polynomials in a polynomial domain [] is a Groebner basis (with respect to a specified term ordering) if

is in if and only if -reduces to 0 .

An equivalent definition is provided by the following theorem, which tells us that for a Groebner basis the process of -reduction produces a unique canonical form.

Theorem 1

A set of polynomials in a polynomial domain [] is a Groebner basis if and only if the following property holds:

-reduces to and -reduces to implies .

Concluding Remarks on Computing Groebner Bases

For a detailed development of Buchberger's algorithm to compute a Groebner basis, see [1]. The general idea is that, given an ideal basis , we must compute another ideal basis such that and is a Groebner basis. The algorithm consists of a sequence of operations based on computing -polynomials and applying the process of -reduction.

The known algorithms for computing a Groebner basis have time complexity which is exponential in the number of variables. Therefore, if there are too many variables the computation becomes "hopeless". However, for many reasonably-sized problems, the method has proved to be very useful.

As mentioned above, we can answer the general ideal membership question once we have computed a Groebner basis for the ideal. Specifically, to determine whether a given polynomial is a member of we simply apply -reductions to determine whether -reduces to zero. In Maple's Groebner package, the NormalForm function can be used for this purpose.

Example 6

Consider the polynomial domain Q[] and the ideal specified above.

> Id;

The Groebner basis for was determined to be as follows.

> Gb;

Let be the polynomial defined above. Is in ?

> p;

> Groebner:-NormalForm(p, Gb, TermOrder);

Since -reduces to zero we conclude that is in .

Create two different polynomials and which are known to be equivalent modulo .

> q := 3*x^5*y*z^2 - 1/2*x^4*y^3 + x*y*z;

> p1 := expand(q + (x^2 + y^2 + z^2)*p);

> p2 := expand(q + (x^3*y^2 - 3/4*x^2*z + 1/4*x*z^3 - 4/5)*p);

Applying NormalForm to each of and should yield the same canonical form.

> Groebner:-NormalForm(p1, Gb, TermOrder);

> Groebner:-NormalForm(p2, Gb, TermOrder);

This must also be the canonical form of the polynomial .

> Groebner:-NormalForm(q, Gb, TermOrder);

Solving Systems of Polynomial Equations

In this section we note, by looking at some examples, that a Groebner basis can be a very powerful tool for the problem of computing solutions to systems of polynomial equations. Specifically, the term ordering which is most desirable for this application is pure lexicographical ordering . For example, in the polynomial domain Q[] the pure lexicographical ordering implies

< < < < < < < < < < < < < < < .

The Problem

Given a system of polynomial equations

we wish to find values of ( ) which simultaneously satisfy the polynomial equations.

Solution Technique

Consider , the ideal generated by the given polynomials , and compute its Groebner basis using pure lexicographical ordering. Then the set of common zeros of is identical to the set of common zeros of and, moreover, we can obtain much more information about the common zeros from than from the original polynomials .

Example 7

Suppose that we wish to solve the three polynomial equations: defined as follows.

> restart;

> q1 := x^2*y + 4*y^2 - 17:

> q2 := 2*x*y - 3*y^3 + 8:

> q3 := x*y^2 - 5*x*y + 1:

> F := [q1, q2, q3];

> G := Groebner:-Basis(F, plex(x,y,z));

The system of equations specified by the Groebner basis is 1 = 0 which has no solution. Therefore the original set of polynomial equations has no solution.

Example 8

Suppose that we wish to solve the following system of three polynomials.

> p1 := x^2 + y*z - 2:

> p2 := y^2 + x*z - 3:

> p3 := x*y + z^2 - 5:

> F := [p1, p2, p3];

> G := Groebner:-Basis(F, plex(x,y,z));

From the original system of polynomials it is difficult to determine information about the solutions. However, the system of polynomial equations specified by the Groebner basis has a very interesting structure: the system has been triangularized ! Namely, in one equation the variable is isolated as a function of ; in another equation the variable is isolated as a function of ; and the remaining equation involves a univariate polynomial in the variable . Therefore, the solutions can be described as follows.

> xpoly := select(has, G, x)[];

> ypoly := select(has, G, y)[];

> zpoly := remove(has, G, {x,y})[];

We can solve explicitly for and as a function of .

> xval := solve(xpoly, x);

> yval := solve(ypoly, y);

For each of the 8 roots of the univariate polynomial we have a triple ( ) which is a solution of the original system of polynomial equations.

The symbolic representation of the roots of obtained via is expressed using the construct (by default) and is not very informative. One can note that is actually just a quartic polynomial in and therefore an explicit symbolic representation of its roots in terms of radicals can be obtained -- the following Maple commands will express the roots in terms of radicals.

> # _EnvExplicit := true;

> # solve(zpoly, z);

These commands are commented out here because the resulting expressions for the eight roots are somewhat complicated.

However, we already have a complete structural specification for the solutions of the given system of polynomial equations. We may choose to do numerical root-finding for the roots of .

> zval := fsolve(zpoly, z, 'complex');

The eight solutions of the original polynomial system can be computed as follows.

> soln := seq( [x = eval(xval, z=zval[i]),
             y = eval(yval, z=zval[i]),
             z = zval[i]],
                   i = 1..nops([zval]) );

Check that each of these eight triples is a zero of the original polynomial system (to the numerical accuracy being used).

> seq( eval(F,soln[i]), i=1..nops([soln]) );

Example 9

In some cases, the Groebner basis for a polynomial system may contain one or more polynomials which can be factored, in which case the polynomial system breaks into subsystems (corresponding to subvarieties in the solution space). The Solve function in the Groebner package is designed to perform factoring whenever possible while computing the lexicographic Groebner basis, so as to facilitate solving the polynomial system. Hence it is advisable to use the Groebner:-Solve function rather than the more basic Groebner:-Basis function when the objective is to solve a system of polynomial equations.

Consider the following system of polynomials.

> f1 := 4*x^2 + x*y^2 - z + 1/4:

> f2 := 2*x + y^2*z + 1/2:

> f3 := x^2*z - 1/2*x - y^2:

> F := [f1, f2, f3];

> s := Groebner:-Solve(F, [x,y,z]);

${[[z-1, 2*y^2-1, 2*x+1], plex(x, y, z), {}], [[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*...$
${[[z-1, 2*y^2-1, 2*x+1], plex(x, y, z), {}], [[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*...$
${[[z-1, 2*y^2-1, 2*x+1], plex(x, y, z), {}], [[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*...$
${[[z-1, 2*y^2-1, 2*x+1], plex(x, y, z), {}], [[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*...$
${[[z-1, 2*y^2-1, 2*x+1], plex(x, y, z), {}], [[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*...$
${[[z-1, 2*y^2-1, 2*x+1], plex(x, y, z), {}], [[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*...$
${[[z-1, 2*y^2-1, 2*x+1], plex(x, y, z), {}], [[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*...$

The result consists of a set of two subsystems, as follows.

> s[1];

$[[z-1, 2*y^2-1, 2*x+1], plex(x, y, z), {}]$

> s[2];

$[[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*z+21382], plex(x, y, z), {}]$
$[[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*z+21382], plex(x, y, z), {}]$
$[[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*z+21382], plex(x, y, z), {}]$
$[[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*z+21382], plex(x, y, z), {}]$
$[[16*z^6+8*z^5+9*z^4+61*z^3+136*z^2-206*z+60, 284*y^2+5664*z^5+5568*z^4+5866*z^3+24365*z^2+59937*z-43978, 568*x-2736*z^5-2680*z^4-2771*z^3-11793*z^2-28946*z+21382], plex(x, y, z), {}]$

The notation for each subsystem is a list of three elements: a list of polynomials which is a Groebner basis for the subsystem, the term ordering which was used, and the last element is a set of constraints in the form of polynomials which must not vanish.

Note that the simpler of the two subsystems contains a polynomial in of degree . Let be the Groebner basis of the simpler subsystem and let be the Groebner basis of the more complicated subsystem.

> (G1,G2) := (s[1][1], s[2][1]):

> if not member(z-1, G1) then
# Make G1 be the simpler subsystem.
(G1,G2) := (G2,G1)
end if:

> G1;

> G2;

From we obtain two solutions.

> _EnvExplicit := true:

> G1_soln := solve(G1, [x,y,z]);

From , first separate out the three Groebner basis polynomials.

> xpoly := select(has, G2, x)[];

> ypoly := select(has, G2, y)[];

> zpoly := remove(has, G2, {x,y})[];

There is one value of corresponding to each value of .

> xval := solve(xpoly, x);

There are two values of corresponding to each value of .

> yval := solve(ypoly, y);

There are six values of to be determined

> zval := solve(zpoly, z);

Let us express the 12 solutions corresponding to subsystem numerically.

> zval := evalf(zval);

> G2_soln := NULL:

> for i to nops([zval]) do
zi := zval[i];
G2_soln := G2_soln,
[x=eval(xval,z=zi), y=eval(yval[1],z=zi), z=zi],
[x=eval(xval,z=zi), y=eval(yval[2],z=zi), z=zi]
end do:

> G2_soln;

Finally, and together represent the 14 solutions of the original polynomial system .

> F;

Check the solutions.

> seq( eval(F, G1_soln[i]), i=1..nops(G1_soln) );

> seq( eval(F, G2_soln[i]), i=1..nops([G2_soln]) );

Concluding Remarks

In addition to reference [1], for further reading on the solution of systems of polynomial equations and related topics, the undergraduate-level textbook [2] is highly recommended.

References

[1] K.O. Geddes, S.R. Czapor and G. Labahn, Algorithms for Computer Algebra , Kluwer Academic Publishers, Boston, 1992.

[2] D. Cox, J. Little and D. O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra , Springer-Verlag, New York, 1992.