Groebner Bases for Polynomial Systems: An IntroductionK.O. Geddes Symbolic Computation Group School of Computer Science University of Waterloo Waterloo ON N2L 3G1 CANADA

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.

Suppose that we wish to simplify an expression which contains various powers of the symbol NiMlImlH , under the assumption that NiMlImlH represents the complex number NiMtJSVzcXJ0RzYjLCQiIiIhIiI= . For example,restart;e := 4*i^5 - 7*i^4 + i^3 + 3*i^2 - 5*i + 11;

NiM+SSJlRzYiLC4qJEkiaUdGJSIiJiIiJSokRihGKiEiKCokRigiIiQiIiIqJEYoIiIjRi5GKCEiJiIjNkYv

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.eval(e, {i^2=-1, i^3=-i, i^4=1, i^5=i});

NiMsJkkiaUc2IiEiIyIiIkYn

An algorithmic approach to the problem is as follows. We wish to simplify the expression NiMlImVH with respect to the following side relation which the variable NiMlImlH must satisfy: NiMvLCYqJCUiaUciIiMiIiJGKEYoIiIh . The given expression lies in a polynomial domain NiMlIkRH[NiMlImlH] over some coefficient domain NiMlIkRH but we really want to represent the expression in a canonical form as an element of the quotient ring D[NiNJImlHNiI=] / <NiMsJiokSSJpRzYiIiIjIiIiRihGKA==> -- i.e. as a polynomial modulo the ideal generated by NiMsJiokJSJpRyIiIyIiIkYnRic= .Question: Is it possible to specify a canoncial form for elements of the quotient ring D[NiNJImlHNiI=] / <NiMsJiokSSJpRzYiIiIjIiIiRihGKA==> ?Yes it is possible. Any element of the quotient ring can be represented uniquely in terms of the basis NiM8JCIiIiUiaUc= -- i.e. as a polynomial of degree 1 in the variable NiMlImlH .

For the quotient ring discussed above, transformation to canonical form can be obtained by applying Euclidean division with remainder: NiMlImVH --> NiMtJSRyZW1HNiUlImVHLCYqJCUiaUciIiMiIiJGK0YrRik= .Reason: Euclidean division yields a quotient NiNJInFHNiI= and remainder NiNJInJHNiI= such that NiMvSSJlRzYiLCYqJkkicUdGJSIiIiwmKiRJImlHRiUiIiNGKUYpRilGKUYpSSJyR0YlRik= and any multiple of NiMsJiokSSJpRzYiIiIjIiIiRihGKA== is equivalent to zero.In other words, we can reduce the expression NiNJImVHNiI= by subtracting any element of the ideal <NiMsJiokSSJpRzYiIiIjIiIiRihGKA==> (i.e. by subtracting any multiple of NiMsJiokSSJpRzYiIiIjIiIiRihGKA==).

e;

NiMsLiokSSJpRzYiIiImIiIlKiRGJUYoISIoKiRGJSIiJCIiIiokRiUiIiNGLEYlISImIiM2Ri0=

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

NiMsJkkiaUc2IiEiIyIiIkYn

Of course, Maple will automatically simplify expressions involving NiMtJSVzcXJ0RzYjLCQiIiIhIiI= which has the alias NiMlIklH in Maple.eval(e, i=I);

NiNeJCIiIiEiIw==

The above discussion applies to any univariate side relation.As a second example, consider an expression in the symbol NiMlInJH which represents NiMtJSVzcXJ0RzYjIiIj .In this case, the side relation satisfied by the symbol NiMlInJH is: NiMvLCYqJCUickciIiMiIiJGJyEiIiIiIQ== .f := r^6 - 5/7*r^5 + 23*r^4 + 1/2*r^3 - 35/11*r^2 + r - 1/2;

NiM+SSJmRzYiLDAqJEkickdGJSIiJyIiIiokRigiIiYjISImIiIoKiRGKCIiJSIjQiokRigiIiQjRioiIiMqJEYoRjYjISNOIiM2RihGKiMhIiJGNkYq

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

NiMsJiMiJVw/IiNBIiIiSSJyRzYiIyEiJyIiKA==

Again, Maple will automatically simplify expressions involving NiMtJSVzcXJ0RzYjIiIj .eval(f, r=sqrt(2));

NiMsJiMiJVw/IiNBIiIiKiQiIiMjRidGKSMhIiciIig=

Suppose, for example, that we have a trigonometric expression involving NiMtJSRzaW5HNiMlInhH and NiMtJSRjb3NHNiMlInhH and we wish to simplify the expression with respect to the following side relation: NiMvLCYqJC0lJHNpbkc2IyUieEciIiMiIiIqJC0lJGNvc0dGKEYqRitGKw== .We can choose to think of this as a polynomial side relation NiMvLCYqJCUic0ciIiMiIiIqJCUiY0dGJ0YoRig= and to represent NiMtJSRzaW5HNiMlInhH and NiMtJSRjb3NHNiMlInhH in the expression by the symbols NiMlInNH and NiMlImNH, 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 polynomial domain NiMlIkRH[NiM2JEkic0c2IkkiY0dGJQ==] and we wish to express it (in a canonical form, if possible) as an element of the quotient ring D[NiM2JEkic0c2IkkiY0dGJQ==] / <NiMsKCokSSJzRzYiIiIjIiIiKiRJImNHRiZGJ0YoRighIiI=> .Question: Is it possible to specify a canoncial form for elements of the quotient ring D[NiM2JEkic0c2IkkiY0dGJQ==] / <NiMsKCokSSJzRzYiIiIjIiIiKiRJImNHRiZGJ0YoRighIiI=> ?The answer is not obvious.For example, the following expressions are mathematically equivalent:e1 := sin(x)^2 * cos(x)^2;

NiM+SSNlMUc2IiomLUkkc2luRzYkSSpwcm90ZWN0ZWRHRipJKF9zeXNsaWJHRiU2I0kieEdGJSIiIy1JJGNvc0dGKUYsRi4=

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

NiM+SSNlMkc2IiwmKiQtSSRzaW5HNiRJKnByb3RlY3RlZEdGK0koX3N5c2xpYkdGJTYjSSJ4R0YlIiIjIiIiKiRGKCIiJSEiIg==

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

NiM+SSNlM0c2IiwmKiQtSSRjb3NHNiRJKnByb3RlY3RlZEdGK0koX3N5c2xpYkdGJTYjSSJ4R0YlIiIjIiIiKiRGKCIiJSEiIg==

Which form is "best"? "simplest"? It depends on your point of view.The more general Question is: Given a multivariate polynomial domain NiMlIkRH[NiUmJSJ4RzYjIiIiJSQuLi5HJkYkNiMlInZH] and one or more side relations NiMvLSYlInJHNiMlImpHNiUmJSJ4RzYjIiIiJSQuLi5HJkYrNiMlInZHIiIh (NiUvJSJqRyIiIiIiIyUkLi4uRw== ), is it possible to specify a canonical form for elements of the quotient ring NiMlIkRH[NiUmJSJ4RzYjIiIiJSQuLi5HJkYkNiMlInZH] / NiMlI0lkRw== where NiMlI0lkRw== is the ideal generated by the polynomials NiMtJiUickc2IyUiakc2JSYlInhHNiMiIiIlJC4uLkcmRio2IyUidkc= ?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.

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 NiMtJSlzaW1wbGlmeUc2JCUlZXhwckclKXNpZGVyZWxzRw== where NiMlKXNpZGVyZWxzRw== 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 NiMlKXNpZGVyZWxzRw== is computed and then NiMlJWV4cHJH 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 NiMtJSlzaW1wbGlmeUc2JSUlZXhwckclKXNpZGVyZWxzRyUldmFyc0c= where NiMlJXZhcnNH is a list of variables in the desired order.

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

NiM+SSlzaWRlcmVsc0c2IjwjLywmKiQtSSRzaW5HNiRJKnByb3RlY3RlZEdGLUkoX3N5c2xpYkdGJTYjSSJ4R0YlIiIjIiIiKiQtSSRjb3NHRixGL0YxRjJGMg==

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

NiM+SSJlRzYiLCwqJC1JJHNpbkc2JEkqcHJvdGVjdGVkR0YrSShfc3lzbGliR0YlNiNJInhHRiUiIiQiIiIqJkYoIiIjLUkkY29zR0YqRi1GMCEjNiokRjNGL0YvKiZGKEYwRjNGMCEiIkYyRjA=

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)]);

NiMsLCokLUkkc2luRzYkSSpwcm90ZWN0ZWRHRihJKF9zeXNsaWJHNiI2I0kieEdGKiIiJCIiIiomRiUiIiMtSSRjb3NHRidGK0YuISM5KiZGJUYuRjFGLiEiIkYwRi5GMUYt

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)]);

NiMsLiokLUkkY29zRzYkSSpwcm90ZWN0ZWRHRihJKF9zeXNsaWJHNiI2I0kieEdGKiIiJCIjOSomLUkkc2luR0YnRisiIiJGJUYyISIiIiIjRjIqJkYlRjRGMEYyRjNGMEYyRiUhIzY=

Try simplifying the following expression NiMlImZH .f := sin(x)^2 * cos(x)^2;

NiM+SSJmRzYiKiYtSSRzaW5HNiRJKnByb3RlY3RlZEdGKkkoX3N5c2xpYkdGJTYjSSJ4R0YlIiIjLUkkY29zR0YpRixGLg==

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

NiMsJiokLUkkc2luRzYkSSpwcm90ZWN0ZWRHRihJKF9zeXNsaWJHNiI2I0kieEdGKiIiIyIiIiokRiUiIiUhIiI=

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

NiMsJiokLUkkY29zRzYkSSpwcm90ZWN0ZWRHRihJKF9zeXNsaWJHNiI2I0kieEdGKiIiIyIiIiokRiUiIiUhIiI=

The expression NiMlImdH is equivalent to zero, and therefore its canonical form must be 0 (regardless of ordering).g := f - sin(x)^2 + sin(x)^4;

NiM+SSJnRzYiLCgqJi1JJHNpbkc2JEkqcHJvdGVjdGVkR0YrSShfc3lzbGliR0YlNiNJInhHRiUiIiMtSSRjb3NHRipGLUYvIiIiKiRGKEYvISIiKiRGKCIiJUYy

simplify(g, siderels);

NiMiIiE=

Consider the polynomial domain Q[NiUlInhHJSJ5RyUiekc=] 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};

NiM+SSlzaWRlcmVsc0c2IjwlLyooSSJ4R0YlIiIkSSJ5R0YlIiIiSSJ6R0YlRiwqJkYpRixGLSIiIy8qKEYpRixGK0YvRi1GLCooRilGLEYrRixGLUYsLyomRilGL0YrRi8qJEYtRi8=

Consider the following polynomial expression.p := x*z^4 - x*y*z^3;

NiM+SSJwRzYiLCYqJkkieEdGJSIiIkkiekdGJSIiJUYpKihGKEYpSSJ5R0YlRilGKiIiJCEiIg==

Problem: Express NiMlInBH in a canonical form with respect to NiMlKXNpZGVyZWxzRw== .This can be accomplished in Maple as follows.simplify(p, siderels);

NiMiIiE=

Offhand, you would not be able to recognize that NiMlInBH is equivalent to zero. How would you proceed to try to "reduce" NiMlInBH with respect to the given side relations?The mathematical framework is as follows. In the original polynomial domain Q[NiUlInhHJSJ5RyUiekc=] 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.Generate the list of all terms in the variables NiM2JUkieEc2IkkieUdGJUkiekdGJQ== of total degree less than or equal to NiMiIiQ=.L:=[ op(eval(convert(map(expand,series(1/((1-x*u)*(1-y*u)*(1-z*u)),u,4)),polynom), u=1)) ];

NiM+SSJMRzYiNzYiIiJJInhHRiVJInlHRiVJInpHRiUqJEYoIiIjKiZGKUYnRihGJyokRilGLComRihGJ0YqRicqJkYpRidGKkYnKiRGKkYsKiRGKCIiJComRihGLEYpRicqJkYoRidGKUYsKiRGKUYzKiZGKkYnRihGLCooRihGJ0YpRidGKkYnKiZGKUYsRipGJyomRihGJ0YqRiwqJkYpRidGKkYsKiRGKkYz

Sort this list of terms in the tdeg ordering.with(Groebner):TermOrder := tdeg(x,y,z);

NiM+SSpUZXJtT3JkZXJHNiItSSV0ZGVnR0YlNiVJInhHRiVJInlHRiVJInpHRiU=

tdegBasis := sort(L, (t1,t2)->testorder(t1,t2,TermOrder));

NiM+SSp0ZGVnQmFzaXNHNiI3NiIiIkkiekdGJUkieUdGJUkieEdGJSokRigiIiMqJkYpRidGKEYnKiZGKkYnRihGJyokRilGLComRilGJ0YqRicqJEYqRiwqJEYoIiIkKiZGKUYnRihGLComRipGJ0YoRiwqJkYpRixGKEYnKihGKkYnRilGJ0YoRicqJkYoRidGKkYsKiRGKUYzKiZGKkYnRilGLComRipGLEYpRicqJEYqRjM=

Given the polynomial expression NiMlInBH in the domain Q[NiUlInhHJSJ5RyUiekc=] , we are required to simplify NiMlInBH with respect to NiMlKXNpZGVyZWxzRw== ; in other words, we want to express NiMlInBH in a canonical form as an element of the quotient ring Q[NiUlInhHJSJ5RyUiekc=] / NiMlI0lkRw== where NiMlI0lkRw== is the ideal generated by the side relations. For NiMlKXNpZGVyZWxzRw== as specified above, the corresponding ideal is NiMlI0lkRw== = < NiUsJiooJSJ4RyIiJCUieUciIiIlInpHRihGKComRiVGKCokRikiIiNGKCEiIiwmKihGJUYoKiRGJ0YsRihGKUYoRigqKEYlRihGJ0YoRilGKEYtLCYqJkYlRixGJ0YsRihGK0Yt > .Objective: Define a basis for the quotient ring Q[NiUlInhHJSJ5RyUiekc=] / NiMlI0lkRw== and specify an algorithm to express any particular polynomial NiMlInBH in terms of that basis.The basis NiMlKnRkZWdCYXNpc0c= specified above for the domain Q[NiUlInhHJSJ5RyUiekc=] clearly is not a basis for the quotient ring. The monomials are not all independent in the quotient ring; for example, NiMvKiYlInhHIiIjJSJ5R0YmKiQlInpHRiY= .Question: Which monomials should be deleted from NiMlKnRkZWdCYXNpc0c= 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 NiMlI0lkRw== .Step 2: Examine each monomial NiM2KCIiIkkiekc2IkkieUdGJkkieEdGJiokRiUiIiMqJkYlRiRGJ0Yk, ... with respect to the Groebner basis for NiMlI0lkRw== to determine whether, as an element of Q[NiUlInhHJSJ5RyUiekc=] / NiMlI0lkRw== , it can be reduced to a lower-order monomial (with respect to the specified ordering of monomials). (E.g. NiMqJiUieEciIiMlInlHRiU= reduces to NiMqJCUiekciIiM= .)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 NiMlInBH that we wish to simplify.

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 is a concept of a "set of generators for the ideal". Indeed, for the ideal NiMlI0lkRw== = < NiUsJiooJSJ4RyIiJCUieUciIiIlInpHRihGKComRiVGKCokRikiIiNGKCEiIiwmKihGJUYoKiRGJ0YsRihGKUYoRigqKEYlRihGJ0YoRilGKEYtLCYqJkYlRixGJ0YsRihGK0Yt > the corresponding Groebner basis will have more elements (i.e. more generators) than the three specified in the original definition of NiMlI0lkRw== . Using Maple, we can determine a Groebner basis NiMlI0diRw== for the ideal NiMlI0lkRw== 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.)

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

NiM+SSNJZEc2IjclLCYqKEkieEdGJSIiJEkieUdGJSIiIkkiekdGJUYsRiwqJkYpRixGLSIiIyEiIiwmKihGKUYsRitGL0YtRixGLCooRilGLEYrRixGLUYsRjAsJiomRilGL0YrRi9GLCokRi1GL0Yw

nops(Id);

NiMiIiQ=

Gb := gbasis(Id, TermOrder);

NiM+SSNHYkc2IjcqLCYqJEkiekdGJSIiJCEiIiomSSJ5R0YlIiIiRilGKkYuLCYqJkkieEdGJUYuRikiIiNGKyomRjFGLkYpRipGLiwmKihGLUYuRjFGLkYpRjJGLkYwRissJiokRikiIiVGKyomRjFGMkYpRjJGLiwmKihGMUYuRi1GMkYpRi5GLiooRjFGLkYtRi5GKUYuRissJiooRjFGMkYtRi5GKUYuRi5GKEYrLCYqJkYxRjJGLUYyRi4qJEYpRjJGKywmKiRGKSIiJkYuRjdGKw==

nops(Gb);

NiMiIik=

Note that the original specification of the ideal NiMlI0lkRw== has 3 generators whereas the Groebner basis NiMlI0diRw== has 8 generators.However, the same ideal is being specified with different sets of generators: NiMvLSUmSWRlYWxHNiMlI0lkRy1GJTYjJSNHYkc= .(See the definition of a Groebner basis in the next section.)For the polynomial NiMlInBH specified above, our task now is to reduce NiMlInBH with respect to the Groebner basis NiMlI0diRw== . The function normalf 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;

NiMsJiomSSJ4RzYiIiIiSSJ6R0YmIiIlRicqKEYlRidJInlHRiZGJ0YoIiIkISIi

normalf(p, Gb, TermOrder);

NiMiIiE=

If the original list of generators NiMlI0lkRw== was used to specify the ideal then the reduction process applied by the normalf function would fail to recognize that NiMlInBH reduces to zero modulo the ideal.normalf(p, Id, TermOrder);

NiMsJiomSSJ4RzYiIiIiSSJ6R0YmIiIlRicqKEYlRidJInlHRiZGJ0YoIiIkISIi

The S-polynomial of two polynomials NiQlImFHJSJiRw== is defined by NiMvLSUiU0c2JCUiYUclImJHKiYsJiomLSUiaEc2I0YoIiIiRidGL0YvKiYtRi02I0YnRi9GKEYvISIiRi8tJSRHQ0RHNiRGMUYsRjM=where NiMtJSJoRzYjJSJwRw== denotes the "head term" of a polynomial NiMlInBH , meaning the leading monomial (with respect to a specified term ordering).

An important property of NiMtJSJTRzYkJSJhRyUiYkc= is that the head term of NiMlImFH will be eliminated in the case where NiMtJSJoRzYjJSJiRw== | NiMtJSJoRzYjJSJhRw== , in which case we have NiMvLSUiU0c2JCUiYUclImJHLCZGJyIiIiooLSUiaEc2I0YnRipGKEYqLUYtNiNGKCEiIkYx .

p;

NiMsJiomSSJ4RzYiIiIiSSJ6R0YmIiIlRicqKEYlRidJInlHRiZGJ0YoIiIkISIi

Let's choose one particular element from the Groebner basis NiMlI0diRw== .G1 := x*y*z^2 - x*z^2;

NiM+SSNHMUc2IiwmKihJInlHRiUiIiJJInhHRiVGKUkiekdGJSIiI0YpKiZGKkYpRitGLCEiIg==

With NiMvLSUiaEc2IyUicEcsJCooJSJ4RyIiIiUieUdGKyUiekciIiQhIiI= and NiMvLSUiaEc2IyUjRzFHKiglInhHIiIiJSJ5R0YqJSJ6RyIiIw== we see that NiMtJSJoRzYjJSNHMUc= | NiMtJSJoRzYjJSJwRw== . Hence the NiMlIlNH-polynomial NiMtJSJTRzYkJSJwRyUjRzFH is as follows.headp := -x*y*z^3;

NiM+SSZoZWFkcEc2IiwkKihJInhHRiUiIiJJInlHRiVGKUkiekdGJSIiJCEiIg==

headG1 := x*y*z^2;

NiM+SSdoZWFkRzFHNiIqKEkieUdGJSIiIkkieEdGJUYoSSJ6R0YlIiIj

S := (headG1*p - headp*G1) / gcd(headp,headG1):S := normal(S,expanded);

NiM+SSJTRzYiLCYqJkkieEdGJSIiIkkiekdGJSIiJCEiIiomRihGKUYqIiIlRik=

or equivalently,S := p - (headp/headG1)*G1;

NiM+SSJTRzYiLCgqJkkieEdGJSIiIkkiekdGJSIiJUYpKihGKEYpSSJ5R0YlRilGKiIiJCEiIiomRipGKSwmKihGLUYpRihGKUYqIiIjRikqJkYoRilGKkYzRi9GKUYp

S := expand(S);

NiM+SSJTRzYiLCYqJkkieEdGJSIiIkkiekdGJSIiJCEiIiomRihGKUYqIiIlRik=

The point to be noted in the above example is that the computation of the NiMlIlNH-polynomial NiMtJSJTRzYkJSJwRyUjRzFH results in a reduction of NiMlInBH in the following sense. The computed polynomial NiMlIlNH is equivalent to the polynomial NiMlInBH in the quotient ring Q[NiUlInhHJSJ5RyUiekc=] / NiMtJSZJZGVhbEc2IyUjR2JH (equivalently, Q[NiUlInhHJSJ5RyUiekc=] / NiMtJSZJZGVhbEc2IyUjSWRH ) because all we did was to subtract from NiMlInBH a multiple of NiMlI0cxRw== , which is an element of the ideal (i.e. NiMvJSNHMUciIiE= ). Moreover, the head term NiMvLSUiaEc2IyUiU0cqJiUieEciIiIqJCUiekciIiVGKg== is smaller (in the specified term ordering) than the original head term NiMvLSUiaEc2IyUicEcsJCooJSJ4RyIiIiUieUdGKyUiekciIiQhIiI= .It is precisely this type of reduction of the terms in the polynomial NiMlInBH that we wish to perform, and we wish to be guaranteed that NiMlInBH will get reduced to a canonical form. The desired guarantee comes from the definition of a Groebner basis for the ideal.

A polynomial NiMlInBH is F-reduced modulo the ideal basis NiMvJSJGRzwlJiUiZkc2IyIiIiUofi5+Ln4ufkcmRic2IyUia0c= if no head term NiMtJSJoRzYjJiUiZkc2IyUiaUc= divides NiMtJSJoRzYjJSJwRw== , for NiYvJSJpRyIiIiIiIyUofi5+Ln4ufkclImtH .

Method of F-reduction: If NiMtJSJoRzYjJiUiZkc2IyUiaUc= | NiMtJSJoRzYjJSJwRw== then replace NiMlInBH by the NiMlIlNH-polynomial NiMtJSJTRzYkJSJwRyYlImZHNiMlImlH . I.e. perform the reduction NiMlInBH --> NiMtJSJTRzYkJSJwRyYlImZHNiMlImlH . Continue performing reductions until Definition 2 is satisfied.It is clear that if a polynomial NiMlInBH NiMlIkZH-reduces to zero then NiMlInBH is in NiMtJSZJZGVhbEc2IyUiRkc= . 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 NiMlIkdH , we would have the property: NiMlInBH is in NiMtJSZJZGVhbEc2IyUiR0c= if and only if NiMlInBH NiMlIkdH-reduces to zero.This property is precisely what a Groebner basis gives us.

A set of polynomials NiMlIkdH in a polynomial domain NiMlIkRH[NiUmJSJ4RzYjIiIiJSh+Ln4ufi5+RyZGJDYjJSJ2Rw==] is a Groebner basis (with respect to a fixed term ordering) if NiMlInBH is in NiMtJSZJZGVhbEc2IyUiR0c= if and only if NiMlInBH NiMlIkdH-reduces to 0 .

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

A set of polynomials NiMlIkdH in a polynomial domain NiMlIkRH[NiUmJSJ4RzYjIiIiJSh+Ln4ufi5+RyZGJDYjJSJ2Rw==] is a Groebner basis if and only if the following property holds: NiMlInBH NiMlIkdH-reduces to NiMlInFH and NiMlInBH NiMlIkdH-reduces to NiMlInJH implies NiMvJSJxRyUickc= .

For a detailed development of Buchberger's algorithm to compute a Groebner basis, see [1]. The general idea is that, given an ideal basis NiMlI0lkRw== , we must compute another ideal basis NiMlIkdH such that NiMvLSUmSWRlYWxHNiMlIkdHLUYlNiMlI0lkRw== and NiMlIkdH is a Groebner basis. The algorithm consists of a sequence of operations based on computing NiMlIlNH-polynomials and applying the process of NiMlIkZH-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 NiMlIkdH for the ideal. Specifically, to determine whether a given polynomial NiMlInBH is a member of NiMtJSZJZGVhbEc2IyUiR0c= we simply apply NiMlIkdH-reductions to determine whether NiMlInBH NiMlIkdH-reduces to zero. In Maple, the normalf function can be used for this purpose.

Consider the polynomial domain Q[NiUlInhHJSJ5RyUiekc=] and the ideal NiMlI0lkRw== specified above.Id;

NiM3JSwmKihJInhHNiIiIiRJInlHRiciIiJJInpHRidGKkYqKiZGJkYqRisiIiMhIiIsJiooRiZGKkYpRi1GK0YqRioqKEYmRipGKUYqRitGKkYuLCYqJkYmRi1GKUYtRioqJEYrRi1GLg==

The Groebner basis for NiMlI0lkRw== was determined to be as follows.Gb;

NiM3KiwmKiRJInpHNiIiIiQhIiIqJkkieUdGJyIiIkYmRihGLCwmKiZJInhHRidGLEYmIiIjRikqJkYvRixGJkYoRiwsJiooRitGLEYvRixGJkYwRixGLkYpLCYqJEYmIiIlRikqJkYvRjBGJkYwRiwsJiooRi9GLEYrRjBGJkYsRiwqKEYvRixGK0YsRiZGLEYpLCYqKEYvRjBGK0YsRiZGLEYsRiVGKSwmKiZGL0YwRitGMEYsKiRGJkYwRiksJiokRiYiIiZGLEY1Rik=

Let NiMlInBH be the polynomial defined above. Is NiMlInBH in NiMtJSZJZGVhbEc2IyUjSWRH ?p;

NiMsJiomSSJ4RzYiIiIiSSJ6R0YmIiIlRicqKEYlRidJInlHRiZGJ0YoIiIkISIi

normalf(p, Gb, TermOrder);

NiMiIiE=

Since NiMlInBH NiMlI0diRw==-reduces to zero we conclude that NiMlInBH is in NiMvLSUmSWRlYWxHNiMlI0lkRy1GJTYjJSNHYkc= .Create two different polynomials NiMlI3AxRw== and NiMlI3AyRw== which are known to be equivalent modulo NiMtJSZJZGVhbEc2IyUjSWRH .q := 3*x^5*y*z^2 - 1/2*x^4*y^3 + x*y*z;

NiM+SSJxRzYiLCgqKEkieEdGJSIiJkkieUdGJSIiIkkiekdGJSIiIyIiJComRigiIiVGKkYuIyEiIkYtKihGKEYrRipGK0YsRitGKw==

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

NiM+SSNwMUc2Iiw0KihJInhHRiUiIiZJInlHRiUiIiJJInpHRiUiIiMiIiQqJkYoIiIlRipGLiMhIiJGLSooRihGK0YqRitGLEYrRisqJkYoRi5GLEYwRisqKEYoRi5GKkYrRixGLkYyKihGKkYtRihGK0YsRjBGKyooRipGLkYoRitGLEYuRjIqJkYsIiInRihGK0YrKihGLEYpRipGK0YoRitGMg==

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

NiM+SSNwMkc2Iiw4KihJInhHRiUiIiZJInlHRiUiIiJJInpHRiUiIiMiIiQqJkYoIiIlRipGLiMhIiJGLSooRihGK0YqRitGLEYrRisqKEYoRjBGKkYtRixGMEYrKihGKEYwRipGLkYsRi5GMiomRixGKUYoRi4jISIkRjAqKEYsRjBGKEYuRipGKyNGLkYwKiZGKEYtRiwiIigjRitGMCooRihGLUYsIiInRipGKyNGMkYwKiZGKEYrRixGMCMhIiVGKSooRihGK0YqRitGLEYuI0YwRik=

Applying normalf to each of NiMlI3AxRw== and NiMlI3AyRw== should yield the same canoncial form.normalf(p1, Gb, TermOrder);

NiMsKCooSSJ4RzYiIiIiSSJ5R0YmRidJInpHRiZGJ0YnKiRGKSIiJSMhIiIiIiMqJkYlRidGKUYuIiIk

normalf(p2, Gb, TermOrder);

NiMsKCooSSJ4RzYiIiIiSSJ5R0YmRidJInpHRiZGJ0YnKiRGKSIiJSMhIiIiIiMqJkYlRidGKUYuIiIk

This must also be the canonical form of the polynomial NiMlInFH .normalf(q, Gb, TermOrder);

NiMsKCooSSJ4RzYiIiIiSSJ5R0YmRidJInpHRiZGJ0YnKiRGKSIiJSMhIiIiIiMqJkYlRidGKUYuIiIk

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[NiUlInhHJSJ5RyUiekc=] the pure lexicographical ordering implies NiMiIiI= < NiMlInpH < NiMqJCUiekciIiM= < NiMlKH4ufi5+Ln5H < NiMlInlH < NiMqJiUieUciIiIlInpHRiU= < NiMqJiUieUciIiIqJCUiekciIiNGJQ== < NiMlKH4ufi5+Ln5H < NiMqJCUieUciIiM= < NiMqJiUieUciIiMlInpHIiIi < NiMlKH4ufi5+Ln5H < NiMlInhH < NiMqJiUieEciIiIlInpHRiU= < NiMlKH4ufi5+Ln5H < NiMqJiUieEciIiIlInlHRiU= < NiMlKH4ufi5+Ln5H .The ProblemGiven a system of polynomial equations NiMvLSYlInBHNiMiIiI2JSYlInhHRiclKH4ufi5+Ln5HJkYrNiMlIm5HIiIh NiMvLSYlInBHNiMiIiM2JSYlInhHNiMiIiIlKH4ufi5+Ln5HJkYrNiMlIm5HIiIh NiMlKH4ufi5+Ln5H NiMvLSYlInBHNiMlImtHNiUmJSJ4RzYjIiIiJSh+Ln4ufi5+RyZGKzYjJSJuRyIiIQ==we wish to find values of ( NiUmJSJ4RzYjIiIiJSh+Ln4ufi5+RyZGJDYjJSJuRw== ) which simultaneously satisfy the NiMlImtH polynomial equations.Solution TechniqueConsider NiMtJSZJZGVhbEc2IyUiRkc= , the ideal generated by the given polynomials NiMvJSJGRzclJiUicEc2IyIiIiUofi5+Ln4ufkcmRic2IyUia0c= , and compute its Groebner basis NiMlIkdH using pure lexicographical ordering. Then the set of common zeros of NiMlIkZH is identical to the set of common zeros of NiMlIkdH and, moreover, we can obtain much more information about the common zeros from NiMlIkdH than from the original polynomials NiMlIkZH .

Suppose that we wish to solve the three polynomial equations: NiUvJSNxMUciIiEvJSNxMkdGJS8lI3EzR0Yl defined as follows.restart;with(Groebner):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];

NiM+SSJGRzYiNyUsKComSSJ4R0YlIiIjSSJ5R0YlIiIiRiwqJEYrRioiIiUhIzxGLCwoKiZGKUYsRitGLEYqKiRGKyIiJCEiJCIiKUYsLCgqJkYpRixGK0YqRixGMSEiJkYsRiw=

G := gbasis(F, plex(x,y,z));

NiM+SSJHRzYiNyMiIiI=

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.

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];

NiM+SSJGRzYiNyUsKCokSSJ4R0YlIiIjIiIiKiZJInlHRiVGK0kiekdGJUYrRishIiNGKywoKiRGLUYqRisqJkYpRitGLkYrRishIiRGKywoKiZGKUYrRi1GK0YrKiRGLkYqRishIiZGKw==

G := gbasis(F, plex(x,y,z));

NiM+SSJHRzYiNyUsLCIkaCQiIiIqJEkiekdGJSIiIyEkZygqJEYrIiIlIiRRJSokRisiIichJCsiKiRGKyIiKUY1LCxJInlHRiVGKCokRisiIihGNSokRisiIiYiI18qJEYrIiIkISRTKEYrIiVEOSwsSSJ4R0YlRihGOCEjKSlGOiIkcylGPSElIXAjRisiJXZC

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 NiMlInhH is isolated as a function of NiMlInpH ; in another equation the variable NiMlInlH is isolated as a function of NiMlInpH; and the remaining equation involves a univariate polynomial in the variable NiMlInpH . Therefore, the solutions can be described as follows.xpoly := select(has, G, x)[];

NiM+SSZ4cG9seUc2IiwsSSJ4R0YlIiRoJCokSSJ6R0YlIiIoISMpKSokRioiIiYiJHMpKiRGKiIiJCElIXAjRioiJXZC

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

NiM+SSZ5cG9seUc2IiwsSSJ5R0YlIiRoJCokSSJ6R0YlIiIoIiIpKiRGKiIiJiIjXyokRioiIiQhJFMoRioiJUQ5

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

NiM+SSZ6cG9seUc2IiwsIiRoJCIiIiokSSJ6R0YlIiIjISRnKCokRioiIiUiJFElKiRGKiIiJyEkKyIqJEYqIiIpRjQ=

We can solve explicitly for NiMlInhH and NiMlInlH as a function of NiMlInpH .xval := solve(xpoly, x);

NiM+SSV4dmFsRzYiLCpJInpHRiUjISREIiIjPiokRiciIigjIiMpKSIkaCQqJEYnIiImIyEkcylGLyokRiciIiQjIiUhcCNGLw==

yval := solve(ypoly, y);

NiM+SSV5dmFsRzYiLCoqJEkiekdGJSIiKCMhIikiJGgkKiRGKCIiJiMhI19GLCokRigiIiQjIiRTKEYsRigjISN2IiM+

For each of the 8 roots of the univariate polynomial NiMlJnpwb2x5Rw== we have a triple ( NiUlInhHJSJ5RyUiekc= ) which is a solution of the original system of polynomial equations.The symbolic representation of the roots of NiMlJnpwb2x5Rw== obtained via NiMtJSZzb2x2ZUc2JCUmenBvbHlHJSJ6Rw== is expressed using the NiMlJ1Jvb3RPZkc= construct (by default) and is not very informative. One can note that NiMlJnpwb2x5Rw== is actually just a quartic polynomial in NiMqJCUiekciIiM= 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 NiMlJnpwb2x5Rw== .zval := fsolve(zpoly, z, 'complex');

NiM+SSV6dmFsRzYiNiokIStmOCNHQCMhIipeJCQhKz1zM2w9RikkIStzISlceUAhIzVeJEYrJCIrcyEpXHlARi8kISt6Iz0mNCcpRi8kIit6Iz0mNCcpRi9eJCQiKz1zM2w9RilGLV4kRjhGMSQiK2Y4I0dAI0Yp

The eight solutions of the original polynomial system NiMlIkZH 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]) );

NiM+SSVzb2xuRzYiNio3JS9JInhHRiUkISpEJjRgOCEiKS9JInlHRiUkISknUUxrKCEiKi9JInpHRiUkIStmOCNHQCNGMTclL0YpXiQkISlsT2p1RiwkIilMKEheKkYsL0YuXiQkISsleSJvSDhGMSQhKzBVTGdnISM1L0YzXiQkISs9czNsPUYxJCErcyEpXHlARkM3JS9GKV4kRjkkISlMKEheKkYsL0YuXiRGPyQiKzBVTGdnRkMvRjNeJEZGJCIrcyEpXHlARkM3JS9GKSQiKz96J2YnPkYxL0YuJCIrTD1DbUBGMS9GMyQhK3ojPSY0JylGQzclL0YpJCErP3onZic+RjEvRi4kIStMPUNtQEYxL0YzJCIreiM9JjQnKUZDNyUvRileJCQiKWxPanVGLEY7L0YuXiQkIisleSJvSDhGMUZBL0YzXiQkIis9czNsPUYxRkg3JS9GKV4kRmhvRk0vRi5eJEZccEZRL0YzXiRGYHBGVTclL0YpJCIqRCY0YDhGLC9GLiQiKSdRTGsoRjEvRjMkIitmOCNHQCNGMQ==

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]) );

Nio3JSQiJCY9ISIqJCIkSyJGJiQiIz1GJjclXiQkIiNARiYkISM9RiZeJCQiI0VGJiQiIiVGJl4kJCIjOkYmJCIjUCEjNTclXiRGLUYpXiRGMiQhIiVGJl4kRjckISNQRjs3JUY/JCIiJkYmJCIiIkYmRkRGPEYrRiM=

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 gsolve 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 gsolve function rather than the more basic gbasis 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];

NiM+SSJGRzYiNyUsKiokSSJ4R0YlIiIjIiIlKiZGKSIiIkkieUdGJUYqRi1JInpHRiUhIiIjRi1GK0YtLChGKUYqKiZGLkYqRi9GLUYtI0YtRipGLSwoKiZGKUYqRi9GLUYtRikjRjBGKiokRi5GKkYw

s := gsolve(F, [x,y,z]);

NiM+SSJzRzYiPCQ3JTclLCZJInpHRiUiIiIhIiJGKywmKiRJInlHRiUiIiNGMEYsRissJkkieEdGJUYwRitGKy1JJXBsZXhHRiU2JUYyRi9GKjwiNyU3JSwwKiRGKiIiJyIjOyokRioiIiYiIikqJEYqIiIlIiIqKiRGKiIiJCIjaCokRipGMCIkTyJGKiEkMSMiI2dGKywwRi4iJCVHRj0iJWtjRkAiJW9iRkMiJW1lRkYiJmxWI0YqIiZQKmYhJnlSJUYrLDBGMiIkbyZGPSElT0ZGQCElIW8jRkMhJXJGRkYhJiR6NkYqISZZKkciJiNRQEYrRjM8I0Yp

The result NiMlInNH consists of a set of two subsystems, as follows.s[1];

NiM3JTclLCZJInpHNiIiIiIhIiJGKCwmKiRJInlHRiciIiNGLUYpRigsJkkieEdGJ0YtRihGKC1JJXBsZXhHRic2JUYvRixGJjwi

s[2];

NiM3JTclLDAqJEkiekc2IiIiJyIjOyokRiciIiYiIikqJEYnIiIlIiIqKiRGJyIiJCIjaCokRiciIiMiJE8iRichJDEjIiNnIiIiLDAqJEkieUdGKEY1IiQlR0YrIiVrY0YuIiVvYkYxIiVtZUY0IiZsViNGJyImUCpmISZ5UiVGOSwwSSJ4R0YoIiRvJkYrISVPRkYuISUhbyNGMSElckZGNCEmJHo2RichJlkqRyImI1FARjktSSVwbGV4R0YoNiVGRUY8Ric8IywmRidGOSEiIkY5

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 (empty in this example).Note that the simpler of the two subsystems contains a polynomial in NiMlInpH of degree NiMiIiI= . Let NiMlI0cxRw== be the Groebner basis of the simpler subsystem and let NiMlI0cyRw== 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) fi:G1;

NiM3JSwmSSJ6RzYiIiIiISIiRicsJiokSSJ5R0YmIiIjRixGKEYnLCZJInhHRiZGLEYnRic=

G2;

NiM3JSwwKiRJInpHNiIiIiciIzsqJEYmIiImIiIpKiRGJiIiJSIiKiokRiYiIiQiI2gqJEYmIiIjIiRPIkYmISQxIyIjZyIiIiwwKiRJInlHRidGNCIkJUdGKiIla2NGLSIlb2JGMCIlbWVGMyImbFYjRiYiJlAqZiEmeVIlRjgsMEkieEdGJyIkbyZGKiElT0ZGLSElIW8jRjAhJXJGRjMhJiR6NkYmISZZKkciJiNRQEY4

From NiMlI0cxRw== we obtain two solutions._EnvExplicit := true:G1_soln := solve(convert(G1,'set'), {x,y,z});

NiM+SShHMV9zb2xuRzYiNiQ8JS9JInlHRiUsJCokIiIjIyIiIkYsRi0vSSJ6R0YlRi4vSSJ4R0YlIyEiIkYsPCUvRiksJEYrRjNGL0Yx

From NiMlI0cyRw== , first separate out the three Groebner basis polynomials.xpoly := select(has, G2, x)[];

NiM+SSZ4cG9seUc2IiwwSSJ4R0YlIiRvJiokSSJ6R0YlIiImISVPRiokRioiIiUhJSFvIyokRioiIiQhJXJGKiRGKiIiIyEmJHo2RiohJlkqRyImI1FAIiIi

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

NiM+SSZ5cG9seUc2IiwwKiRJInlHRiUiIiMiJCVHKiRJInpHRiUiIiYiJWtjKiRGLCIiJSIlb2IqJEYsIiIkIiVtZSokRixGKSImbFYjRiwiJlAqZiEmeVIlIiIi

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

NiM+SSZ6cG9seUc2IiwwKiRJInpHRiUiIiciIzsqJEYoIiImIiIpKiRGKCIiJSIiKiokRigiIiQiI2gqJEYoIiIjIiRPIkYoISQxIyIjZyIiIg==

There is one value of NiMlInhH corresponding to each value of NiMlInpH .xval := solve(xpoly, x);

NiM+SSV4dmFsRzYiLC4qJEkiekdGJSIiIyMiJiR6NiIkbyYqJEYoIiImIyIkVSQiI3IqJEYoIiIlIyIkTiRGMSokRigiIiQjIiVyRkYsRigjIiZ0VyIiJCVHIyEmInA1RjwiIiI=

There are two values of NiMlInlH corresponding to each value of NiMlInpH .yval := solve(ypoly, y);

NiM+SSV5dmFsRzYiNiQsJCokLC4qJEkiekdGJSIiJiEnV0BTKiRGKyIiJSEnR2BSKiRGKyIiJCEnJ1s7JSokRisiIiMhKDoqSDxGKyEoRmJEJSIoUUM3JCIiIiNGOUY1I0Y5IiRVIiwkRigjISIiRjw=

There are six values of NiMlInpH to be determined zval := solve(zpoly, z);

NiM+SSV6dmFsRzYiNigtSSdSb290T2ZHNiRJKnByb3RlY3RlZEdGKkkoX3N5c2xpYkdGJTYkLDAqJEkjX1pHRiUiIiciIzsqJEYvIiImIiIpKiRGLyIiJSIiKiokRi8iIiQiI2gqJEYvIiIjIiRPIkYvISQxIyIjZyIiIi9JJmluZGV4R0YpRkAtRig2JEYtL0ZCRjwtRig2JEYtL0ZCRjktRig2JEYtL0ZCRjYtRig2JEYtL0ZCRjMtRig2JEYtL0ZCRjA=

Let us express the 12 solutions corresponding to subsystem NiMlI0cyRw== numerically.zval := evalf(zval);

NiM+SSV6dmFsRzYiNigkIitPVGRLWyEjNSQiKzJBVSNvJkYpXiQkIis7VlpXJSlGKSQiK0o1ajI8ISIqXiQkIStccz4/O0YxJCIrSSQpcG01RjFeJEYzJCErSSQpcG01RjFeJEYtJCErSjVqMjxGMQ==

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] od:G2_soln;

Ni43JS9JInhHNiIkISphIkhMcyEiKS9JInlHRiYkIitQdSZmUCYhIiovSSJ6R0YmJCIrT1RkS1shIzU3JUYkL0YrJCErUHUmZlAmRi5GLzclL0YlJCEpbjYlNCRGKS9GKyQiK2kqPkdkJUYzL0YwJCIrMkFVI28mRjM3JUY5L0YrJCEraSo+R2QlRjNGPzclL0YlXiQkIilMbHNpRikkIilET1dIRikvRiteJCQiK0QhPUR5JEYzJCIraUV3LCIqRjMvRjBeJCQiKztWWlclKUYzJCIrSjVqMjxGLjclRkcvRiteJCQhK0QhPUR5JEYzJCEraUV3LCIqRjNGUzclL0YlXiQkISlrODRCRikkISkhPiU9a0YpL0YrXiQkIitfUU4+c0YzJCErcnI0YFBGMy9GMF4kJCErXHM+PztGLiQiK0kkKXBtNUYuNyVGW28vRiteJCQhK19RTj5zRjMkIitycjRgUEYzRmdvNyUvRiVeJEZdbyQiKSE+JT1rRikvRiteJEZjb0ZicC9GMF4kRmlvJCErSSQpcG01Ri43JUZlcC9GK14kRmBwRmVvRltxNyUvRiVeJEZJJCEpRE9XSEYpL0YrXiRGT0Zobi9GMF4kRlUkIStKNWoyPEYuNyVGY3EvRiteJEZmbkZRRmlx

Finally, NiMlKEcxX3NvbG5H and NiMlKEcyX3NvbG5H together represent the 14 solutions of the original polynomial system NiMlIkZH .F;

NiM3JSwqKiRJInhHNiIiIiMiIiUqJkYmIiIiSSJ5R0YnRihGK0kiekdGJyEiIiNGK0YpRissKEYmRigqJkYsRihGLUYrRisjRitGKEYrLCgqJkYmRihGLUYrRitGJiNGLkYoKiRGLEYoRi4=

Check the solutions.seq( eval(F, G1_soln[i]), i=1..nops([G1_soln]) );

NiQ3JSIiIUYkRiRGIw==

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

Ni43JSQiJWtHISM1JCEkKyNGJiQiIichIilGIzclJCIkUSJGJiQhJFMiRiYkIiQvIkYmRiw3JV4kJCIlUUtGJiQhIyQpISIqXiQkISR6JUY5JCElS2tGJl4kJCIlUGJGJiQiJHgnRiZGMzclXiQkIiRFIkY5JCIjO0Y5XiQkIiZMKD4hIzYkISNhRjleJCQiJEwpRiYkIiRGJkYmRkQ3JV4kRkYkISM7RjleJEZLJCIjYUY5XiRGUSQhJEYmRiZGVTclXiRGNSQiIyQpRjleJEY7JCIlS2tGJl4kRkAkISR4J0YmRmlu

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.

[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.