# 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..z, w] 1277 i24 : gb I -- registering gb 5 at 0x7ff339412c40 -- [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.454409 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.00434345 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.