# source:git/Singular/LIB/schreyer.lib@4c6c938

spielwiese
Last change on this file since 4c6c938 was 4c6c938, checked in by Oleksandr Motsak <motsak@…>, 12 years ago
added a new experimental library: schreyer.lib for working with Schreyer orderings NOTE: the library requires the dynamic module: syzextra
• Property mode set to `100644`
File size: 11.4 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  attrib(M, "isHomog", @V);
147  attrib(M, "isSB", 1);
148
149
150  if( @DEBUG )
151  {
152    "Sinit::SB_Input: ";
153    type(M);
154    attrib(M);
155    attrib(M, "isHomog");
156    DetailedPrint(M);
157  }
158
159  // 0^th syz. property
160  if( size(module(transpose( transpose(M) * transpose(MRES) ))) > 0 )
161  {
162    transpose( transpose(M) * transpose(MRES) );
163    "transpose( transpose(M) * transpose(MRES) ) != 0!!!";
164    \$
165  }
166
167  RES[size(RES)+1] = M; // list of all syzygy modules
168  MRES = MRES, M;
169
170  attrib(MRES, "isHomog", @V);
171
173  attrib(S, "InducionStart", @RANK);
174
175  if( @DEBUG )
176  {
177    "Sinit::MRES";
178    DetailedPrint(MRES);
179    attrib(MRES, "isHomog");
180    attrib(S);
181  }
182
183  export RES;
184  export MRES;
185  return (S);
186}
187
188static proc Sstep()
189{
190  int @DEBUG = !system("with", "ndebug");
191
192  if( @DEBUG )
193  {
194    "Sstep::NextInducedRing";
195    DetailedPrint(basering);
196
198    attrib(basering, "InducionStart");
199
200    GetInducedData();
201  }
202
203  // syzygy step:
204
205/*
206  // is initial weights are all zeroes!
208  intvec @V = deg(M[1..ncols(M)]);  @W;  @V;  @W = @V;  attrib(L, "isHomog", @W);
209  SetInducedReferrence(L, @RANK, 0);
210*/
211
213//  @W = @W, @V;
214//  attrib(L, "isHomog", @W);
215
216
217  // General setting:
218//  SetInducedReferrence(MRES, 0, 0); // limit: 0!
219  int @l = size(RES);
220
221  module M = RES[@l];
222
223  module L = attrib(basering, "InducionLeads");
224  int limit = attrib(basering, "InducionStart");
225
226//  L;  limit;
227
228  int @RANK = ncols(MRES) - ncols(M); // nrows(M); // what if M is zero?!
229
230/*
231  if( @RANK !=  nrows(M) )
232  {
233    type(MRES);
234    @RANK;
235    type(M);
236    pause();
237  }
238*/
239
240  intvec @W = attrib(M, "isHomog");
241  intvec @V = deg(M[1..ncols(M)]);
242  @V = @W, @V;
243
244  if( @DEBUG )
245  {
246    "Sstep::NextInput: ";
247    M;
248    @V;
249    @RANK;
250    DetailedPrint(MRES);
251    attrib(MRES, "isHomog");
252  }
253
254
255
256  SetInducedReferrence(L, limit, 0);
257
258  def K = prepareSyz(M, @RANK);
259//  K;
260
261//   attrib(K, "isHomog", @V);   DetailedPrint(K, 1000);
262
263//  pause();
264
265  K = idPrepare(K, @RANK); // std(K); // ?
266  K = simplify(K, 2);
267
268//  K;
269
270  module N = separateSyzGB(K, @RANK)[2]; // 1^st syz. module: vectors which start in lower part (comp >= @RANK)
271  attrib(N, "isHomog", @V);
272
273// "N_0: "; N; DetailedPrint(N, 10);
274
275  N = std(N); // TODO: fix "wrong weights"!!!?
276  attrib(N, "isHomog", @V);
277
278//  N;
279
280  if( size(N) > 0 )
281  {
282    // next syz. property
283    if( size(module(transpose( transpose(N) * transpose(MRES) ))) > 0 )
284    {
285      MRES;
286
287      "N: "; N; DetailedPrint(N, 10);
288
289      "K:"; K; DetailedPrint(K, 10);
290
291      "RANKS: ", @RANK;
292
293      "transpose( transpose(N) * transpose(MRES) ) != 0!!!";
294      transpose( transpose(N) * transpose(MRES) );
295
296      "transpose(N) * transpose(MRES): ";
297      transpose(N) * transpose(MRES);
298      DetailedPrint(module(_), 2);
299      \$
300    }
301  }
302
303  RES[@l + 1] = N; // list of all syzygy modules
304
305  MRES = MRES, N;
306  attrib(MRES, "isHomog", @V);
307
308
311
312  if( @DEBUG )
313  {
314    "Sstep::NextSyzOutput: ";
315    DetailedPrint(N);
316    attrib(N, "isHomog");
317  }
318
319}
320
321proc Scontinue(int l)
322"USAGE:  Scontinue(l)
323RETURN:  nothing, instead it changes RES and MRES variables in the current ring
324PURPOSE: computes further (at most l) syzygies
325NOTE:    must be used within a ring returned by Sres or Ssyz. RES and MRES are
326         explained in Sres
327EXAMPLE: example Scontinue; shows an example
328"
329{
330  def data = GetInducedData();
331
332  if( (!defined(RES)) || (!defined(MRES)) || (typeof(data) != "list") || (size(data) != 2) )
333  {
334    ERROR("Sorry, but basering does not seem to be returned by Sres or Ssyz");
335  }
336  for (;  (l != 0) && (size(RES[size(RES)]) > 0); l-- )
337  {
338    Sstep();
339  }
340}
341example
342{ "EXAMPLE:"; echo = 2;
343  ring r;
344  module M = maxideal(1); M;
345  def S = Ssyz(M); setring S; S;
346  "Only the first syzygy: ";
347  RES; MRES;
348  "More syzygies: ";
349  Scontinue(10);
350  RES; MRES;
351}
352
353proc Ssyz(module M)
354"USAGE:  Ssyz(M)
355RETURN:  ring, containing a list of modules RES and a module MRES
356PURPOSE: computes the first syzygy module of M (wrt some Schreyer ordering)
357NOTE:    The output is explained in Sres
358EXAMPLE: example Ssyz; shows an example
359"
360{
361  def S = Sinit(M); setring S;
362
363  Sstep(); // NOTE: what if M is zero?
364
365  return (S);
366}
367example
368{ "EXAMPLE:"; echo = 2;
369  ring r;
370  module M = maxideal(1); M;
371  def S = Ssyz(M); setring S; S;
372  "Only the first syzygy: ";
373  RES;
374  MRES; // Note gen(i)
375  kill S;
376  setring r; kill M;
377
378  module M = 0;
379  def S = Ssyz(M); setring S; S;
380  "Only the first syzygy: ";
381  RES;
382  MRES;
383
384}
385
386proc Sres(module M, int l)
387"USAGE:  Sres(M, l)
388RETURN:  ring, containing a list of modules RES and a module MRES
389PURPOSE: computes (at most l) syzygy modules of M wrt the classical Schreyer
390         induced ordering with gen(i) > gen(j) if i > j, provided both gens
391         are from the same syzygy level.
392NOTE:    RES contains the images of maps subsituting the beginning of the
393         Schreyer free resolution of baseRing^r/M, while MRES is a sum of
394         these images in a big free sum, containing all the syzygy modules.
395         The syzygy modules are shifted so that gen(i) correspons to MRES[i].
396         The leading zero module RES[0] indicates the fact that coker of the
397         first map is zero. The number of zeroes inducates the rank of input.
398NOTE:    If l == 0 then l is set to be nvars(basering) + 1
399EXAMPLE: example Sres; shows an example
400"
401{
402  def S = Sinit(M); setring S;
403
404  if (l == 0)
405  {
406    l = nvars(basering) + 1; // not really an estimate...?!
407  }
408
409  Sstep(); l = l - 1;
410
411  Scontinue(l);
412
413  return (S);
414}
415example
416{ "EXAMPLE:"; echo = 2;
417  ring r;
418  module M = maxideal(1); M;
419  def S = Sres(M, 0); setring S; S;
420  RES;
421  MRES;
422  kill S;
423  setring r; kill M;
424
425  def A = nc_algebra(-1,0); setring A;
426  ideal Q = var(1)^2, var(2)^2, var(3)^2;
427  qring SCA = twostd(Q);
428  basering;
429
430  module M = maxideal(1);
431  def S = Sres(M, 2); setring S; S;
432  RES;
433  MRES;
434}
435
436
437
438
440{
441  int @DEBUG = !system("with", "ndebug");
442
443  if( @DEBUG )
444  {
445
446    "ndebug?: ", system("with", "ndebug");
447    "om_ndebug?: ", system("with", "om_ndebug");
448
449    listvar(Top);
450    listvar(Schreyer);
451  }
452//  listvar(Syzextra); listvar(Syzextra_g);
453
454  if( !defined(DetailedPrint) )
455  {
456    if( !@DEBUG )
457    {
458
459      if( @DEBUG )
460      {
462      }
464
465      if( @DEBUG )
466      {
467        listvar(Syzextra);
468      }
469
470//      export Syzextra;
471
472//      exportto(Schreyer, Syzextra::noop);
473      exportto(Schreyer, Syzextra::DetailedPrint);
477//      exportto(Schreyer, Syzextra::ISUpdateComponents);
478      exportto(Schreyer, Syzextra::SetInducedReferrence);
479      exportto(Schreyer, Syzextra::GetInducedData);
480      exportto(Schreyer, Syzextra::GetAMData);
481//      exportto(Schreyer, Syzextra::SetSyzComp);
482      exportto(Schreyer, Syzextra::MakeInducedSchreyerOrdering);
483//      exportto(Schreyer, Syzextra::MakeSyzCompOrdering);
484      exportto(Schreyer, Syzextra::idPrepare);
485//      exportto(Schreyer, Syzextra::reduce_syz);
486//      exportto(Schreyer, Syzextra::p_Content);
487
488    }
489    else
490    {
491      if( @DEBUG )
492      {
494      }
495
497
498      if( @DEBUG )
499      {
500        listvar(Syzextra_g);
501      }
502
503//      export Syzextra_g;
504//      exportto(Schreyer, Syzextra_g::noop);
505      exportto(Schreyer, Syzextra_g::DetailedPrint);
509//      exportto(Schreyer, Syzextra_g::ISUpdateComponents);
510      exportto(Schreyer, Syzextra_g::SetInducedReferrence);
511      exportto(Schreyer, Syzextra_g::GetInducedData);
512      exportto(Schreyer, Syzextra_g::GetAMData);
513//      exportto(Schreyer, Syzextra_g::SetSyzComp);
514      exportto(Schreyer, Syzextra_g::MakeInducedSchreyerOrdering);
515//      exportto(Schreyer, Syzextra_g::MakeSyzCompOrdering);
516      exportto(Schreyer, Syzextra_g::idPrepare);
517//      exportto(Schreyer, Syzextra_g::reduce_syz);
518//      exportto(Schreyer, Syzextra_g::p_Content);
519
520
521    }
522
523    exportto(Top, DetailedPrint);
524    exportto(Top, GetInducedData);
525
526    if( @DEBUG )
527    {
528      listvar(Top);
529      listvar(Schreyer);
530    }
531  }
532
533  if( !defined(GetInducedData) )
534  {
535    ERROR("Sorry but we are missing the dynamic module (syzextra(_g)?.so)...");
536  }
537
538}
539
540static proc mod_init()
541{
543}
544
545
546proc testallSexamples()
547{
548  example Ssyz;
549  example Scontinue;
550  example Sres;
551}
552example
553{ "EXAMPLE:"; echo = 2;
554  testallSexamples();
555}
Note: See TracBrowser for help on using the repository browser.