next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Macaulay2Doc > Gröbner bases > computing Groebner bases

computing Groebner bases

Groebner bases are computed with the gb command; see gb. It returns an object of class GroebnerBasis.
i1 : R = ZZ/1277[x,y];
i2 : I = ideal(x^3 - 2*x*y, x^2*y - 2*y^2 + x);

o2 : Ideal of R
i3 : g = gb I

o3 = GroebnerBasis[status: done; S-pairs encountered up to degree 8]

o3 : GroebnerBasis
To get the polynomials in the Groebner basis, use gens
i4 : gens g

o4 = | y2+638x xy x2 |

             1       3
o4 : Matrix R  <--- R

How do we control the computation of Groebner bases? If we are working with homogeneous ideals, we may stop the computation of a Groebner basis after S-polynomials up to a certain degree have been handled, with the option DegreeLimit. (This is meaningful only in homogeneous cases.)

i5 : R = ZZ/1277[x,y,z,w];
i6 : I = ideal(x*y-z^2,y^2-w^2);

o6 : Ideal of R
i7 : g2 = gb(I,DegreeLimit => 2)

o7 = GroebnerBasis[status: DegreeLimit; all S-pairs handled up to degree 2]

o7 : GroebnerBasis
i8 : gens g2

o8 = | y2-w2 xy-z2 |

             1       2
o8 : Matrix R  <--- R
The result of the computation is stored internally, so when gb is called with a higher degree limit, only the additionally required computation is done.
i9 : g3 = gb(I,DegreeLimit => 3);
i10 : gens g3

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

              1       3
o10 : Matrix R  <--- R

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.

i11 : g2

o11 = GroebnerBasis[status: DegreeLimit; all S-pairs handled up to degree 3]

o11 : GroebnerBasis
i12 : g2 === g3

o12 = 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.
i13 : I = ideal(x*y-z^2,y^2-w^2)

                    2   2    2
o13 = ideal (x*y - z , y  - w )

o13 : Ideal of R
i14 : gb(I,PairLimit => 2)

o14 = GroebnerBasis[status: PairLimit; all S-pairs handled up to degree 1]

o14 : GroebnerBasis
i15 : gb(I,PairLimit => 3)

o15 = GroebnerBasis[status: PairLimit; all S-pairs handled up to degree 2]

o15 : GroebnerBasis
The option BasisElementLimit can be used to stop after a certain number of basis elements have been found.
i16 : I = ideal(x*y-z^2,y^2-w^2)

                    2   2    2
o16 = ideal (x*y - z , y  - w )

o16 : Ideal of R
i17 : gb(I,BasisElementLimit => 2)

o17 = GroebnerBasis[status: BasisElementLimit; all S-pairs handled up to degree 1]

o17 : GroebnerBasis
i18 : gb(I,BasisElementLimit => 3)

o18 = GroebnerBasis[status: BasisElementLimit; all S-pairs handled up to degree 2]

o18 : 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.

i19 : R = ZZ/1277[t,F,G,MonomialOrder => Eliminate 1];
i20 : I = ideal(F - (t^3 + t^2 + 1), G - (t^4 - t))

                3    2             4
o20 = ideal (- t  - t  + F - 1, - t  + t + G)

o20 : Ideal of R
i21 : transpose gens gb (I, SubringLimit => 1)

o21 = {-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
o21 : 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.

i22 : gbTrace = 3

o22 = 3
i23 : I = ideal(x*y-z^2,y^2-w^2)

                    2   2    2
o23 = ideal (x*y - z , y  - w )

                ZZ
o23 : Ideal of ----[x, y, z, w]
               1277
i24 : gb I

   -- registering gb 5 at 0x555559b4e380

   -- [gb]{2}(2)mm{3}(1)m{4}(2)om{5}(1)onumber of (nonminimal) gb elements = 4
   -- number of monomials                = 8
   -- #reduction steps = 2
   -- #spairs done = 6
   -- ncalls = 0
   -- nloop = 0
   -- nsaved = 0
   -- 
o24 = GroebnerBasis[status: done; S-pairs encountered up to degree 4]

o24 : 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.

i25 : gbTrace = 0

o25 = 0

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 generators or syz. The computation can be continued later.

i26 : R = ZZ/1277[x..z];
i27 : I = ideal(x*y+y*z, y^2, x^2);

o27 : Ideal of R
i28 : g = gb(I, StopBeforeComputation => true)

o28 = GroebnerBasis[status: not started; all S-pairs handled up to degree -1]

o28 : GroebnerBasis
i29 : gens g

o29 = 0

              1
o29 : Matrix R  <--- 0

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

i30 : R = ZZ/1277[a..e];
i31 : T = (degreesRing R)_0

o31 = T

o31 : ZZ[T]
i32 : f = random(R^1,R^{-3,-3,-5,-6});

              1       4
o32 : Matrix R  <--- R
i33 : time betti gb f
     -- used 0.205138 seconds

             0  1
o33 = 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

o33 : BettiTally
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.
i34 : remove(f.cache,{false,0})
Now we provide the hint and compute the Groebner basis anew.
i35 : (cokernel f).cache.poincare = (1-T^3)*(1-T^3)*(1-T^5)*(1-T^6)

            3    5     8     9    12     14    17
o35 = 1 - 2T  - T  + 2T  + 2T  - T   - 2T   + T

o35 : ZZ[T]
i36 : time betti gb f
     -- used 0.00258165 seconds

             0  1
o36 = 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

o36 : BettiTally
The computation turns out to be substantially faster.