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