# source:git/Singular/LIB/schreyer.lib@b0ca43c

spielwiese
Last change on this file since b0ca43c was b0ca43c, checked in by Oleksandr Motsak <motsak@…>, 11 years ago
new global option for auto-testing the Syzygy property ("SYZCHECK") NOTE: it is On for now... TODO: disable later!
• Property mode set to `100644`
File size: 29.2 KB
Line
1//////////////////////////////////////////////////////////////////////////////
2version="\$Id\$";
3category="General purpose";
4info="
5LIBRARY: schreyer.lib     Helpers for working with the Schreyer induced ordering
6AUTHOR:  Oleksandr Motsak <U@D>, where U={motsak}, D={mathematik.uni-kl.de}
7
8PROCEDURES:
9 Sres(M,l)      Schreyer resolution of module M of maximal length l
10 Ssyz(M)        Schreyer resolution of module M of length 1
11 Scontinue(l)   continue the resolution computation by most l steps
12
13KEYWORDS:  syzygy; Schreyer induced ordering; Schreyer free resolution
14NOTE:  requires the dynamic module: syzextra
15";
16
17static proc prepareSyz( module I, list # )
18{
19  int i;
20  int k = 0;
21  int r = nrows(I);
22  int c = ncols(I);
23
24
25  if( size(#) > 0 )
26  {
27    if( typeof(#[1]) == "int" || typeof(#[1]) == "bigint" )
28    {
29      k = #[1];
30    }
31  }
32
33  if( k < r )
34  {
35    "// *** Wrong k: ", k, " < nrows: ", r, " => setting k = r = ", r;
36    k = r;
37  }
38
39//   "k: ", k;  "c: ", c;   "I: ", I;
40
41  for( i = c; i > 0; i-- )
42  {
43    I[i] = I[i] + gen(k + i);
44  }
45
46//  DetailedPrint(I);
47
48  return(I);
49}
50
51static proc separateSyzGB( module J, int c )
52{
53  module II, G; vector v; int i;
54
55  J = simplify(J, 2);
56
57  for( i = ncols(J); i > 0; i-- )
58  {
59    v = J[i];
60    if( leadcomp(v) > c )
61    {
62      II[i] = v;
63    } else
64    {
65      G[i] = v; // leave only gen(i): i <= c
66    }
67  }
68
69  II = simplify(II, 2);
70  G = simplify(G, 2);
71
72  return (list(G, II));
73}
74
75static proc splitSyzGB( module J, int c )
76{
77  module JJ; vector v, vv; int i;
78
79  for( i = ncols(J); i > 0; i-- )
80  {
81    v = J[i];
82
83    vv = 0;
84
85    while( leadcomp(v) <= c )
86    {
87      vv = vv + lead(v);
88      v  = v  - lead(v);
89    }
90
91    J[i] = vv;
92    JJ[i] = v;
93  }
94
95  J = simplify(J, 2);
96  JJ = simplify(JJ, 2);
97
98  return (list(J, JJ));
99}
100
101
102static proc Sinit(module M)
103{
104  def @save = basering;
105
106  int @DEBUG = !system("with", "ndebug");
107  if( @DEBUG )
108  {
109    "Sinit::Input";
110    type(M);
111    DetailedPrint(M);
112    attrib(M);
113  }
114
115  int @RANK = nrows(M); int @SIZE = ncols(M);
116
117  int @IS_A_SB = attrib(M, "isSB"); // ??? only if all weights were zero?!
118
119  if( !@IS_A_SB )
120  {
121    M = std(M); // this should be faster than computing std in S (later on)
122  }
123
124  def S = MakeInducedSchreyerOrdering(1); // 1 puts history terms to the back
125  // TODO: NOTE: +1 causes trouble to Singular interpreter!!!???
126  setring S; // a new ring with a Schreyer ordering
127
128  if( @DEBUG )
129  {
130    "Sinit::StartingISRing";
131    basering;
132//    DetailedPrint(basering);
133  }
134
135  // Setup the leading syzygy^{-1} module to zero:
136  module Z = 0; Z[@RANK] = 0; attrib(Z, "isHomog", intvec(0));
137
138  module MRES = Z;
139
140  list RES; RES[1] = Z;
141
142  module F = freemodule(@RANK);
143  intvec @V = deg(F[1..@RANK]);
144
145  module M = imap(@save, M);
146
147  attrib(M, "isHomog", @V);
148  attrib(M, "isSB", 1);
149
150
151  if( @DEBUG )
152  {
153    "Sinit::SB_Input: ";
154    type(M);
155    attrib(M);
156    attrib(M, "isHomog");
157    DetailedPrint(M);
158  }
159
160  if( @DEBUG )
161  {
162    // 0^th syz. property
163    if( size(module(transpose( transpose(M) * transpose(MRES) ))) > 0 )
164    {
165      transpose( transpose(M) * transpose(MRES) );
166      "transpose( transpose(M) * transpose(MRES) ) != 0!!!";
167      \$
168    }
169  }
170
171  RES[size(RES)+1] = M; // list of all syzygy modules
172  MRES = MRES, M;
173
174  attrib(MRES, "isHomog", @V);
175
177  attrib(S, "InducionStart", @RANK);
178
179  if( @DEBUG )
180  {
181    "Sinit::MRES";
182    DetailedPrint(MRES);
183    attrib(MRES, "isHomog");
184    attrib(S);
185  }
186
187  export RES;
188  export MRES;
189  return (S);
190}
191
192static proc Sstep()
193{
194  int @DEBUG = !system("with", "ndebug");
195
196  if( @DEBUG )
197  {
198    "Sstep::NextInducedRing";
199    DetailedPrint(basering);
200
202    attrib(basering, "InducionStart");
203
204    GetInducedData();
205  }
206
207  // syzygy step:
208
209/*
210  // is initial weights are all zeroes!
212  intvec @V = deg(M[1..ncols(M)]);  @W;  @V;  @W = @V;  attrib(L, "isHomog", @W);
213  SetInducedReferrence(L, @RANK, 0);
214*/
215
217//  @W = @W, @V;
218//  attrib(L, "isHomog", @W);
219
220
221  // General setting:
222//  SetInducedReferrence(MRES, 0, 0); // limit: 0!
223  int @l = size(RES);
224
225  module M = RES[@l];
226
227  module L = attrib(basering, "InducionLeads");
228  int limit = attrib(basering, "InducionStart");
229
230//  L;  limit;
231
232  int @RANK = ncols(MRES) - ncols(M); // nrows(M); // what if M is zero?!
233
234/*
235  if( @RANK !=  nrows(M) )
236  {
237    type(MRES);
238    @RANK;
239    type(M);
240    pause();
241  }
242*/
243
244  intvec @W = attrib(M, "isHomog");
245  intvec @V = deg(M[1..ncols(M)]);
246  @V = @W, @V;
247
248  if( @DEBUG )
249  {
250    "Sstep::NextInput: ";
251    M;
252    @V;
253    @RANK;
254    DetailedPrint(MRES);
255    attrib(MRES, "isHomog");
256  }
257
258
259
260  SetInducedReferrence(L, limit, 0);
261
262  def K = prepareSyz(M, @RANK);
263//  K;
264
265//   attrib(K, "isHomog", @V);   DetailedPrint(K, 1000);
266
267//  pause();
268
269  K = idPrepare(K, @RANK); // std(K); // ?
270  K = simplify(K, 2);
271
272//  K;
273
274  module N = separateSyzGB(K, @RANK)[2]; // 1^st syz. module: vectors which start in lower part (comp >= @RANK)
275  attrib(N, "isHomog", @V);
276
277// "N_0: "; N; DetailedPrint(N, 10);
278
279  N = std(N); // TODO: fix "wrong weights"!!!?
280  attrib(N, "isHomog", @V);
281
282//  N;
283
284  if( @DEBUG )
285  {
286    if( size(N) > 0 )
287    {
288      // next syz. property
289      if( size(module(transpose( transpose(N) * transpose(MRES) ))) > 0 )
290      {
291        MRES;
292
293        "N: "; N; DetailedPrint(N, 10);
294
295        "K:"; K; DetailedPrint(K, 10);
296
297        "RANKS: ", @RANK;
298
299        "transpose( transpose(N) * transpose(MRES) ) != 0!!!";
300        transpose( transpose(N) * transpose(MRES) );
301
302        "transpose(N) * transpose(MRES): ";
303        transpose(N) * transpose(MRES);
304        DetailedPrint(module(_), 2);
305        \$
306      }
307    }
308  }
309
310  RES[@l + 1] = N; // list of all syzygy modules
311
312  MRES = MRES, N;
313  attrib(MRES, "isHomog", @V);
314
315
318
319  if( @DEBUG )
320  {
321    "Sstep::NextSyzOutput: ";
322    DetailedPrint(N);
323    attrib(N, "isHomog");
324  }
325
326}
327
328proc Scontinue(int l)
329"USAGE:  Scontinue(l)
330RETURN:  nothing, instead it changes RES and MRES variables in the current ring
331PURPOSE: computes further (at most l) syzygies
332NOTE:    must be used within a ring returned by Sres or Ssyz. RES and MRES are
333         explained in Sres
334EXAMPLE: example Scontinue; shows an example
335"
336{
337  def data = GetInducedData();
338
339  if( (!defined(RES)) || (!defined(MRES)) || (typeof(data) != "list") || (size(data) != 2) )
340  {
341    ERROR("Sorry, but basering does not seem to be returned by Sres or Ssyz");
342  }
343  for (;  (l != 0) && (size(RES[size(RES)]) > 0); l-- )
344  {
345    Sstep();
346  }
347}
348example
349{ "EXAMPLE:"; echo = 2;
350  ring r;
351  module M = maxideal(1); M;
352  def S = Ssyz(M); setring S; S;
353  "Only the first syzygy: ";
354  RES; MRES;
355  "More syzygies: ";
356  Scontinue(10);
357  RES; MRES;
358}
359
360proc Ssyz(module M)
361"USAGE:  Ssyz(M)
362RETURN:  ring, containing a list of modules RES and a module MRES
363PURPOSE: computes the first syzygy module of M (wrt some Schreyer ordering)
364NOTE:    The output is explained in Sres
365EXAMPLE: example Ssyz; shows an example
366"
367{
368  def S = Sinit(M); setring S;
369
370  Sstep(); // NOTE: what if M is zero?
371
372  return (S);
373}
374example
375{ "EXAMPLE:"; echo = 2;
376  ring r;
377  module M = maxideal(1); M;
378  def S = Ssyz(M); setring S; S;
379  "Only the first syzygy: ";
380  RES;
381  MRES; // Note gen(i)
382  kill S;
383  setring r; kill M;
384
385  module M = 0;
386  def S = Ssyz(M); setring S; S;
387  "Only the first syzygy: ";
388  RES;
389  MRES;
390}
391
392proc Sres(module M, int l)
393"USAGE:  Sres(M, l)
394RETURN:  ring, containing a list of modules RES and a module MRES
395PURPOSE: computes (at most l) syzygy modules of M wrt the classical Schreyer
396         induced ordering with gen(i) > gen(j) if i > j, provided both gens
397         are from the same syzygy level.
398NOTE:    RES contains the images of maps subsituting the beginning of the
399         Schreyer free resolution of baseRing^r/M, while MRES is a sum of
400         these images in a big free sum, containing all the syzygy modules.
401         The syzygy modules are shifted so that gen(i) correspons to MRES[i].
402         The leading zero module RES[0] indicates the fact that coker of the
403         first map is zero. The number of zeroes inducates the rank of input.
404NOTE:    If l == 0 then l is set to be nvars(basering) + 1
405EXAMPLE: example Sres; shows an example
406"
407{
408  def S = Sinit(M); setring S;
409
410  if (l == 0)
411  {
412    l = nvars(basering) + 1; // not really an estimate...?!
413  }
414
415  Sstep(); l = l - 1;
416
417  Scontinue(l);
418
419  return (S);
420}
421example
422{ "EXAMPLE:"; echo = 2;
423  ring r;
424  module M = maxideal(1); M;
425  def S = Sres(M, 0); setring S; S;
426  RES;
427  MRES;
428  kill S;
429  setring r; kill M;
430
431  def A = nc_algebra(-1,0); setring A;
432  ideal Q = var(1)^2, var(2)^2, var(3)^2;
433  qring SCA = twostd(Q);
434  basering;
435
436  module M = maxideal(1);
437  def S = Sres(M, 2); setring S; S;
438  RES;
439  MRES;
440}
441
442
443
444// ================================================================== //
445
446
447LIB "general.lib"; // for sort
448
449// TODO: in C++!
450static proc Tail(def M)
451{
452  int i = ncols(M); def m;
453  while (i > 0)
454  {
455    m = M[i];
456
457    m = m - lead(m); // m = tail(m)
458
459    M[i] = m;
460
461    i--;
462  }
463  return (M);
464}
465
466/* static */ proc SSinit(def M)
467{
468  if( (typeof(M) != "module") && (typeof(M) != "ideal") )
469  {
470    ERROR("Sorry: need an ideal or a module for input");
471  }
472
473  // TODO! DONE?
474  def @save = basering;
475
476  int @DEBUG = !system("with", "ndebug");
477  int @SYZCHECK = 1 || @DEBUG; // TODO: only for now!!
478
479  if( @DEBUG )
480  {
481    "SSinit::Input";
482    type(M);
483//    DetailedPrint(M);
484    attrib(M);
485  }
486
487  int @RANK = nrows(M); int @SIZE = ncols(M);
488
489  int @IS_A_SB = attrib(M, "isSB"); // ??? only if all weights were zero?!
490
491  if( !@IS_A_SB )
492  {
493    def opts = option(get);
494    option(redSB); option(redTail);
495    M = std(M);
496    option(set, opts);
497    kill opts;
498  } else
499  {
500    M = simplify(M, 2 + 4 + 32);
501  }
502
504
505  // sort wrt neg.deg.rev.lex!
506  intvec iv_ds = sort(LEAD, "ds", 1)[2]; // ,1 => reversed!
507
508  M = M[iv_ds]; // sort M wrt ds on current leading terms
510
511  def TAIL = Tail(M);
512
513  intvec @DEGS = deg(M[1..@SIZE]); // store actuall degrees of input elements
514
515  // TODO: what about real modules? weighted ones?
516
517  list @l = ringlist(@save);
518
519  int @z = 0; ideal @m = maxideal(1); intvec @wdeg = deg(@m[1..ncols(@m)]);
520
521  // NOTE: @wdeg will be ignored anyway :(
522  @l[3] = list(list("C", @z), list("lp", @wdeg));
523
524  kill @z, @wdeg; // since these vars are ring independent!
525
526  def S = ring(@l); // --MakeInducedSchreyerOrdering(1);
527
528  module F = freemodule(@RANK);
529  intvec @V = deg(F[1..@RANK]);
530
531  setring S; // ring with an easy divisibility test ("C, lex")
532
533  if( @DEBUG )
534  {
535    "SSinit::NewRing(C, lex)";
536    basering;
537//    DetailedPrint(basering);
538  }
539
540  // Setup the leading syzygy^{-1} module to zero:
541  module Z = 0; Z[@RANK] = 0; attrib(Z, "isHomog", intvec(0));
542
543  module MRES = Z;
544
545  list RES;  RES[1] = Z;
546  list LRES; LRES[1] = Z;
547  list TRES; TRES[1] = Z;
548
549  def M = imap(@save, M);
550
551  attrib(M, "isHomog", @V);
552  attrib(M, "isSB", 1);
553  attrib(M, "degrees", @DEGS);
554
556
559
560  def TAIL = imap(@save, TAIL);
561
562  if( @DEBUG )
563  {
564    "SSinit::(sorted) SB_Input: ";
565    type(M);
566    attrib(M);
567    attrib(M, "isHomog");
568//    DetailedPrint(M);
569  }
570
571  if( @SYZCHECK )
572  {
573    // 0^th syz. property
574    if( size(module(transpose( transpose(M) * transpose(MRES) ))) > 0 )
575    {
576      transpose( transpose(M) * transpose(MRES) );
577      "ERROR: transpose( transpose(M) * transpose(MRES) ) != 0!!!";
578      \$
579    }
580  }
581
582  RES[size(RES)+1] = M; // list of all syzygy modules
583  LRES[size(LRES)+1] = LEAD; // list of all syzygy modules
584  TRES[size(TRES)+1] = TAIL; // list of all syzygy modules
585
586  MRES = MRES, M; //?
587
588  attrib(MRES, "isHomog", @V);
589
590//  attrib(S, "InducionStart", @RANK);
592  attrib(S, "TAILREDSYZ", 0);
593  attrib(S, "DEBUG", @DEBUG);
594  attrib(S, "SYZCHECK", @SYZCHECK);
595
596  if( @DEBUG )
597  {
598    "SSinit::MRES";
599    MRES;
600//    DetailedPrint(MRES);
601    attrib(MRES, "isHomog");
602    attrib(S);
603  }
604
605  export RES;
606  export MRES;
607  export LRES;
608  export TRES;
609  return (S);
610}
611example
612{ "EXAMPLE:"; echo = 2;
613  ring R = 0, (w, x, y, z), dp;
614
615  def M = maxideal(1);
616  def S = SSinit(M); setring S; S;
617
618  "Only the first initialization: ";
619  RES; LRES; TRES;
620  MRES;
621
622  kill S; setring R; kill M;
623
624  ideal M = w^2 - x*z,  w*x - y*z,  x^2 - w*y, x*y - z^2, y^2 - w*z;
625  def S = SSinit(M); setring S; S;
626
627  "Only the first initialization: ";
628  RES; LRES; TRES;
629  MRES;
630
631  kill S; setring R; kill M;
632}
633
634
635LIB "poly.lib"; // for lcm
636
637
638
639/// Compute L(Syz(L))
641{
642  if( typeof( attrib(basering, "DEBUG") ) == "int" )
643  {
644    int @DEBUG = attrib(basering, "DEBUG");
645  } else
646  {
647    int @DEBUG = !system("with", "ndebug");
648  }
649
650  if( @DEBUG )
651  {
653    L;
654  }
655
656  int i, j, r; intvec iv_ds;
657  int N = ncols(L);
658  def a, b;
659  poly aa, bb;
660
661  bigint c;
662
663  ideal M;
664
665  module S = 0;
666
667  for(i = 1; i <= N; i++)
668  {
669    a = L[i];
670//    "a: ", a;
672    r = int(c);
673
674    if(r > 0)
675    {
676      aa = a[r];
677    } else
678    {
679      aa = a;
680    }
681
682    M = 0;
683
684    for(j = i-1; j > 0; j--)
685    {
686      b = L[j];
687//      "b: ", b;
688
689      if( leadcomp(b) == c )
690      {
691        if(r > 0)
692        {
693          bb = b[r];
694        } else
695        {
696          bb = b;
697        }
698
699        M[j] = (lcm(aa, bb) / aa);
700      }
701    }
702
703    // TODO: add quotient relations here...
704
705    M = simplify(M, 1 + 2 + 32);
706
707    iv_ds = sort(M, "ds", 1)[2]; // ,1 => reversed!
708
709    M = M[iv_ds];
710
711    S = S, M * gen(i);
712  }
713
714  S = simplify(S, 2);
715
716  S = sort(S, "ds", 1)[1]; // ,1 => reversed! // TODO: not needed?
717
718  if( @DEBUG )
719  {
721    S;
722  }
723
724  attrib(S, "isSB", 1);
725
726  return (S);
727}
728
729/// Compute Syz(L), where L is a monomial (leading) module
731{
732  if( typeof( attrib(basering, "DEBUG") ) == "int" )
733  {
734    int @DEBUG = attrib(basering, "DEBUG");
735  } else
736  {
737    int @DEBUG = !system("with", "ndebug");
738  }
739
740  if( typeof( attrib(basering, "SYZCHECK") ) == "int" )
741  {
742    int @SYZCHECK = attrib(basering, "SYZCHECK");
743  } else
744  {
745    int @SYZCHECK = @DEBUG;
746  }
747
748
749  if( @DEBUG )
750  {
752    L;
753    "@TAILREDSYZ: ", @TAILREDSYZ;
754  }
755
756  int i, j, r;
757  int N = ncols(L);
758  def a, b;
759
760  poly aa, bb, @lcm;
761
762  bigint c;
763
764  module M;
765
766  module S = 0;
767
768  for(i = 1; i <= N; i++)
769  {
770    a = L[i];
771//    "a: ", a;
773    r = int(c);
774
776
777    M = 0;
778
779    for(j = i-1; j > 0; j--)
780    {
781      b = L[j];
782//      "b: ", b;
783
784      if( leadcomp(b) == c )
785      {
787        @lcm = lcm(aa, bb);
788
789        M[j] = (@lcm / aa)* gen(i) - (@lcm / bb)* gen(j);
790      }
791    }
792
793    M = simplify(M, 2);
794
795    // TODO: add quotient relations here...
796    S = S, M;
797  }
798
799  if( @TAILREDSYZ )
800  {
801    // Make sure that 2nd syzygy terms are not reducible by 1st
802    def opts = option(get);
803    option(redSB); option(redTail);
804    S = std(S); // binomial module
805    option(set, opts);
806    //  kill opts;
807  } else
808  {
809    S = simplify(S, 2 + 32);
810  }
811
812  S = sort(S, "ds", 1)[1]; // ,1 => reversed!
813
814  if( @DEBUG )
815  {
817  }
818
819  if( @SYZCHECK )
820  {
821    if( size(S) > 0 and size(L) > 0 )
822    {
823      if( size(module(transpose( transpose(S) * transpose(L) ))) > 0 )
824      {
825        transpose( transpose(S) * transpose(L) );
826        "ERROR: transpose( transpose(S) * transpose(L) ) != 0!!!";
827        \$
828      }
829    }
830  }
831
832  module S2 = Tail(S);
833  S = lead(S); // (C,lp) on base ring!
834
835  if( @DEBUG )
836  {
838  }
839
840  attrib(S, "isSB", 1);
841
842  return (S, S2);
843}
844
845// -------------------------------------------------------- //
846
847/// TODO: save shortcut LM(m) * "t" -> ?
848proc SSReduceTerm(poly m, def t, def L, def T, list #)
849{
850  if( typeof( attrib(basering, "DEBUG") ) == "int" )
851  {
852    int @DEBUG = attrib(basering, "DEBUG");
853  } else
854  {
855    int @DEBUG = !system("with", "ndebug");
856  }
857
858  if( @DEBUG )
859  {
860    "SSReduce::Input: ";
861
862    "mult: ", m;
863    "term: ", t;
864    "L: ", L;
865    "T: ", T;
866    if( size(#) > 0 )
867    {
868      "LSyz: ", #;
869    }
870//    "attrib(LS, 'isSB')", attrib(LS, "isSB");
871  }
872
873  vector s = 0;
874
875  if( t == 0 )
876  {
877    return (s);
878  }
879
880  def product = m * t;
881
883  int r = int(c);
884
885  def a, b, nf, bb;
886
887  // looking for an appropriate reducer
888  for( int k = ncols(L); k > 0; k-- )
889  {
890    a = L[k];
891    // with the same mod. component
892    if( leadcomp(a) == c )
893    {
895
896      // which divides the product
897      if( b != 0 )
898      {
899//        "b: ", b;
900        bb = b * gen(k);
901        nf = bb;
902
903        if( size(#) > 0 )
904        {
905          if( typeof(#[1]) == "module" )
906          {
907            nf = NF(bb, #[1]);
908//        "NF: ", nf;
909          }
910        }
911
912        // while the complement (the fraction) is not reducible by leading syzygies
913        if( nf != 0 )
914        {
915          /// TODO: save shortcut LM(m) * T[i] -> ?
916
917          // choose ANY such reduction... (with the biggest index?)
918          s = bb + SSTraverseTail(b, T[k], L, T, #);
919          break;
920        }
921      }
922    }
923  }
924  if( @DEBUG )
925  {
926    "SSReduceTerm::Output: ", s;
927  }
928  return (s);
929}
930
931// TODO: store m * @tail -.-^-.-^-.--> ?
932proc SSTraverseTail(poly m, def @tail, def L, def T, list #)
933{
934  if( typeof( attrib(basering, "DEBUG") ) == "int" )
935  {
936    int @DEBUG = attrib(basering, "DEBUG");
937  } else
938  {
939    int @DEBUG = !system("with", "ndebug");
940  }
941
942  if( @DEBUG )
943  {
944    "SSTraverse::Input: ";
945
946    "mult: ", m;
947    "tail: ", @tail; // T[i];
948
949    if( size(#) > 0 )
950    {
951      "LSyz: "; #[1];
952    }
953  }
954
955  vector s = 0;
956
957  def @l;
958
959  // iterate tail-terms in ANY order!
960  while( size(@tail) > 0 )
961  {
963    s = s + SSReduceTerm(m, @l, L, T, #);
964    @tail = @tail - @l;
965  }
966
967  if( @DEBUG )
968  {
969    "SSTraverseTail::Output: ", s;
970  }
971  return (s);
972}
973
974// -------------------------------------------------------- //
975
976// module (N, LL, TT) = SSComputeSyzygy(L, T);
977// Compute Syz(L ++ T) = N = LL ++ TT
978proc SSComputeSyzygy(def L, def T)
979{
980  if( typeof( attrib(basering, "DEBUG") ) == "int" )
981  {
982    int @DEBUG = attrib(basering, "DEBUG");
983  } else
984  {
985    int @DEBUG = !system("with", "ndebug");
986  }
987
988  if( @DEBUG )
989  {
990    "SSComputeSyzygy::Input";
991    "basering: ", basering; attrib(basering);
992//    DetailedPrint(basering);
993
994//    "iCompShift: ", iCompShift;
995
996    "L: "; L;
997    "T: "; T;
998  }
999
1000  def a; bigint c; int r, k; poly aa;
1001
1003  if( typeof( attrib(basering, "LEAD2SYZ") ) == "int" )
1004  {
1006  }
1007
1008  int @TAILREDSYZ = 1;
1009  if( typeof( attrib(basering, "TAILREDSYZ") ) == "int" )
1010  {
1011    @TAILREDSYZ = attrib(basering, "TAILREDSYZ");
1012//    @TAILREDSYZ;
1013  }
1014
1015  /// Get the critical leading syzygy terms
1016  if( @LEAD2SYZ ) // & 2nd syz. term
1017  {
1018    def a2; int r2; poly aa2;
1019    module LL, LL2;
1020    (LL, LL2) = SSCompute2LeadingSyzygyTerms(L, @TAILREDSYZ); // ++
1021  } else
1022  {
1024  }
1025
1026  module TT, SYZ;
1027
1028  if( size(LL) > 0 )
1029  {
1030    list LS;
1031
1032    if( @TAILREDSYZ )
1033    {
1034      LS = list(LL);
1035    }
1036
1037    vector @tail;
1038
1039    for(k = ncols(LL); k > 0; k-- )
1040    {
1042      a = LL[k]; c = leadcomp(a); r = int(c); aa = leadmonomial(a);
1043      //    "A: ", a, " --->>>> ", aa, " **** [", r, "]: ";
1044
1045      /// TODO: save shortcut (aa) * T[r] -> ?
1046      @tail = SSTraverseTail(aa, T[r], L, T, LS);
1047
1048      // get the 2nd syzygy term...
1049
1050      if( @LEAD2SYZ ) // with the 2nd syz. term:
1051      {
1052        a2 = LL2[k]; c = leadcomp(a2); r2 = int(c); aa2 = leadmonomial(a2);
1053        @tail = @tail +
1054             /// TODO: save shortcut (aa2) * T[r2] -> ?
1055             a2 + SSTraverseTail(aa2, T[r2], L, T, LS);
1056      } else
1057      {
1058        @tail = @tail + SSReduceTerm(aa, L[r], L, T, LS);
1059      }
1060
1061
1062      TT[k] = @tail;
1063      SYZ[k] = a + @tail;
1064    }
1065  }
1066
1067/*
1068  def opts = option(get); option(redSB); option(redTail);
1069  module SYZ = std(syz(M));
1070  option(set, opts); kill opts;
1071
1072  module LL = lead(SYZ); // TODO: WRONG ORDERING!!!!!!!!
1073  module TT = Tail(SYZ);
1074*/
1075
1076  if( @DEBUG )
1077  {
1078    "SSComputeSyzygy::Output";
1079
1080    "SYZ: "; SYZ;
1081    "LL: "; LL;
1082    "TT: "; TT;
1083  }
1084
1085  return (SYZ, LL, TT);
1086}
1087
1088// resolution/syzygy step:
1089static proc SSstep()
1090{
1091  if( typeof( attrib(basering, "DEBUG") ) == "int" )
1092  {
1093    int @DEBUG = attrib(basering, "DEBUG");
1094  } else
1095  {
1096    int @DEBUG = !system("with", "ndebug");
1097  }
1098
1099
1100  if( typeof( attrib(basering, "SYZCHECK") ) == "int" )
1101  {
1102    int @SYZCHECK = attrib(basering, "SYZCHECK");
1103  } else
1104  {
1105    int @SYZCHECK = @DEBUG;
1106  }
1107
1108  if( @DEBUG )
1109  {
1110    "SSstep::NextInducedRing";
1111    "basering: ", basering; attrib(basering);
1112  }
1113
1114/*
1115  // is initial weights are all zeroes!
1117  intvec @V = deg(M[1..ncols(M)]);  @W;  @V;  @W = @V;  attrib(L, "isHomog", @W);
1118  SetInducedReferrence(L, @RANK, 0);
1119*/
1120
1122//  @W = @W, @V;
1123//  attrib(L, "isHomog", @W);
1124
1125
1126  // General setting:
1127//  SetInducedReferrence(MRES, 0, 0); // limit: 0!
1128  int @l = size(RES);
1129
1130  def M =  RES[@l];
1131
1132  def L = LRES[@l];
1133  def T = TRES[@l];
1134
1135
1136  //// TODO: wrong !!!!!
1137  int @RANK = ncols(MRES) - ncols(M); // nrows(M); // what if M is zero?!
1138
1139
1140
1141/*
1142  if( @RANK !=  nrows(M) )
1143  {
1144    type(MRES);
1145    @RANK;
1146    type(M);
1147    pause();
1148  }
1149*/
1150
1151  intvec @W = attrib(M, "isHomog"); intvec @V = attrib(M, "degrees"); @V = @W, @V;
1152
1153  if( @DEBUG )
1154  {
1155    "Sstep::NextInput: ";
1156    M;
1157    L;
1158    @V;
1159    @RANK;
1160//    DetailedPrint(MRES);
1161    attrib(MRES, "isHomog");
1162  }
1163
1164
1165  // TODO: N  = SYZ( M )!!!
1166  module N, LL, TT;
1167  (N, LL, TT) = SSComputeSyzygy(/*M, */L, T/*, @RANK*/);
1168
1169  // shift syz.comp by @RANK:
1170  module Z;
1171  Z = 0; Z[@RANK] = 0; Z = Z, transpose(LL);   LL = transpose(Z);
1172  Z = 0; Z[@RANK] = 0; Z = Z, transpose(TT);   TT = transpose(Z);
1173  Z = 0; Z[@RANK] = 0; Z = Z, transpose(N);     N = transpose(Z);
1174
1175
1176  if( @SYZCHECK )
1177  {
1178    if( size(N) > 0 )
1179    {
1180      // next syz. property
1181      if( size(module(transpose( transpose(N) * transpose(MRES) ))) > 0 )
1182      {
1183        "MRES", MRES;
1184
1185        "N: "; N; // DetailedPrint(N, 2);
1186
1187        "LL:"; LL; // DetailedPrint(LL, 1);
1188        "TT:"; TT; // DetailedPrint(TT, 10);
1189
1190        "RANKS: ", @RANK;
1191
1192        "transpose( transpose(N) * transpose(MRES) ) != 0!!!";
1193        transpose( transpose(N) * transpose(MRES) );
1194
1195        "transpose(N) * transpose(MRES): ";
1196        transpose(N) * transpose(MRES);
1197        // DetailedPrint(module(_), 2);
1198        \$
1199      }
1200    }
1201  }
1202
1203  attrib(N, "isHomog", @V);
1204
1205  // TODO: correct the following:
1206  intvec @DEGS = deg(N[1..ncols(N)]); // no mod. comp. weights :(
1207
1208
1209  attrib(N, "degrees", @DEGS);
1210
1211   RES[@l + 1] = N; // list of all syzygy modules
1212  LRES[@l + 1] = LL; // list of all syzygy modules
1213  TRES[@l + 1] = TT; // list of all syzygy modules
1214
1215  MRES = MRES, N;
1216
1217  attrib(MRES, "isHomog", @V);
1218
1220
1221  if( @DEBUG )
1222  {
1223    "SSstep::NextSyzOutput: ";
1224    N;
1225//    DetailedPrint(N);
1226    attrib(N);
1227  }
1228
1229}
1230
1231proc SScontinue(int l)
1232"USAGE:  SScontinue(l)
1233RETURN:  nothing, instead it changes RES and MRES variables in the current ring
1234PURPOSE: computes further (at most l) syzygies
1235NOTE:    must be used within a ring returned by Sres or Ssyz. RES and MRES are
1236         explained in Sres
1237EXAMPLE: example Scontinue; shows an example
1238"
1239{
1240
1241  /// TODO!
1242//  def data = GetInducedData();
1243
1244  if( (!defined(RES)) || (!defined(MRES)) ) /* || (typeof(data) != "list") || (size(data) != 2) */
1245  {
1246    ERROR("Sorry, but basering does not seem to be returned by Sres or Ssyz");
1247  }
1248  for (;  (l != 0) && (size(RES[size(RES)]) > 0); l-- )
1249  {
1250    SSstep();
1251  }
1252}
1253example
1254{ "EXAMPLE:"; echo = 2;
1255  ring r;
1256  module M = maxideal(1); M;
1257  def S = SSsyz(M); setring S; S;
1258  "Only the first syzygy: ";
1259  RES; MRES;
1260  "More syzygies: ";
1261  SScontinue(10);
1262  RES; MRES;
1263}
1264
1265proc SSsyz(def M)
1266"USAGE:  SSsyz(M)
1267RETURN:  ring, containing a list of modules RES and a module MRES
1268PURPOSE: computes the first syzygy module of M (wrt some Schreyer ordering)?
1269NOTE:    The output is explained in Sres
1270EXAMPLE: example Ssyz; shows an example
1271"
1272{
1273  if( (typeof(M) != "module") && (typeof(M) != "ideal") )
1274  {
1275    ERROR("Sorry: need an ideal or a module for input");
1276  }
1277
1278  def SS = SSinit(M); setring SS;
1279
1280  SSstep(); // NOTE: what if M is zero?
1281
1282  return (SS);
1283}
1284example
1285{ "EXAMPLE:"; echo = 2;
1286  ring r;
1287
1288/*  ideal M = 0;
1289  def S = SSsyz(M); setring S; S;
1290  "Only the first syzygy: ";
1291  RES; LRES; TRES;
1292  MRES;
1293
1294  kill S; setring r; kill M;
1295*/
1296
1297  module M = maxideal(1); M;
1298  def S = SSres(M, 0); setring S; S;
1299  MRES;
1300  RES;
1301  "";
1302  LRES;
1303  "";
1304  TRES;
1305
1306  kill S; setring r; kill M;
1307
1308  kill r;
1309
1310  ring R = 0, (w, x, y, z), dp;
1311  ideal M = w^2 - x*z,  w*x - y*z,  x^2 - w*y, x*y - z^2, y^2 - w*z;
1312
1313  def S = SSres(M, 0); setring S; S;
1314  MRES;
1315  RES;
1316  "";
1317  LRES;
1318  "";
1319  TRES;
1320}
1321
1322proc SSres(def M, int l)
1323"USAGE:  SSres(I, l)
1324RETURN:  ring, containing a list of modules RES and a module MRES
1325PURPOSE: computes (at most l) syzygy modules of M wrt the classical Schreyer
1326         induced ordering with gen(i) > gen(j) if i > j, provided both gens
1327         are from the same syzygy level.???
1328NOTE:    RES contains the images of maps subsituting the beginning of the
1329         Schreyer free resolution of baseRing^r/M, while MRES is a sum of
1330         these images in a big free sum, containing all the syzygy modules.
1331         The syzygy modules are shifted so that gen(i) correspons to MRES[i].
1332         The leading zero module RES[0] indicates the fact that coker of the
1333         first map is zero. The number of zeroes inducates the rank of input.
1334NOTE:    If l == 0 then l is set to be nvars(basering) + 1
1335EXAMPLE: example SSres; shows an example
1336"
1337{
1338  if( (typeof(M) != "module") && (typeof(M) != "ideal") )
1339  {
1340    ERROR("Sorry: need an ideal or a module for input");
1341  }
1342
1343  def SS = SSinit(M); setring SS;
1344
1345  if (l == 0)
1346  {
1347    l = nvars(basering) + 1; // not really an estimate...?!
1348  }
1349
1350  SSstep(); l = l - 1;
1351
1352  SScontinue(l);
1353
1354  return (SS);
1355}
1356example
1357{ "EXAMPLE:"; echo = 2;
1358  ring r;
1359  module M = maxideal(1); M;
1360  def S = SSres(M, 0); setring S; S;
1361  RES;
1362  MRES;
1363  kill S;
1364  setring r; kill M;
1365
1366  def A = nc_algebra(-1,0); setring A;
1367  ideal Q = var(1)^2, var(2)^2, var(3)^2;
1368  qring SCA = twostd(Q);
1369  basering;
1370
1371  module M = maxideal(1);
1372  def S = SSres(M, 2); setring S; S;
1373  RES;
1374  MRES;
1375}
1376
1377
1378
1380{
1381  int @DEBUG = !system("with", "ndebug");
1382
1383  if( @DEBUG )
1384  {
1385
1386    "ndebug?: ", system("with", "ndebug");
1387    "om_ndebug?: ", system("with", "om_ndebug");
1388
1389    listvar(Top);
1390    listvar(Schreyer);
1391  }
1392//  listvar(Syzextra); listvar(Syzextra_g);
1393
1394  if( !defined(DetailedPrint) )
1395  {
1396    if( !@DEBUG )
1397    {
1398
1399      if( @DEBUG )
1400      {
1402      }
1404
1405      if( @DEBUG )
1406      {
1407        listvar(Syzextra);
1408      }
1409
1410//      export Syzextra;
1411
1412//      exportto(Schreyer, Syzextra::noop);
1413      exportto(Schreyer, Syzextra::DetailedPrint);
1417//      exportto(Schreyer, Syzextra::ISUpdateComponents);
1418      exportto(Schreyer, Syzextra::SetInducedReferrence);
1419      exportto(Schreyer, Syzextra::GetInducedData);
1420//      exportto(Schreyer, Syzextra::GetAMData);
1421//      exportto(Schreyer, Syzextra::SetSyzComp);
1422      exportto(Schreyer, Syzextra::MakeInducedSchreyerOrdering);
1423//      exportto(Schreyer, Syzextra::MakeSyzCompOrdering);
1424      exportto(Schreyer, Syzextra::idPrepare);
1425//      exportto(Schreyer, Syzextra::reduce_syz);
1426//      exportto(Schreyer, Syzextra::p_Content);
1427
1428    }
1429    else
1430    {
1431      if( @DEBUG )
1432      {
1434      }
1435
1437
1438      if( @DEBUG )
1439      {
1440        listvar(Syzextra_g);
1441      }
1442
1443//      export Syzextra_g;
1444//      exportto(Schreyer, Syzextra_g::noop);
1445      exportto(Schreyer, Syzextra_g::DetailedPrint);
1449//      exportto(Schreyer, Syzextra_g::ISUpdateComponents);
1450      exportto(Schreyer, Syzextra_g::SetInducedReferrence);
1451      exportto(Schreyer, Syzextra_g::GetInducedData);
1452//      exportto(Schreyer, Syzextra_g::GetAMData);
1453//      exportto(Schreyer, Syzextra_g::SetSyzComp);
1454      exportto(Schreyer, Syzextra_g::MakeInducedSchreyerOrdering);
1455//      exportto(Schreyer, Syzextra_g::MakeSyzCompOrdering);
1456      exportto(Schreyer, Syzextra_g::idPrepare);
1457//      exportto(Schreyer, Syzextra_g::reduce_syz);
1458//      exportto(Schreyer, Syzextra_g::p_Content);
1459
1460
1461    }
1462
1463    exportto(Top, DetailedPrint);
1464    exportto(Top, GetInducedData);
1465
1466    if( @DEBUG )
1467    {
1468      listvar(Top);
1469      listvar(Schreyer);
1470    }
1471  }
1472
1473  if( !defined(GetInducedData) )
1474  {
1475    ERROR("Sorry but we are missing the dynamic module (syzextra(_g)?.so)...");
1476  }
1477
1478}
1479
1480static proc mod_init()
1481{
1483}
1484
1485
1486proc testallSexamples()
1487{
1488  example Ssyz;
1489  example Scontinue;
1490  example Sres;
1491}
1492
1493proc testallSSexamples()
1494{
1495  example SSsyz;
1496  example SScontinue;
1497  example SSres;
1498}
1499
1500example
1501{ "EXAMPLE:"; echo = 2;
1502  testallSexamples();
1503  testallSSexamples();
1504}
Note: See TracBrowser for help on using the repository browser.