next | previous | forward | backward | up | top | index | toc | Macaulay2 website
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 $m_0, \ldots, m_{s-1}$ of $G$, and a monomial order on the monomials of $G$, the induced order, or, Schreyer order on $F = R^s$ is defined by: $a F_i > b F_j$ (in $F$) iff $a m_i > b m_j$ (in $G$), or $a m_i and b m_j$ are scalar multiples of each other, and $i>j$, where $F_i$ are the unit column vectors of $F$. Typically the monomials $m_0, \ldots, m_{s-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 m_i$ and $b m_j$ 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      2
o10 = ideal (a*b*c - d*e*f, a c - d f, - b*c*d + a*e*f, a  - d , - c*d  + 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        acd-acf          a2c-a2f+acf-d2f  -a2f+acf        
      {3} | 0        0       aef-def     abe-bde     0        a3-d3    -bcd-ace+bcf+aef ace-bcf-aef+def  abc+ace-bcf-aef 
      {3} | a2+ad+d2 abc-def acd+adf+d2f abd+bd2+d2e 0        0        d2f-df2          cd2-adf-d2f+df2  cd2-adf-d2f+df2 
      {3} | -bc-ef   0       -bcf-cef    -b2c-bce    -abc+def -a2c+d2f c2e-cef          -bc2-c2e+bcf+cef -bc2-c2e+bcf+cef
      {3} | 0        0       0           0           0        0        -cde+def         cde-def          cde-def         
      ---------------------------------------------------------------------------------------------------------------------------
      a2d-a2f          a2e+bdf+aef d3-d2f   0        0        0       cd2-af2 0       ad2-adf  0       abc2-def2 
      -a2e+ade         ae2-bef     a2e-d2e  -ade+abf 0        a2c-df2 0       cd2-af2 -ade+bdf 0       -b2c2+e2f2
      d3-d2f           ade+d2e+abf ad2-adf  -d3+d2f  -cd2+af2 0       0       0       0        0       bcdf-acef 
      -bcd+ace-cde+bcf -bce-ce2    -ace+ef2 cde-bcf  0        -ac2+f3 0       0       cde-bf2  cd2-af2 0         
      -ade+d2e         -abe+de2    -a2e+ade bd2-d2e  bcd-aef  acd-a2f abc-def a2c-d2f a2b-d2e  a3-d3   0         
      ---------------------------------------------------------------------------------------------------------------------------
      ac2f-df3            ab2c+bdef+ae2f     cdef-bcf2 |
      ac2e-bc2f-acef+ef3  -b3c+abe2+ae3-be2f 0         |
      cdf2-af3            bd2e+d2e2+b2df     -bc2d+ef3 |
      -c3e+c2ef           -bce2-ce3          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        acd-acf          a2c-a2f+acf-d2f  -a2f+acf        
      {3} | 0        0       aef-def     abe-bde     0        a3-d3    -bcd-ace+bcf+aef ace-bcf-aef+def  abc+ace-bcf-aef 
      {3} | a2+ad+d2 abc-def acd+adf+d2f abd+bd2+d2e 0        0        d2f-df2          cd2-adf-d2f+df2  cd2-adf-d2f+df2 
      {3} | -bc-ef   0       -bcf-cef    -b2c-bce    -abc+def -a2c+d2f c2e-cef          -bc2-c2e+bcf+cef -bc2-c2e+bcf+cef
      {3} | 0        0       0           0           0        0        -cde+def         cde-def          cde-def         
      ---------------------------------------------------------------------------------------------------------------------------
      a2d-a2f          a2e+bdf+aef d3-d2f   0        0        0       cd2-af2 0       ad2-adf  0       abc2-def2 
      -a2e+ade         ae2-bef     a2e-d2e  -ade+abf 0        a2c-df2 0       cd2-af2 -ade+bdf 0       -b2c2+e2f2
      d3-d2f           ade+d2e+abf ad2-adf  -d3+d2f  -cd2+af2 0       0       0       0        0       bcdf-acef 
      -bcd+ace-cde+bcf -bce-ce2    -ace+ef2 cde-bcf  0        -ac2+f3 0       0       cde-bf2  cd2-af2 0         
      -ade+d2e         -abe+de2    -a2e+ade bd2-d2e  bcd-aef  acd-a2f abc-def a2c-d2f a2b-d2e  a3-d3   0         
      ---------------------------------------------------------------------------------------------------------------------------
      ac2f-df3            ab2c+bdef+ae2f     cdef-bcf2 |
      ac2e-bc2f-acef+ef3  -b3c+abe2+ae3-be2f 0         |
      cdf2-af3            bd2e+d2e2+b2df     -bc2d+ef3 |
      -c3e+c2ef           -bce2-ce3          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