[Math] Solving a polynomial system using Groebner basis computations.

algebraic-geometrycomputer sciencecomputer-algebra-systemsgroebner-basis

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?

Best Answer

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 :)

Related Question