<?xml version="1.0" encoding="utf-8" ?> <!-- for emacs: -*- coding: utf-8 -*- -->
<!-- Apache may like this line in the file .htaccess: AddCharset utf-8 .html -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" >
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head><title>computing Groebner bases</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_normal_spforms.html">next</a> | <a href="_simple_sp__Groebner_spbasis_spcomputations_spover_spvarious_springs.html">previous</a> | forward | <a href="___Groebner_spbasis_spexamples_spand_spapplications.html">backward</a> | <a href="___Gröbner_spbases.html">up</a> | <a href="index.html">top</a> | <a href="master.html">index</a> | <a href="toc.html">toc</a> | <a href="http://www.math.uiuc.edu/Macaulay2/">Macaulay2 web site</a></div>
</td>
</tr>
</table>
<div><a href="index.html" title="">Macaulay2Doc</a> > <a href="___Gröbner_spbases.html" title="">Gröbner bases</a> > <a href="_computing_sp__Groebner_spbases.html" title="">computing Groebner bases</a></div>
<hr/>
<div><h1>computing Groebner bases</h1>
<div>Groebner bases are computed with the <tt>gb</tt> command; see <a href="_gb.html" title="compute a Gröbner basis">gb</a>. It returns an object of class <tt>GroebnerBasis</tt>.<table class="examples"><tr><td><pre>i1 : R = ZZ/1277[x,y];</pre>
</td></tr>
<tr><td><pre>i2 : I = ideal(x^3 - 2*x*y, x^2*y - 2*y^2 + x);
o2 : Ideal of R</pre>
</td></tr>
<tr><td><pre>i3 : g = gb I
o3 = GroebnerBasis[status: done; S-pairs encountered up to degree 5]
o3 : GroebnerBasis</pre>
</td></tr>
</table>
To get the polynomials in the Groebner basis, use <tt>gens</tt><table class="examples"><tr><td><pre>i4 : gens g
o4 = | y2+638x xy x2 |
1 3
o4 : Matrix R <--- R</pre>
</td></tr>
</table>
<p/>
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 <a href="___Degree__Limit.html" title="name for an optional argument">DegreeLimit</a>. (This is meaningful only in homogeneous cases.)<table class="examples"><tr><td><pre>i5 : R = ZZ/1277[x,y,z,w];</pre>
</td></tr>
<tr><td><pre>i6 : I = ideal(x*y-z^2,y^2-w^2);
o6 : Ideal of R</pre>
</td></tr>
<tr><td><pre>i7 : g2 = gb(I,DegreeLimit => 2)
o7 = GroebnerBasis[status: DegreeLimit; all S-pairs handled up to degree 2]
o7 : GroebnerBasis</pre>
</td></tr>
<tr><td><pre>i8 : gens g2
o8 = | y2-w2 xy-z2 |
1 2
o8 : Matrix R <--- R</pre>
</td></tr>
</table>
The result of the computation is stored internally, so when <tt>gb</tt>is called with a higher degree limit, only the additionally required computation is done.<table class="examples"><tr><td><pre>i9 : g3 = gb(I,DegreeLimit => 3);</pre>
</td></tr>
<tr><td><pre>i10 : gens g3
o10 = | y2-w2 xy-z2 yz2-xw2 |
1 3
o10 : Matrix R <--- R</pre>
</td></tr>
</table>
<p/>
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.<table class="examples"><tr><td><pre>i11 : g2
o11 = GroebnerBasis[status: DegreeLimit; all S-pairs handled up to degree 3]
o11 : GroebnerBasis</pre>
</td></tr>
<tr><td><pre>i12 : g2 === g3
o12 = true</pre>
</td></tr>
</table>
The option <a href="___Pair__Limit.html" title="name for an optional argument">PairLimit</a> 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.<table class="examples"><tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>i14 : gb(I,PairLimit => 2)
o14 = GroebnerBasis[status: PairLimit; all S-pairs handled up to degree 1]
o14 : GroebnerBasis</pre>
</td></tr>
<tr><td><pre>i15 : gb(I,PairLimit => 3)
o15 = GroebnerBasis[status: PairLimit; all S-pairs handled up to degree 2]
o15 : GroebnerBasis</pre>
</td></tr>
</table>
The option <a href="___Basis__Element__Limit.html" title="name for an optional argument">BasisElementLimit</a> can be used to stop after a certain number of basis elements have been found.<table class="examples"><tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>i17 : gb(I,BasisElementLimit => 2)
o17 = GroebnerBasis[status: BasisElementLimit; all S-pairs handled up to degree 1]
o17 : GroebnerBasis</pre>
</td></tr>
<tr><td><pre>i18 : gb(I,BasisElementLimit => 3)
o18 = GroebnerBasis[status: BasisElementLimit; all S-pairs handled up to degree 2]
o18 : GroebnerBasis</pre>
</td></tr>
</table>
The option <a href="___Codimension__Limit.html" title="name for an optional argument">CodimensionLimit</a> 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.<p/>
The option <a href="___Subring__Limit.html" title="stop after finding enough elements of a subring">SubringLimit</a> 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 <tt>Eliminate n</tt> the subring consists of those polynomials not involving any of the first <tt>n</tt> variables. For <tt>Lex</tt> the subring consists of those polynomials not involving the first variable. For <tt>ProductOrder {m,n,p}</tt> the subring consists of those polynomials not involving the first <tt>m</tt> variables.<p/>
Here is an example where we are satisfied to find one relation from which the variable <tt>t</tt> has been eliminated.<table class="examples"><tr><td><pre>i19 : R = ZZ/1277[t,F,G,MonomialOrder => Eliminate 1];</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
</table>
<p/>
Sometimes a Groebner basis computation can seem to last forever. An ongoing visual display of its progress can be obtained with <a href="_gb__Trace.html" title="provide tracing output during various computations in the engine.">gbTrace</a>.<table class="examples"><tr><td><pre>i22 : gbTrace = 3
o22 = 3</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>i24 : gb I
-- registering gb 6 at 0x933e260
-- [gb]{2}(2)mm{3}(1)m{4}(2)om{5}(1)o
-- number of (nonminimal) gb elements = 4
-- number of monomials = 8
-- ncalls = 0
-- nloop = 0
-- nsaved = 0
--
o24 = GroebnerBasis[status: done; S-pairs encountered up to degree 4]
o24 : GroebnerBasis</pre>
</td></tr>
</table>
Here is what the tracing symbols indicate.<pre> {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</pre>
<p/>
Let's turn off the tracing.<table class="examples"><tr><td><pre>i25 : gbTrace = 0
o25 = 0</pre>
</td></tr>
</table>
<p/>
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 <tt>StopBeforeComputation => true</tt>. It will stop immediately, and return a Groebner basis object that can be inspected with <a href="_generators.html" title="provide matrix or list of generators">generators</a> or <a href="_syz.html" title="the syzygy matrix">syz</a>. The computation can be continued later.<table class="examples"><tr><td><pre>i26 : R = ZZ/1277[x..z];</pre>
</td></tr>
<tr><td><pre>i27 : I = ideal(x*y+y*z, y^2, x^2);
o27 : Ideal of R</pre>
</td></tr>
<tr><td><pre>i28 : g = gb(I, StopBeforeComputation => true)
o28 = GroebnerBasis[status: not started; all S-pairs handled up to degree -1]
o28 : GroebnerBasis</pre>
</td></tr>
<tr><td><pre>i29 : gens g
o29 = 0
1
o29 : Matrix R <--- 0</pre>
</td></tr>
</table>
<p/>
The function <a href="_force__G__B.html" title="declare that the columns of a matrix are a Gröbner basis">forceGB</a> 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.<p/>
If the Poincare polynomial (or Hilbert function) for a homogeneous submodule <tt>M</tt> 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 <tt>M.cache.poincare</tt>.<p/>
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.<table class="examples"><tr><td><pre>i30 : R = ZZ/1277[a..e];</pre>
</td></tr>
<tr><td><pre>i31 : T = (degreesRing R)_0
o31 = T
o31 : ZZ[T]</pre>
</td></tr>
<tr><td><pre>i32 : f = random(R^1,R^{-3,-3,-5,-6});
1 4
o32 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i33 : time betti gb f
-- used 0.290956 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</pre>
</td></tr>
</table>
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.<table class="examples"><tr><td><pre>i34 : remove(f.cache,{false,0})</pre>
</td></tr>
</table>
Now we provide the hint and compute the Groebner basis anew.<table class="examples"><tr><td><pre>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]</pre>
</td></tr>
<tr><td><pre>i36 : time betti gb f
-- used 0.004 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</pre>
</td></tr>
</table>
The computation turns out to be substantially faster.</div>
</div>
</body>
</html>
