next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Macaulay2Doc > rings > monomial orderings > monomial orders for free modules > Schreyer orders

Schreyer orders -- induced monomial order on a free module

The Schreyer order is a monomial order on a free module that is particularly efficient for computing Gröbner bases and syzygies. The size of Gröbner bases of submodules using such orders is often much much smaller than if a position over term or term over position order would be used. We call these Schreyer orders, after Frank-Olaf Schreyer, who used them to give an algorithm for syzygies, and who also recognized many of their beneficial properties. See [S1] and [S2] for the algorithm, and [LS] for improvements and details on the implementation in Macaulay2

Given a free R-module G, a set of monomials m0, ..., ms-1 of G, and a monomial order on the monomials of G, the induced order, or, Schreyer order on F = Rs is defined by: a Fi > b Fj (in F) iff a mi > b mj (in G), or a mi and b mj are scalar multiples of each other, and i>j, where Fi are the unit column vectors of F. Typically the monomials m0, ..., ms-1 are the initial monomials of a Gröbner basis of a submodule of G.

In Macaulay2, free modules with a Schreyer order on them can be created using schreyerOrder(Matrix).

i1 : R = ZZ/101[a..f];
i2 : m = matrix{{a,b,c,d}};

             1       4
o2 : Matrix R  <--- R
i3 : m1 = schreyerOrder m

o3 = | a b c d |

             1       4
o3 : Matrix R  <--- R
i4 : F = source m1

      4
o4 = R

o4 : R-module, free, degrees {4:1}
i5 : g = syz m1

o5 = {1} | -b 0  -c 0  0  -d |
     {1} | a  -c 0  0  -d 0  |
     {1} | 0  b  a  -d 0  0  |
     {1} | 0  0  0  c  b  a  |

             4       6
o5 : Matrix R  <--- R
i6 : leadTerm g

o6 = {1} | 0 0 0 0 0 0 |
     {1} | a 0 0 0 0 0 |
     {1} | 0 b a 0 0 0 |
     {1} | 0 0 0 c b a |

             4       6
o6 : Matrix R  <--- R
In Macaulay2, free modules are displayed without any indication of whether they are endowed with a Schreyer order or not. To determine whether one is, use schreyerOrder(Module). If the result is the zero matrix, then the monomial order associated with this free module is not a Schreyer order. In that case, the monomial order for the free module is the one determined directly from the ring.
i7 : schreyerOrder target m

o7 = 0

                    1
o7 : Matrix 0 <--- R
i8 : schreyerOrder source g

o8 = 0

                    6
o8 : Matrix 0 <--- R
Over quotient rings, the multiplications a mi and b mj are over the ambient polynomial ring, not the quotient.

It is fine for the free module G above to be endowed with a Schreyer order too.

The only places that Schreyer orders are considered is in computation of Gröbner bases, syzygies, and free resolutions, and with the leadTerm routine.

The size of the Gröbner bases of syzygy modules is often dramatically smaller if the monomial order is the Schreyer order, as in the following example.

i9 : R = QQ[a..f];
i10 : I = ideal"abc-def,a2c-d2f,aef-bcd,a3-d3,af2-cd2"

                             2     2                     3    3       2  
o10 = ideal (a*b*c - d*e*f, a c - d f, - b*c*d + a*e*f, a  - d , - c*d  +
      -----------------------------------------------------------------------
         2
      a*f )

o10 : Ideal of R
i11 : F = syz gens I

o11 = {3} | a2+ad+d2 bcd-aef cd2+a2f+d2f a2b+bd2+ade a3-d3    0       
      {3} | 0        0       aef-def     abe-bde     0        a3-d3   
      {3} | a2+ad+d2 abc-def acd+adf+d2f abd+bd2+d2e 0        0       
      {3} | -bc-ef   0       -bcf-cef    -b2c-bce    -abc+def -a2c+d2f
      {3} | 0        0       0           0           0        0       
      -----------------------------------------------------------------------
      acd-acf          a2c-a2f+acf-d2f  -a2f+acf         a2d-a2f         
      -bcd-ace+bcf+aef ace-bcf-aef+def  abc+ace-bcf-aef  -a2e+ade        
      d2f-df2          cd2-adf-d2f+df2  cd2-adf-d2f+df2  d3-d2f          
      c2e-cef          -bc2-c2e+bcf+cef -bc2-c2e+bcf+cef -bcd+ace-cde+bcf
      -cde+def         cde-def          cde-def          -ade+d2e        
      -----------------------------------------------------------------------
      a2e+bdf+aef d3-d2f   0        0        0       cd2-af2 0       ad2-adf 
      ae2-bef     a2e-d2e  -ade+abf 0        a2c-df2 0       cd2-af2 -ade+bdf
      ade+d2e+abf ad2-adf  -d3+d2f  -cd2+af2 0       0       0       0       
      -bce-ce2    -ace+ef2 cde-bcf  0        -ac2+f3 0       0       cde-bf2 
      -abe+de2    -a2e+ade bd2-d2e  bcd-aef  acd-a2f abc-def a2c-d2f a2b-d2e 
      -----------------------------------------------------------------------
      0       abc2-def2  ac2f-df3            ab2c+bdef+ae2f     cdef-bcf2 |
      0       -b2c2+e2f2 ac2e-bc2f-acef+ef3  -b3c+abe2+ae3-be2f 0         |
      0       bcdf-acef  cdf2-af3            bd2e+d2e2+b2df     -bc2d+ef3 |
      cd2-af2 0          -c3e+c2ef           -bce2-ce3          0         |
      a3-d3   0          c2de-acef-cdef+aef2 -b2de+de3          b2c2-e2f2 |

              5       23
o11 : Matrix R  <--- R
i12 : betti gens gb syz F

              0  1
o12 = total: 23 67
          5:  1  .
          6: 18 19
          7:  4 27
          8:  .  8
          9:  .  8
         10:  .  5

o12 : BettiTally
i13 : G = schreyerOrder F

o13 = {3} | a2+ad+d2 bcd-aef cd2+a2f+d2f a2b+bd2+ade a3-d3    0       
      {3} | 0        0       aef-def     abe-bde     0        a3-d3   
      {3} | a2+ad+d2 abc-def acd+adf+d2f abd+bd2+d2e 0        0       
      {3} | -bc-ef   0       -bcf-cef    -b2c-bce    -abc+def -a2c+d2f
      {3} | 0        0       0           0           0        0       
      -----------------------------------------------------------------------
      acd-acf          a2c-a2f+acf-d2f  -a2f+acf         a2d-a2f         
      -bcd-ace+bcf+aef ace-bcf-aef+def  abc+ace-bcf-aef  -a2e+ade        
      d2f-df2          cd2-adf-d2f+df2  cd2-adf-d2f+df2  d3-d2f          
      c2e-cef          -bc2-c2e+bcf+cef -bc2-c2e+bcf+cef -bcd+ace-cde+bcf
      -cde+def         cde-def          cde-def          -ade+d2e        
      -----------------------------------------------------------------------
      a2e+bdf+aef d3-d2f   0        0        0       cd2-af2 0       ad2-adf 
      ae2-bef     a2e-d2e  -ade+abf 0        a2c-df2 0       cd2-af2 -ade+bdf
      ade+d2e+abf ad2-adf  -d3+d2f  -cd2+af2 0       0       0       0       
      -bce-ce2    -ace+ef2 cde-bcf  0        -ac2+f3 0       0       cde-bf2 
      -abe+de2    -a2e+ade bd2-d2e  bcd-aef  acd-a2f abc-def a2c-d2f a2b-d2e 
      -----------------------------------------------------------------------
      0       abc2-def2  ac2f-df3            ab2c+bdef+ae2f     cdef-bcf2 |
      0       -b2c2+e2f2 ac2e-bc2f-acef+ef3  -b3c+abe2+ae3-be2f 0         |
      0       bcdf-acef  cdf2-af3            bd2e+d2e2+b2df     -bc2d+ef3 |
      cd2-af2 0          -c3e+c2ef           -bce2-ce3          0         |
      a3-d3   0          c2de-acef-cdef+aef2 -b2de+de3          b2c2-e2f2 |

              5       23
o13 : Matrix R  <--- R
i14 : betti gens gb syz G     

              0  1
o14 = total: 23 45
          5:  1  .
          6: 18 19
          7:  4 22
          8:  .  4

o14 : BettiTally

See also