# Solving a nonlinear system using Groebner basis computations

I have discovered that Groebner basis computations may help in a problem I am working on. However, I am having some very specific problems. First, the literature I have discovered on Groebner basis calculations are either extremely advanced or sacrifice completeness for simplicity. Secondly, to come to grips with these methods I have tried working with computer algebra systems (specifically Macaulay 2, version 1.2) to wade through examples.

Therein, my problem has a similar flavor to this post (I found the answers moderately helpful). One of the answers to this question provides an example of a computation that works out correctly - I cannot get Macaulay to behave the same way on a randomly selected toy problem.

It is my understanding that Groebner basis methods are an infallible way to find solutions to nonlinear systems of equations over any field (barring some issues with numerical stability and computational complexity). That is, it is my understanding that Groebner basis computations will always reduce a system of equations to an equivalent system in which there exist polynomials of one variable (and that solving the system can proceed from finding roots to this one polynomial and then "steamroll" the rest).

I believe I have followed the steps necessary to get a system of nonlinear equations into its Groebner basis form. However, I do not see a clear means of finding solutions to my system. Here is my Macaulay 2 history.

i29 : T = ZZ[f,g,h]

o29 = T

o29 : PolynomialRing

i32 : Woot = gb ideal(f^2*g + g^2*h + 2*h^2, f + g + h, f^3*g^2*h) o32 = GroebnerBasis[status: done; S-pairs encountered up to degree 9]

o32 : GroebnerBasis

i33 : ideal gens Woot

o33 = ideal ($f+g+h$, $g^3+3g^2h+g*h^2+2h^2$, $8g*h^5+4h^6-8h^5$, $5g^2h^4+2g*h^5+2g^2h^3+4h^5$, $4h^7+2g^2h^4+4g*h^5+24h^6-12g^2h^3+40h^5$, $g*h^6+g^2h^4+4g*h^5-2h^6+2g^2h^3-8h^5$, $g^2h^5+2g^2h^4+4g*h^5+4h^6$

None of these are univariate. (This particular system of equations is not important to me - I just used them as an example).

Have I chosen a bad monomial ordering? (Is it possible to compute an "unhelpful" Goebner basis if you have a bad monomial ordering?) Have I run the wrong commands through Macaulay? Is my understanding of Groebner basis misinformed? How would I solve this system of equations with Groebner basis reduction?

-

Usually, if you want to solve the system, you use something closer to the lexicographical ordering, which gives triangular Groebner bases:

i1 : T = ZZ[f,g,h, MonomialOrder => Lex]

o1 = T

o1 : PolynomialRing


After this, the rest is just the same as what you did:

i2 : Woot = gb ideal(f^2*g + g^2*h + 2*h^2, f + g + h, f^3*g^2*h)

o2 = GroebnerBasis[status: done; S-pairs encountered up to degree 10]

o2 : GroebnerBasis

i3 : ideal gens Woot

8      7      6      5      5     6     5     7       6       5     7     6     5    2 3       6       5     7
o3 = ideal (4h  + 24h  + 48h  + 32h , 8g*h  + 4h  - 8h , g*h  + 4g*h  + 4g*h  - 2h  - 8h  - 8h , 8g h  - 3g*h  + 2g*h  - 4h  -
-------------------------------------------------------------------------------------------------------------------------
6      5   2 4     2 3      6       5     6     5   3     2       2     2
10h  - 28h , g h  + 2g h  + g*h  + 4g*h  - 2h  - 8h , g  + 3g h + g*h  + 2h , f + g + h)

o3 : Ideal of T


Incidentally, the order in which you order the variables is quite important (but I think no one knows how to pick it, so you have to try a bit...) For example, if I change the order in this example, I get a considerably simpler triangular system:

i12 : T = ZZ[g,h,f, MonomialOrder => Lex]

o12 = T

o12 : PolynomialRing

i13 : ideal gens gb ideal(f^2*g + g^2*h + 2*h^2, f + g + h, f^3*g^2*h)

8      5     7     7       6    8    2 3      5    6   2 5      6       5     7   3     2      2    3
o13 = ideal (4f , 4h*f  + 4f , h*f  + 2h*f  + f , 2h f  - h*f  - f , h f  - h*f  + 2h*f  + 2f , h  + 2h f + 2h  - f , g + h +
------------------------------------------------------------------------------------------------------------------------
f)

o13 : Ideal of T


One can solve it almost mentally now :)

-
Wow, thank you for this. I will rush to apply this to the problem I am trying to solve. – user6213 Jan 25 '11 at 4:49
Hmm, I now get the results that you do for this system. However, for another (quite different) system I do not get a triangular Groebner basis. – user6213 Jan 25 '11 at 4:58
@Jason, it is impossible to say anything without seeing the system... – Mariano Suárez-Alvarez Jan 25 '11 at 5:00
@Jason: use Cramer's formula for the system, viewed as a linear system of equations for $a$, $b$, $c$ and $d$. That will give you formulas for $a$, $b$, $c$, $d$ in terms of $x$, $y$, $z$, $w$. When $(x,y,z,w)$ is real and non zero, that is the only solution; a bit of linear algebra should give you the remaining solutions. If you solve for $x$, $y$, $z$, $w$ in terms of $a$, $b$, $c$, $d$, exactly the same thing happens. – Mariano Suárez-Alvarez Jan 25 '11 at 5:08
I will investigate Cramer's formula - thank you for the tip. It is important to note that I consider a,b,c,d and w,x,y,z to be variables and furthermore integral variables. – user6213 Jan 25 '11 at 5:12