computing Groebner bases

computing Groebner bases

In this section we give some more detail about how to control the computation of Groebner bases.

We may stop the computation of a homogeneous Groebner basis after S-polynomials up to a certain degree have been handled with the DegreeLimit option. (This is meaningful only in homogeneous situations.) Certains statistics about the suspended computation can be displayed with summary.

i1 : R = ZZ/101[x,y,z,w];

i2 : I = ideal(x*y-z^2,y^2-w^2)



                   2   2    2

o2 = ideal (x*y - z , y  - w )



o2 : Ideal of R

i3 : g2 = gb(I,DegreeLimit => 2)



o3 = | y2-w2 xy-z2 |



o3 : GroebnerBasis

i4 : summary g2

# pairs computed = 2

i5 : g3 = gb(I,DegreeLimit => 3)



o5 = | y2-w2 xy-z2 yz2-xw2 |



o5 : GroebnerBasis

i6 : summary g3

# pairs computed = 3

The computation advanced further with the higher degree limit.

The second computation advances the state of the Groebner basis object started by the first, and the two results are exactly the same Groebner basis object.

i7 : g2



o7 = | y2-w2 xy-z2 yz2-xw2 |



o7 : GroebnerBasis

i8 : g2 === g3



o8 = true

The option PairLimit can be used to stop after a certain number of S-polynomials have been reduced. After being reduced, the S-polynomial is added to the basis, or a syzygy has been found.

i9 : I = ideal(x*y-z^2,y^2-w^2)



                   2   2    2

o9 = ideal (x*y - z , y  - w )



o9 : Ideal of R

i10 : gb(I,PairLimit => 2)



o10 = | y2-w2 xy-z2 |



o10 : GroebnerBasis

i11 : gb(I,PairLimit => 3)



o11 = | y2-w2 xy-z2 yz2-xw2 |



o11 : GroebnerBasis

The option BasisElementLimit can be used to stop after a certain number of basis elements have been found.

i12 : I = ideal(x*y-z^2,y^2-w^2)



                    2   2    2

o12 = ideal (x*y - z , y  - w )



o12 : Ideal of R

i13 : gb(I,BasisElementLimit => 2)



o13 = | y2-w2 xy-z2 |



o13 : GroebnerBasis

i14 : gb(I,BasisElementLimit => 3)



o14 = | y2-w2 xy-z2 yz2-xw2 |



o14 : GroebnerBasis

The option CodimensionLimit can be used to stop after the apparent codimension, as gauged by the leading terms of the basis elements found so far, reaches a certain number.

The option SubringLimit can be used to stop after a certain number of basis elements in a subring have been found. The subring is determined by the monomial ordering in use. For Eliminate n the subring consists of those polynomials not involving any of the first n variables. For Lex the subring consists of those polynomials not involving the first variable. For ProductOrder {m,n,p} the subring consists of those polynomials not involving the first m variables.

Here is an example where we are satisfied to find one relation from which the variable t has been eliminated.

i15 : R = ZZ/101[t,F,G,MonomialOrder => Eliminate 1];

i16 : I = ideal(F - (t^3 + t^2 + 1), G - (t^4 - t))



                3    2             4

o16 = ideal (- t  - t  + F - 1, - t  + t + G)



o16 : Ideal of R

i17 : transpose gens gb (I, SubringLimit => 1)



o17 = {-4} | F4-7F3-2F2G-4FG2-G3+18F2+3FG+6G2-21F-G+9 |

      {-3} | tG2-tF+6tG+5t-F3+3F2+3FG+3G2+G-2         |

      {-3} | tFG+tF-4tG-3t+F2-FG-G2-4F-G+3            |

      {-3} | tF2-4tF+tG+5t-F2-FG+3F+3G-2              |

      {-2} | t2+tF-2t-F-G+1                           |



              5       1

o17 : Matrix R  <--- R

Sometimes a Groebner basis computation can seem to last forever. An ongoing visual display of its progress can be obtained with gbTrace.

i18 : gbTrace 3



o18 = 0

i19 : I = ideal(x*y-z^2,y^2-w^2)



                    2   2    2

o19 = ideal (x*y - z , y  - w )



                ZZ

o19 : Ideal of --- [x, y, z, w]

               101

i20 : gb I

{2}(0)gg{3}(1)m{4}(2)om{5}(1)o



o20 = | y2-w2 xy-z2 yz2-xw2 z4-x2w2 |



o20 : GroebnerBasis

Here is what the tracing symbols indicate.

         {2}   ready to reduce S-polynomials of degree 2
         (0)   there are 0 more S-polynomials (the basis is empty)
          g    the generator yx-z2 has been added to the basis
          g    the generator y2-w2 has been added to the basis
         {3}   ready to reduce S-polynomials of degree 3
         (1)   there is 1 more S-polynomial
          m    the reduced S-polynomial yz2-xw2 has been added to the basis
         {4}   ready to reduce S-polynomials of degree 4
         (2)   there are 2 more S-polynomials
          m    the reduced S-polynomial z4-x2w2 has been added to the basis
          o    an S-polynomial reduced to zero and has been discarded
         {5}   ready to reduce S-polynomials of degree 5
         (1)   there is 1 more S-polynomial
          o    an S-polynomial reduced to zero and has been discarded

Let's turn off the tracing.

i21 : gbTrace 0



o21 = 3

Each of the operations dealing with Groebner bases may be interrupted or stopped (by typing CTRL-C). The computation is continued by re-issuing the same command. Alternatively, the command can be issued with the option StopBeforeComputation => true. It will stop immediately, and return a Groebner basis object that can be inspected with summary, gens or syz. The computation can be continued later.

The function forceGB can be used to create a Groebner basis object with a specified Groebner basis. No computation is performed to check whether the specified basis is a Groebner basis.

If the Poincare polynomial (or Hilbert function) for a homogeneous submodule M is known, you can speed up the computation of a Groebner basis by informing the system. This is done by storing the Poincare polynomial in M.poincare.

As an example, we compute the Groebner basis of a random ideal, which is almost certainly a complete intersection, in which case we know the Hilbert function already.

i22 : R = ZZ/101[a..e];

i23 : T = (degreesRing R)_0



o23 = $T



o23 : ZZ[ZZ^1]

i24 : f = random(R^1,R^{-3,-3,-5,-6});



              1       4

o24 : Matrix R  <--- R

i25 : time betti gb f

     -- used 2.8 seconds



o25 = total: 1 53

          0: 1  .

          1: .  .

          2: .  2

          3: .  1

          4: .  2

          5: .  3

          6: .  5

          7: .  5

          8: .  8

          9: .  9

         10: .  8

         11: .  6

         12: .  3

         13: .  1

The matrix was randomly chosen, and we'd like to use the same one again, but this time with a hint about the Hilbert function, so first we must erase the memory of the Groebner basis computed above.

i26 : remove(f.cache,{false,0})

Now we provide the hint and compute the Groebner basis anew.

i27 : (cokernel f).poincare = (1-T^3)*(1-T^3)*(1-T^5)*(1-T^6)



             3     5      8      9     12      14     17

o27 = 1 - 2$T  - $T  + 2$T  + 2$T  - $T   - 2$T   + $T



o27 : ZZ[ZZ^1]

i28 : time betti gb f

     -- used 0.79 seconds



o28 = total: 1 53

          0: 1  .

          1: .  .

          2: .  2

          3: .  1

          4: .  2

          5: .  3

          6: .  5

          7: .  5

          8: .  8

          9: .  9

         10: .  8

         11: .  6

         12: .  3

         13: .  1

The computation turns out to be substantially faster.