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 0x7c95d2cf2a80
-- [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
gens 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.24386 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 : poincare cokernel f = (1-T^3)*(1-T^3)*(1-T^5)*(1-T^6) -- cache poincare
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.00342635 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.