Macaulay2 » Documentation
Packages » Complexes :: Strategy for free resolutions via Schreyer-Lascala
next | previous | forward | backward | up | index | toc

Strategy for free resolutions via Schreyer-Lascala -- algorithm for computing free resolutions exploiting the Schreyer frame

Synopsis

Description

This is one of the algorithms in the engine of Macaulay2 for computing minimal free resolutions. This particular variant requires that the ring $S$ be commutative, and homogeneous over a base field.

This first example computes a minimal free resolution of the twisted cubic curve in projective $3$-space.

i1 : kk = ZZ/32003;
 
i2 : S = kk[a..d];
 
i3 : I = ideal(b^2-a*c, b*c - a*d, c^2-b*d)

             2                    2
o3 = ideal (b  - a*c, b*c - a*d, c  - b*d)

o3 : Ideal of S
 
i4 : M = S^1/I

o4 = cokernel | b2-ac bc-ad c2-bd |

                            1
o4 : S-module, quotient of S
 
i5 : F = freeResolution(M, Strategy => 0)

      1      3      2
o5 = S  <-- S  <-- S
                    
     0      1      2

o5 : Complex
 
i6 : dd^F

          1                             3
o6 = 0 : S  <------------------------- S  : 1
               | c2-bd bc-ad b2-ac |

          3                     2
     1 : S  <----------------- S  : 2
               {2} | -b a  |
               {2} | c  -b |
               {2} | -d c  |

o6 : ComplexMap
 
i7 : betti F

            0 1 2
o7 = total: 1 3 2
         0: 1 . .
         1: . 3 2

o7 : BettiTally
 
i8 : assert isWellDefined F
 
i9 : assert(isQuasiIsomorphism augmentationMap F)

When the input is an ideal $I$, the free resolution of $S^1/I$ is returned.

i10 : F1 = freeResolution(I, Strategy => 0)

       1      3      2
o10 = S  <-- S  <-- S
                     
      0      1      2

o10 : Complex
 
i11 : assert(F1 == F)
 
i12 : F2 = freeResolution(module I, Strategy => 0)

       3      2
o12 = S  <-- S
              
      0      1

o12 : Complex
 
i13 : dd^F1

           1                             3
o13 = 0 : S  <------------------------- S  : 1
                | c2-bd bc-ad b2-ac |

           3                     2
      1 : S  <----------------- S  : 2
                {2} | -b a  |
                {2} | c  -b |
                {2} | -d c  |

o13 : ComplexMap
 
i14 : dd^F2

           3                     2
o14 = 0 : S  <----------------- S  : 1
                {2} | d  c  |
                {2} | -c -b |
                {2} | b  a  |

o14 : ComplexMap

This strategy also works when the underlying ring is a homogeneous quotient.

i15 : R = S/(a^3, b^3, c^3, d^3);
 
i16 : J = ideal(b^2-a*c, b*c - a*d, c^2-b*d + (b^2-a*c))

              2                    2          2
o16 = ideal (b  - a*c, b*c - a*d, b  - a*c + c  - b*d)

o16 : Ideal of R
 
i17 : M = R^1/J

o17 = cokernel | b2-ac bc-ad b2-ac+c2-bd |

                             1
o17 : R-module, quotient of R
 
i18 : C = freeResolution(M, Strategy => 0, LengthLimit => 8)

       1      3      5      15      36      68      114      175      255
o18 = R  <-- R  <-- R  <-- R   <-- R   <-- R   <-- R    <-- R    <-- R
                                                                      
      0      1      2      3       4       5       6        7        8

o18 : Complex
 
i19 : assert isWellDefined C
 
i20 : betti C

             0 1 2  3  4  5   6   7   8
o20 = total: 1 3 5 15 36 68 114 175 255
          0: 1 . .  .  .  .   .   .   .
          1: . 3 2  .  .  .   .   .   .
          2: . . 3  .  .  .   .   .   .
          3: . . . 15 18  .   .   .   .
          4: . . .  . 18 68  54   .   .
          5: . . .  .  .  .  60 175 120
          6: . . .  .  .  .   .   . 135

o20 : BettiTally

The first map in the resulting complex is not necessarily given by the generators of the ideal or the relations of the module.

i21 : dd^C_1

o21 = | c2-bd bc-ad b2-ac |

              1      3
o21 : Matrix R  <-- R
 
i22 : gens J

o22 = | b2-ac bc-ad b2-ac+c2-bd |

              1      3
o22 : Matrix R  <-- R
 
i23 : relations M

o23 = | b2-ac bc-ad b2-ac+c2-bd |

              1      3
o23 : Matrix R  <-- R

This strategy is an implementation of the algorithm in Roberto La Scala and Mike Stillman, Strategies for computing minimal free resolutions J. Symbolic Comput. 26 (1998), no.4, 409-431.

It uses the Schreyer algorithm for free resolutions, including using induced (Schreyer) monomial orders on the free modules in the resolution, together with a method to minimize the resolution appearing in the above paper.

Both strategies 0 and 1 are implementations of this algorithm, however they use slightly different internal data structures. Moreover, strategy 0 precomputes a Groebner basis for the presentation of the module. In contrast, strategy 1 obtains the Groebner basis as part of the algorithm.

See also