syz1.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT: resolutions
6 */
7 
8 
9 
10 
11 #include <kernel/mod2.h>
12 
13 #include <misc/mylimits.h>
14 #include <omalloc/omalloc.h>
15 
16 #include <misc/options.h>
17 #include <misc/intvec.h>
18 #include <coeffs/numbers.h>
19 
20 #include <polys/monomials/ring.h>
21 #include <polys/kbuckets.h>
22 #include <polys/prCopy.h>
23 
24 #include <kernel/polys.h>
25 
26 #include <kernel/GBEngine/kstd1.h>
27 #include <kernel/GBEngine/kutil.h>
29 //#include "cntrlc.h"
30 #include <kernel/ideals.h>
31 #include <kernel/GBEngine/syz.h>
32 // #include <kernel/idrec.h>
33 
34 extern void p_Setm_Syz(poly p, ring r,
35  int* Components, long* ShiftedComponents);
36 
37 /*--------------static variables------------------------*/
38 /*---points to the real components, shifted of the actual module-*/
41 
42 
43 /*---head-term-polynomials for the reduction------------*/
44 static poly redpol=NULL;
45 /*---counts number of applications of GM-criteria-------*/
46 //static int crit;
47 //static int euler;
48 
49 /*3
50 * deletes all entres of a pair
51 */
52 void syDeletePair(SObject * so)
53 {
54  pDelete(&(*so).p);
55  pDelete(&(*so).lcm);
56  pDelete(&(*so).syz);
57  (*so).p1 = NULL;
58  (*so).p2 = NULL;
59  (*so).ind1 = 0;
60  (*so).ind2 = 0;
61  (*so).syzind = -1;
62  (*so).order = 0;
63  (*so).isNotMinimal = NULL;
64  (*so).length = -1;
65  (*so).reference = -1;
66 }
67 
68 /*3
69 * initializes all entres of a pair
70 */
71 void syInitializePair(SObject * so)
72 {
73  (*so).p = NULL;
74  (*so).lcm = NULL;
75  (*so).syz = NULL;
76  (*so).p1 = NULL;
77  (*so).p2 = NULL;
78  (*so).ind1 = 0;
79  (*so).ind2 = 0;
80  (*so).syzind = -1;
81  (*so).order = 0;
82  (*so).isNotMinimal = NULL;
83  (*so).length = -1;
84  (*so).reference = -1;
85 }
86 
87 /*3
88 * puts all entres of a pair to another
89 */
90 void syCopyPair(SObject * argso, SObject * imso)
91 {
92  *imso=*argso;
93  (*argso).p = NULL;
94  (*argso).p1 = NULL;
95  (*argso).p2 = NULL;
96  (*argso).lcm = NULL;
97  (*argso).syz = NULL;
98  (*argso).ind1 = 0;
99  (*argso).ind2 = 0;
100  (*argso).syzind = -1;
101  (*argso).order = 0;
102  (*argso).isNotMinimal = NULL;
103  (*argso).length = -1;
104  (*argso).reference = -1;
105 }
106 
107 /*3
108 * deletes empty objects from a pair set beginning with
109 * pair first
110 * assumes a pair to be empty if .lcm does so
111 */
112 void syCompactifyPairSet(SSet sPairs, int sPlength, int first)
113 {
114  int k=first,kk=0;
115 
116  while (k+kk<sPlength)
117  {
118  if (sPairs[k+kk].lcm!=NULL)
119  {
120  if (kk>0) syCopyPair(&sPairs[k+kk],&sPairs[k]);
121  k++;
122  }
123  else
124  {
125  kk++;
126  }
127  }
128  while (k<sPlength)
129  {
130  syInitializePair(&sPairs[k]);
131  k++;
132  }
133 }
134 
135 /*3
136 * deletes empty objects from a pair set beginning with
137 * pair first
138 * assumes a pair to be empty if .lcm does so
139 */
140 void syCompactify1(SSet sPairs, int* sPlength, int first)
141 {
142  int k=first,kk=0;
143 
144  while (k+kk<*sPlength)
145  {
146  if (sPairs[k+kk].lcm!=NULL)
147  {
148  if (kk>0) syCopyPair(&sPairs[k+kk],&sPairs[k]);
149  k++;
150  }
151  else
152  {
153  kk++;
154  }
155  }
156  while (k<*sPlength)
157  {
158  syInitializePair(&sPairs[k]);
159  k++;
160  }
161  *sPlength -= kk;
162 }
163 
164 /*3
165 * replaces comp1dpc during homogeneous syzygy-computations
166 * compares with components of currcomponents instead of the
167 * exp[0]
168 */
169 
170 #ifdef PDEBUG
171 static int syzcomp2dpc_test(poly p1, poly p2)
172 {
173  long c1, c2, cc1, cc2, ccc1, ccc2, ec1, ec2;
174  c1 = pGetComp(p1);
175  c2 = pGetComp(p2);
176  cc1 = currcomponents[c1];
177  cc2 = currcomponents[c2];
178  ccc1 = currShiftedComponents[cc1];
179  ccc2 = currShiftedComponents[cc2];
180  ec1 = p1->exp[currRing->typ[1].data.syzcomp.place];
181  ec2 = p2->exp[currRing->typ[1].data.syzcomp.place];
182 
183  if (ec1 != ccc1)
184  {
185  Warn("Shifted comp of p1 out of sync. should %d, is %d", ccc1, ec1);
186  //mmDBInfoBlock(p1);
187  }
188  if (ec2 != ccc2)
189  {
190  Warn("Shifted comp of p2 out of sync. should %d, is %d", ccc2, ec2);
191  //mmDBInfoBlock(p2);
192  }
193 
194  if (c1 == c2)
195  {
196  assume(ccc1 == ccc2);
197  }
198  else if (cc1 > cc2)
199  {
200  assume(ccc1 > ccc2);
201  }
202  else
203  {
204  assume (cc1 < cc2);
205  assume (ccc1 < ccc2);
206  }
207  int o1=pGetOrder(p1), o2=pGetOrder(p2);
208  if (o1 > o2) return 1;
209  if (o1 < o2) return -1;
210 
211  //if (o1>0)
212  {
213  int i = (currRing->N);
214  while ((i>1) && (pGetExp(p1,i)==pGetExp(p2,i)))
215  i--;
216  //(*orderingdepth)[(currRing->N)-i]++;
217  if (i>1)
218  {
219  if (pGetExp(p1,i) < pGetExp(p2,i)) return 1;
220  return -1;
221  }
222  }
223  o1=pGetComp(p1);
224  o2=pGetComp(p2);
225  if (o1==o2/*pGetComp(p1)==pGetComp(p2)*/) return 0;
226  if (currcomponents[o1]>currcomponents[o2]) return 1;
227  return -1;
228 }
229 #endif // PDEBUG
230 
232 {
233  poly h, hn;
234  int j,pos;
235  ideal redWith=syzstr->orderedRes[index];
236 
237  h = p;
238  hn = pNext(h);
239  while(hn != NULL)
240  {
241  j = syzstr->Firstelem[index-1][pGetComp(hn)]-1;
242  if (j>=0)
243  {
244  pos = j+syzstr->Howmuch[index-1][pGetComp(hn)];
245  while (j < pos)
246  {
247  if (pLmDivisibleByNoComp(redWith->m[j], hn))
248  {
249  //hn = sySPolyRed(hn,redWith->m[j]);
250  hn = ksOldSpolyRed(redWith->m[j],hn);
251  if (hn == NULL)
252  {
253  pNext(h) = NULL;
254  return p;
255  }
256  j = syzstr->Firstelem[index-1][pGetComp(hn)]-1;
257  pos = j+syzstr->Howmuch[index-1][pGetComp(hn)];
258  }
259  else
260  {
261  j++;
262  }
263  }
264  }
265  h = pNext(h) = hn;
266  hn = pNext(h);
267  }
268  return p;
269 }
270 
271 
272 /*3
273 * local procedure for of syInitRes for the module case
274 */
275 static int syChMin(intvec * iv)
276 {
277  int i,j=-1,r=-1;
278 
279  for (i=iv->length()-1;i>=0;i--)
280  {
281  if ((*iv)[i]>=0)
282  {
283  if ((j<0) || ((*iv)[i]<j))
284  {
285  j = (*iv)[i];
286  r = i;
287  }
288  }
289  }
290  return r;
291 }
292 
293 /*3
294 * initialize the resolution and puts in the argument as
295 * zeroth entre, length must be > 0
296 * assumes that the basering is degree-compatible
297 */
298 SRes syInitRes(ideal arg,int * length, intvec * Tl, intvec * cw)
299 {
300  if (idIs0(arg)) return NULL;
301  SRes resPairs = (SRes)omAlloc0(*length*sizeof(SSet));
302  resPairs[0] = (SSet)omAlloc0(IDELEMS(arg)*sizeof(SObject));
303  intvec * iv=NULL;
304  int i,j;
305 
306  if (id_RankFreeModule(arg,currRing)==0)
307  {
308  iv = idSort(arg);
309  for (i=0;i<IDELEMS(arg);i++)
310  {
311  (resPairs[0])[i].syz = /*pCopy*/(arg->m[(*iv)[i]-1]);
312  arg->m[(*iv)[i]-1] = NULL;
313  (resPairs[0])[i].order = pTotaldegree((resPairs[0])[i].syz);
314  }
315  }
316  else
317  {
318  iv = new intvec(IDELEMS(arg),1,-1);
319  for (i=0;i<IDELEMS(arg);i++)
320  {
321  (*iv)[i] = pTotaldegree(arg->m[i])+(*cw)[pGetComp(arg->m[i])-1];
322  }
323  for (i=0;i<IDELEMS(arg);i++)
324  {
325  j = syChMin(iv);
326  if (j<0) break;
327  (resPairs[0])[i].syz = arg->m[j];
328  arg->m[j] = NULL;
329  (resPairs[0])[i].order = (*iv)[j];
330  (*iv)[j] = -1;
331  }
332  }
333  if (iv!=NULL) delete iv;
334  (*Tl)[0] = IDELEMS(arg);
335  return resPairs;
336 }
337 
338 // rearrange shifted components
339 long syReorderShiftedComponents(long * sc, int n)
340 {
341  long holes = 0;
342  int i;
343  long new_comps = 0, new_space, max;
344 
345  // count number of holes
346  for (i=1; i<n; i++)
347  {
348  if (sc[i-1] + 1 < sc[i]) holes++;
349  }
350 
351  if (LONG_MAX - SYZ_SHIFT_BASE <= sc[n-1])
352  {
353  // need new components
354  new_comps = (((long) 1) << SYZ_SHIFT_MAX_NEW_COMP_ESTIMATE) - 1;
355  max = LONG_MAX;
356  }
357  else
358  {
359  max = sc[n-1] + SYZ_SHIFT_BASE;
360  }
361 
362  // no we arrange things such that
363  // (n - holes) + holes*new_space + new_comps*SYZ_SHIFT_BASE= LONG_MAX
364  new_space = (max - n + holes - new_comps*SYZ_SHIFT_BASE) / holes;
365 
366  assume(new_space < SYZ_SHIFT_BASE && new_space >= 4);
367 
368  long* tc = ( long*) omAlloc(n*sizeof(long));
369  tc[0] = sc[0];
370  // rearrange things
371  for (i=1; i<n; i++)
372  {
373  if (sc[i-1] + 1 < sc[i])
374  {
375  tc[i] = tc[i-1] + new_space;
376  }
377  else
378  {
379  tc[i] = tc[i-1] + 1;
380  }
381  assume(tc[i] > tc[i-1]);
382  }
383 
384  assume(LONG_MAX - SYZ_SHIFT_BASE > tc[n-1]);
385 #ifdef HAVE_ASSUME
386  for (i=1; i<n; i++)
387  {
388  assume(tc[i] >= 0);
389  assume(tc[i-1] + 1 <= tc[i]);
390  }
391 #endif
392 
393  omMemcpyW(sc, tc, n);
394  omFreeSize(tc, n*sizeof(long));
395  return new_space;
396 }
397 
398 // this make a Setm on p
399 static void pResetSetm(poly p)
400 {
401 #ifdef PDEBUG
402  poly q = p;
403 #endif
404  while (p!= NULL)
405  {
406  pSetm(p);
407  pIter(p);
408  }
409 #ifdef PDEBUG
410  pTest(q);
411 #endif
412 }
413 
414 void syResetShiftedComponents(syStrategy syzstr, int index,int hilb)
415 {
416  assume(index > 0);
417  int i;
418  if (syzstr->res[index] != NULL)
419  {
420  long * prev_s;
421  int* prev_c;
422  int p_length;
423  rGetSComps(&prev_c, &prev_s, &p_length, currRing);
424  currcomponents = syzstr->truecomponents[index-1];
425  currShiftedComponents = syzstr->ShiftedComponents[index-1];
428  IDELEMS(syzstr->res[index-1]), currRing);
429  if (hilb==0)
430  {
431  ideal id = syzstr->res[index];
432  for (i=0; i<IDELEMS(id); i++)
433  {
434  pResetSetm(id->m[i]);
435  }
436  }
437  else if (hilb==1)
438  {
439  assume (index>1);
440  assume (syzstr->resPairs[index-1]!=NULL);
441  SSet Pairs=syzstr->resPairs[index-1];
442  SSet Pairs1=syzstr->resPairs[index];
443  int till=(*syzstr->Tl)[index-1];
444  for (i=0;i<till;i++)
445  {
446  if (Pairs[i].syz!=NULL)
447  pResetSetm(Pairs[i].syz);
448  }
449  till=(*syzstr->Tl)[index];
450  for (i=0;i<till;i++)
451  {
452  if (Pairs1[i].p!=NULL)
453  pResetSetm(Pairs1[i].p);
454  }
455  }
456  currcomponents = prev_c;
457  currShiftedComponents = prev_s;
458  rChangeSComps(prev_c, prev_s, p_length, currRing);
459  }
460 }
461 
462 /*3
463 * determines the place of a polynomial in the right ordered resolution
464 * set the vectors of truecomponents
465 */
466 static BOOLEAN syOrder(poly p,syStrategy syzstr,int index,
467  int realcomp)
468 {
469  int i=IDELEMS(syzstr->res[index-1])+1,j=0,k,tc,orc,ie=realcomp-1;
470  int *trind1=syzstr->truecomponents[index-1];
471  int *trind=syzstr->truecomponents[index];
472  long *shind=syzstr->ShiftedComponents[index];
473  int *bc=syzstr->backcomponents[index];
474  int *F1=syzstr->Firstelem[index-1];
475  int *H1=syzstr->Howmuch[index-1];
476  polyset o_r=syzstr->orderedRes[index]->m;
477  BOOLEAN ret = FALSE;
478 
479  // if != 0, then new element can go into same component
480  // i.e., we do not need to leave space in shifted components
481  long same_comp = 0;
482 
483  if (p==NULL) return FALSE;
484  if (realcomp==0) realcomp=1;
485 
486  if (index>1)
487  tc = trind1[pGetComp(p)]-1;
488  else
489  tc = pGetComp(p)-1;
490  loop //while ((j<ie) && (trind1[orc]<=tc+1))
491  {
492  if (j>=ie)
493  break;
494  else
495  {
496  orc = pGetComp(o_r[j]);
497  if (trind1[orc]>tc+1) break;
498  else if (trind1[orc] == tc+1)
499  {
500  same_comp = 1;
501  }
502  else
503  {
504  assume(same_comp == 0);
505  }
506  j += H1[orc];
507  }
508  }
509  if (j>ie)
510  {
511  WerrorS("orderedRes to small");
512  return FALSE;
513  }
514  ie++;
515  if (j == (ie -1))
516  {
517  // new element is the last in ordered module
518  if (same_comp == 0)
519  same_comp = SYZ_SHIFT_BASE;
520 
521  // test wheter we have enough space for new shifted component
522  if ((LONG_MAX - same_comp) <= shind[ie-1])
523  {
524  long new_space = syReorderShiftedComponents(shind, ie);
525  assume((LONG_MAX - same_comp) > shind[ie-1]);
526  ret = TRUE;
527  if (TEST_OPT_PROT) Print("(T%ld)", new_space);
528  }
529 
530  // yes, then set new shifted component
531  assume(ie == 1 || shind[ie-1] > 0);
532  shind[ie] = shind[ie-1] + same_comp;
533  }
534  else
535  {
536  // new element must come in between
537  // i.e. at place j+1
538  long prev, next;
539 
540  // test whether new component can get shifted value
541  prev = shind[j];
542  next = shind[j+1];
543  assume(next > prev);
544  if ((same_comp && prev + 2 >= next) || (!same_comp && next - prev < 4))
545  {
546  long new_space = syReorderShiftedComponents(shind, ie);
547  prev = shind[j];
548  next = shind[j+1];
549  assume((same_comp && prev + 2 < next) || (!same_comp && next - prev >= 4));
550  ret = TRUE;
551  if (TEST_OPT_PROT) Print("(B%ld)", new_space);
552  }
553 
554  // make room for insertion of j+1 shifted component
555  for (k=ie; k > j+1; k--) shind[k] = shind[k-1];
556 
557  if (same_comp)
558  {
559  // can simply add one
560  shind[j+1] = prev + 1;
561  assume(shind[j+1] + 1 < shind[j+2]);
562  }
563  else
564  {
565  // need to leave more breathing room - i.e. value goes in
566  // between
567  shind[j+1] = prev + ((next - prev) >> 1);
568  assume (shind[j] + 1 < shind[j+1] && shind[j+1] + 1 < shind[j+2]);
569  }
570  }
571 
572  if (o_r[j]!=NULL)
573  {
574  for (k=ie-1;k>j;k--)
575  {
576  o_r[k] = o_r[k-1];
577  bc[k] = bc[k-1];
578  }
579  }
580  o_r[j] = p;
581  bc[j] = realcomp-1;
582  (H1[pGetComp(p)])++;
583  for (k=0;k<i;k++)
584  {
585  if (F1[k]>j)
586  (F1[k])++;
587  }
588  if (F1[pGetComp(p)]==0)
589  F1[pGetComp(p)]=j+1;
590  for (k=0;k<IDELEMS((syzstr->res)[index]);k++)
591  {
592  if (trind[k]>j)
593  trind[k] += 1;
594  }
595  for (k=IDELEMS((syzstr->res)[index])-1;k>realcomp;k--)
596  trind[k] = trind[k-1];
597  trind[realcomp] = j+1;
598  return ret;
599 }
600 
601 //#define OLD_PAIR_ORDER
602 #ifdef OLD_PAIR_ORDER
603 static intvec* syLinStrat(SSet nextPairs, syStrategy syzstr,
604  int howmuch, int index)
605 {
606  int i=howmuch-1,i1=0,l,ll;
607  int ** Fin=syzstr->Firstelem;
608  int ** Hin=syzstr->Howmuch;
609  int ** bin=syzstr->backcomponents;
610  ideal o_r=syzstr->orderedRes[index+1];
611  intvec *result=new intvec(howmuch+1);
612  BOOLEAN isDivisible;
613  SObject tso;
614 
615  while (i>=0)
616  {
617  tso = nextPairs[i];
618  isDivisible = FALSE;
619  if (syzstr->res[index+1]!=NULL)
620  {
621  l = Fin[index][pGetComp(tso.lcm)]-1;
622  if (l>=0)
623  {
624  ll = l+Hin[index][pGetComp(tso.lcm)];
625  while ((l<ll) && (!isDivisible))
626  {
627  if (o_r->m[l]!=NULL)
628  {
629  isDivisible = isDivisible ||
630  pLmDivisibleByNoComp(o_r->m[l],tso.lcm);
631  }
632  l++;
633  }
634  }
635  }
636  if (isDivisible)
637  {
638  syDeletePair(&nextPairs[i]);
639  //crit++;
640  }
641  else
642  {
643  nextPairs[i].p =
644  //sySPoly(tso.p1, tso.p2,tso.lcm);
645  spSpolyCreate(tso.p2, tso.p1,NULL,spSpolyLoop_General);
646  (*result)[i1] = i+1;
647  i1++;
648  }
649  i--;
650  }
651  return result;
652 }
653 #else
654 static intvec* syLinStrat(SSet nextPairs, syStrategy syzstr,
655  int howmuch, int index)
656 {
657  int i=howmuch-1,i1=0,i2,i3,l,ll;
658  int ** Fin=syzstr->Firstelem;
659  int ** Hin=syzstr->Howmuch;
660  ideal o_r=syzstr->orderedRes[index+1];
661  intvec *result=new intvec(howmuch+1);
662  intvec *spl=new intvec(howmuch,1,-1);
663  BOOLEAN isDivisible;
664  SObject tso;
665 
666  while (i>=0)
667  {
668  tso = nextPairs[i];
669  isDivisible = FALSE;
670  if (syzstr->res[index+1]!=NULL)
671  {
672  l = Fin[index][pGetComp(tso.lcm)]-1;
673  if (l>=0)
674  {
675  ll = l+Hin[index][pGetComp(tso.lcm)];
676  while ((l<ll) && (!isDivisible))
677  {
678  if (o_r->m[l]!=NULL)
679  {
680  isDivisible = isDivisible ||
681  pLmDivisibleByNoComp(o_r->m[l],tso.lcm);
682  }
683  l++;
684  }
685  }
686  }
687  if (isDivisible)
688  {
689  syDeletePair(&nextPairs[i]);
690  //crit++;
691  }
692  else
693  {
694  pTest(tso.p2);
695  pTest(tso.p1);
696  nextPairs[i].p =
697  ksOldCreateSpoly(tso.p2, tso.p1,NULL);
698  (*spl)[i] = pLength(nextPairs[i].p);
699  }
700  i--;
701  }
702  i3 = 0;
703  loop
704  {
705  i2 = -1;
706  for (i1=0;i1<howmuch;i1++)
707  {
708  if (i2==-1)
709  {
710  if ((*spl)[i1]!=-1)
711  {
712  i2 = i1;
713  }
714  }
715  else
716  {
717  if (((*spl)[i1]>=0) && ((*spl)[i1]<(*spl)[i2]))
718  {
719  i2 = i1;
720  }
721  }
722  }
723  if (i2>=0)
724  {
725  (*result)[i3] = i2+1;
726  (*spl)[i2] = -1;
727  i3++;
728  }
729  else
730  {
731  break;
732  }
733  }
734  delete spl;
735  return result;
736 }
737 #endif
738 
740 {
741  pEnlargeSet(&(syzstr->res[index]->m),IDELEMS(syzstr->res[index]),16);
743  (IDELEMS(syzstr->res[index])+1)*sizeof(int),
744  (IDELEMS(syzstr->res[index])+17)*sizeof(int));
745  syzstr->ShiftedComponents[index]
746  =(long*)omRealloc0Size((ADDRESS)syzstr->ShiftedComponents[index],
747  (IDELEMS(syzstr->res[index])+1)*sizeof(long),
748  (IDELEMS(syzstr->res[index])+17)*sizeof(long));
750  (IDELEMS(syzstr->res[index])+1)*sizeof(int),
751  (IDELEMS(syzstr->res[index])+17)*sizeof(int));
752  syzstr->Howmuch[index]=(int*)omRealloc0Size((ADDRESS)syzstr->Howmuch[index],
753  (IDELEMS(syzstr->res[index])+1)*sizeof(int),
754  (IDELEMS(syzstr->res[index])+17)*sizeof(int));
755  syzstr->Firstelem[index]=(int*)omRealloc0Size((ADDRESS)syzstr->Firstelem[index],
756  (IDELEMS(syzstr->res[index])+1)*sizeof(int),
757  (IDELEMS(syzstr->res[index])+17)*sizeof(int));
758  syzstr->elemLength[index]=(int*)omRealloc0Size((ADDRESS)syzstr->elemLength[index],
759  (IDELEMS(syzstr->res[index])+1)*sizeof(int),
760  (IDELEMS(syzstr->res[index])+17)*sizeof(int));
761  syzstr->sev[index]=(unsigned long*)omRealloc0Size((ADDRESS)syzstr->sev[index],
762  (IDELEMS(syzstr->res[index])+1)*sizeof(unsigned long),
763  (IDELEMS(syzstr->res[index])+17)*sizeof(unsigned long));
764  IDELEMS(syzstr->res[index]) += 16;
765  pEnlargeSet(&(syzstr->orderedRes[index]->m),IDELEMS(syzstr->orderedRes[index]),16);
766  IDELEMS(syzstr->orderedRes[index]) += 16;
767 }
768 /*3
769 * reduces all pairs of degree deg in the module index
770 * put the reduced generators to the resolvente which contains
771 * the truncated kStd
772 */
773 static void syRedNextPairs(SSet nextPairs, syStrategy syzstr,
774  int howmuch, int index)
775 {
776  int i,j,k=IDELEMS(syzstr->res[index]);
777  int ks=IDELEMS(syzstr->res[index+1]);
778  int * Fin=syzstr->Firstelem[index-1];
779  int * Hin=syzstr->Howmuch[index-1];
780  int * bin=syzstr->backcomponents[index];
781  int * elL=syzstr->elemLength[index];
782  number coefgcd;
783  polyset redset=syzstr->orderedRes[index]->m;
784  poly p=NULL,q;
785  intvec *spl1;
786  SObject tso;
787  long * ShiftedComponents = syzstr->ShiftedComponents[index];
788  int* Components = syzstr->truecomponents[index];
789  assume(Components != NULL && ShiftedComponents != NULL);
790  BOOLEAN need_reset;
791 
792  if ((nextPairs==NULL) || (howmuch==0)) return;
793  while ((k>0) && (syzstr->res[index]->m[k-1]==NULL)) k--;
794  while ((ks>0) && (syzstr->res[index+1]->m[ks-1]==NULL)) ks--;
795  spl1 = syLinStrat(nextPairs,syzstr,howmuch,index);
796  i=0;
797  while ((*spl1)[i]>0)
798  {
799  need_reset = FALSE;
800  tso = nextPairs[(*spl1)[i]-1];
801  if ((tso.p1!=NULL) && (tso.p2!=NULL))
802  {
803  nNormalize(pGetCoeff(tso.p1));
804  nNormalize(pGetCoeff(tso.p2));
805  coefgcd =
806  n_SubringGcd(pGetCoeff(tso.p1),pGetCoeff(tso.p2),currRing->cf);
807  tso.syz = pHead(tso.lcm);
808  p = tso.syz;
809  pSetCoeff(p,nDiv(pGetCoeff(tso.p1),coefgcd));
810  pGetCoeff(p) = nInpNeg(pGetCoeff(p));
811  pSetComp(p,tso.ind2+1);
812  p_Setm_Syz(p, currRing, Components, ShiftedComponents); // actueller index
813  pNext(p) = pHead(tso.lcm);
814  pIter(p);
815  pSetComp(p,tso.ind1+1);
816  p_Setm_Syz(p, currRing, Components, ShiftedComponents); // actueller index
817  pSetCoeff(p,nDiv(pGetCoeff(tso.p2),coefgcd));
818  nDelete(&coefgcd);
819  if (tso.p != NULL)
820  {
821  kBucketInit(syzstr->bucket,tso.p,-1);
822  q = kBucketGetLm(syzstr->bucket);
823  j = Fin[pGetComp(q)]-1;
824  int pos = j+Hin[pGetComp(q)];
825  loop
826  {
827  if (j<0) break;
828  if (pLmDivisibleByNoComp(redset[j],q))
829  {
830  pNext(p) = pHead(q);
831  pIter(p);
832  pSetComp(p,bin[j]+1);
833  p_Setm_Syz(p, currRing, Components, ShiftedComponents); // actueller index
834 //if (pLength(redset[j])!=syzstr->elemLength[index][bin[j]])
835 //Print("Halt");
836 //if (pLength(redset[j])!=syzstr->elemLength[index][bin[j]])
837 //Print("Halt");
838  pGetCoeff(p) = nInpNeg(pGetCoeff(p));
839  number up = kBucketPolyRed(syzstr->bucket,redset[j],elL[bin[j]],
840  NULL);
841  // Thomas: Check whether you need number here
842  nDelete(&up);
843  q = kBucketGetLm(syzstr->bucket);
844  if (q==NULL) break;
845  j = Fin[pGetComp(q)]-1;
846  pos = j+Hin[pGetComp(q)];
847  }
848  else
849  {
850  j++;
851  if (j==pos) break;
852  }
853  }
854  int lb;
855  kBucketClear(syzstr->bucket,&tso.p,&lb);
856  }
857  if (tso.p != NULL)
858  {
859  if (TEST_OPT_PROT) PrintS("g");
860  if (k==IDELEMS((syzstr->res)[index]))
861  {
862  syEnlargeFields(syzstr,index);
863  bin=syzstr->backcomponents[index];
864  elL=syzstr->elemLength[index];
865  redset=syzstr->orderedRes[index]->m;
866  Components = syzstr->truecomponents[index];
867  ShiftedComponents = syzstr->ShiftedComponents[index];
868  }
869  pNext(p) = pHead(tso.p);
870  pIter(p);
871 
872  assume(p!= NULL);
873  k++;
874  syzstr->res[index]->m[k-1] = tso.p;
875  syzstr->elemLength[index][k-1] = pLength(tso.p);
876  pNorm(syzstr->res[index]->m[k-1]);
877  need_reset = syOrder(syzstr->res[index]->m[k-1],syzstr,index,k);
878  pSetComp(p,k); // actueller index
879  p_Setm_Syz(p, currRing, Components, ShiftedComponents);
880  pGetCoeff(p) = nInpNeg(pGetCoeff(p));
881 
882  tso.isNotMinimal = p;
883  tso.p = NULL;
884  }
885  else
886  {
887  if (TEST_OPT_PROT) PrintS(".");
888  //if (index % 2==0)
889  //euler++;
890  //else
891  //euler--;
892  }
893  if (ks==IDELEMS(syzstr->res[index+1]))
894  {
895  syEnlargeFields(syzstr,index+1);
896  }
897  syzstr->res[index+1]->m[ks] = tso.syz;
898  syzstr->elemLength[index+1][ks] = pLength(tso.syz);
899  pNorm(syzstr->res[index+1]->m[ks]);
900  tso.syz =NULL;
901  tso.syzind = ks;
902  if (need_reset)
903  syResetShiftedComponents(syzstr, index+1);
904  if (syOrder(syzstr->res[index+1]->m[ks],syzstr,index+1,ks+1))
905  syResetShiftedComponents(syzstr, index+2);
906  ks++;
907  p = NULL;
908  nextPairs[(*spl1)[i]-1] = tso;
909  }
910  i++;
911  }
912  delete spl1;
913 }
914 
915 /*3
916 * reduces the generators of the module index in degree deg
917 * (which are actual syzygies of the module index-1)
918 * wrt. the ideal generated by elements of lower degrees
919 */
920 static void syRedGenerOfCurrDeg(syStrategy syzstr, int deg, int index)
921 {
922  ideal res=syzstr->res[index];
923  int i=0,j,k=IDELEMS(res);
924  SSet sPairs=syzstr->resPairs[index-1];
925 
926  while ((k>0) && (res->m[k-1]==NULL)) k--;
927  while ((i<(*syzstr->Tl)[index-1]) && (((sPairs)[i].syz==NULL) ||
928  ((sPairs)[i].order<deg)))
929  i++;
930  if ((i>=(*syzstr->Tl)[index-1]) || ((sPairs)[i].order>deg)) return;
931  while ((i<(*syzstr->Tl)[index-1]) && (((sPairs)[i].syz==NULL) ||
932  ((sPairs)[i].order==deg)))
933  {
934  if ((sPairs)[i].syz!=NULL)
935  {
936  j = k-1;
937  while ((j>=0) && (res->m[j]!=NULL) &&
938  ((sPairs)[i].syz!=NULL))
939  {
940  if (pLmDivisibleBy(res->m[j],(sPairs)[i].syz))
941  {
942  (sPairs)[i].syz =
943  ksOldSpolyRed(res->m[j],(sPairs)[i].syz);
944  //sySPolyRed((sPairs)[i].syz,res->m[j]);
945  j = k-1;
946  }
947  else
948  {
949  j--;
950  }
951  }
952  if ((sPairs)[i].syz != NULL)
953  {
954  if (k==IDELEMS(res))
955  {
956  syEnlargeFields(syzstr,index);
957  res=syzstr->res[index];
958  }
959  if (TEST_OPT_DEBUG)
960  {
961  if ((sPairs)[i].isNotMinimal==NULL)
962  {
963  PrintLn();
964  PrintS("minimal generator: ");pWrite((syzstr->resPairs[index-1])[i].syz);
965  PrintS("comes from: ");pWrite((syzstr->resPairs[index-1])[i].p1);
966  PrintS("and: ");pWrite((syzstr->resPairs[index-1])[i].p2);
967  }
968  }
969  //res->m[k] = (sPairs)[i].syz;
970  res->m[k] = syRedtail((sPairs)[i].syz,syzstr,index);
971  (sPairs)[i].syzind = k;
972  syzstr->elemLength[index][k] = pLength((sPairs)[i].syz);
973  pNorm(res->m[k]);
974  // (sPairs)[i].syz = NULL;
975  k++;
976  if (syOrder(res->m[k-1],syzstr,index,k))
977  syResetShiftedComponents(syzstr, index);
978  //euler++;
979  }
980  else
981  (sPairs)[i].syzind = -1;
982  }
983  i++;
984  }
985 }
986 
987 /*3
988 * puts a pair into the right place in resPairs
989 */
990 void syEnterPair(SSet sPairs, SObject * so, int * sPlength,int /*index*/)
991 {
992  int ll,k,no=(*so).order,sP=*sPlength,i;
993 
994  if ((sP==0) || (sPairs[sP-1].order<=no))
995  ll = sP;
996  else if (sP==1)
997  ll = 0;
998  else
999  {
1000  int an=0,en=sP-1;
1001  loop
1002  {
1003  if (an>=en-1)
1004  {
1005  if ((sPairs[an].order<=no) && (sPairs[an+1].order>no))
1006  {
1007  ll = an+1;
1008  break;
1009  }
1010  else if ((sPairs[en].order<=no) && (sPairs[en+1].order>no))
1011  {
1012  ll = en+1;
1013  break;
1014  }
1015  else if (sPairs[an].order>no)
1016  {
1017  ll = an;
1018  break;
1019  }
1020  else
1021  {
1022  PrintS("Hier ist was faul!\n");
1023  break;
1024  }
1025  }
1026  i=(an+en) / 2;
1027  if (sPairs[i].order <= no)
1028  an=i;
1029  else
1030  en=i;
1031  }
1032  }
1033  for (k=(*sPlength);k>ll;k--)
1034  {
1035  syCopyPair(&sPairs[k-1],&sPairs[k]);
1036  }
1037  syCopyPair(so,&sPairs[ll]);
1038  (*sPlength)++;
1039 }
1040 void syEnterPair(syStrategy syzstr, SObject * so, int * sPlength,int index)
1041 {
1042  int ll;
1043 
1044  if (*sPlength>=(*syzstr->Tl)[index])
1045  {
1046  SSet temp = (SSet)omAlloc0(((*syzstr->Tl)[index]+16)*sizeof(SObject));
1047  for (ll=0;ll<(*syzstr->Tl)[index];ll++)
1048  {
1049  temp[ll].p = (syzstr->resPairs[index])[ll].p;
1050  temp[ll].p1 = (syzstr->resPairs[index])[ll].p1;
1051  temp[ll].p2 = (syzstr->resPairs[index])[ll].p2;
1052  temp[ll].syz = (syzstr->resPairs[index])[ll].syz;
1053  temp[ll].lcm = (syzstr->resPairs[index])[ll].lcm;
1054  temp[ll].ind1 = (syzstr->resPairs[index])[ll].ind1;
1055  temp[ll].ind2 = (syzstr->resPairs[index])[ll].ind2;
1056  temp[ll].syzind = (syzstr->resPairs[index])[ll].syzind;
1057  temp[ll].order = (syzstr->resPairs[index])[ll].order;
1058  temp[ll].isNotMinimal = (syzstr->resPairs[index])[ll].isNotMinimal;
1059  temp[ll].length = (syzstr->resPairs[index])[ll].length;
1060  temp[ll].reference = (syzstr->resPairs[index])[ll].reference;
1061  }
1062  if (syzstr->resPairs[index] != NULL) // OB: ?????
1063  omFreeSize((ADDRESS)syzstr->resPairs[index],(*syzstr->Tl)[index]*sizeof(SObject));
1064  (*syzstr->Tl)[index] += 16;
1065  syzstr->resPairs[index] = temp;
1066  }
1067  syEnterPair(syzstr->resPairs[index],so,sPlength,index);
1068 }
1069 
1070 /*3
1071 * computes pairs from the new elements (beginning with the element newEl)
1072 * in the module index
1073 */
1074 static void syCreateNewPairs(syStrategy syzstr, int index, int newEl)
1075 {
1076  SSet temp;
1077  SObject tso;
1078  int i,ii,j,k=IDELEMS(syzstr->res[index]),l=(*syzstr->Tl)[index],ll;
1079  int first,pos,jj,j1;
1080  int * bci=syzstr->backcomponents[index];
1081  poly p,q;
1082  polyset rs=syzstr->res[index]->m,nPm;
1083 
1084 
1085  while ((k>0) && (rs[k-1]==NULL)) k--;
1086  if (newEl>=k) return;
1087 
1088  long * ShiftedComponents = syzstr->ShiftedComponents[index];
1089  int* Components = syzstr->truecomponents[index];
1090 
1091  ideal nP=idInit(k,syzstr->res[index]->rank);
1092  nPm=nP->m;
1093  while ((l>0) && ((syzstr->resPairs[index])[l-1].p1==NULL)) l--;
1094  for (j=newEl;j<k;j++)
1095  {
1096  q = rs[j];
1097  first = syzstr->Firstelem[index-1][pGetComp(q)]-1;
1098  pos = first+syzstr->Howmuch[index-1][pGetComp(q)];
1099  for (i=first;i<pos;i++)
1100  {
1101  jj = bci[i];
1102  if (jj>=j) break;
1103  p = pOne();
1104  pLcm(rs[jj],q,p);
1105  pSetComp(p,j+1);
1106  p_Setm_Syz(p, currRing, Components, ShiftedComponents);
1107  ii = first;
1108  loop
1109  {
1110  j1 = bci[ii];
1111  if (nPm[j1]!=NULL)
1112  {
1113  if (pLmDivisibleByNoComp(nPm[j1],p))
1114  {
1115  pDelete(&p);
1116  break;
1117  }
1118  else if (pLmDivisibleByNoComp(p,nPm[j1]))
1119  {
1120  pDelete(&(nPm[j1]));
1121  //break;
1122  }
1123  }
1124  ii++;
1125  if (ii>=pos) break;
1126  }
1127  if (p!=NULL)
1128  {
1129  nPm[jj] = p;
1130  }
1131  }
1132  for (i=first;i<pos;i++)
1133  {
1134  ii = bci[i];
1135  if (nPm[ii]!=NULL)
1136  {
1137  if (l>=(*syzstr->Tl)[index])
1138  {
1139  temp = (SSet)omAlloc0(((*syzstr->Tl)[index]+16)*sizeof(SObject));
1140  for (ll=0;ll<(*syzstr->Tl)[index];ll++)
1141  {
1142  temp[ll].p = (syzstr->resPairs[index])[ll].p;
1143  temp[ll].p1 = (syzstr->resPairs[index])[ll].p1;
1144  temp[ll].p2 = (syzstr->resPairs[index])[ll].p2;
1145  temp[ll].syz = (syzstr->resPairs[index])[ll].syz;
1146  temp[ll].lcm = (syzstr->resPairs[index])[ll].lcm;
1147  temp[ll].ind1 = (syzstr->resPairs[index])[ll].ind1;
1148  temp[ll].ind2 = (syzstr->resPairs[index])[ll].ind2;
1149  temp[ll].syzind = (syzstr->resPairs[index])[ll].syzind;
1150  temp[ll].order = (syzstr->resPairs[index])[ll].order;
1151  temp[ll].isNotMinimal = (syzstr->resPairs[index])[ll].isNotMinimal;
1152  }
1153  if (syzstr->resPairs[index] != NULL) // OB: ????
1154  omFreeSize((ADDRESS)syzstr->resPairs[index],(*syzstr->Tl)[index]*sizeof(SObject));
1155  (*syzstr->Tl)[index] += 16;
1156  syzstr->resPairs[index] = temp;
1157  }
1158  tso.lcm = p = nPm[ii];
1159  nPm[ii] = NULL;
1160  tso.order = pTotaldegree(p);
1161  if ((syzstr->cw!=NULL) && (index>0) && (pGetComp(q)>0))
1162  {
1163  int ii=index-1,jj=pGetComp(q);
1164  while (ii>0)
1165  {
1166  jj = pGetComp(syzstr->res[ii]->m[jj-1]);
1167  ii--;
1168  }
1169  tso.order += (*syzstr->cw)[jj-1];
1170  }
1171  tso.p1 = rs[ii];
1172  tso.p2 = q;
1173  tso.ind1 = ii;
1174  tso.ind2 = j;
1175  tso.syzind = -1;
1176  tso.isNotMinimal = NULL;
1177  tso.p = NULL;
1178  tso.syz = NULL;
1179  syEnterPair(syzstr->resPairs[index],&tso,&l,index);
1180  }
1181  }
1182  }
1183  idDelete(&nP);
1184 }
1185 
1187  int *howmuch, int * actdeg, int an, int en)
1188 {
1189  int newdeg=*actdeg,newindex=-1,i,t,sldeg;
1190  SSet result;
1191  SRes resPairs=syzstr->resPairs;
1192 
1193  if (an>syzstr->length) return NULL;
1194  if (en>syzstr->length) en=syzstr->length;
1195  while (*index<en)
1196  {
1197  if (resPairs[*index]!=NULL)
1198  {
1199  sldeg = (*actdeg)+*index;
1200  i = 0;
1201  if (*index!=0)
1202  {
1203  while ((i<(*syzstr->Tl)[*index]))
1204  {
1205  if ((resPairs[*index])[i].lcm!=NULL)
1206  {
1207  if ((resPairs[*index])[i].order == sldeg)
1208  {
1209  result = &(resPairs[*index])[i];
1210  *howmuch =1;
1211  i++;
1212  while ((i<(*syzstr->Tl)[*index]) && ((resPairs[*index])[i].lcm!=NULL)
1213  && ((resPairs[*index])[i].order == sldeg))
1214  {
1215  i++;
1216  (*howmuch)++;
1217  }
1218  return result;
1219  }
1220  }
1221  i++;
1222  }
1223  }
1224  else
1225  {
1226  while ((i<(*syzstr->Tl)[*index]))
1227  {
1228  if ((resPairs[*index])[i].syz!=NULL)
1229  {
1230  if ((resPairs[*index])[i].order == sldeg)
1231  {
1232  result = &(resPairs[*index])[i];
1233  (*howmuch) =1;
1234  i++;
1235  while ((i<(*syzstr->Tl)[*index]) && ((resPairs[*index])[i].syz!=NULL)
1236  && ((resPairs[*index])[i].order == *actdeg))
1237  {
1238  i++;
1239  (*howmuch)++;
1240  }
1241  return result;
1242  }
1243  }
1244  i++;
1245  }
1246  }
1247  }
1248  (*index)++;
1249  }
1250  *index = an;
1251  //if (TEST_OPT_PROT) Print("(Euler:%d)",euler);
1252  while (*index<en)
1253  {
1254  if (resPairs[*index]!=NULL)
1255  {
1256  i = 0;
1257  while ((i<(*syzstr->Tl)[*index]))
1258  {
1259  t = *actdeg+*index;
1260  if (((resPairs[*index])[i].lcm!=NULL) ||
1261  ((resPairs[*index])[i].syz!=NULL))
1262  {
1263  if ((resPairs[*index])[i].order > t)
1264  t = (resPairs[*index])[i].order;
1265  }
1266  if ((t>*actdeg+*index) && ((newdeg==*actdeg) || (t<newdeg+*index)))
1267  {
1268  newdeg = t-*index;
1269  newindex = *index;
1270  break;
1271  }
1272  i++;
1273  }
1274  }
1275  (*index)++;
1276  }
1277  if (newdeg>*actdeg)
1278  {
1279  *actdeg = newdeg;
1280  *index = newindex;
1281  return syChosePairsPutIn(syzstr,index,howmuch,actdeg,an,en);
1282  }
1283  else return NULL;
1284 }
1285 
1286 /*3
1287 * FOR THE HOMOGENEOUS CASE ONLY!
1288 * looks through the pair set and the given module for
1289 * remaining pairs or generators to consider
1290 * returns a pointer to the first pair and the number of them in the given module
1291 * works with slanted degree (i.e. deg=realdeg-index)
1292 */
1293 SSet syChosePairs(syStrategy syzstr, int *index, int *howmuch, int * actdeg)
1294 {
1295  return syChosePairsPutIn(syzstr,index,howmuch,actdeg,0,syzstr->length);
1296 }
1297 
1298 /*3
1299 * FOR THE INHOMOGENEOUS CASE ONLY!
1300 * looks through the pair set and the given module for
1301 * remaining pairs or generators to consider
1302 * returns a pointer to the first pair and the number of them in the given module
1303 * works with slanted degree (i.e. deg=realdeg-index)
1304 * looks first through the 0 and 1 module then through the other
1305 */
1306 static SSet syChosePairsIH(syStrategy syzstr, int *index,
1307  int *howmuch, int * actdeg, int mindeg)
1308 {
1309  SSet result=NULL;
1310 
1311  result = syChosePairsPutIn(syzstr,index,howmuch,actdeg,0,2);
1312  if (result == NULL)
1313  {
1314  *actdeg = mindeg;
1315  result = syChosePairsPutIn(syzstr,index,howmuch,actdeg,2,syzstr->length);
1316  }
1317  return result;
1318 }
1319 
1320 /*3
1321 * looks through the pair set and the given module for
1322 * remaining pairs or generators to consider
1323 * returns a pointer to the first pair and the number of them in the given module
1324 * works deg by deg
1325 */
1326 /*
1327 *static SSet syChosePairs1(SRes resPairs,intvec * Tl, int *index, int *howmuch,
1328 * int length,int * actdeg)
1329 *{
1330 * int newdeg=*actdeg,newindex=-1,i,t;
1331 * SSet result;
1332 *
1333 * while (*index>=0)
1334 * {
1335 * if (resPairs[*index]!=NULL)
1336 * {
1337 * i = 0;
1338 * if (*index!=0)
1339 * {
1340 * while ((i<(*Tl)[*index]))
1341 * {
1342 * if ((resPairs[*index])[i].lcm!=NULL)
1343 * {
1344 * if (pGetOrder((resPairs[*index])[i].lcm) == *actdeg)
1345 * {
1346 * result = &(resPairs[*index])[i];
1347 * *howmuch =1;
1348 * i++;
1349 * while ((i<(*Tl)[*index]) && ((resPairs[*index])[i].lcm!=NULL)
1350 * && (pGetOrder((resPairs[*index])[i].lcm) == *actdeg))
1351 * {
1352 * i++;
1353 * (*howmuch)++;
1354 * }
1355 * return result;
1356 * }
1357 * }
1358 * i++;
1359 * }
1360 * }
1361 * else
1362 * {
1363 * while ((i<(*Tl)[*index]))
1364 * {
1365 * if ((resPairs[*index])[i].syz!=NULL)
1366 * {
1367 * if ((resPairs[*index])[i].order == *actdeg)
1368 * {
1369 * result = &(resPairs[*index])[i];
1370 * (*howmuch) =1;
1371 * i++;
1372 * while ((i<(*Tl)[*index]) && ((resPairs[*index])[i].syz!=NULL)
1373 * && ((resPairs[*index])[i].order == *actdeg))
1374 * {
1375 * i++;
1376 * (*howmuch)++;
1377 * }
1378 * return result;
1379 * }
1380 * }
1381 * i++;
1382 * }
1383 * }
1384 * }
1385 * (*index)--;
1386 * }
1387 * *index = length-1;
1388 * while (*index>=0)
1389 * {
1390 * if (resPairs[*index]!=NULL)
1391 * {
1392 * i = 0;
1393 * while ((i<(*Tl)[*index]))
1394 * {
1395 * t = *actdeg;
1396 * if ((resPairs[*index])[i].lcm!=NULL)
1397 * {
1398 * if (pGetOrder((resPairs[*index])[i].lcm) > *actdeg)
1399 * t = pGetOrder((resPairs[*index])[i].lcm);
1400 * }
1401 * else if ((resPairs[*index])[i].syz!=NULL)
1402 * {
1403 * if ((resPairs[*index])[i].order > *actdeg)
1404 * t = (resPairs[*index])[i].order;
1405 * }
1406 * if ((t>*actdeg) && ((newdeg==*actdeg) || (t<newdeg)))
1407 * {
1408 * newdeg = t;
1409 * newindex = *index;
1410 * break;
1411 * }
1412 * i++;
1413 * }
1414 * }
1415 * (*index)--;
1416 * }
1417 * if (newdeg>*actdeg)
1418 * {
1419 * *actdeg = newdeg;
1420 * *index = newindex;
1421 * return syChosePairs1(resPairs,Tl,index,howmuch,length,actdeg);
1422 * }
1423 * else return NULL;
1424 *}
1425 */
1426 #if 0 /* only debugging */
1427 /*3
1428 * statistics of the resolution
1429 */
1430 static void syStatistics(resolvente res,int length)
1431 {
1432  int i,j=1,k;
1433  long deg = 0;
1434 
1435  PrintLn();
1436  while ((j<length) && (res[j]!=NULL))
1437  {
1438  Print("In module %d: \n",j);
1439  k = 0;
1440  while ((k<IDELEMS(res[j])) && (res[j]->m[k]!=NULL))
1441  {
1442  i = 1;
1443  deg = pGetOrder(res[j]->m[k]);
1444  k++;
1445  while ((k<IDELEMS(res[j])) && (res[j]->m[k]!=NULL) &&
1446  (pGetOrder(res[j]->m[k])==deg))
1447  {
1448  i++;
1449  k++;
1450  }
1451  Print("%d elements of degree %ld\n",i,deg);
1452  }
1453  j++;
1454  }
1455 }
1456 #endif
1457 
1458 /*3
1459 * initialize a module
1460 */
1461 int syInitSyzMod(syStrategy syzstr, int index, int init)
1462 {
1463  int result;
1464 
1465  if (syzstr->res[index]==NULL)
1466  {
1467  syzstr->res[index] = idInit(init-1,1);
1468  syzstr->truecomponents[index] = (int*)omAlloc0(init*sizeof(int));
1469  syzstr->ShiftedComponents[index] = (long*)omAlloc0(init*sizeof(long));
1470  if (index==0)
1471  {
1472  for (int i=0;i<init;i++)
1473  {
1474  syzstr->truecomponents[0][i] = i;
1475  syzstr->ShiftedComponents[0][i] = (i)*SYZ_SHIFT_BASE;
1476  }
1477  }
1478  syzstr->backcomponents[index] = (int*)omAlloc0(init*sizeof(int));
1479  syzstr->Howmuch[index] = (int*)omAlloc0(init*sizeof(int));
1480  syzstr->Firstelem[index] = (int*)omAlloc0(init*sizeof(int));
1481  syzstr->elemLength[index] = (int*)omAlloc0(init*sizeof(int));
1482  syzstr->orderedRes[index] = idInit(init-1,1);
1483  syzstr->sev[index] = (unsigned long*) omAlloc0(init*sizeof(unsigned long));
1484  result = 0;
1485  }
1486  else
1487  {
1488  result = IDELEMS(syzstr->res[index]);
1489  while ((result>0) && (syzstr->res[index]->m[result-1]==NULL)) result--;
1490  }
1491  return result;
1492 }
1493 
1494 /*3
1495 * deletes a resolution
1496 */
1497 void syKillComputation(syStrategy syzstr, ring r)
1498 {
1499  if (syzstr->references>0)
1500  {
1501  (syzstr->references)--;
1502  }
1503  else
1504  {
1505  int i,j;
1506  if (syzstr->minres!=NULL)
1507  {
1508  for (i=0;i<syzstr->length;i++)
1509  {
1510  if (syzstr->minres[i]!=NULL)
1511  {
1512  id_Delete(&(syzstr->minres[i]),r);
1513  }
1514  }
1515  omFreeSize((ADDRESS)syzstr->minres,(syzstr->length+1)*sizeof(ideal));
1516  }
1517  if (syzstr->fullres!=NULL)
1518  {
1519  for (i=0;i<syzstr->length;i++)
1520  {
1521  if (syzstr->fullres[i]!=NULL)
1522  {
1523  id_Delete(&(syzstr->fullres[i]),r);
1524  }
1525  }
1526  omFreeSize((ADDRESS)syzstr->fullres,(syzstr->length+1)*sizeof(ideal));
1527  }
1528  if (syzstr->weights!=0)
1529  {
1530  for (i=0;i<syzstr->length;i++)
1531  {
1532  if (syzstr->weights[i]!=NULL)
1533  {
1534  delete syzstr->weights[i];
1535  }
1536  }
1537  omFreeSize((ADDRESS)syzstr->weights,syzstr->length*sizeof(intvec*));
1538  }
1539 
1540  ring sr=syzstr->syRing;
1541  if (sr==NULL) sr=r;
1542 
1543  if (syzstr->resPairs!=NULL)
1544  {
1545  for (i=0;i<syzstr->length;i++)
1546  {
1547  for (j=0;j<(*syzstr->Tl)[i];j++)
1548  {
1549  if ((syzstr->resPairs[i])[j].lcm!=NULL)
1550  p_Delete(&((syzstr->resPairs[i])[j].lcm),sr);
1551  if ((i>0) && ((syzstr->resPairs[i])[j].syz!=NULL))
1552  p_Delete(&((syzstr->resPairs[i])[j].syz),sr);
1553  }
1554  if (syzstr->orderedRes[i]!=NULL)
1555  {
1556  for (j=0;j<IDELEMS(syzstr->orderedRes[i]);j++)
1557  {
1558  syzstr->orderedRes[i]->m[j] = NULL;
1559  }
1560  id_Delete(&(syzstr->orderedRes[i]),sr);
1561  }
1562  if (syzstr->truecomponents[i]!=NULL)
1563  {
1564  omFreeSize((ADDRESS)syzstr->truecomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1565  syzstr->truecomponents[i]=NULL;
1566  omFreeSize((ADDRESS)syzstr->ShiftedComponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(long));
1567  syzstr->ShiftedComponents[i]=NULL;
1568  }
1569  if (syzstr->backcomponents[i]!=NULL)
1570  {
1571  omFreeSize((ADDRESS)syzstr->backcomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1572  syzstr->backcomponents[i]=NULL;
1573  }
1574  if (syzstr->Howmuch[i]!=NULL)
1575  {
1576  omFreeSize((ADDRESS)syzstr->Howmuch[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1577  syzstr->Howmuch[i]=NULL;
1578  }
1579  if (syzstr->Firstelem[i]!=NULL)
1580  {
1581  omFreeSize((ADDRESS)syzstr->Firstelem[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1582  syzstr->Firstelem[i]=NULL;
1583  }
1584  if (syzstr->elemLength[i]!=NULL)
1585  {
1586  omFreeSize((ADDRESS)syzstr->elemLength[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1587  syzstr->elemLength[i]=NULL;
1588  }
1589  if (syzstr->res[i]!=NULL)
1590  {
1591  for (j=0;j<IDELEMS(syzstr->res[i]);j++)
1592  {
1593  if (syzstr->res[i]->m[j]!=NULL)
1594  p_Delete(&(syzstr->res[i]->m[j]),sr);
1595  }
1596  }
1597  if ((syzstr->hilb_coeffs!=NULL)
1598  && (syzstr->hilb_coeffs[i]!=NULL))
1599  delete syzstr->hilb_coeffs[i];
1600  if (syzstr->sev[i] != NULL)
1601  omFreeSize((ADDRESS)syzstr->sev[i], (IDELEMS(syzstr->res[i])+1)*sizeof(unsigned long));
1602  id_Delete(&(syzstr->res[i]),sr);
1603  if (syzstr->resPairs[i] != NULL) // OB: ????
1604  omFreeSize((ADDRESS)syzstr->resPairs[i],(*syzstr->Tl)[i]*sizeof(SObject));
1605  }
1606  omFreeSize((ADDRESS)syzstr->resPairs,syzstr->length*sizeof(SObject*));
1607  omFreeSize((ADDRESS)syzstr->res,(syzstr->length+1)*sizeof(ideal));
1608  omFreeSize((ADDRESS)syzstr->orderedRes,(syzstr->length+1)*sizeof(ideal));
1609  omFreeSize((ADDRESS)syzstr->elemLength,(syzstr->length+1)*sizeof(int*));
1610  omFreeSize((ADDRESS)syzstr->truecomponents,(syzstr->length+1)*sizeof(int*));
1611  omFreeSize((ADDRESS)syzstr->ShiftedComponents,(syzstr->length+1)*sizeof(long*));
1612  if (syzstr->sev != NULL)
1613  omFreeSize(((ADDRESS)syzstr->sev), (syzstr->length+1)*sizeof(unsigned long*));
1614  omFreeSize((ADDRESS)syzstr->backcomponents,(syzstr->length+1)*sizeof(int*));
1615  omFreeSize((ADDRESS)syzstr->Howmuch,(syzstr->length+1)*sizeof(int*));
1616  omFreeSize((ADDRESS)syzstr->Firstelem,(syzstr->length+1)*sizeof(int*));
1617  if (syzstr->hilb_coeffs!=NULL)
1618  omFreeSize((ADDRESS)syzstr->hilb_coeffs,(syzstr->length+1)*sizeof(intvec*));
1619  }
1620  if (syzstr->cw!=NULL)
1621  delete syzstr->cw;
1622  if (syzstr->betti!=NULL)
1623  delete syzstr->betti;
1624  if (syzstr->resolution!=NULL)
1625  delete syzstr->resolution;
1626  if (syzstr->Tl!=NULL)
1627  delete syzstr->Tl;
1628  if ((syzstr->syRing != NULL) && (syzstr->syRing != r))
1629  {
1630  if(syzstr->syRing->typ[1].ord_typ == ro_syzcomp)
1631  rChangeSComps(NULL, NULL, 0, syzstr->syRing);
1632 
1633  rDelete(syzstr->syRing);
1634  }
1635  omFreeSize((ADDRESS)syzstr, sizeof(ssyStrategy));
1636  }
1637 }
1638 
1639 /*2
1640 * divides out the weight monomials (given by the Schreyer-ordering)
1641 * from the LaScala-resolution
1642 */
1644  syStrategy syzstr,BOOLEAN toCopy,resolvente totake)
1645 {
1646  int i,j,l;
1647  poly p,q,tq;
1648  polyset ri1;
1649  resolvente fullres;
1650  ring origR=syzstr->syRing;
1651  fullres = (resolvente)omAlloc0((length+1)*sizeof(ideal));
1652  if (totake==NULL)
1653  totake = res;
1654  for (i=length-1;i>0;i--)
1655  {
1656  if (res[i]!=NULL)
1657  {
1658  if (i>1)
1659  {
1660  j = IDELEMS(res[i-1]);
1661  while ((j>0) && (res[i-1]->m[j-1]==NULL)) j--;
1662  fullres[i-1] = idInit(IDELEMS(res[i]),j);
1663  ri1 = totake[i-1]->m;
1664  for (j=IDELEMS(res[i])-1;j>=0;j--)
1665  {
1666  p = res[i]->m[j];
1667  q = NULL;
1668  while (p!=NULL)
1669  {
1670  if (toCopy)
1671  {
1672  if (origR!=NULL)
1673  tq = prHeadR(p,origR, currRing);
1674  else
1675  tq = pHead(p);
1676  pIter(p);
1677  }
1678  else
1679  {
1680  res[i]->m[j] = NULL;
1681  if (origR!=NULL)
1682  {
1683  poly pp=p;
1684  pIter(p);
1685  pNext(pp)=NULL;
1686  tq = prMoveR(pp, origR, currRing);
1687  }
1688  else
1689  {
1690  tq = p;
1691  pIter(p);
1692  pNext(tq) = NULL;
1693  }
1694  }
1695 // pWrite(tq);
1696  pTest(tq);
1697  for (l=(currRing->N);l>0;l--)
1698  {
1699  if (origR!=NULL)
1700  pSubExp(tq,l, p_GetExp(ri1[pGetComp(tq)-1],l,origR));
1701  else
1702  pSubExp(tq,l, pGetExp(ri1[pGetComp(tq)-1],l));
1703  }
1704  pSetm(tq);
1705  pTest(tq);
1706  q = pAdd(q,tq);
1707  pTest(q);
1708  }
1709  fullres[i-1]->m[j] = q;
1710  }
1711  }
1712  else
1713  {
1714  if (origR!=NULL)
1715  {
1716  fullres[i-1] = idInit(IDELEMS(res[i]),res[i]->rank);
1717  for (j=IDELEMS(res[i])-1;j>=0;j--)
1718  {
1719  if (toCopy)
1720  fullres[i-1]->m[j] = prCopyR(res[i]->m[j], origR, currRing);
1721  else
1722  {
1723  fullres[i-1]->m[j] = prMoveR(res[i]->m[j], origR, currRing);
1724  res[i]->m[j] = NULL;
1725  }
1726  }
1727  }
1728  else
1729  {
1730  if (toCopy)
1731  fullres[i-1] = idCopy(res[i]);
1732  else
1733  {
1734  fullres[i-1] = res[i];
1735  res[i] = NULL;
1736  }
1737  }
1738  for (j=IDELEMS(fullres[i-1])-1;j>=0;j--)
1739  fullres[i-1]->m[j] = pSortCompCorrect(fullres[i-1]->m[j]);
1740  }
1741  if (!toCopy)
1742  {
1743  if (res[i]!=NULL) idDelete(&res[i]);
1744  }
1745  }
1746  }
1747  if (!toCopy)
1748  omFreeSize((ADDRESS)res,(length+1)*sizeof(ideal));
1749  //syzstr->length = length;
1750  return fullres;
1751 }
1752 
1753 /*3
1754 * read out the Betti numbers from resolution
1755 * (if not LaScala calls the traditional Betti procedure)
1756 */
1757 intvec * syBettiOfComputation(syStrategy syzstr, BOOLEAN minim,int * row_shift,
1758  intvec* weights)
1759 {
1760  int dummy;
1761  BOOLEAN std_weights=TRUE;
1762  if ((weights!=NULL)
1763  && (syzstr->betti!=NULL)
1764  && (syzstr->weights!=NULL) && (syzstr->weights[0]!=NULL))
1765  {
1766  int i;
1767  for(i=weights->length()-1; i>=0; i--)
1768  {
1769  //Print("test %d: %d - %d\n",i,(*weights)[i], (*(syzstr->weights[0]))[i]);
1770  if ((*weights)[i]!=(*(syzstr->weights[0]))[i])
1771  {
1772  std_weights=FALSE;
1773  break;
1774  }
1775  }
1776  }
1777  if ((syzstr->betti!=NULL)
1778  && (std_weights))
1779  {
1780  if (minim || (syzstr->resPairs!=NULL))
1781  return ivCopy(syzstr->betti);
1782  }
1783 
1784  resolvente fullres = syzstr->fullres;
1785  resolvente minres = syzstr->minres;
1786  const int length = syzstr->length;
1787 
1788  if ((fullres==NULL) && (minres==NULL))
1789  {
1790  if (syzstr->hilb_coeffs==NULL)
1791  { // LA SCALA
1792  fullres = syReorder(syzstr->res, length, syzstr);
1793  }
1794  else
1795  { // HRES
1796  minres = syReorder(syzstr->orderedRes, length, syzstr);
1797  syKillEmptyEntres(minres, length);
1798  }
1799  }
1800 
1801  intvec *result=NULL;
1802 
1803  if (fullres!=NULL)
1804  result = syBetti(fullres,length,&dummy,weights,minim,row_shift);
1805  else
1806  result = syBetti(minres,length,&dummy,weights,minim,row_shift);
1807 
1808 
1809  return result; /// Don't change the syzstr???
1810 
1811  // TODO: cleanup thses!
1812  if( fullres != NULL && syzstr->fullres == NULL )
1813  syzstr->fullres = fullres;
1814  if( minres != NULL && syzstr->minres == NULL )
1815  syzstr->minres = minres;
1816 
1817  if ((result!=NULL)
1818  && ((minim) || (syzstr->resPairs!=NULL))
1819  && std_weights
1820  && (syzstr->betti==NULL))
1821  {
1822  syzstr->betti = ivCopy(result); // cache the result...
1823  }
1824 
1825  return result;
1826 }
1827 
1828 /*3
1829 * computes the real length of the resolution
1830 */
1831 int sySize(syStrategy syzstr)
1832 {
1833  resolvente r=syzstr->res;
1834  if (r==NULL)
1835  r = syzstr->fullres;
1836  if (r==NULL)
1837  r = syzstr->minres;
1838  if (r==NULL)
1839  {
1840  WerrorS("No resolution found");
1841  return 0;
1842  }
1843  int i=syzstr->length;
1844  while ((i>0) && (r[i-1]==NULL)) i--;
1845  return i;
1846 }
1847 
1848 /*3
1849 * computes the cohomological dimension of res[1]
1850 */
1851 int syDim(syStrategy syzstr)
1852 {
1853  int i,l;
1854  if (syzstr->resPairs!=NULL)
1855  {
1856  SRes rP=syzstr->resPairs;
1857 
1858  l = syzstr->length;
1859  while ((l>0) && (rP[l-1]==NULL)) l--;
1860  if (l==0) return -1;
1861  l--;
1862  while (l>=0)
1863  {
1864  i = 0;
1865  while ((i<(*syzstr->Tl)[l]) &&
1866  ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)) &&
1867  (rP[l][i].isNotMinimal!=NULL))
1868  {
1869  i++;
1870  }
1871  if ((i<(*syzstr->Tl)[l]) &&
1872  ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)) &&
1873  (rP[l][i].isNotMinimal==NULL))
1874  return l;
1875  l--;
1876  }
1877  return l;
1878  }
1879  else
1880  return sySize(syzstr);
1881 }
1882 
1883 /*3
1884 * copies the resolution (by increment the reference counter)
1885 */
1887 {
1888  syStrategy result=syzstr;
1889  (result->references)++;
1890  return result;
1891 }
1892 
1893 /*2
1894 * local print procedure used in syPrint
1895 */
1896 static void syPrintEmptySpaces(int i)
1897 {
1898  if (i!=0)
1899  {
1900  PrintS(" ");
1901  syPrintEmptySpaces(i/10);
1902  }
1903 }
1904 
1905 /*2
1906 * local print procedure used in syPrint
1907 */
1908 static void syPrintEmptySpaces1(int i)
1909 {
1910  if (i!=0)
1911  {
1912  PrintS(" ");
1913  syPrintEmptySpaces1(i-1);
1914  }
1915 }
1916 
1917 /*2
1918 * local print procedure used in syPrint
1919 */
1920 static int syLengthInt(int i)
1921 {
1922  int j=0;
1923 
1924  if (i==0) return 1;
1925  while (i!=0)
1926  {
1927  j++;
1928  i = i/10;
1929  }
1930  return j;
1931 }
1932 
1933 /*3
1934 * prints the resolution as sequence of free modules
1935 */
1936 void syPrint(syStrategy syzstr, const char *sn)
1937 {
1938  if ( (syzstr->resPairs==NULL) &&
1939  (syzstr->fullres==NULL) &&
1940  (syzstr->minres==NULL) &&
1941  (syzstr->resolution == NULL) )
1942  {
1943  PrintS("No resolution defined\n");
1944  return;
1945  }
1946 
1947  intvec* resolution = syzstr->resolution;
1948 
1949  if (resolution==NULL)
1950  {
1951  if (syzstr->resPairs!=NULL)
1952  {
1953  resolution = new intvec(syzstr->length+1);
1954  SRes rP = syzstr->resPairs;
1955 // assume(idRankFreeModule(syzstr->res[1], (syzstr->syRing != NULL ? syzstr->syRing : currRing))==syzstr->res[1]->rank);
1956  (*resolution)[0] = syzstr->res[1]->rank;
1957  int k=0;
1958  while ((k<syzstr->length) && (rP[k]!=NULL))
1959  {
1960  int j = 0;
1961  while ((j<(*syzstr->Tl)[k]) &&
1962  ((rP[k][j].lcm!=NULL) || (rP[k][j].syz!=NULL)))
1963  {
1964  if (rP[k][j].isNotMinimal==NULL)
1965  ((*resolution)[k+1])++;
1966  j++;
1967  }
1968  k++;
1969  }
1970  }
1971  else
1972  {
1973  resolution = new intvec(syzstr->length+2);
1974  resolvente rr;
1975  if (syzstr->minres!=NULL)
1976  rr = syzstr->minres;
1977  else
1978  rr = syzstr->fullres;
1979  (*resolution)[0]
1980  = si_max(1,(int)id_RankFreeModule(rr[0],
1981  (syzstr->syRing != NULL ? syzstr->syRing : currRing)));
1982  int k=0;
1983  while ((k<syzstr->length) && (rr[k]!=NULL))
1984  {
1985  (*resolution)[k+1] = idElem(rr[k]);
1986  k++;
1987  }
1988  }
1989  }
1990 
1991  int sl=strlen(sn);
1992  syPrintEmptySpaces1(sl);
1993  int k = 0;
1994  loop
1995  {
1996  if ((k>=resolution->length()) || ((*resolution)[k]==0))
1997  break;
1998  Print("%d",(*resolution)[k]);
1999  syPrintEmptySpaces1(sl+5);
2000  k++;
2001  }
2002  PrintLn();
2003  k = 0;
2004  loop
2005  {
2006  if ((k>=resolution->length()) || ((*resolution)[k]==0))
2007  break;
2008  PrintS(sn);
2009  if (((k+1)>=resolution->length()) || ((*resolution)[(k+1)]==0))
2010  break;
2011  PrintS(" <-- ");
2012  syPrintEmptySpaces((*resolution)[k]);
2013  k++;
2014  }
2015  PrintLn();
2016  PrintLn();
2017  k = 0;
2018  loop
2019  {
2020  if ((k>=resolution->length()) || ((*resolution)[k]==0))
2021  break;
2022  Print("%d",k);
2023  syPrintEmptySpaces1(sl+5+syLengthInt((*resolution)[k])-
2024  syLengthInt(k));
2025  k++;
2026  }
2027  PrintLn();
2028  if (syzstr->minres==NULL)
2029  {
2030  PrintS("resolution not minimized yet\n");
2031  }
2032 
2033  if (syzstr->resolution == NULL) syzstr->resolution = resolution;
2034 }
2035 
2036 /*2
2037 * deleting all monomials the component of which correspond
2038 * to non-minimal generators
2039 */
2040 static poly syStripOut(poly p,intvec * toStrip)
2041 {
2042  if (toStrip==NULL) return p;
2043  poly pp=p;
2044 
2045  while ((pp!=NULL) && ((*toStrip)[pGetComp(pp)]!=0))
2046  pLmDelete(&pp);
2047  p = pp;
2048  if (pp!=NULL)
2049  {
2050  while (pNext(pp)!=NULL)
2051  {
2052  if ((*toStrip)[pGetComp(pNext(pp))]!=0)
2053  pLmDelete(&pNext(pp));
2054  else
2055  pIter(pp);
2056  }
2057  }
2058  return p;
2059 }
2060 
2061 /*2
2062 * copies only those monomials the component of which correspond
2063 * to minimal generators
2064 */
2065 static poly syStripOutCopy(poly p,intvec * toStrip)
2066 {
2067  if (toStrip==NULL) return pCopy(p);
2068  poly result=NULL,pp;
2069 
2070  while (p!=NULL)
2071  {
2072  if ((*toStrip)[pGetComp(p)]==0)
2073  {
2074  if (result==NULL)
2075  {
2076  result = pp = pHead(p);
2077  }
2078  else
2079  {
2080  pNext(pp) = pHead(p);
2081  pIter(pp);
2082  }
2083  }
2084  pIter(p);
2085  }
2086  return result;
2087 }
2088 
2089 /*2
2090 * minimizes toMin
2091 */
2092 #if 0 /* unused */
2093 static poly syMinimizeP(int toMin,syStrategy syzstr,intvec * ordn,int index,
2094  intvec * toStrip)
2095 {
2096  int ii=0,i,j,tc;
2097  poly p,pp,q=NULL,tq,pisN;
2098  SSet sPairs=syzstr->resPairs[index];
2099  poly tempStripped=NULL;
2100 
2101  //pp=pCopy(syzstr->res[index+1]->m[toMin]);
2102  pp = syStripOutCopy(syzstr->res[index+1]->m[toMin],toStrip);
2103  while ((ii<ordn->length()) && ((*ordn)[ii]!=-1) &&
2104  (sPairs[(*ordn)[ii]].syzind!=toMin))
2105  {
2106  ii++;
2107  }
2108  while (ii>=0)
2109  {
2110  i = (*ordn)[ii];
2111  if (sPairs[i].isNotMinimal!=NULL)
2112  {
2113  tempStripped =
2114  syStripOutCopy(syzstr->res[index+1]->m[sPairs[i].syzind],toStrip);
2115  pisN = sPairs[i].isNotMinimal;
2116  tc = pGetComp(pisN);
2117  p = pp;
2118  while (p!=NULL)
2119  {
2120  if (pGetComp(p)==(unsigned)tc)
2121  {
2122  tq = pInit();
2123  for(j=(currRing->N); j>0; j--)
2124  pSetExp(tq,j, pGetExp(p,j)-pGetExp(pisN,j));
2125  pSetComp(tq, 0);
2126  pSetCoeff0(tq,nDiv(pGetCoeff(p),pGetCoeff(pisN)));
2127  pGetCoeff(tq) = nInpNeg(pGetCoeff(tq));
2128  pSetm(tq);
2129  q = pAdd(q,pMult_mm(pCopy(tempStripped),tq));
2130  pDelete(&tq);
2131  }
2132  pIter(p);
2133  }
2134  if (q!=NULL)
2135  {
2136  pp = pAdd(pp,q);
2137  q = NULL;
2138  }
2139  pDelete(&tempStripped);
2140  }
2141  ii--;
2142  }
2143  return pp;
2144 }
2145 #endif
2146 
2147 /*2
2148 * minimizes toMin
2149 */
2150 static poly syMinimizeP1(int toMin,syStrategy syzstr,intvec * ordn,int index,
2151  intvec * toStrip)
2152 {
2153  int ii=0,i,tc,lp,ltS=-1;
2154  poly p,mp=NULL,pp;
2155  SSet sPairs=syzstr->resPairs[index];
2156  poly tempStripped=NULL;
2157 
2158  pp = syStripOutCopy(syzstr->res[index+1]->m[toMin],toStrip);
2159  kBucketInit(syzstr->bucket,pp,-1);
2160  while ((ii<ordn->length()) && ((*ordn)[ii]!=-1) &&
2161  (sPairs[(*ordn)[ii]].syzind!=toMin))
2162  {
2163  ii++;
2164  }
2165  while (ii>=0)
2166  {
2167  i = (*ordn)[ii];
2168  if (sPairs[i].isNotMinimal!=NULL)
2169  {
2170  tempStripped =
2171  syStripOutCopy(syzstr->res[index+1]->m[sPairs[i].syzind],toStrip);
2172  tc = pGetComp(sPairs[i].isNotMinimal);
2173  //p = pTakeOutComp1(&tempStripped,tc);
2174  int lu;
2175  pTakeOutComp(&tempStripped,tc,&p,&lu);
2176  kBucketTakeOutComp(syzstr->bucket,tc,&mp,&lp);
2177  mp = pDivideM(mp,p);
2178  while (mp!=NULL)
2179  {
2180  p = pNext(mp);
2181  pNext(mp) = NULL;
2182  ltS = -1;
2183  kBucket_Minus_m_Mult_p(syzstr->bucket,mp,tempStripped,&ltS);
2184  pDelete(&mp);
2185  mp = p;
2186  }
2187  pDelete(&mp);
2188  pDelete(&tempStripped);
2189  }
2190  ii--;
2191  }
2192  kBucketClear(syzstr->bucket,&pp,&lp);
2193  return pp;
2194 }
2195 
2196 /*2
2197 * deletes empty components after minimization
2198 */
2200 {
2201  int i,j,jj,k,rj;
2202  intvec * changes;
2203  poly p;
2204  ideal ri;
2205 
2206  for (i=0;i<length;i++)
2207  {
2208  ri = res[i];
2209  if (ri!=NULL)
2210  {
2211  rj = IDELEMS(ri);
2212  changes = new intvec(rj+1,1,-1);
2213  while ((rj>0) && (ri->m[rj-1]==NULL)) rj--;
2214  j = k = 0;
2215  while (j+k<rj)
2216  {
2217  if (ri->m[j+k]!=NULL)
2218  {
2219  ri->m[j] = ri->m[j+k];
2220  (*changes)[j+k+1] = j+1;
2221  j++;
2222  }
2223  else
2224  {
2225  k++;
2226  }
2227  }
2228  for (jj=j;jj<rj;jj++)
2229  ri->m[jj] = NULL;
2230  if (res[i+1]!=NULL)
2231  {
2232  ri = res[i+1];
2233  for (j=IDELEMS(ri)-1;j>=0;j--)
2234  {
2235  p = ri->m[j];
2236  while (p!=NULL)
2237  {
2238  pSetComp(p,(*changes)[pGetComp(p)]);
2239  pSetm(p);
2240  pIter(p);
2241  }
2242  }
2243  }
2244  delete changes;
2245  }
2246  }
2247 }
2248 
2249 /*2
2250 * determines the components for minimization
2251 */
2252 static intvec * syToStrip(syStrategy syzstr, int index)
2253 {
2254  intvec * result=NULL;
2255 
2256  if ((syzstr->resPairs[index-1]!=NULL) && (!idIs0(syzstr->res[index])))
2257  {
2258  result=new intvec(IDELEMS(syzstr->res[index])+1);
2259  for (int i=(*syzstr->Tl)[index-1]-1;i>=0;i--)
2260  {
2261  if (syzstr->resPairs[index-1][i].isNotMinimal!=NULL)
2262  {
2263  (*result)[syzstr->resPairs[index-1][i].syzind+1] = 1;
2264  }
2265  }
2266  }
2267  return result;
2268 }
2269 
2270 /*2
2271 * re-computes the order of pairs during the algorithm
2272 * this ensures to procede with a triangular matrix
2273 */
2274 static intvec * syOrdPairs(SSet sPairs, int length)
2275 {
2276  intvec * result=new intvec(length,1,-1);
2277  int i,j=0,k=-1,l,ii;
2278 
2279  loop
2280  {
2281  l = -1;
2282  for(i=0;i<length;i++)
2283  {
2284  if (sPairs[i].syzind>k)
2285  {
2286  if (l==-1)
2287  {
2288  l = sPairs[i].syzind;
2289  ii = i;
2290  }
2291  else
2292  {
2293  if (sPairs[i].syzind<l)
2294  {
2295  l = sPairs[i].syzind;
2296  ii = i;
2297  }
2298  }
2299  }
2300  }
2301  if (l==-1) break;
2302  (*result)[j] = ii;
2303  j++;
2304  k = l;
2305  }
2306  return result;
2307 }
2308 
2309 /*2
2310 * minimizes the output of LaScala
2311 */
2313  BOOLEAN computeStd=FALSE)
2314 {
2315  intvec * Strip, * ordn;
2316  resolvente tres=(resolvente)omAlloc0((syzstr->length+1)*sizeof(ideal));
2317  ring origR = currRing;
2318 
2319 //Print("Hier ");
2320  if (computeStd)
2321  {
2322  tres[0] = syzstr->res[1];
2323  syzstr->res[1] = idInit(IDELEMS(tres[0]),tres[0]->rank);
2324  return tres;
2325  }
2326  int i,l,index,i1;
2327  SSet sPairs;
2328 
2329  assume(syzstr->syRing != NULL);
2330  rChangeCurrRing(syzstr->syRing);
2331 //Print("laeufts ");
2332  syzstr->bucket = kBucketCreate(syzstr->syRing);
2333  for (index=syzstr->length-1;index>0;index--)
2334  {
2335  if (syzstr->resPairs[index]!=NULL)
2336  {
2337 //Print("ideal %d: \n",index);
2338  currcomponents = syzstr->truecomponents[index];
2341  IDELEMS(syzstr->res[index]), currRing);
2342  sPairs = syzstr->resPairs[index];
2343  Strip = syToStrip(syzstr,index);
2344  tres[index+1] = idInit(IDELEMS(syzstr->res[index+1]),syzstr->res[index+1]->rank);
2345  i1 = (*syzstr->Tl)[index];
2346 //Print("i1= %d\n",i1);
2347  ordn = syOrdPairs(sPairs,i1);
2348  for (i=0;i<i1;i++)
2349  {
2350  if ((sPairs[i].isNotMinimal==NULL) && (sPairs[i].lcm!=NULL))
2351  {
2352  l = sPairs[i].syzind;
2353 //Print("Minimiere Poly %d: ",l);pWrite(syzstr->res[index+1]->m[l]);
2354  tres[index+1]->m[l] =
2355  syMinimizeP1(l,syzstr,ordn,index,Strip);
2356  }
2357  }
2358  delete Strip;
2359  delete ordn;
2360  Strip = NULL;
2361  }
2362  }
2363  currcomponents = syzstr->truecomponents[0];
2366  IDELEMS(syzstr->res[0]), currRing);
2367  tres[1] = idInit(IDELEMS(syzstr->res[1]),syzstr->res[1]->rank);
2368  sPairs = syzstr->resPairs[0];
2369  for (i=(*syzstr->Tl)[0]-1;i>=0;i--)
2370  {
2371  if (sPairs[i].syzind>=0)
2372  {
2373  tres[1]->m[sPairs[i].syzind] = pCopy(syzstr->res[1]->m[sPairs[i].syzind]);
2374  }
2375  }
2376 /*--- changes to the original ring------------------*/
2377  kBucketDestroy(&syzstr->bucket);
2378  if (syzstr->syRing != NULL)
2379  {
2380  rChangeCurrRing(origR);
2381  // Thomas: now make sure that all data which you need is pFetchCopied
2382  // maybe incoporate it into syReorder ??
2383  }
2384  tres = syReorder(tres,syzstr->length,syzstr,FALSE,syzstr->res);
2385  syKillEmptyEntres(tres,syzstr->length);
2386  idSkipZeroes(tres[0]);
2387  return tres;
2388 }
2389 
2390 /*3
2391 * minimizes any kind of resolution
2392 */
2394 {
2395  if (syzstr->minres==NULL)
2396  {
2397  if (syzstr->resPairs!=NULL)
2398  {
2399  if (syzstr->hilb_coeffs==NULL)
2400  {
2401  // La Scala Resolution
2402  syzstr->minres = syReadOutMinimalRes(syzstr);
2403  }
2404  else
2405  { // HRES
2406  syzstr->minres = syReorder(syzstr->orderedRes,syzstr->length,syzstr);
2407  }
2408  }
2409  else if (syzstr->fullres!=NULL)
2410  {
2411  syMinimizeResolvente(syzstr->fullres,syzstr->length,1);
2412  syzstr->minres = syzstr->fullres;
2413  syzstr->fullres = NULL;
2414  }
2415  }
2416  (syzstr->references)++;
2417  return syzstr;
2418 }
2419 
2420 /*2
2421 * implementation of LaScala's algorithm
2422 * assumes that the given module is homogeneous
2423 * works with slanted degree, uses syChosePairs
2424 */
2425 syStrategy syLaScala3(ideal arg,int * length)
2426 {
2427  int i,j,actdeg=32000,index=0;
2428  int howmuch;
2429  ideal temp;
2430  SSet nextPairs;
2431  syStrategy syzstr=(syStrategy)omAlloc0(sizeof(ssyStrategy));
2432  ring origR = currRing;
2433 
2434  if ((idIs0(arg)) ||
2435  ((id_RankFreeModule(arg,currRing)>0) && (!idHomModule(arg,NULL,&(syzstr->cw)))))
2436  {
2438  syzstr->length = 1;
2439  syzstr->minres[0] = idInit(1,arg->rank);
2440  return syzstr;
2441  }
2442 
2443  //crit = 0;
2444  //euler = -1;
2445  redpol = pInit();
2446  syzstr->length = *length = (currRing->N)+2;
2447 
2448  // Creare dp,S ring and change to it
2449  syzstr->syRing = rAssure_dp_S(origR);
2450  assume(syzstr->syRing != origR); // why?
2451  rChangeCurrRing(syzstr->syRing);
2452 
2453  // set initial ShiftedComps
2454  currcomponents = (int*)omAlloc0((arg->rank+1)*sizeof(int));
2455  currShiftedComponents = (long*)omAlloc0((arg->rank+1)*sizeof(long));
2456  for (i=0;i<=arg->rank;i++)
2457  {
2459  currcomponents[i] = i;
2460  }
2462 /*--- initializes the data structures---------------*/
2463  syzstr->Tl = new intvec(*length);
2464  temp = idInit(IDELEMS(arg),arg->rank);
2465  for (i=0;i<IDELEMS(arg);i++)
2466  {
2467  temp->m[i] = prCopyR( arg->m[i], origR, syzstr->syRing);
2468  if (temp->m[i]!=NULL)
2469  {
2470  j = pTotaldegree(temp->m[i]);
2471  if (j<actdeg) actdeg = j;
2472  }
2473  }
2474  idTest(temp);
2475  idSkipZeroes(temp);
2476  idTest(temp);
2477  syzstr->resPairs = syInitRes(temp,length,syzstr->Tl,syzstr->cw);
2478  omFreeSize((ADDRESS)currcomponents,(arg->rank+1)*sizeof(int));
2479  omFreeSize((ADDRESS)currShiftedComponents,(arg->rank+1)*sizeof(long));
2480  syzstr->res = (resolvente)omAlloc0((*length+1)*sizeof(ideal));
2481  syzstr->orderedRes = (resolvente)omAlloc0((*length+1)*sizeof(ideal));
2482  syzstr->elemLength = (int**)omAlloc0((*length+1)*sizeof(int*));
2483  syzstr->truecomponents = (int**)omAlloc0((*length+1)*sizeof(int*));
2484  syzstr->ShiftedComponents = (long**)omAlloc0((*length+1)*sizeof(long*));
2485  syzstr->backcomponents = (int**)omAlloc0((*length+1)*sizeof(int*));
2486  syzstr->Howmuch = (int**)omAlloc0((*length+1)*sizeof(int*));
2487  syzstr->Firstelem = (int**)omAlloc0((*length+1)*sizeof(int*));
2488  syzstr->sev = (unsigned long **) omAlloc0((*length+1)*sizeof(unsigned long *));
2489  syzstr->bucket = kBucketCreate(currRing);
2490  int len0=id_RankFreeModule(temp,currRing)+1;
2491 
2492  nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2493  //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2494 /*--- computes the resolution ----------------------*/
2495  while (nextPairs!=NULL)
2496  {
2497  if (TEST_OPT_PROT) Print("%d",actdeg);
2498  if (TEST_OPT_PROT) Print("(m%d)",index);
2499  if (index==0)
2500  i = syInitSyzMod(syzstr,index,len0);
2501  else
2502  i = syInitSyzMod(syzstr,index);
2503  currcomponents = syzstr->truecomponents[si_max(index-1,0)];
2504  currShiftedComponents = syzstr->ShiftedComponents[si_max(index-1,0)];
2505  rChangeSComps(currcomponents, currShiftedComponents,
2506  IDELEMS(syzstr->res[si_max(index-1,0)]), currRing);
2507  j = syInitSyzMod(syzstr,index+1);
2508  if (index>0)
2509  {
2510  syRedNextPairs(nextPairs,syzstr,howmuch,index);
2511  syCompactifyPairSet(syzstr->resPairs[index],(*syzstr->Tl)[index],0);
2512  }
2513  else
2514  syRedGenerOfCurrDeg(syzstr,actdeg,index+1);
2515 /*--- creates new pairs -----------------------------*/
2516  syCreateNewPairs(syzstr,index,i);
2517  if (index<(*length)-1)
2518  {
2519  syCreateNewPairs(syzstr,index+1,j);
2520  }
2521  index++;
2522  nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2523  //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2524  }
2525  if (temp!=NULL) idDelete(&temp);
2526  kBucketDestroy(&(syzstr->bucket));
2527 
2528  if (origR != syzstr->syRing)
2529  rChangeCurrRing(origR);
2530  pLmDelete(&redpol);
2531 
2532  if (TEST_OPT_PROT) PrintLn();
2533 
2534  assume(syzstr->minres==NULL); assume(syzstr->fullres ==NULL);
2535  assume(syzstr->resPairs!=NULL); assume(syzstr->hilb_coeffs==NULL);
2536  assume(syzstr->res!=NULL);
2537 
2538  if(! TEST_OPT_NO_SYZ_MINIM )
2539  syzstr->minres = syReadOutMinimalRes(syzstr);
2540  else
2541  syzstr->fullres = syReorder(syzstr->res, syzstr->length, syzstr); // buggy? (betti...?)
2542 
2543  return syzstr;
2544 }
2545 
2546 
2547 
2548 /*2
2549 * more general implementation of LaScala's algorithm
2550 * assumes that the given module is (quasi-)homogeneous
2551 * works with slanted degree, uses syChosePairs
2552 */
2553 syStrategy syLaScala(ideal arg, int& maxlength, intvec* weights)
2554 {
2555  int i,j,actdeg=32000,index=0;
2556  int howmuch;
2557  ideal temp;
2558  SSet nextPairs;
2559  syStrategy syzstr=(syStrategy)omAlloc0(sizeof(ssyStrategy));
2560  ring origR = currRing;
2561 
2562  if(weights!= NULL)
2563  syzstr->cw = new intvec(weights);
2564  else
2565  syzstr->cw = NULL;
2566 
2567  if ((idIs0(arg)) ||
2568  ((id_RankFreeModule(arg,currRing)>0) && (!idTestHomModule(arg, NULL, syzstr->cw))))
2569  {
2571  syzstr->length = 1;
2572  syzstr->minres[0] = idInit(1,arg->rank);
2573  return syzstr;
2574  }
2575 
2576 
2577  //crit = 0;
2578  //euler = -1;
2579  redpol = pInit();
2580 
2581  if( maxlength > 0 )
2582  syzstr->length = maxlength; // = (currRing->N)+2;
2583  else
2584  syzstr->length = maxlength = (currRing->N)+2;
2585 
2586  // Creare dp,S ring and change to it
2587  syzstr->syRing = rAssure_dp_S(origR);
2588  assume(syzstr->syRing != origR);
2589  assume(syzstr->syRing->typ[1].ord_typ == ro_syzcomp);
2590  rChangeCurrRing(syzstr->syRing);
2591 
2592  // set initial ShiftedComps
2593  currcomponents = (int*)omAlloc0((arg->rank+1)*sizeof(int));
2594  currShiftedComponents = (long*)omAlloc0((arg->rank+1)*sizeof(long));
2595  for (i=0;i<=arg->rank;i++)
2596  {
2598  currcomponents[i] = i;
2599  }
2601 /*--- initializes the data structures---------------*/
2602  syzstr->Tl = new intvec(maxlength);
2603  temp = idInit(IDELEMS(arg),arg->rank);
2604  for (i=0;i<IDELEMS(arg);i++)
2605  {
2606  temp->m[i] = prCopyR( arg->m[i], origR, currRing);
2607  if (temp->m[i]!=NULL)
2608  {
2609  j = pTotaldegree(temp->m[i]);
2610  if (j<actdeg) actdeg = j;
2611  }
2612  }
2613  idTest(temp);
2614  idSkipZeroes(temp);
2615  idTest(temp);
2616  syzstr->resPairs = syInitRes(temp,&maxlength,syzstr->Tl,syzstr->cw);
2617  omFreeSize((ADDRESS)currcomponents,(arg->rank+1)*sizeof(int));
2618  omFreeSize((ADDRESS)currShiftedComponents,(arg->rank+1)*sizeof(long));
2619 
2620  syzstr->res = (resolvente)omAlloc0((maxlength+1)*sizeof(ideal));
2621  syzstr->orderedRes = (resolvente)omAlloc0((maxlength+1)*sizeof(ideal));
2622  syzstr->elemLength = (int**)omAlloc0((maxlength+1)*sizeof(int*));
2623 
2624  syzstr->truecomponents = (int**)omAlloc0((maxlength+1)*sizeof(int*));
2625  syzstr->ShiftedComponents = (long**)omAlloc0((maxlength+1)*sizeof(long*));
2626 
2627  syzstr->backcomponents = (int**)omAlloc0((maxlength+1)*sizeof(int*));
2628  syzstr->Howmuch = (int**)omAlloc0((maxlength+1)*sizeof(int*));
2629  syzstr->Firstelem = (int**)omAlloc0((maxlength+1)*sizeof(int*));
2630  syzstr->sev = (unsigned long **) omAlloc0((maxlength+1)*sizeof(unsigned long *));
2631 
2632  assume( syzstr->length == maxlength );
2633 
2634  syzstr->bucket = kBucketCreate(currRing);
2635  int len0=id_RankFreeModule(temp,currRing)+1;
2636 
2637  nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2638  //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2639 /*--- computes the resolution ----------------------*/
2640  while (nextPairs!=NULL)
2641  {
2642  if (TEST_OPT_PROT) Print("%d",actdeg);
2643  if (TEST_OPT_PROT) Print("(m%d)",index);
2644  if (index==0)
2645  i = syInitSyzMod(syzstr,index,len0);
2646  else
2647  i = syInitSyzMod(syzstr,index);
2648  currcomponents = syzstr->truecomponents[si_max(index-1,0)];
2649  currShiftedComponents = syzstr->ShiftedComponents[si_max(index-1,0)];
2650  rChangeSComps(currcomponents, currShiftedComponents,
2651  IDELEMS(syzstr->res[si_max(index-1,0)]), currRing);
2652  j = syInitSyzMod(syzstr,index+1);
2653  if (index>0)
2654  {
2655  syRedNextPairs(nextPairs,syzstr,howmuch,index);
2656  syCompactifyPairSet(syzstr->resPairs[index],(*syzstr->Tl)[index],0);
2657  }
2658  else
2659  syRedGenerOfCurrDeg(syzstr,actdeg,index+1);
2660 /*--- creates new pairs -----------------------------*/
2661  syCreateNewPairs(syzstr,index,i);
2662  if (index<(maxlength-1))
2663  {
2664  syCreateNewPairs(syzstr,index+1,j);
2665  }
2666  index++;
2667  nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2668  //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2669  }
2670  if (temp!=NULL) idDelete(&temp);
2671  kBucketDestroy(&(syzstr->bucket));
2672  if (origR != syzstr->syRing)
2673  rChangeCurrRing(origR);
2674  pLmDelete(&redpol);
2675  if (TEST_OPT_PROT) PrintLn();
2676  return syzstr;
2677 }
2678 
int length
Definition: syz.h:60
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:495
intvec ** weights
Definition: syz.h:45
poly prHeadR(poly p, ring src_r, ring dest_r, prCopyProc_t prproc)
Definition: prCopy.cc:127
#define omRealloc0Size(addr, o_size, size)
Definition: omAllocDecl.h:221
static intvec * syLinStrat(SSet nextPairs, syStrategy syzstr, int howmuch, int index)
Definition: syz1.cc:654
void syKillEmptyEntres(resolvente res, int length)
Definition: syz1.cc:2199
static void syCreateNewPairs(syStrategy syzstr, int index, int newEl)
Definition: syz1.cc:1074
#define pSetm(p)
Definition: polys.h:253
intvec * syBettiOfComputation(syStrategy syzstr, BOOLEAN minim, int *row_shift, intvec *weights)
Definition: syz1.cc:1757
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:467
void syEnlargeFields(syStrategy syzstr, int index)
Definition: syz1.cc:739
void PrintLn()
Definition: reporter.cc:310
#define Print
Definition: emacs.cc:83
#define pAdd(p, q)
Definition: polys.h:186
static SSet syChosePairsPutIn(syStrategy syzstr, int *index, int *howmuch, int *actdeg, int an, int en)
Definition: syz1.cc:1186
poly prCopyR(poly p, ring src_r, ring dest_r)
Definition: prCopy.cc:36
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
kBucket_pt bucket
Definition: syz.h:54
syStrategy syCopy(syStrategy syzstr)
Definition: syz1.cc:1886
#define nNormalize(n)
Definition: numbers.h:30
int syDim(syStrategy syzstr)
Definition: syz1.cc:1851
#define TEST_OPT_PROT
Definition: options.h:98
loop
Definition: myNF.cc:98
if(0 > strat->sl)
Definition: myNF.cc:73
#define pSetExp(p, i, v)
Definition: polys.h:42
#define FALSE
Definition: auxiliary.h:95
Compatiblity layer for legacy polynomial operations (over currRing)
#define omMemcpyW(p1, p2, l)
Definition: omMemOps.h:29
return P p
Definition: myNF.cc:203
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition: kbuckets.cc:1053
void syInitializePair(SObject *so)
Definition: syz1.cc:71
void syMinimizeResolvente(resolvente res, int length, int first)
Definition: syz.cc:360
short references
Definition: syz.h:63
intvec * betti
Definition: syz.h:53
int * currcomponents
Definition: syz1.cc:39
BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
Definition: ideals.cc:1834
poly prMoveR(poly &p, ring src_r, ring dest_r)
Definition: prCopy.cc:91
#define pTest(p)
Definition: polys.h:399
poly syRedtail(poly p, syStrategy syzstr, int index)
Definition: syz1.cc:231
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:480
#define pSubExp(p, i, v)
Definition: polys.h:46
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
intvec * ivCopy(const intvec *o)
Definition: intvec.h:126
static void syRedNextPairs(SSet nextPairs, syStrategy syzstr, int howmuch, int index)
Definition: syz1.cc:773
KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether, ring r)
Definition: kInline.h:1073
resolvente syReorder(resolvente res, int length, syStrategy syzstr, BOOLEAN toCopy, resolvente totake)
Definition: syz1.cc:1643
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
resolvente res
Definition: syz.h:47
#define TRUE
Definition: auxiliary.h:99
#define pLcm(a, b, m)
Definition: polys.h:278
void * ADDRESS
Definition: auxiliary.h:116
static resolvente syReadOutMinimalRes(syStrategy syzstr, BOOLEAN computeStd=FALSE)
Definition: syz1.cc:2312
void pWrite(poly p)
Definition: polys.h:291
void WerrorS(const char *s)
Definition: feFopen.cc:24
int k
Definition: cfEzgcd.cc:93
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition: ideals.h:169
#define TEST_OPT_DEBUG
Definition: options.h:103
#define pLmDivisibleBy(a, b)
like pDivisibleBy, except that it is assumed that a!=NULL, b!=NULL
Definition: polys.h:140
#define pMult_mm(p, m)
Definition: polys.h:185
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:51
#define SYZ_SHIFT_MAX_NEW_COMP_ESTIMATE
Definition: syz.h:15
#define omAlloc(size)
Definition: omAllocDecl.h:210
void syCopyPair(SObject *argso, SObject *imso)
Definition: syz1.cc:90
#define pGetComp(p)
Component.
Definition: polys.h:37
poly pp
Definition: myNF.cc:296
long syReorderShiftedComponents(long *sc, int n)
Definition: syz1.cc:339
omBin char_ptr_bin
Definition: ring.cc:55
void syPrint(syStrategy syzstr, const char *sn)
Definition: syz1.cc:1936
intvec ** hilb_coeffs
Definition: syz.h:46
void syCompactifyPairSet(SSet sPairs, int sPlength, int first)
Definition: syz1.cc:112
#define pIter(p)
Definition: monomials.h:44
intvec * Tl
Definition: syz.h:50
poly res
Definition: myNF.cc:322
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
#define pGetExp(p, i)
Exponent.
Definition: polys.h:41
void rGetSComps(int **currComponents, long **currShiftedComponents, int *length, ring r)
Definition: ring.cc:4328
const ring r
Definition: syzextra.cc:208
static BOOLEAN syOrder(poly p, syStrategy syzstr, int index, int realcomp)
Definition: syz1.cc:466
resolvente orderedRes
Definition: syz.h:48
syStrategy syLaScala3(ideal arg, int *length)
Definition: syz1.cc:2425
#define pGetOrder(p)
Order.
Definition: polys.h:34
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:200
#define pSortCompCorrect(p)
Assume: If considerd only as poly in any component of p (say, monomials of other components of p are ...
Definition: polys.h:210
Definition: intvec.h:14
static int syChMin(intvec *iv)
Definition: syz1.cc:275
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:464
#define TEST_OPT_NO_SYZ_MINIM
Definition: options.h:118
int j
Definition: myNF.cc:70
static int max(int a, int b)
Definition: fast_mult.cc:264
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
Definition: polys.h:142
static long pTotaldegree(poly p)
Definition: polys.h:265
void syKillComputation(syStrategy syzstr, ring r)
Definition: syz1.cc:1497
#define assume(x)
Definition: mod2.h:403
static poly syMinimizeP1(int toMin, syStrategy syzstr, intvec *ordn, int index, intvec *toStrip)
Definition: syz1.cc:2150
#define nInpNeg(n)
Definition: numbers.h:21
#define pDivideM(a, b)
Definition: polys.h:277
#define SYZ_SHIFT_BASE
Definition: syz.h:18
int syInitSyzMod(syStrategy syzstr, int index, int init)
Definition: syz1.cc:1461
#define pSetComp(p, v)
Definition: polys.h:38
int m
Definition: cfEzgcd.cc:119
int ** backcomponents
Definition: syz.h:41
int sySize(syStrategy syzstr)
Definition: syz1.cc:1831
static int si_max(const int a, const int b)
Definition: auxiliary.h:121
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
int ** Howmuch
Definition: syz.h:42
static void syPrintEmptySpaces(int i)
Definition: syz1.cc:1896
#define pOne()
Definition: polys.h:298
static unsigned pLength(poly a)
Definition: p_polys.h:189
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
Definition: kbuckets.cc:690
SSet syChosePairs(syStrategy syzstr, int *index, int *howmuch, int *actdeg)
Definition: syz1.cc:1293
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
static int syLengthInt(int i)
Definition: syz1.cc:1920
#define IDELEMS(i)
Definition: simpleideals.h:24
static void syRedGenerOfCurrDeg(syStrategy syzstr, int deg, int index)
Definition: syz1.cc:920
static void syPrintEmptySpaces1(int i)
Definition: syz1.cc:1908
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
resolvente fullres
Definition: syz.h:57
#define nDelete(n)
Definition: numbers.h:16
static int syzcomp2dpc_test(poly p1, poly p2)
Definition: syz1.cc:171
int ** Firstelem
Definition: syz.h:43
ideal idCopy(ideal A)
Definition: ideals.h:60
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
void rChangeCurrRing(ring r)
Definition: polys.cc:12
void p_Setm_Syz(poly p, ring r, int *Components, long *ShiftedComponents)
Definition: p_polys.cc:530
resolvente minres
Definition: syz.h:58
int ** elemLength
Definition: syz.h:44
intvec * cw
Definition: syz.h:52
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
int ** truecomponents
Definition: syz.h:39
static poly syStripOut(poly p, intvec *toStrip)
Definition: syz1.cc:2040
syStrategy syLaScala(ideal arg, int &maxlength, intvec *weights)
Definition: syz1.cc:2553
#define nDiv(a, b)
Definition: numbers.h:32
static poly syStripOutCopy(poly p, intvec *toStrip)
Definition: syz1.cc:2065
long ** ShiftedComponents
Definition: syz.h:40
#define NULL
Definition: omList.c:10
poly * polyset
Definition: hutil.h:15
ring rAssure_dp_S(const ring r)
Definition: ring.cc:4843
ring syRing
Definition: syz.h:56
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3555
SRes resPairs
Definition: syz.h:49
int length() const
Definition: intvec.h:86
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:448
void pTakeOutComp(poly *p, long comp, poly *q, int *lq, const ring R=currRing)
Splits *p into two polys: *q which consists of all monoms with component == comp and *p of all other ...
Definition: polys.h:322
static SSet syChosePairsIH(syStrategy syzstr, int *index, int *howmuch, int *actdeg, int mindeg)
Definition: syz1.cc:1306
syStrategy syMinimize(syStrategy syzstr)
Definition: syz1.cc:2393
static void pResetSetm(poly p)
Definition: syz1.cc:399
void syEnterPair(SSet sPairs, SObject *so, int *sPlength, int)
Definition: syz1.cc:990
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:346
unsigned long ** sev
Definition: syz.h:59
#define pInit()
allocates a new monomial and initializes everything to 0
Definition: polys.h:61
#define pDelete(p_ptr)
Definition: polys.h:169
long * currShiftedComponents
Definition: syz1.cc:40
#define pNext(p)
Definition: monomials.h:43
void syDeletePair(SObject *so)
Definition: syz1.cc:52
SObject * SSet
Definition: syz.h:32
poly p
Definition: kbuckets.h:181
SSet * SRes
Definition: syz.h:33
SRes syInitRes(ideal arg, int *length, intvec *Tl, intvec *cw)
Definition: syz1.cc:298
#define pSetCoeff0(p, n)
Definition: monomials.h:67
ideal * resolvente
Definition: ideals.h:18
KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether)
Definition: kInline.h:1053
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition: coeffs.h:692
int idElem(const ideal F)
count non-zero elements
intvec * syBetti(resolvente res, int length, int *regularity, intvec *weights, BOOLEAN tomin, int *row_shift)
Definition: syz.cc:791
static poly redpol
Definition: syz1.cc:44
long ind2(long arg)
Definition: kutil.cc:4197
static intvec * syToStrip(syStrategy syzstr, int index)
Definition: syz1.cc:2252
END_NAMESPACE const void * p2
Definition: syzextra.cc:202
polyrec * poly
Definition: hilb.h:10
static intvec * syOrdPairs(SSet sPairs, int length)
Definition: syz1.cc:2274
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:193
void syCompactify1(SSet sPairs, int *sPlength, int first)
Definition: syz1.cc:140
static Poly * h
Definition: janet.cc:978
int BOOLEAN
Definition: auxiliary.h:86
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
void rChangeSComps(int *currComponents, long *currShiftedComponents, int length, ring r)
Definition: ring.cc:4319
void kBucketTakeOutComp(kBucket_pt bucket, long comp, poly *r_p, int *l)
Definition: kbuckets.cc:1012
BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition: ideals.h:96
#define omAlloc0(size)
Definition: omAllocDecl.h:211
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
void syResetShiftedComponents(syStrategy syzstr, int index, int hilb)
Definition: syz1.cc:414
#define pCopy(p)
return a copy of the poly
Definition: polys.h:168
intvec * resolution
Definition: syz.h:51
#define idTest(id)
Definition: ideals.h:47
ssyStrategy * syStrategy
Definition: syz.h:35
ListNode * next
Definition: janet.h:31
#define Warn
Definition: emacs.cc:80