source: git/Singular/syz1.cc @ 0c6135

fieker-DuValspielwiese
Last change on this file since 0c6135 was 0c6135, checked in by Hans Schönemann <hannes@…>, 26 years ago
*hannes: Print optimized git-svn-id: file:///usr/local/Singular/svn/trunk@2626 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 69.7 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: syz1.cc,v 1.34 1998-11-02 09:05:43 Singular Exp $ */
5/*
6* ABSTRACT: resolutions
7*/
8
9
10#include "mod2.h"
11#include "tok.h"
12#include "mmemory.h"
13#include "polys.h"
14#include "febase.h"
15#include "kstd1.h"
16#include "kutil.h"
17#include "spolys.h"
18#include "spolys0.h"
19#include "stairc.h"
20#include "ipid.h"
21#include "cntrlc.h"
22#include "ipid.h"
23#include "intvec.h"
24#include "ipshell.h"
25#include "limits.h"
26#include "numbers.h"
27#include "modulop.h"
28#include "ideals.h"
29#include "intvec.h"
30#include "ring.h"
31#include "lists.h"
32#include "syz.h"
33
34
35/*--------------static variables------------------------*/
36/*---contains the real components wrt. cdp--------------*/
37//static int ** truecomponents=NULL;
38//static int ** backcomponents=NULL;
39//static int ** Howmuch=NULL;
40//static int ** Firstelem=NULL;
41/*---points to the real components of the actual module-*/
42static int *  currcomponents=NULL;
43/*---head-term-polynomials for the reduction------------*/
44static poly redpol=NULL;
45/*---counts number of applications of GM-criteria-------*/
46//static int crit;
47//static int zeroRed;
48//static int dsim;
49//static int simple;
50static int euler;
51/*---controls the ordering------------------------------*/
52static intvec * orderedcomp;
53static int *binomials;
54static int highdeg;
55static int highdeg_1;
56
57// uncomment to play around with new spolys for syzygies
58// #include "syzvector.cc"
59
60/*3
61* deletes all entres of a pair
62*/
63static void syDeletePair(SObject * so)
64{
65  pDelete(&(*so).p);
66  pDelete(&(*so).lcm);
67  pDelete(&(*so).syz);
68  (*so).p1 = NULL;
69  (*so).p2 = NULL;
70  (*so).ind1 = 0;
71  (*so).ind2 = 0;
72  (*so).syzind = -1;
73  (*so).order = 0;
74  (*so).isNotMinimal = NULL;
75}
76
77/*3
78* puts all entres of a pair to another
79*/
80static void syCopyPair(SObject * argso, SObject * imso)
81{
82  *imso=*argso;
83  //(*imso).p = (*argso).p;
84  //(*imso).p1 = (*argso).p1;
85  //(*imso).p2 = (*argso).p2;
86  //(*imso).lcm = (*argso).lcm;
87  //(*imso).syz = (*argso).syz;
88  //(*imso).ind1 = (*argso).ind1;
89  //(*imso).ind2 = (*argso).ind2;
90  //(*imso).syzind = (*argso).syzind;
91  //(*imso).order = (*argso).order;
92  //(*imso).isNotMinimal = (*argso).isNotMinimal;
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}
104
105/*3
106* deletes empty objects from a pair set beginning with
107* pair first
108* assumes a pair to be empty if .lcm does so
109*/
110static void syCompactifyPairSet(SSet sPairs, int sPlength, int first)
111{
112  int k=first,kk=0;
113
114  while (k+kk<sPlength)
115  {
116    if (sPairs[k+kk].lcm!=NULL)
117    {
118      if (kk>0) syCopyPair(&sPairs[k+kk],&sPairs[k]);
119      k++;
120    }
121    else
122    {
123      kk++;
124    }
125  }
126}
127
128/*3
129* deletes empty objects from a pair set beginning with
130* pair first
131* assumes a pair to be empty if .lcm does so
132*/
133static void syCompactify1(SSet sPairs, int* sPlength, int first)
134{
135  int k=first,kk=0;
136
137  while (k+kk<=*sPlength)
138  {
139    if (sPairs[k+kk].lcm!=NULL)
140    {
141      if (kk>0) syCopyPair(&sPairs[k+kk],&sPairs[k]);
142      k++;
143    }
144    else
145    {
146      kk++;
147    }
148  }
149  *sPlength -= kk;
150}
151
152/*3
153* replaces comp1dpc during homogeneous syzygy-computations
154* compares with components of currcomponents instead of the
155* exp[0]
156*/
157static int syzcomp1dpc(poly p1, poly p2)
158{
159  /*4 compare monomials by order then revlex*/
160    int i = pVariables;
161    if ((pGetExp(p1,i) == pGetExp(p2,i)))
162    {
163      do
164      {
165        i--;
166        if (i <= 1)
167        {
168          //(*orderingdepth)[pVariables-i]++;
169           /*4 handle module case:*/
170           if (pGetComp(p1)==pGetComp(p2)) return 0;
171           else if
172              (currcomponents[pGetComp(p1)]>currcomponents[pGetComp(p2)])
173                return 1;
174           else return -1;
175        }
176      } while ((pGetExp(p1,i) == pGetExp(p2,i)));
177    }
178    //(*orderingdepth)[pVariables-i]++;
179    if (pGetExp(p1,i) < pGetExp(p2,i)) return 1;
180    return -1;
181}
182
183/*3
184* replaces comp1dpc during homogeneous syzygy-computations
185* compares with components of currcomponents instead of the
186* exp[0]
187*/
188
189#ifdef SY_VEC_DEBUG
190static int normal_syzcomp2dpc(poly p1, poly p2);
191
192static int syzcomp2dpc(poly p1, poly p2)
193{
194  int n1 = normal_syzcomp2dpc(p1, p2);
195  int n2 = SyVecSyzCmp(p1, p2);
196
197  if (n1 != n2)
198  {
199    PrintS("Error in syzcomp\n");
200    SyVecSyzCmp(p1, p2);
201    normal_syzcomp2dpc(p1, p2);
202  }
203  return n1;
204}
205
206static int normal_syzcomp2dpc(poly p1, poly p2)
207#else
208#ifdef HAVE_SY_VECTOR
209static int dummy(poly p1, poly p2)
210#else
211static int syzcomp2dpc(poly p1, poly p2)
212#endif
213#endif
214{
215  int o1=pGetOrder(p1), o2=pGetOrder(p2);
216  if (o1 > o2) return 1;
217  if (o1 < o2) return -1;
218
219  if (o1>0)
220  {
221    int i = pVariables;
222    while ((i>1) && (pGetExp(p1,i)==pGetExp(p2,i)))
223      i--;
224    //(*orderingdepth)[pVariables-i]++;
225    if (i>1)
226    {
227      if (pGetExp(p1,i) < pGetExp(p2,i)) return 1;
228      return -1;
229    }
230  }
231  o1=pGetComp(p1);
232  o2=pGetComp(p2);
233  if (o1==o2/*pGetComp(p1)==pGetComp(p2)*/) return 0;
234  if (currcomponents[o1]>currcomponents[o2]) return 1;
235  return -1;
236}
237
238/*3
239* compares only the monomial without component
240*/
241static int syzcompmonomdp(poly p1, poly p2)
242{
243  int i;
244
245  /*4 compare monomials by order then revlex*/
246  if (pGetOrder(p1) == pGetOrder(p2))
247  {
248    i = pVariables;
249    if ((pGetExp(p1,i) == pGetExp(p2,i)))
250    {
251      do
252      {
253        i--;
254        if (i <= 1)
255          return 0;
256      } while ((pGetExp(p1,i) == pGetExp(p2,i)));
257    }
258    if (pGetExp(p1,i) < pGetExp(p2,i)) return 1;
259    return -1;
260  }
261  else if (pGetOrder(p1) > pGetOrder(p2)) return 1;
262  return -1;
263}
264
265/*
266* (i,j) in binomials[j-1,i-j+1]
267* table size is: pVariables * (highdeg+1)
268* highdeg_1==highdeg+1
269*/
270static void syBinomSet()
271{
272  highdeg_1=highdeg+1;
273  for(int j=1;j<=highdeg;j++)
274  {
275    binomials[j/*0,j*/] = j;
276    for (int i=1;i<pVariables;i++)
277    {
278      binomials[i*(highdeg_1)+j/*i,j*/]
279      = binomials[(i-1)*(highdeg_1)+j/*i-1,j*/]*(j+i)/(i+1);
280    }
281  }
282  for (int i=0;i<pVariables;i++)
283  {
284    binomials[i*(highdeg_1)/*i,0*/]=0;
285  }
286}
287
288static inline int syBinom(int i,int j)
289{
290  return binomials[(j-1)*(highdeg_1)+i-j+1/*j-1,i-j*/];
291}
292
293#if defined(HAVE_SY_VECTOR) && ! defined(SY_VEC_DEBUG)
294#define syzSetm(p) pSetm(p)
295#else
296static void syzSetm(poly p)
297{
298  int i = 0,j;
299  for (j=pVariables;j>0;j--)
300    i += pGetExp(p,j);
301
302  if (i<=highdeg)
303  {
304    i=1;
305    j = -INT_MAX;
306    int *ip=binomials+pGetExp(p,1);
307    loop
308    {
309      j += (*ip);
310      if (i==pVariables) break;
311      i++;
312      ip+=highdeg_1+pGetExp(p,i);
313    }
314    pGetOrder(p) = j;
315  }
316  else
317    pGetOrder(p)=i;
318}
319#endif
320
321static inline poly syMultT(poly p,poly m)
322{
323  poly q,result=q=pNew();
324  int j;
325
326  if (pGetOrder(p)>0)
327  {
328    loop
329    {
330      spMemcpy(q,p);
331      for (j=pVariables;j>0;j--)
332        pAddExp(q,j, pGetExp(m,j));
333      pSetCoeff0(q,nCopy(pGetCoeff(p)));
334      syzSetm(q);
335      pIter(p);
336      if (p!=NULL)
337      {
338        pNext(q) = pNew();
339        pIter(q);
340      }
341      else break;
342    }
343  }
344  else
345  {
346    poly lastmon=NULL;
347    int i=0;
348    loop
349    {
350      if (pGetOrder(p)!=i)
351      {
352        spMemcpy(q,p);
353        for (j=pVariables;j>0;j--)
354          pAddExp(q,j,  pGetExp(m,j));
355        syzSetm(q);
356        lastmon = q;
357        i = pGetOrder(p);
358      }
359      else
360      {
361        spMemcpy(q,lastmon);
362        pSetComp(q,pGetComp(p));
363      }
364      pSetCoeff0(q,nCopy(pGetCoeff(p)));
365      pIter(p);
366      if (p!=NULL)
367      {
368        pNext(q) = pNew();
369        pIter(q);
370      }
371      else break;
372    }
373  }
374  pNext(q) = NULL;
375  return result;
376}
377
378static inline poly syMultTNeg(poly p,poly m)
379{
380  poly q,result=q=pNew();
381  int j;
382
383  if (pGetOrder(p)>0)
384  {
385    loop
386    {
387      spMemcpy(q,p);
388      for (j=pVariables;j>0;j--)
389        pAddExp(q,j, pGetExp(m,j));
390      pSetCoeff0(q,nCopy(pGetCoeff(p)));
391      pGetCoeff(q) = nNeg(pGetCoeff(q));
392      syzSetm(q);
393      pIter(p);
394      if (p!=NULL)
395      {
396        pNext(q) = pNew();
397        pIter(q);
398      }
399      else break;
400    }
401  }
402  else
403  {
404    poly lastmon=NULL;
405    int i=0;
406    loop
407    {
408      if (pGetOrder(p)!=i)
409      {
410        spMemcpy(q,p);
411        for (j=pVariables;j>0;j--)
412          pAddExp(q,j, pGetExp(m,j));
413        syzSetm(q);
414        lastmon = q;
415        i = pGetOrder(p);
416      }
417      else
418      {
419        spMemcpy(q,lastmon);
420        pSetComp(q,pGetComp(p));
421      }
422      pSetCoeff0(q,nCopy(pGetCoeff(p)));
423      pGetCoeff(q) = nNeg(pGetCoeff(q));
424      pIter(p);
425      if (p!=NULL)
426      {
427        pNext(q) = pNew();
428        pIter(q);
429      }
430      else break;
431    }
432  }
433  pNext(q) = NULL;
434  return result;
435}
436
437static poly syMultT1(poly p,poly m)
438{
439  poly q,result=q=pNew();
440  int j;
441
442  if (pGetOrder(p)>0)
443  {
444    loop
445    {
446      spMemcpy(q,p);
447      for (j=pVariables;j>0;j--)
448        pAddExp(q,j, pGetExp(m,j));
449      pSetCoeff0(q,nMult(pGetCoeff(p),pGetCoeff(m)));
450      syzSetm(q);
451      pIter(p);
452      if (p!=NULL)
453      {
454        pNext(q) = pNew();
455        pIter(q);
456      }
457      else break;
458    }
459  }
460  else
461  {
462    poly lastmon=NULL;
463    int i=0;
464    loop
465    {
466      if (pGetOrder(p)!=i)
467      {
468        spMemcpy(q,p);
469        for (j=pVariables;j>0;j--)
470          pAddExp(q,j, pGetExp(m,j));
471        syzSetm(q);
472        lastmon = q;
473        i = pGetOrder(p);
474      }
475      else
476      {
477        spMemcpy(q,lastmon);
478        pSetComp(q,pGetComp(p));
479      }
480      pSetCoeff0(q,nMult(pGetCoeff(p),pGetCoeff(m)));
481      pIter(p);
482      if (p!=NULL)
483      {
484        pNext(q) = pNew();
485        pIter(q);
486      }
487      else break;
488    }
489  }
490  pNext(q) = NULL;
491  return result;
492}
493
494static inline poly syAdd(poly m1,poly m2)
495{
496  if (m1==NULL)
497    return m2;
498  if (m2==NULL)
499    return m1;
500  if ((pGetOrder(m1)>0) && (pGetOrder(m2)>0))
501  {
502    return pAdd(m1,m2);
503  }
504  else
505  {
506    poly p,result=p=pInit();
507    number n;
508    loop
509    {
510      if (pGetOrder(m1)>pGetOrder(m2))
511      {
512        pNext(p) = m1;
513        pIter(p);
514        pIter(m1);
515      }
516      else if (pGetOrder(m1)<pGetOrder(m2))
517      {
518        pNext(p) = m2;
519        pIter(p);
520        pIter(m2);
521      }
522      else if (currcomponents[pGetComp(m1)]>currcomponents[pGetComp(m2)])
523      {
524        pNext(p) = m1;
525        pIter(p);
526        pIter(m1);
527      }
528      else if (currcomponents[pGetComp(m1)]<currcomponents[pGetComp(m2)])
529      {
530        pNext(p) = m2;
531        pIter(p);
532        pIter(m2);
533      }
534      else
535      {
536        n = nAdd(pGetCoeff(m1),pGetCoeff(m2));
537        if (nIsZero(n))
538        {
539          pDelete1(&m1);
540        }
541        else
542        {
543          pNext(p) = m1;
544          pIter(p);
545          pIter(m1);
546          pSetCoeff(p,n);
547        }
548        pDelete1(&m2);
549      }
550      if (m1==NULL)
551      {
552        pNext(p) = m2;
553        break;
554      }
555      if (m2==NULL)
556      {
557        pNext(p) = m1;
558        break;
559      }
560    }
561    pDelete1(&result);
562    return result;
563  }
564}
565
566poly syOrdPolySchreyer(poly p)
567{
568  return pOrdPolyMerge(p);
569}
570
571#ifdef SY_VEC_DEBUG
572static poly normal_sySPAdd(poly m1,poly m2,poly m);
573static poly sySPAdd(poly m1, poly m2, poly m)
574{
575  poly temp1 = pCopy(m1);
576
577  poly p1 = normal_sySPAdd(m1, m2, m);
578  poly p2 = syVecSpoly(m2, temp1, m);
579
580  pTest(p1);
581  pTest(p2);
582  if (p1 != NULL)
583  {
584    if (p2 == NULL || ! pEqual(p1, p2))
585    {
586      PrintS("Error in SySpoly\n");
587//      poly temp5 = pCopy(temp3);
588//      poly temp6 = pCopy(temp4);
589//      p1 = normal_sySPAdd(temp3, temp4, m);
590//      p2 = syVecSpoly(temp6, temp5, m);
591    }
592  }
593  else if (p2 != NULL)
594    PrintS("Error in SySpoly\n");
595
596  return p1;
597}
598
599static poly normal_sySPAdd(poly m1,poly m2,poly m)
600#else
601#ifdef HAVE_SY_VECTOR
602#define sySPAdd(p1, p2, m) syVecSpoly(p2, p1, m)
603static poly dummy(poly m1,poly m2,poly m)
604#else
605static poly sySPAdd(poly m1,poly m2,poly m)
606#endif
607#endif
608{
609  int i2=-INT_MAX;
610  int i1;
611  int j;
612  //register poly m1=m11;
613  poly p=redpol;
614  poly tm2=pNew();
615  number multwith=pGetCoeff(m);
616
617  pDelete1(&m1);
618  i1 = pGetOrder(m1);
619  pIter(m2);
620  spMemcpy(tm2,m2);
621  j = 1;
622  pAddExp(tm2,1, pGetExp(m,1));
623  int *ip=binomials+pGetExp(tm2,1);
624  loop
625  {
626    i2 += (*ip);
627    if (j==pVariables) break;
628    j++;
629    pAddExp(tm2,j,pGetExp(m,j));
630    ip+=highdeg_1+pGetExp(tm2,j);
631  }
632  pGetOrder(tm2) = i2;
633  pSetCoeff0(tm2,nMult(pGetCoeff(m2),multwith));
634  loop
635  {
636    j = i1-i2;
637    if (j>0/*m1->order>tm2->order*/)
638    {
639      p = pNext(p) = m1;
640      pIter(m1);
641      if (m1!=NULL)
642        i1 = pGetOrder(m1);
643      else
644        break;
645    }
646    else if (j<0/*m1->order<tm2->order*/)
647    {
648      p = pNext(p) = tm2;
649      j = pGetOrder(m2);
650      pIter(m2);
651      if (m2!=NULL)
652      {
653        j -=pGetOrder(m2);
654        tm2 = pNew();
655        if (j!=0)
656        {
657          spMemcpy(tm2,m2);
658          j = 1;
659          pAddExp(tm2,1, pGetExp(m,1));
660          int *ip=binomials+pGetExp(tm2,1);
661          i2=-INT_MAX;
662          loop
663          {
664            i2 += (*ip);
665            if (j==pVariables) break;
666            j++;
667            pAddExp(tm2,j, pGetExp(m,j));
668            ip+=highdeg_1+pGetExp(tm2,j);
669          }
670          pGetOrder(tm2) = i2;
671          //simple++;
672        }
673        else
674        {
675          spMemcpy(tm2,p);
676          pSetComp(tm2,pGetComp(m2));
677          //dsim++;
678        }
679        //pNext(tm2) = NULL;
680        pSetCoeff0(tm2,nMult(pGetCoeff(m2),multwith));
681      }
682      else
683        break;
684    }
685    else
686    {
687      j = currcomponents[pGetComp(m1)]-currcomponents[pGetComp(m2)];
688      if (j>0/*currcomponents[pGetComp(m1)]>currcomponents[pGetComp(m2)]*/)
689      {
690        p = pNext(p) = m1;
691        pIter(m1);
692        if (m1!=NULL)
693          i1 = pGetOrder(m1);
694        else
695          break;
696      }
697      else
698      {
699        if (j<0/*currcomponents[pGetComp(m1)]<currcomponents[pGetComp(m2)]*/)
700        {
701          p = pNext(p) = tm2;
702          j = pGetOrder(m2);
703        }
704        else
705        {
706          number n = nAdd(pGetCoeff(m1),pGetCoeff(tm2));
707          if (nIsZero(n))
708          {
709            pDelete1(&tm2);
710            nDelete(&n);
711            j = 0;
712          }
713          else
714          {
715            p = pNext(p) = tm2;
716            pSetCoeff(p,n);
717            j = pGetOrder(m2);
718          }
719          pDelete1(&m1);
720          if (m1==NULL)
721          {
722            pIter(m2);
723            break;
724          }
725          else
726            i1 = pGetOrder(m1);
727        }
728        pIter(m2);
729        if (m2!=NULL)
730        {
731          j -=pGetOrder(m2);
732          tm2 = pNew();
733          if (j!=0)
734          {
735            spMemcpy(tm2,m2);
736            j = 1;
737            pAddExp(tm2,1, pGetExp(m,1));
738            int *ip=binomials+pGetExp(tm2,1);
739            i2=-INT_MAX;
740            loop
741            {
742              i2 += (*ip);
743              if (j==pVariables) break;
744              j++;
745              pAddExp(tm2,j, pGetExp(m,j));
746              ip+=highdeg_1+pGetExp(tm2,j);
747            }
748            pGetOrder(tm2) = i2;
749            //simple++;
750          }
751          else
752          {
753            spMemcpy(tm2,p);
754            pSetComp(tm2,pGetComp(m2));
755            //dsim++;
756          }
757          //pNext(tm2) = NULL;
758          pSetCoeff0(tm2,nMult(pGetCoeff(m2),multwith));
759        }
760        else
761          break;
762      }
763    }
764  }
765  if (m2==NULL)
766  {
767    pNext(p) = m1;
768  }
769  else
770  {
771    pNext(p) = syMultT1(m2,m);
772  }
773  return pNext(redpol);
774}
775
776static inline poly sySPoly(poly m1,poly m2,poly lcm)
777{
778  poly a=pDivide(lcm,m1);
779  poly b1=NULL,b2=NULL;
780  if (pNext(m1)!=NULL)
781    b1 = syMultT(pNext(m1),a);
782  pDelete(&a);
783  a=pDivide(lcm,m2);
784  if (pNext(m2)!=NULL)
785    b2 = syMultTNeg(pNext(m2),a);
786  pDelete(&a);
787  return syAdd(b1,b2);
788}
789
790static poly sySPolyRed(poly m1,poly m2)
791{
792  if (pNext(m2)==NULL)
793  {
794    pDelete1(&m1);
795    return m1;
796  }
797  poly a=pDivide(m1,m2);
798  pSetCoeff0(a,nCopy(pGetCoeff(m1)));
799  pGetCoeff(a) = nNeg(pGetCoeff(a));
800  //return spSpolyRed(m2,m1,NULL);
801  if (pNext(m2)==NULL)
802  {
803    pDelete1(&m1);
804    return m1;
805  }
806  if (pNext(m1)==NULL)
807    return syMultT1(pNext(m2),a);
808  poly res;
809#if defined(HAVE_SY_VECTOR) && ! defined (SY_VEC_DEBUG)
810    res = sySpolyProc(m2, m1,a);
811#else
812  if (pGetOrder(m1)>0)
813  {
814    // TBC: initialize spSpolyLoop where ordering is set!!!
815    res = spSpolyRed(m2,m1,NULL, NULL);
816  }
817  else
818  {
819    res = sySPAdd(m1,m2,a);
820  }
821#endif
822  pDelete1(&a);
823  return res;
824}
825
826static int syLength(poly p)
827{
828  int result=0;
829
830  while (p!=NULL)
831  {
832    result++;
833    pIter(p);
834  }
835  return result;
836}
837
838poly syRedtail (poly p, syStrategy syzstr, int index)
839{
840  poly h, hn;
841  int j,pos;
842  ideal redWith=syzstr->orderedRes[index];
843
844  h = p;
845  hn = pNext(h);
846  while(hn != NULL)
847  {
848    j = syzstr->Firstelem[index-1][pGetComp(hn)]-1;
849    if (j>=0)
850    {
851      pos = j+syzstr->Howmuch[index-1][pGetComp(hn)];
852      while (j < pos)
853      {
854        if (pDivisibleBy2(redWith->m[j], hn))
855        {
856           //int syL=syLength(redWith->m[j]);
857            //PrintS("r");
858//for(int jj=j+1;jj<pos;jj++)
859//{
860  //if (syDivisibleBy1(redWith->m[jj],hn))
861  //{
862    //int syL1=syLength(redWith->m[jj]);
863    //if (syL1<syL)
864    //{
865      //j = jj;
866      //syL = syL1;
867      //Print("take poly %d with %d monomials\n",j,syL);
868      //Print("have poly %d with %d monomials\n",jj,syL1);
869    //}
870  //}
871//}
872          //if (pGetComp(redWith->m[j])!=pGetComp(hn))
873          //{
874            //PrintS("Hilfe!!!!!!!\n");
875            //Print("Fehler in Modul %d bei Elem %d\n",index,j);
876            //PrintS("Poly p: ");pWrite(hn);
877            //PrintS("Poly redWith: ");pWrite(redWith->m[j]);
878          //}
879          hn = sySPolyRed(hn,redWith->m[j]);
880          if (hn == NULL)
881          {
882            pNext(h) = NULL;
883            return p;
884          }
885          j = syzstr->Firstelem[index-1][pGetComp(hn)]-1;
886          pos = j+syzstr->Howmuch[index-1][pGetComp(hn)];
887        }
888        else
889        {
890          j++;
891        }
892      }
893    }
894    h = pNext(h) = hn;
895    hn = pNext(h);
896  }
897  return p;
898}
899
900/*3
901* local procedure for of syInitRes for the module case
902*/
903static int syChMin(intvec * iv)
904{
905  int i,j=-1,r=-1;
906
907  for (i=iv->length()-1;i>=0;i--)
908  {
909    if ((*iv)[i]>=0)
910    {
911      if ((j<0) || ((*iv)[i]<j))
912      {
913        j = (*iv)[i];
914        r = i;
915      }
916    }
917  }
918  return r;
919}
920
921/*3
922* initialize the resolution and puts in the argument as
923* zeroth entre, length must be > 0
924* assumes that the basering is degree-compatible
925*/
926static SRes syInitRes(ideal arg,int * length, intvec * Tl, intvec * cw=NULL)
927{
928  if (idIs0(arg)) return NULL;
929  SRes resPairs = (SRes)Alloc0(*length*sizeof(SSet));
930  resPairs[0] = (SSet)Alloc0(IDELEMS(arg)*sizeof(SObject));
931  intvec * iv=NULL;
932  int i,j;
933
934  if (idRankFreeModule(arg)==0)
935  {
936    iv = idSort(arg);
937    for (i=0;i<IDELEMS(arg);i++)
938    {
939      (resPairs[0])[i].syz = /*pCopy*/(arg->m[(*iv)[i]-1]);
940      arg->m[(*iv)[i]-1] = NULL;
941      (resPairs[0])[i].order = pTotaldegree((resPairs[0])[i].syz);
942    }
943  }
944  else
945  {
946    iv = new intvec(IDELEMS(arg),1,-1);
947    for (i=0;i<IDELEMS(arg);i++)
948    {
949      (*iv)[i] = pTotaldegree(arg->m[i])+(*cw)[pGetComp(arg->m[i])-1];
950    }
951    for (i=0;i<IDELEMS(arg);i++)
952    {
953      j = syChMin(iv);
954      if (j<0) break;
955      (resPairs[0])[i].syz = arg->m[j];
956      arg->m[j] = NULL;
957      (resPairs[0])[i].order = (*iv)[j];
958      (*iv)[j] = -1;
959    }
960  }
961  if (iv!=NULL)  delete iv;
962  (*Tl)[0] = IDELEMS(arg);
963  return resPairs;
964}
965
966/*3
967* determines the place of a polynomial in the right ordered resolution
968* set the vectors of truecomponents
969*/
970static void syOrder(poly p,syStrategy syzstr,int index,
971                    int realcomp)
972{
973  int i=IDELEMS(syzstr->res[index-1])+1,j=0,k,tc,orc,ie=realcomp-1;
974  int *trind1=syzstr->truecomponents[index-1];
975  int *trind=syzstr->truecomponents[index];
976  int *bc=syzstr->backcomponents[index];
977  int *F1=syzstr->Firstelem[index-1];
978  int *H1=syzstr->Howmuch[index-1];
979  poly pp;
980  polyset o_r=syzstr->orderedRes[index]->m;
981  polyset or1=syzstr->orderedRes[index-1]->m;
982
983  if (p==NULL) return;
984  if (realcomp==0) realcomp=1;
985
986  if (index>1)
987    tc = trind1[pGetComp(p)]-1;
988  else
989    tc = pGetComp(p)-1;
990  loop         //while ((j<ie) && (trind1[orc]<=tc+1))
991  {
992    if (j>=ie)
993      break;
994    else
995    {
996      orc = pGetComp(o_r[j]);
997      if (trind1[orc]>tc+1) break;
998      j += H1[orc];
999    }
1000  }
1001  if (j>ie)
1002  {
1003    WerrorS("orderedRes to small");
1004    return;
1005  }
1006  ie++;
1007  if (o_r[j]!=NULL)
1008  {
1009    for (k=ie-1;k>j;k--)
1010    {
1011      o_r[k] = o_r[k-1];
1012      bc[k] = bc[k-1];
1013    }
1014  }
1015  o_r[j] = p;
1016  bc[j] = realcomp-1;
1017  (H1[pGetComp(p)])++;
1018  for (k=0;k<i;k++)
1019  {
1020    if (F1[k]>j)
1021      (F1[k])++;
1022  }
1023  if (F1[pGetComp(p)]==0)
1024    F1[pGetComp(p)]=j+1;
1025//Print("write in sort %d till %d\n",index-1,i-1);
1026//PrintS("poly: ");pWrite(p);
1027//Print("in module %d as %d -th element\n",index,j);
1028  for (k=0;k<IDELEMS((syzstr->res)[index]);k++)
1029  {
1030    if (trind[k]>j)
1031      trind[k] += 1;
1032  }
1033  for (k=IDELEMS((syzstr->res)[index])-1;k>realcomp;k--)
1034    trind[k] = trind[k-1];
1035  trind[realcomp] = j+1;
1036}
1037
1038static intvec* syLinStrat(SSet nextPairs, syStrategy syzstr,
1039                          int howmuch, int index)
1040{
1041  int i=howmuch-1,i1=0,l,ll;
1042  int ** Fin=syzstr->Firstelem;
1043  int ** Hin=syzstr->Howmuch;
1044  int ** bin=syzstr->backcomponents;
1045  ideal o_r=syzstr->orderedRes[index+1];
1046  intvec *result=new intvec(howmuch+1);
1047  BOOLEAN isDivisible;
1048  SObject tso;
1049
1050  while (i>=0)
1051  {
1052    tso = nextPairs[i];
1053    isDivisible = FALSE;
1054    if (syzstr->res[index+1]!=NULL)
1055    {
1056      l = Fin[index][pGetComp(tso.lcm)]-1;
1057      if (l>=0)
1058      {
1059        ll = l+Hin[index][pGetComp(tso.lcm)];
1060        while ((l<ll) && (!isDivisible))
1061        {
1062          if (o_r->m[l]!=NULL)
1063          {
1064            isDivisible = isDivisible ||
1065              pDivisibleBy2(o_r->m[l],tso.lcm);
1066          }
1067          l++;
1068        }
1069      }
1070    }
1071    if (isDivisible)
1072    {
1073      syDeletePair(&nextPairs[i]);
1074      //crit++;
1075    }
1076    else
1077    {
1078      nextPairs[i].p =
1079        sySPoly(tso.p1, tso.p2,tso.lcm);
1080      (*result)[i1] = i+1;
1081      i1++;
1082    }
1083    i--;
1084  }
1085  return result;
1086}
1087
1088static intvec* syLinStrat1(SSet nextPairs, syStrategy syzstr,
1089                          int howmuch, int index)
1090{
1091  int i=howmuch-1,i1=0,i2,i3,l,ll;
1092  int ** Fin=syzstr->Firstelem;
1093  int ** Hin=syzstr->Howmuch;
1094  int ** bin=syzstr->backcomponents;
1095  ideal o_r=syzstr->orderedRes[index+1];
1096  intvec *result=new intvec(howmuch+1);
1097  intvec *spl=new intvec(howmuch,1,-1);
1098  BOOLEAN isDivisible;
1099  SObject tso;
1100
1101  while (i>=0)
1102  {
1103    tso = nextPairs[i];
1104    isDivisible = FALSE;
1105    if (syzstr->res[index+1]!=NULL)
1106    {
1107      l = Fin[index][pGetComp(tso.lcm)]-1;
1108      if (l>=0)
1109      {
1110        ll = l+Hin[index][pGetComp(tso.lcm)];
1111        while ((l<ll) && (!isDivisible))
1112        {
1113          if (o_r->m[l]!=NULL)
1114          {
1115            isDivisible = isDivisible ||
1116              pDivisibleBy2(o_r->m[l],tso.lcm);
1117          }
1118          l++;
1119        }
1120      }
1121    }
1122    if (isDivisible)
1123    {
1124      syDeletePair(&nextPairs[i]);
1125      //crit++;
1126    }
1127    else
1128    {
1129      nextPairs[i].p =
1130        sySPoly(tso.p1, tso.p2,tso.lcm);
1131      (*spl)[i] = pLength(nextPairs[i].p);
1132    }
1133    i--;
1134  }
1135//PrintLn();Print("Laengenvektor: ");spl->show(1,1);PrintLn();
1136  i3 = 0;
1137  loop
1138  {
1139    i2 = -1;
1140    for (i1=0;i1<howmuch;i1++)
1141    {
1142      if (i2==-1)
1143      {
1144        if ((*spl)[i1]!=-1)
1145        {
1146          i2 = i1;
1147        }
1148      }
1149      else
1150      {
1151        if (((*spl)[i1]>=0) && ((*spl)[i1]<(*spl)[i2]))
1152        {
1153          i2 = i1;
1154        }
1155      }
1156    }
1157    if (i2>=0)
1158    {
1159      (*result)[i3] = i2+1;
1160      (*spl)[i2] = -1;
1161      i3++;
1162    }
1163    else
1164    {
1165      break;
1166    }
1167  }
1168  return result;
1169}
1170
1171/*3
1172* reduces all pairs of degree deg in the module index
1173* put the reduced generators to the resolvente which contains
1174* the truncated kStd
1175*/
1176static void syRedNextPairs(SSet nextPairs, syStrategy syzstr,
1177               int howmuch, int index)
1178{
1179  int i,j,k=IDELEMS(syzstr->res[index]);
1180  int ks=IDELEMS(syzstr->res[index+1]),kk,l,ll;
1181  int ** Fin=syzstr->Firstelem;
1182  int ** Hin=syzstr->Howmuch;
1183  int ** bin=syzstr->backcomponents;
1184  number coefgcd,n;
1185  polyset redset=syzstr->orderedRes[index]->m;
1186  poly p=NULL,q;
1187  intvec *spl1=new intvec(howmuch+1);
1188  SObject tso;
1189
1190  if ((nextPairs==NULL) || (howmuch==0)) return;
1191  while ((k>0) && (syzstr->res[index]->m[k-1]==NULL)) k--;
1192  while ((ks>0) && (syzstr->res[index+1]->m[ks-1]==NULL)) ks--;
1193  spl1 = syLinStrat1(nextPairs,syzstr,howmuch,index);
1194//PrintLn();Print("Ordnungsvektor: ");spl1->show(1,1);PrintLn();
1195  i=0;
1196  while ((*spl1)[i]>0)
1197  {
1198    tso = nextPairs[(*spl1)[i]-1];
1199    if ((tso.p1!=NULL) && (tso.p2!=NULL))
1200    {
1201      coefgcd =
1202        nGcd(pGetCoeff(tso.p1),pGetCoeff(tso.p2));
1203      tso.syz = pHead(tso.lcm);
1204      pSetm(tso.syz);
1205      p = tso.syz;
1206      pSetCoeff(p,nDiv(pGetCoeff(tso.p1),coefgcd));
1207      pGetCoeff(p) = nNeg(pGetCoeff(p));
1208      pSetComp(p,tso.ind2+1);
1209      pNext(p) = pHead(tso.lcm);
1210      pIter(p);
1211      pSetm(p);
1212      pSetComp(p,tso.ind1+1);
1213      pSetCoeff(p,nDiv(pGetCoeff(tso.p2),coefgcd));
1214      nDelete(&coefgcd);
1215      if (tso.p != NULL)
1216      {
1217        q = tso.p;
1218        j = Fin[index-1][pGetComp(q)]-1;
1219        int pos = j+Hin[index-1][pGetComp(q)];
1220        loop
1221        {
1222          if (j<0) break;
1223          if (pDivisibleBy2(redset[j],q))
1224          {
1225            //int syL=syLength(redset[j]);
1226            //PrintS("r");
1227//for(int jj=j+1;jj<k;jj++)
1228//{
1229  //if (syDivisibleBy(redset[jj],q))
1230  //{
1231    //int syL1=syLength(redset[jj]);
1232    //if (syL1<syL)
1233    //{
1234      //j = jj;
1235      //syL = syL1;
1236      //Print("take poly %d with %d monomials\n",j,syL);
1237      //Print("have poly %d with %d monomials\n",jj,syL1);
1238    //}
1239  //}
1240//}
1241            pNext(p) = pHead(q);
1242            pIter(p);
1243            pSetComp(p,bin[index][j]+1);
1244            pGetCoeff(p) = nNeg(pGetCoeff(p));
1245            q = sySPolyRed(q,redset[j]);
1246            if (q==NULL) break;
1247            j = Fin[index-1][pGetComp(q)]-1;
1248            pos = j+Hin[index-1][pGetComp(q)];
1249          }
1250          else
1251          {
1252            j++;
1253            if (j==pos) break;
1254          }
1255        }
1256        tso.p = q;
1257      }
1258      if (tso.p != NULL)
1259      {
1260        if (TEST_OPT_PROT) PrintS("g");
1261        if (k==IDELEMS((syzstr->res)[index]))
1262        {
1263          pEnlargeSet(&(syzstr->res[index]->m),IDELEMS(syzstr->res[index]),16);
1264          syzstr->truecomponents[index]=(int*)ReAlloc((ADDRESS)syzstr->truecomponents[index],
1265                                       (IDELEMS(syzstr->res[index])+1)*sizeof(int),
1266                                       (IDELEMS(syzstr->res[index])+17)*sizeof(int));
1267          syzstr->backcomponents[index]=(int*)ReAlloc((ADDRESS)syzstr->backcomponents[index],
1268                                       (IDELEMS(syzstr->res[index])+1)*sizeof(int),
1269                                       (IDELEMS(syzstr->res[index])+17)*sizeof(int));
1270          syzstr->Howmuch[index]=(int*)ReAlloc((ADDRESS)syzstr->Howmuch[index],
1271                                       (IDELEMS(syzstr->res[index])+1)*sizeof(int),
1272                                       (IDELEMS(syzstr->res[index])+17)*sizeof(int));
1273          syzstr->Firstelem[index]=(int*)ReAlloc((ADDRESS)syzstr->Firstelem[index],
1274                                       (IDELEMS(syzstr->res[index])+1)*sizeof(int),
1275                                       (IDELEMS(syzstr->res[index])+17)*sizeof(int));
1276        int mk;
1277        for (mk=IDELEMS(syzstr->res[index])+1;mk<IDELEMS(syzstr->res[index])+17;mk++)
1278        {
1279          syzstr->Howmuch[index][mk] = 0;
1280          syzstr->Firstelem[index][mk] = 0;
1281        }
1282//Print("sort %d has now size %d\n",index,IDELEMS(res[index])+17);
1283          IDELEMS(syzstr->res[index]) += 16;
1284          pEnlargeSet(&(syzstr->orderedRes[index]->m),IDELEMS(syzstr->orderedRes[index]),16);
1285          IDELEMS(syzstr->orderedRes[index]) += 16;
1286          redset=syzstr->orderedRes[index]->m;
1287        }
1288        pNext(p) = pHead(tso.p);
1289        pIter(p);
1290        if (p!=NULL)
1291        {
1292          k++;
1293          pSetComp(p,k);
1294          pGetCoeff(p) = nNeg(pGetCoeff(p));
1295        }
1296        if (tso.p!=NULL)
1297        {
1298          syzstr->res[index]->m[k-1] = tso.p;
1299          pNorm(syzstr->res[index]->m[k-1]);
1300          syOrder(syzstr->res[index]->m[k-1],syzstr,index,k);
1301        }
1302        tso.isNotMinimal = p;
1303        tso.p = NULL;
1304      }
1305      else
1306      {
1307        if (TEST_OPT_PROT) PrintS(".");
1308        if (index % 2==0)
1309          euler++;
1310        else
1311          euler--;
1312      }
1313      if (ks==IDELEMS(syzstr->res[index+1]))
1314      {
1315        pEnlargeSet(&(syzstr->res[index+1]->m),IDELEMS(syzstr->res[index+1]),16);
1316        syzstr->truecomponents[index+1]=(int*)ReAlloc((ADDRESS)syzstr->truecomponents[index+1],
1317                                       (IDELEMS(syzstr->res[index+1])+1)*sizeof(int),
1318                                       (IDELEMS(syzstr->res[index+1])+17)*sizeof(int));
1319        syzstr->backcomponents[index+1]=(int*)ReAlloc((ADDRESS)syzstr->backcomponents[index+1],
1320                                       (IDELEMS(syzstr->res[index+1])+1)*sizeof(int),
1321                                       (IDELEMS(syzstr->res[index+1])+17)*sizeof(int));
1322        syzstr->Howmuch[index+1]=(int*)ReAlloc((ADDRESS)syzstr->Howmuch[index+1],
1323                                       (IDELEMS(syzstr->res[index+1])+1)*sizeof(int),
1324                                       (IDELEMS(syzstr->res[index+1])+17)*sizeof(int));
1325        syzstr->Firstelem[index+1]=(int*)ReAlloc((ADDRESS)syzstr->Firstelem[index+1],
1326                                       (IDELEMS(syzstr->res[index+1])+1)*sizeof(int),
1327                                       (IDELEMS(syzstr->res[index+1])+17)*sizeof(int));
1328        int mk;
1329        for (mk=IDELEMS(syzstr->res[index+1])+1;mk<IDELEMS(syzstr->res[index+1])+17;mk++)
1330        {
1331          syzstr->Howmuch[index+1][mk] = 0;
1332          syzstr->Firstelem[index+1][mk] = 0;
1333        }
1334//Print("sort %d has now size %d\n",index+1,IDELEMS(res[index+1])+17);
1335        IDELEMS(syzstr->res[index+1]) += 16;
1336        pEnlargeSet(&(syzstr->orderedRes[index+1]->m),IDELEMS(syzstr->orderedRes[index+1]),16);
1337        IDELEMS(syzstr->orderedRes[index+1]) += 16;
1338      }
1339      currcomponents = syzstr->truecomponents[index];
1340      syzstr->res[index+1]->m[ks] = syRedtail(tso.syz,syzstr,index+1);
1341      currcomponents = syzstr->truecomponents[index-1];
1342      syzstr->res[index+1]->m[ks] = tso.syz;
1343      pNorm(syzstr->res[index+1]->m[ks]);
1344      tso.syz =NULL;
1345      tso.syzind = ks;
1346      syOrder(syzstr->res[index+1]->m[ks],syzstr,index+1,ks+1);
1347      ks++;
1348      p = NULL;
1349      nextPairs[(*spl1)[i]-1] = tso;
1350    }
1351    i++;
1352  }
1353  delete spl1;
1354}
1355
1356/*3
1357* reduces the generators of the module index in degree deg
1358* (which are actual syzygies of the module index-1)
1359* wrt. the ideal generated by elements of lower degrees
1360*/
1361static void syRedGenerOfCurrDeg(syStrategy syzstr, int deg, int index)
1362{
1363  ideal res=syzstr->res[index];
1364  int i=0,j,k=IDELEMS(res),kk;
1365  SSet sPairs=syzstr->resPairs[index-1];
1366
1367  while ((k>0) && (res->m[k-1]==NULL)) k--;
1368  while ((i<(*syzstr->Tl)[index-1]) && (((sPairs)[i].syz==NULL) ||
1369          ((sPairs)[i].order<deg)))
1370    i++;
1371  if ((i>=(*syzstr->Tl)[index-1]) || ((sPairs)[i].order>deg)) return;
1372  while ((i<(*syzstr->Tl)[index-1]) && (((sPairs)[i].syz==NULL) ||
1373         ((sPairs)[i].order==deg)))
1374  {
1375    if ((sPairs)[i].syz!=NULL)
1376    {
1377      j = k-1;
1378      while ((j>=0) && (res->m[j]!=NULL) &&
1379             ((sPairs)[i].syz!=NULL))
1380      {
1381        if (pDivisibleBy1(res->m[j],(sPairs)[i].syz))
1382        {
1383          //PrintS("r");
1384          (sPairs)[i].syz =
1385            //spSpolyRed(res->m[j],(sPairs)[i].syz,NULL);
1386            sySPolyRed((sPairs)[i].syz,res->m[j]);
1387          j = k-1;
1388        }
1389        else
1390        {
1391          j--;
1392        }
1393      }
1394      if ((sPairs)[i].syz != NULL)
1395      {
1396        if (k==IDELEMS(res))
1397        {
1398          pEnlargeSet(&(res->m),IDELEMS(res),16);
1399          syzstr->truecomponents[index]=(int*)ReAlloc((ADDRESS)syzstr->truecomponents[index],
1400                                       (IDELEMS(res)+1)*sizeof(int),
1401                                       (IDELEMS(res)+17)*sizeof(int));
1402          syzstr->backcomponents[index]=(int*)ReAlloc((ADDRESS)syzstr->backcomponents[index],
1403                                       (IDELEMS(res)+1)*sizeof(int),
1404                                       (IDELEMS(res)+17)*sizeof(int));
1405          syzstr->Howmuch[index]=(int*)ReAlloc((ADDRESS)syzstr->Howmuch[index],
1406                                       (IDELEMS(res)+1)*sizeof(int),
1407                                       (IDELEMS(res)+17)*sizeof(int));
1408          syzstr->Firstelem[index]=(int*)ReAlloc((ADDRESS)syzstr->Firstelem[index],
1409                                       (IDELEMS(res)+1)*sizeof(int),
1410                                       (IDELEMS(res)+17)*sizeof(int));
1411        int mk;
1412        for (mk=IDELEMS(res)+1;mk<IDELEMS(res)+17;mk++)
1413        {
1414          syzstr->Howmuch[index][mk] = 0;
1415          syzstr->Firstelem[index][mk] = 0;
1416        }
1417//Print("sort %d has now size %d\n",index,IDELEMS(res[index])+17);
1418          IDELEMS(res) += 16;
1419          pEnlargeSet(&(syzstr->orderedRes[index]->m),IDELEMS(syzstr->orderedRes[index]),16);
1420          IDELEMS(syzstr->orderedRes[index]) += 16;
1421        }
1422        if (BTEST1(6))
1423        {
1424          if ((sPairs)[i].isNotMinimal==NULL)
1425          {
1426            PrintS("\nminimal generator: ");
1427            pWrite((syzstr->resPairs[index-1])[i].syz);
1428            PrintS("comes from: ");pWrite((syzstr->resPairs[index-1])[i].p1);
1429            PrintS("and: ");pWrite((syzstr->resPairs[index-1])[i].p2);
1430          }
1431        }
1432        //res->m[k] = (sPairs)[i].syz;
1433        res->m[k] = syRedtail((sPairs)[i].syz,syzstr,index);
1434        (sPairs)[i].syzind = k;
1435        pNorm(res->m[k]);
1436  //      (sPairs)[i].syz = NULL;
1437        k++;
1438        syOrder(res->m[k-1],syzstr,index,k);
1439        euler++;
1440      }
1441      else
1442        (sPairs)[i].syzind = -1;
1443    }
1444    i++;
1445  }
1446}
1447
1448/*3
1449* puts a pair into the right place in resPairs
1450*/
1451static void syEnterPair(SSet sPairs, SObject * so, int * sPlength,int index)
1452{
1453  int ll,k,no=(*so).order,sP=*sPlength,i;
1454  poly p=(*so).lcm;
1455
1456  if ((sP==0) || (sPairs[sP-1].order<=no))
1457    ll = sP;
1458  else if (sP==1)
1459    ll = 0;
1460  else
1461  {
1462    int an=0,en=sP-1;
1463    loop
1464    {
1465      if (an>=en-1)
1466      {
1467        if ((sPairs[an].order<=no) && (sPairs[an+1].order>no))
1468        {
1469          ll = an+1;
1470          break;
1471        }
1472        else if ((sPairs[en].order<=no) && (sPairs[en+1].order>no))
1473        {
1474          ll = en+1;
1475          break;
1476        }
1477        else if (sPairs[an].order>no)
1478        {
1479          ll = an;
1480          break;
1481        }
1482        else
1483        {
1484          PrintS("Hier ist was faul!\n");
1485          break;
1486        }
1487      }
1488      i=(an+en) / 2;
1489      if (sPairs[i].order <= no)
1490        an=i;
1491      else
1492        en=i;
1493    }
1494  }
1495  for (k=(*sPlength);k>ll;k--)
1496  {
1497    syCopyPair(&sPairs[k-1],&sPairs[k]);
1498  }
1499  syCopyPair(so,&sPairs[ll]);
1500  (*sPlength)++;
1501}
1502
1503/*3
1504* computes pairs from the new elements (beginning with the element newEl)
1505* in the module index
1506*/
1507static void syCreateNewPairs(syStrategy syzstr, int index, int newEl)
1508{
1509  SSet temp;
1510  SObject tso;
1511  int i,ii,j,k=IDELEMS(syzstr->res[index]),l=(*syzstr->Tl)[index],ll;
1512  int qc,first,pos,jj,j1;
1513  int * bci=syzstr->backcomponents[index];
1514  poly p,q;
1515  polyset rs=syzstr->res[index]->m,nPm;
1516
1517  while ((k>0) && (rs[k-1]==NULL)) k--;
1518  if (newEl>=k) return;
1519  ideal nP=idInit(k,syzstr->res[index]->rank);
1520  nPm=nP->m;
1521  while ((l>0) && ((syzstr->resPairs[index])[l-1].p1==NULL)) l--;
1522//Print("new pairs in module %d\n",index);
1523  for (j=newEl;j<k;j++)
1524  {
1525    q = rs[j];
1526    qc = pGetComp(q);
1527    first = syzstr->Firstelem[index-1][pGetComp(q)]-1;
1528    pos = first+syzstr->Howmuch[index-1][pGetComp(q)];
1529    for (i=first;i<pos;i++)
1530    {
1531      jj = bci[i];
1532      if (jj>=j) break;
1533      p = pOne();
1534      pLcm(rs[jj],q,p);
1535      pSetComp(p,j+1);
1536      ii = first;
1537      loop
1538      {
1539        j1 = bci[ii];
1540        if (nPm[j1]!=NULL)
1541        {
1542          if (pDivisibleBy2(nPm[j1],p))
1543          {
1544            pDelete(&p);
1545            break;
1546          }
1547          else if (pDivisibleBy2(p,nPm[j1]))
1548          {
1549            pDelete(&(nPm[j1]));
1550            //break;
1551          }
1552        }
1553        ii++;
1554        if (ii>=pos) break;
1555      }
1556      if (p!=NULL)
1557      {
1558        nPm[jj] = p;
1559      }
1560    }
1561    //for (i=0;i<j;i++)
1562    for (i=first;i<pos;i++)
1563    {
1564      ii = bci[i];
1565      if (nPm[ii]!=NULL)
1566      {
1567        if (l>=(*syzstr->Tl)[index])
1568        {
1569          temp = (SSet)Alloc0(((*syzstr->Tl)[index]+16)*sizeof(SObject));
1570          for (ll=0;ll<(*syzstr->Tl)[index];ll++)
1571          {
1572            temp[ll].p = (syzstr->resPairs[index])[ll].p;
1573            temp[ll].p1 = (syzstr->resPairs[index])[ll].p1;
1574            temp[ll].p2 = (syzstr->resPairs[index])[ll].p2;
1575            temp[ll].syz = (syzstr->resPairs[index])[ll].syz;
1576            temp[ll].lcm = (syzstr->resPairs[index])[ll].lcm;
1577            temp[ll].ind1 = (syzstr->resPairs[index])[ll].ind1;
1578            temp[ll].ind2 = (syzstr->resPairs[index])[ll].ind2;
1579            temp[ll].syzind = (syzstr->resPairs[index])[ll].syzind;
1580            temp[ll].order = (syzstr->resPairs[index])[ll].order;
1581            temp[ll].isNotMinimal = (syzstr->resPairs[index])[ll].isNotMinimal;
1582          }
1583          Free((ADDRESS)syzstr->resPairs[index],(*syzstr->Tl)[index]*sizeof(SObject));
1584          (*syzstr->Tl)[index] += 16;
1585          syzstr->resPairs[index] = temp;
1586        }
1587        tso.lcm = p = nPm[ii];
1588        nPm[ii] = NULL;
1589        tso.order = pGetOrder(p) = pTotaldegree(p);
1590        if ((syzstr->cw!=NULL) && (index>0) && (pGetComp(q)>0))
1591        {
1592          int ii=index-1,jj=pGetComp(q);
1593          while (ii>0)
1594          {
1595            jj = pGetComp(syzstr->res[ii]->m[jj-1]);
1596            ii--;
1597          }
1598          tso.order += (*syzstr->cw)[jj-1];
1599        }
1600        tso.p1 = rs[ii];
1601        tso.p2 = q;
1602        tso.ind1 = ii;
1603        tso.ind2 = j;
1604        tso.syzind = -1;
1605        tso.isNotMinimal = NULL;
1606        tso.p = NULL;
1607        tso.syz = NULL;
1608        syEnterPair(syzstr->resPairs[index],&tso,&l,index);
1609      }
1610    }
1611  }
1612  idDelete(&nP);
1613}
1614
1615/*2
1616* tail reduction for the LaScala algorithm
1617* takes care of the special ordering
1618*/
1619static void sySyzTail(syStrategy syzstr, int index, int newEl)
1620{
1621  int j,ll,k=IDELEMS((syzstr->res)[index]);
1622  while ((k>0) && ((syzstr->res)[index]->m[k-1]==NULL)) k--;
1623  for (j=newEl;j<k;j++)
1624  {
1625    ll = 0;
1626    while ((ll<(*syzstr->Tl)[index]) && (syzstr->resPairs[index][ll].p1!=NULL) &&
1627           (syzstr->resPairs[index][ll].ind1!=j) && (syzstr->resPairs[index][ll].ind2!=j))
1628      ll++;
1629    if ((ll<(*syzstr->Tl)[index]) && (syzstr->resPairs[index][ll].p1!=NULL))
1630      syzstr->res[index]->m[j] = syRedtail(syzstr->res[index]->m[j],syzstr,index);
1631  }
1632}
1633
1634static SSet syChosePairsPutIn(syStrategy syzstr, int *index,
1635               int *howmuch, int * actdeg, int an, int en)
1636{
1637  int newdeg=*actdeg,newindex=-1,i,t,sldeg;
1638  poly p;
1639  SSet result;
1640  SRes resPairs=syzstr->resPairs;
1641
1642  if (an>syzstr->length) return NULL;
1643  if (en>syzstr->length) en=syzstr->length;
1644  while (*index<en)
1645  {
1646    if (resPairs[*index]!=NULL)
1647    {
1648      sldeg = (*actdeg)+*index;
1649      i = 0;
1650      if (*index!=0)
1651      {
1652        while ((i<(*syzstr->Tl)[*index]))
1653        {
1654          if ((resPairs[*index])[i].lcm!=NULL)
1655          {
1656            if ((resPairs[*index])[i].order == sldeg)
1657            {
1658              result = &(resPairs[*index])[i];
1659              *howmuch =1;
1660              i++;
1661              while ((i<(*syzstr->Tl)[*index]) && ((resPairs[*index])[i].lcm!=NULL)
1662                      && ((resPairs[*index])[i].order == sldeg))
1663              {
1664                i++;
1665                (*howmuch)++;
1666              }
1667              return result;
1668            }
1669          }
1670          i++;
1671        }
1672      }
1673      else
1674      {
1675        while ((i<(*syzstr->Tl)[*index]))
1676        {
1677          if ((resPairs[*index])[i].syz!=NULL)
1678          {
1679            if ((resPairs[*index])[i].order == sldeg)
1680            {
1681              result = &(resPairs[*index])[i];
1682              (*howmuch) =1;
1683              i++;
1684              while ((i<(*syzstr->Tl)[*index]) && ((resPairs[*index])[i].syz!=NULL)
1685                      && ((resPairs[*index])[i].order == *actdeg))
1686              {
1687                i++;
1688                (*howmuch)++;
1689              }
1690              return result;
1691            }
1692          }
1693          i++;
1694        }
1695      }
1696    }
1697    (*index)++;
1698  }
1699  *index = an;
1700  //if (TEST_OPT_PROT) Print("(Euler:%d)",euler);
1701  while (*index<en)
1702  {
1703    if (resPairs[*index]!=NULL)
1704    {
1705      i = 0;
1706      while ((i<(*syzstr->Tl)[*index]))
1707      {
1708        t = *actdeg+*index;
1709        if (((resPairs[*index])[i].lcm!=NULL) ||
1710              ((resPairs[*index])[i].syz!=NULL))
1711        {
1712          if ((resPairs[*index])[i].order > t)
1713            t = (resPairs[*index])[i].order;
1714        }
1715        if ((t>*actdeg+*index) && ((newdeg==*actdeg) || (t<newdeg+*index)))
1716        {
1717          newdeg = t-*index;
1718          newindex = *index;
1719          break;
1720        }
1721        i++;
1722      }
1723    }
1724    (*index)++;
1725  }
1726  if (newdeg>*actdeg)
1727  {
1728    *actdeg = newdeg;
1729    *index = newindex;
1730    return syChosePairsPutIn(syzstr,index,howmuch,actdeg,an,en);
1731  }
1732  else return NULL;
1733}
1734
1735/*3
1736* FOR THE HOMOGENEOUS CASE ONLY!
1737* looks through the pair set and the given module for
1738* remaining pairs or generators to consider
1739* returns a pointer to the first pair and the number of them in the given module
1740* works with slanted degree (i.e. deg=realdeg-index)
1741*/
1742static SSet syChosePairs(syStrategy syzstr, int *index,
1743               int *howmuch, int * actdeg)
1744{
1745  return syChosePairsPutIn(syzsts,index,howmuch,actdeg,0,syzstr->length);
1746}
1747
1748/*3
1749* FOR THE INHOMOGENEOUS CASE ONLY!
1750* looks through the pair set and the given module for
1751* remaining pairs or generators to consider
1752* returns a pointer to the first pair and the number of them in the given module
1753* works with slanted degree (i.e. deg=realdeg-index)
1754* looks first through the 0 and 1 module then through the other
1755*/
1756static SSet syChosePairsIH(syStrategy syzstr, int *index,
1757               int *howmuch, int * actdeg, int mindeg)
1758{
1759  SSet result=NULL;
1760
1761  result = syChosePairsPutIn(syzstr,index,howmuch,actdeg,0,2);
1762  if (result == NULL)
1763  {
1764    *actdeg = mindeg;
1765    result = syChosePairsPutIn(syzstr,index,howmuch,actdeg,2,syzstr->length);
1766  }
1767  return result;
1768}
1769
1770/*3
1771* looks through the pair set and the given module for
1772* remaining pairs or generators to consider
1773* returns a pointer to the first pair and the number of them in the given module
1774* works deg by deg
1775*/
1776/*
1777*static SSet syChosePairs1(SRes resPairs,intvec * Tl, int *index, int *howmuch,
1778*                   int length,int * actdeg)
1779*{
1780*  int newdeg=*actdeg,newindex=-1,i,t;
1781*  SSet result;
1782*
1783*  while (*index>=0)
1784*  {
1785*    if (resPairs[*index]!=NULL)
1786*    {
1787*      i = 0;
1788*      if (*index!=0)
1789*      {
1790*        while ((i<(*Tl)[*index]))
1791*        {
1792*          if ((resPairs[*index])[i].lcm!=NULL)
1793*          {
1794*            if (pGetOrder((resPairs[*index])[i].lcm) == *actdeg)
1795*            {
1796*              result = &(resPairs[*index])[i];
1797*              *howmuch =1;
1798*              i++;
1799*              while ((i<(*Tl)[*index]) && ((resPairs[*index])[i].lcm!=NULL)
1800*                      && (pGetOrder((resPairs[*index])[i].lcm) == *actdeg))
1801*              {
1802*                i++;
1803*                (*howmuch)++;
1804*              }
1805*              return result;
1806*            }
1807*          }
1808*          i++;
1809*        }
1810*      }
1811*      else
1812*      {
1813*        while ((i<(*Tl)[*index]))
1814*        {
1815*          if ((resPairs[*index])[i].syz!=NULL)
1816*          {
1817*            if ((resPairs[*index])[i].order == *actdeg)
1818*            {
1819*              result = &(resPairs[*index])[i];
1820*              (*howmuch) =1;
1821*              i++;
1822*              while ((i<(*Tl)[*index]) && ((resPairs[*index])[i].syz!=NULL)
1823*                      && ((resPairs[*index])[i].order == *actdeg))
1824*              {
1825*                i++;
1826*                (*howmuch)++;
1827*              }
1828*              return result;
1829*            }
1830*          }
1831*          i++;
1832*        }
1833*      }
1834*    }
1835*    (*index)--;
1836*  }
1837*  *index = length-1;
1838*  while (*index>=0)
1839*  {
1840*    if (resPairs[*index]!=NULL)
1841*    {
1842*      i = 0;
1843*      while ((i<(*Tl)[*index]))
1844*      {
1845*        t = *actdeg;
1846*        if ((resPairs[*index])[i].lcm!=NULL)
1847*        {
1848*          if (pGetOrder((resPairs[*index])[i].lcm) > *actdeg)
1849*            t = pGetOrder((resPairs[*index])[i].lcm);
1850*        }
1851*        else if ((resPairs[*index])[i].syz!=NULL)
1852*        {
1853*          if ((resPairs[*index])[i].order > *actdeg)
1854*            t = (resPairs[*index])[i].order;
1855*        }
1856*        if ((t>*actdeg) && ((newdeg==*actdeg) || (t<newdeg)))
1857*        {
1858*          newdeg = t;
1859*          newindex = *index;
1860*          break;
1861*        }
1862*        i++;
1863*      }
1864*    }
1865*    (*index)--;
1866*  }
1867*  if (newdeg>*actdeg)
1868*  {
1869*    *actdeg = newdeg;
1870*    *index = newindex;
1871*    return syChosePairs1(resPairs,Tl,index,howmuch,length,actdeg);
1872*  }
1873*  else return NULL;
1874*}
1875*/
1876/*3
1877* statistics of the resolution
1878*/
1879static void syStatistics(resolvente res,int length)
1880{
1881  int i,j=1,k,deg=0;
1882
1883  PrintLn();
1884  while ((j<length) && (res[j]!=NULL))
1885  {
1886    Print("In module %d: \n",j);
1887    k = 0;
1888    while ((k<IDELEMS(res[j])) && (res[j]->m[k]!=NULL))
1889    {
1890      i = 1;
1891      deg = pGetOrder(res[j]->m[k]);
1892      k++;
1893      while ((k<IDELEMS(res[j])) && (res[j]->m[k]!=NULL) &&
1894              (pGetOrder(res[j]->m[k])==deg))
1895      {
1896        i++;
1897        k++;
1898      }
1899      Print("%d elements of degree %d\n",i,deg);
1900    }
1901    j++;
1902  }
1903}
1904
1905/*3
1906* initialize a module
1907*/
1908static int syInitSyzMod(syStrategy syzstr, int index, int init=17)
1909{
1910  int result;
1911
1912  if (syzstr->res[index]==NULL)
1913  {
1914    syzstr->res[index] = idInit(init-1,1);
1915    syzstr->truecomponents[index] = (int*)Alloc0(init*sizeof(int));
1916    if (index==0)
1917    {
1918      for (int i=0;i<init;i++)
1919        syzstr->truecomponents[0][i] = i;
1920    }
1921    syzstr->backcomponents[index] = (int*)Alloc0(init*sizeof(int));
1922    syzstr->Howmuch[index] = (int*)Alloc0(init*sizeof(int));
1923    syzstr->Firstelem[index] = (int*)Alloc0(init*sizeof(int));
1924//Print("sort %d has now size %d\n",index,init);
1925    syzstr->orderedRes[index] = idInit(init-1,1);
1926    result = 0;
1927  }
1928  else
1929  {
1930    result = IDELEMS(syzstr->res[index]);
1931    while ((result>0) && (syzstr->res[index]->m[result-1]==NULL)) result--;
1932  }
1933  return result;
1934}
1935
1936/*3
1937* deletes a resolution
1938*/
1939void syKillComputation(syStrategy syzstr)
1940{
1941//Print("ref: %d\n",syzstr->references);
1942  if (syzstr->references>0)
1943  {
1944    (syzstr->references)--;
1945  }
1946  else
1947  {
1948    int i,j;
1949
1950    if (syzstr->resPairs!=NULL)
1951    {
1952      for (i=0;i<syzstr->length;i++)
1953      {
1954        for (j=0;j<(*syzstr->Tl)[i];j++)
1955        {
1956          if ((syzstr->resPairs[i])[j].lcm!=NULL)
1957            pDelete(&((syzstr->resPairs[i])[j].lcm));
1958        }
1959        if (syzstr->orderedRes[i]!=NULL)
1960        {
1961          for (j=0;j<IDELEMS(syzstr->orderedRes[i]);j++)
1962          {
1963            syzstr->orderedRes[i]->m[j] = NULL;
1964          }
1965        }
1966        idDelete(&(syzstr->orderedRes[i]));
1967        if (syzstr->truecomponents[i]!=NULL)
1968        {
1969          Free((ADDRESS)syzstr->truecomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1970          syzstr->truecomponents[i]=NULL;
1971        }
1972        if (syzstr->backcomponents[i]!=NULL)
1973        {
1974          Free((ADDRESS)syzstr->backcomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1975          syzstr->backcomponents[i]=NULL;
1976        }
1977        if (syzstr->Howmuch[i]!=NULL)
1978        {
1979          Free((ADDRESS)syzstr->Howmuch[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1980          syzstr->Howmuch[i]=NULL;
1981        }
1982        if (syzstr->Firstelem[i]!=NULL)
1983        {
1984          Free((ADDRESS)syzstr->Firstelem[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1985          syzstr->Firstelem[i]=NULL;
1986        }
1987        if (syzstr->res[i]!=NULL)
1988        {
1989          for (j=0;j<IDELEMS(syzstr->res[i]);j++)
1990          {
1991            if (syzstr->res[i]->m[j]!=NULL)
1992              pDelete(&(syzstr->res[i]->m[j]));
1993          }
1994        }
1995        if (syzstr->weights!=0)
1996        {
1997          if (syzstr->weights[i]!=NULL)
1998          {
1999            delete syzstr->weights[i];
2000          }
2001          Free((ADDRESS)syzstr->weights,syzstr->length*sizeof(intvec*));
2002        }
2003        idDelete(&(syzstr->res[i]));
2004        Free((ADDRESS)syzstr->resPairs[i],(*syzstr->Tl)[i]*sizeof(SObject));
2005      }
2006      Free((ADDRESS)syzstr->resPairs,syzstr->length*sizeof(SObject*));
2007      Free((ADDRESS)syzstr->res,(syzstr->length+1)*sizeof(ideal));
2008      Free((ADDRESS)syzstr->orderedRes,(syzstr->length+1)*sizeof(ideal));
2009      Free((ADDRESS)syzstr->truecomponents,(syzstr->length+1)*sizeof(int*));
2010      Free((ADDRESS)syzstr->backcomponents,(syzstr->length+1)*sizeof(int*));
2011      Free((ADDRESS)syzstr->Howmuch,(syzstr->length+1)*sizeof(int*));
2012      Free((ADDRESS)syzstr->Firstelem,(syzstr->length+1)*sizeof(int*));
2013      Free((ADDRESS)syzstr->binom,pVariables*(syzstr->highdeg_1)*sizeof(int));
2014    }
2015    if (syzstr->minres!=NULL)
2016    {
2017      for (i=0;i<syzstr->length;i++)
2018      {
2019        if (syzstr->minres[i]!=NULL)
2020        {
2021          for (j=0;j<IDELEMS(syzstr->minres[i]);j++)
2022          {
2023            if (syzstr->minres[i]->m[j]!=NULL)
2024              pDelete(&(syzstr->minres[i]->m[j]));
2025          }
2026        }
2027        idDelete(&(syzstr->minres[i]));
2028      }
2029      Free((ADDRESS)syzstr->minres,(syzstr->length+1)*sizeof(ideal));
2030    }
2031    if (syzstr->fullres!=NULL)
2032    {
2033      for (i=0;i<syzstr->length;i++)
2034      {
2035        if (syzstr->fullres[i]!=NULL)
2036        {
2037          for (j=0;j<IDELEMS(syzstr->fullres[i]);j++)
2038          {
2039            if (syzstr->fullres[i]->m[j]!=NULL)
2040              pDelete(&(syzstr->fullres[i]->m[j]));
2041          }
2042        }
2043        idDelete(&(syzstr->fullres[i]));
2044      }
2045      Free((ADDRESS)syzstr->fullres,(syzstr->length+1)*sizeof(ideal));
2046    }
2047    if (syzstr->cw!=NULL)
2048      delete syzstr->cw;
2049    if (syzstr->resolution!=NULL)
2050      delete syzstr->resolution;
2051    Free((ADDRESS)syzstr,sizeof(ssyStrategy));
2052  }
2053}
2054
2055/*3
2056* read out the Betti numbers from resolution
2057* (if not LaScala calls the traditional Betti procedure)
2058*/
2059intvec * syBettiOfComputation(syStrategy syzstr)
2060{
2061  int dummy;
2062  if (syzstr->resPairs!=NULL)
2063  {
2064    int i,j=-1,jj=-1,l;
2065    SRes rP=syzstr->resPairs;
2066
2067    l = syzstr->length;
2068    while ((l>0) && (rP[l-1]==NULL)) l--;
2069    if (l==0) return NULL;
2070    l--;
2071    while (l>=0)
2072    {
2073      i = 0;
2074      while ((i<(*syzstr->Tl)[l]) &&
2075        ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)))
2076      {
2077        if (rP[l][i].isNotMinimal==NULL)
2078        {
2079          if (j<rP[l][i].order-l)
2080            j = rP[l][i].order-l;
2081          if (jj<l)
2082            jj = l;
2083        }
2084        i++;
2085      }
2086      l--;
2087    }
2088    jj=jj+2;
2089    intvec *result=new intvec(j,jj,0);
2090    IMATELEM(*result,1,1) = max(1,idRankFreeModule(syzstr->res[1]));
2091    for (i=0;i<jj;i++)
2092    {
2093      j = 0;
2094      while ((j<(*syzstr->Tl)[i]) &&
2095        ((rP[i][j].lcm!=NULL) || (rP[i][j].syz!=NULL)))
2096      {
2097        if (rP[i][j].isNotMinimal==NULL)
2098          IMATELEM(*result,rP[i][j].order-i,i+2)++;
2099        j++;
2100      }
2101    }
2102    return result;
2103  }
2104  else if (syzstr->fullres!=NULL)
2105    return syBetti(syzstr->fullres,syzstr->length,&dummy);
2106  else
2107    return syBetti(syzstr->minres,syzstr->length,&dummy);
2108}
2109
2110/*3
2111* computes the allocated length of the resolution
2112*/
2113int syLength(syStrategy syzstr)
2114{
2115  return syzstr->length;
2116}
2117
2118/*3
2119* computes the real length of the resolution
2120*/
2121int sySize(syStrategy syzstr)
2122{
2123  resolvente r=syzstr->res;
2124  if (r==NULL)
2125    r = syzstr->fullres;
2126  if (r==NULL)
2127    r = syzstr->minres;
2128  if (r==NULL)
2129  {
2130    WerrorS("No resolution found");
2131    return 0;
2132  }
2133  int i=syzstr->length;
2134  while ((i>0) && (r[i-1]==NULL)) i--;
2135  return i;
2136}
2137
2138/*3
2139* computes the cohomological dimension of res[1]
2140*/
2141int syDim(syStrategy syzstr)
2142{
2143  int i,j=-1,l;
2144  if (syzstr->resPairs!=NULL)
2145  {
2146    SRes rP=syzstr->resPairs;
2147
2148    l = syzstr->length;
2149    while ((l>0) && (rP[l-1]==NULL)) l--;
2150    if (l==0) return -1;
2151    l--;
2152    while (l>=0)
2153    {
2154      i = 0;
2155      while ((i<(*syzstr->Tl)[l]) &&
2156        ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)) &&
2157        (rP[l][i].isNotMinimal!=NULL))
2158      {
2159        i++;
2160      }
2161      if ((i<(*syzstr->Tl)[l]) &&
2162        ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)) &&
2163        (rP[l][i].isNotMinimal==NULL))
2164        return l;
2165      l--;
2166    }
2167    return l;
2168  }
2169  else
2170    return sySize(syzstr);
2171}
2172
2173/*3
2174* copies the resolution (by increment the reference counter)
2175*/
2176syStrategy syCopy(syStrategy syzstr)
2177{
2178  syStrategy result=syzstr;
2179  (result->references)++;
2180  return result;
2181}
2182
2183/*2
2184* local print procedure used in syPrint
2185*/
2186static void syPrintEmptySpaces(int i)
2187{
2188  if (i!=0)
2189  {
2190    PrintS(" ");
2191    syPrintEmptySpaces(i/10);
2192  }
2193}
2194
2195/*2
2196* local print procedure used in syPrint
2197*/
2198static void syPrintEmptySpaces1(int i)
2199{
2200  if (i!=0)
2201  {
2202    PrintS(" ");
2203    syPrintEmptySpaces1(i-1);
2204  }
2205}
2206
2207/*2
2208* local print procedure used in syPrint
2209*/
2210static int syLengthInt(int i)
2211{
2212  int j=0;
2213
2214  if (i==0) return 1;
2215  while (i!=0)
2216  {
2217    j++;
2218    i = i/10;
2219  }
2220  return j;
2221}
2222
2223static void syLoadResTrad(syStrategy syzstr)
2224{
2225  resolvente rr;
2226  int l=0,j;
2227
2228  if (syzstr->minres!=NULL)
2229    rr = syzstr->minres;
2230  else
2231    rr = syzstr->fullres;
2232  if (syzstr->resolution!=NULL) delete syzstr->resolution;
2233  syzstr->resolution = new intvec(syzstr->length+2);
2234  (*syzstr->resolution)[0] = max(1,idRankFreeModule(rr[0]));
2235  while ((l<syzstr->length) && (rr[l]!=NULL))
2236  {
2237    j = IDELEMS(rr[l]);
2238    while ((j>0) && (rr[l]->m[j-1]==NULL)) j--;
2239    ((*syzstr->resolution)[l+1]) = j;
2240    l++;
2241  }
2242}
2243
2244/*3
2245* prints the resolution as sequence of free modules
2246*/
2247void syPrint(syStrategy syzstr)
2248{
2249  if ((syzstr->resPairs==NULL) && (syzstr->fullres==NULL)
2250     && (syzstr->minres==NULL))
2251  {
2252    PrintS("No resolution defined\n");
2253    return;
2254  }
2255  int l=0;
2256  if (syzstr->resolution==NULL)
2257  {
2258    int j;
2259    if (syzstr->resPairs!=NULL)
2260    {
2261      syzstr->resolution = new intvec(syzstr->length+1);
2262      SRes rP=syzstr->resPairs;
2263      (*syzstr->resolution)[0] = max(1,idRankFreeModule(syzstr->res[1]));
2264      while ((l<syzstr->length) && (rP[l]!=NULL))
2265      {
2266        j=0;
2267        while ((j<(*syzstr->Tl)[l]) &&
2268          ((rP[l][j].lcm!=NULL) || (rP[l][j].syz!=NULL)))
2269        {
2270          if (rP[l][j].isNotMinimal==NULL)
2271            ((*syzstr->resolution)[l+1])++;
2272          j++;
2273        }
2274        l++;
2275      }
2276    }
2277    else
2278    {
2279      syLoadResTrad(syzstr);
2280    }
2281  }
2282  char *sn=currRingHdl->id;
2283  int sl=strlen(sn);
2284  syPrintEmptySpaces1(sl);
2285  l = 0;
2286  loop
2287  {
2288    Print("%d",(*syzstr->resolution)[l]);
2289    if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0))
2290      break;
2291    syPrintEmptySpaces1(sl+5);
2292    l++;
2293  }
2294  PrintLn();
2295  l = 0;
2296  loop
2297  {
2298    Print(sn);
2299    if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0))
2300      break;
2301    syPrintEmptySpaces((*syzstr->resolution)[l]);
2302    PrintS(" <-- ");
2303    l++;
2304  }
2305  PrintLn();
2306  PrintLn();
2307  l = 0;
2308  loop
2309  {
2310    Print("%d",l);
2311    if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0))
2312      break;
2313    syPrintEmptySpaces1(sl+5+syLengthInt((*syzstr->resolution)[l])-
2314                         syLengthInt(l));
2315    l++;
2316  }
2317  PrintLn();
2318  if (syzstr->minres==NULL)
2319  {
2320    PrintS("resolution not minimized yet\n");
2321  }
2322}
2323
2324/*2
2325* divides out the weight monomials (given by the Schreyer-ordering)
2326* fronm the LaScala-resolution
2327*/
2328static resolvente syReorder(resolvente res,int length,
2329        syStrategy syzstr,BOOLEAN toCopy=TRUE,resolvente totake=NULL)
2330{
2331  int i,j,l;
2332  poly p,q,tq;
2333  polyset ri1;
2334  resolvente fullres;
2335  fullres = (resolvente)Alloc0((length+1)*sizeof(ideal));
2336  if (totake==NULL)
2337    totake = res;
2338  for (i=length-1;i>0;i--)
2339  {
2340    if (res[i]!=NULL)
2341    {
2342      if (i>1)
2343      {
2344        j = IDELEMS(res[i-1]);
2345        while ((j>0) && (res[i-1]->m[j-1]==NULL)) j--;
2346        fullres[i-1] = idInit(IDELEMS(res[i]),j);
2347        ri1 = totake[i-1]->m;
2348        for (j=IDELEMS(res[i])-1;j>=0;j--)
2349        {
2350          p = res[i]->m[j];
2351          q = NULL;
2352          while (p!=NULL)
2353          {
2354            if (toCopy)
2355            {
2356              tq = pHead(p);
2357              pIter(p);
2358            }
2359            else
2360            {
2361              tq = p;
2362              pIter(p);
2363              pNext(tq) = NULL;
2364            }
2365            for (l=pVariables;l>0;l--)
2366              pSubExp(tq,l, pGetExp(ri1[pGetComp(tq)-1],l));
2367            pSetm(tq);
2368            q = pAdd(q,tq);
2369          }
2370          fullres[i-1]->m[j] = q;
2371        }
2372      }
2373      else
2374      {
2375        if (toCopy)
2376          fullres[i-1] = idCopy(res[i]);
2377        else
2378          fullres[i-1] = res[i];
2379        for (j=IDELEMS(res[i])-1;j>=0;j--)
2380          fullres[i-1]->m[j] = pOrdPolyInsertSetm(fullres[i-1]->m[j]);
2381      }
2382    }
2383  }
2384  if (!toCopy)
2385    Free((ADDRESS)res,(length+1)*sizeof(ideal));
2386  //syzstr->length = length;
2387  return fullres;
2388}
2389
2390/*3
2391* converts a resolution into a list of modules
2392*/
2393lists syConvRes(syStrategy syzstr)
2394{
2395  if ((syzstr->fullres==NULL) && (syzstr->minres==NULL))
2396  {
2397    syzstr->fullres = syReorder(syzstr->res,syzstr->length,syzstr);
2398  }
2399  resolvente tr;
2400  int typ0=IDEAL_CMD;
2401  if (syzstr->minres!=NULL)
2402    tr = syzstr->minres;
2403  else
2404    tr = syzstr->fullres;
2405  resolvente trueres=NULL;
2406  intvec ** w=NULL;
2407  if (syzstr->length>0)
2408  {
2409    trueres=(resolvente)Alloc0((syzstr->length)*sizeof(ideal));
2410    for (int i=(syzstr->length)-1;i>=0;i--)
2411    {
2412      if (tr[i]!=NULL)
2413      {
2414        trueres[i] = idCopy(tr[i]);
2415      }
2416    }
2417    if (idRankFreeModule(trueres[0]) > 0)
2418      typ0 = MODUL_CMD;
2419    if (syzstr->weights!=NULL)
2420    {
2421      w = (intvec**)Alloc0((syzstr->length)*sizeof(intvec*));
2422      for (int i=(syzstr->length)-1;i>=0;i--)
2423      {
2424        if (syzstr->weights[i]!=NULL) w[i] = ivCopy(syzstr->weights[i]);
2425      }
2426    }
2427  }
2428  return liMakeResolv(trueres,syzstr->length,syzstr->list_length,typ0,w);
2429}
2430
2431/*3
2432* converts a list of modules into a resolution
2433*/
2434syStrategy syConvList(lists li)
2435{
2436  int typ0;
2437  syStrategy result=(syStrategy)Alloc0(sizeof(ssyStrategy));
2438
2439  resolvente fr = liFindRes(li,&(result->length),&typ0,&(result->weights));
2440  result->fullres = (resolvente)Alloc0((result->length+1)*sizeof(ideal));
2441  for (int i=result->length-1;i>=0;i--)
2442  {
2443    if (fr[i]!=NULL)
2444      result->fullres[i] = idCopy(fr[i]);
2445  }
2446  result->list_length=result->length;
2447  Free((ADDRESS)fr,(result->length)*sizeof(ideal));
2448  return result;
2449}
2450
2451/*3
2452* converts a list of modules into a minimal resolution
2453*/
2454syStrategy syForceMin(lists li)
2455{
2456  int typ0;
2457  syStrategy result=(syStrategy)Alloc0(sizeof(ssyStrategy));
2458
2459  resolvente fr = liFindRes(li,&(result->length),&typ0);
2460  result->minres = (resolvente)Alloc0((result->length+1)*sizeof(ideal));
2461  for (int i=result->length-1;i>=0;i--)
2462  {
2463    if (fr[i]!=NULL)
2464      result->minres[i] = idCopy(fr[i]);
2465  }
2466  Free((ADDRESS)fr,(result->length)*sizeof(ideal));
2467  return result;
2468}
2469
2470/*2
2471* deleting all monomials the component of which correspond
2472* to non-minimal generators
2473*/
2474static poly syStripOut(poly p,intvec * toStrip)
2475{
2476  if (toStrip==NULL) return p;
2477  poly pp=p;
2478
2479  while ((pp!=NULL) && ((*toStrip)[pGetComp(pp)]!=0))
2480    pDelete1(&pp);
2481  p = pp;
2482  if (pp!=NULL)
2483  {
2484    while (pNext(pp)!=NULL)
2485    {
2486      if ((*toStrip)[pGetComp(pNext(pp))]!=0)
2487        pDelete1(&pNext(pp));
2488      else
2489        pIter(pp);
2490    }
2491  }
2492  return p;
2493}
2494
2495static poly syMinimizeP(int toMin,syStrategy syzstr,intvec * ordn,int index,
2496                        intvec * toStrip)
2497{
2498  int ii=0,i,j,tc;
2499  poly p,pp,q=NULL,tq,pisN;
2500  SSet sPairs=syzstr->resPairs[index];
2501  poly tempStripped=NULL;
2502
2503  pp=pCopy(syzstr->res[index+1]->m[toMin]);
2504  pp = syStripOut(pp,toStrip);
2505  while ((ii<ordn->length()) && ((*ordn)[ii]!=-1) && (sPairs[(*ordn)[ii]].syzind!=toMin))
2506  {
2507    ii++;
2508  }
2509  while (ii>=0)
2510  {
2511    i = (*ordn)[ii];
2512    if (sPairs[i].isNotMinimal!=NULL)
2513    {
2514      tempStripped = syStripOut(pCopy(syzstr->res[index+1]->m[sPairs[i].syzind]),toStrip);
2515      pisN = sPairs[i].isNotMinimal;
2516      tc = pGetComp(pisN);
2517      p = pp;
2518      while (p!=NULL)
2519      {
2520        if (pGetComp(p)==tc)
2521        {
2522          tq = pInit();
2523          for(j=pVariables; j>0; j--)
2524            pSetExp(tq,j, pGetExp(p,j)-pGetExp(pisN,j));
2525          pSetComp(tq, 0);
2526          pSetCoeff0(tq,nDiv(pGetCoeff(p),pGetCoeff(pisN)));
2527          pGetCoeff(tq) = nNeg(pGetCoeff(tq));
2528          q = syAdd(q,syMultT1(tempStripped,tq));
2529        }
2530        pIter(p);
2531      }
2532      if (q!=NULL)
2533      {
2534        pp = syAdd(pp,q);
2535        q = NULL;
2536      }
2537      pDelete(&tempStripped);
2538    }
2539    ii--;
2540  }
2541  return pp;
2542}
2543
2544void syKillEmptyEntres(resolvente res,int length)
2545{
2546  int i,j,jj,k,rj;
2547  intvec * changes;
2548  poly p;
2549  ideal ri;
2550
2551  for (i=0;i<length;i++)
2552  {
2553    ri = res[i];
2554    if (ri!=NULL)
2555    {
2556      rj = IDELEMS(ri);
2557      changes = new intvec(rj+1,1,-1);
2558      while ((rj>0) && (ri->m[rj-1]==NULL)) rj--;
2559      j = k = 0;
2560      while (j+k<rj)
2561      {
2562        if (ri->m[j+k]!=NULL)
2563        {
2564          ri->m[j] = ri->m[j+k];
2565          (*changes)[j+k+1] = j+1;
2566          j++;
2567        }
2568        else
2569        {
2570          k++;
2571        }
2572      }
2573      for (jj=j;jj<rj;jj++)
2574        ri->m[jj] = NULL;
2575      if (res[i+1]!=NULL)
2576      {
2577        ri = res[i+1];
2578        for (j=IDELEMS(ri)-1;j>=0;j--)
2579        {
2580          p = ri->m[j];
2581          while (p!=NULL)
2582          {
2583            pSetComp(p,(*changes)[pGetComp(p)]);
2584            pIter(p);
2585          }
2586        }
2587      }
2588    }
2589  }
2590}
2591
2592static intvec * syToStrip(syStrategy syzstr, int index)
2593{
2594  intvec * result=NULL;
2595
2596  if ((syzstr->resPairs[index-1]!=NULL) && (!idIs0(syzstr->res[index])))
2597  {
2598    result=new intvec(IDELEMS(syzstr->res[index])+1);
2599    for (int i=(*syzstr->Tl)[index-1]-1;i>=0;i--)
2600    {
2601      if (syzstr->resPairs[index-1][i].isNotMinimal!=NULL)
2602      {
2603        (*result)[syzstr->resPairs[index-1][i].syzind+1] = 1;
2604      }
2605    }
2606  }
2607  return result;
2608}
2609
2610static intvec * syOrdPairs(SSet sPairs, int length)
2611{
2612  intvec * result=new intvec(length,1,-1);
2613  int i,j=0,k=-1,l,ii;
2614
2615  loop
2616  {
2617    l = -1;
2618    for(i=0;i<length;i++)
2619    {
2620      if (sPairs[i].syzind>k)
2621      {
2622        if (l==-1)
2623        {
2624          l = sPairs[i].syzind;
2625          ii = i;
2626        }
2627        else
2628        {
2629          if (sPairs[i].syzind<l)
2630          {
2631            l = sPairs[i].syzind;
2632            ii = i;
2633          }
2634        }
2635      }
2636    }
2637    if (l==-1) break;
2638    (*result)[j] = ii;
2639    j++;
2640    k = l;
2641  }
2642  return result;
2643}
2644
2645static resolvente syReadOutMinimalRes(syStrategy syzstr,
2646           BOOLEAN computeStd=FALSE)
2647{
2648  intvec * Strip, * ordn;
2649  resolvente tres=(resolvente)Alloc0((syzstr->length+1)*sizeof(ideal));
2650  sip_sring tmpR;
2651  ring origR = currRing;
2652
2653  if (computeStd)
2654  {
2655    tres[0] = syzstr->res[1];
2656    syzstr->res[1] = idInit(IDELEMS(tres[0]),tres[0]->rank);
2657    return tres;
2658  }
2659  int i,j,l,index,ii,i1;
2660  poly p;
2661  ideal rs;
2662  SSet sPairs;
2663  int * ord,*b0,*b1;
2664  pSetmProc oldSetm=pSetm;
2665  pCompProc oldComp0=pComp0;
2666
2667  if ((currRing->order[0]==ringorder_dp)
2668  &&  (currRing->order[1]==ringorder_C)
2669  &&  (currRing->order[2]==0))
2670  {
2671    ord=NULL;
2672  }
2673/*--- changes to a dpC-ring with special comp0------*/
2674  else
2675  {
2676    ord = (int*)Alloc0(3*sizeof(int));
2677    b0 = (int*)Alloc0(3*sizeof(int));
2678    b1 = (int*)Alloc0(3*sizeof(int));
2679    ord[0] = ringorder_dp;
2680    ord[1] = ringorder_C;
2681    b0[1] = 1;
2682    b1[0] = pVariables;
2683    tmpR  = *origR;
2684    tmpR.order = ord;
2685    tmpR.block0 = b0;
2686    tmpR.block1 = b1;
2687    rComplete(&tmpR);
2688    //pChangeRing(pVariables,1,ord,b0,b1,currRing->wvhdl);
2689    rChangeCurrRing(&tmpR, TRUE);
2690  }
2691#if ! defined(HAVE_SY_VECTOR) || defined(SY_VEC_DEBUG)
2692  pSetm =syzSetm;
2693#endif
2694  pComp0 = syzcomp2dpc;
2695  binomials = syzstr->binom;
2696  highdeg_1 = syzstr->highdeg_1;
2697  for (index=syzstr->length-1;index>0;index--)
2698  {
2699    if (syzstr->resPairs[index]!=NULL)
2700    {
2701      currcomponents = syzstr->truecomponents[index];
2702      sPairs = syzstr->resPairs[index];
2703      Strip = syToStrip(syzstr,index);
2704      tres[index+1] = idInit(IDELEMS(syzstr->res[index+1]),syzstr->res[index+1]->rank);
2705      i1 = (*syzstr->Tl)[index];
2706      ordn = syOrdPairs(sPairs,i1);
2707      for (i=0;i<i1;i++)
2708      {
2709        if ((sPairs[i].isNotMinimal==NULL) && (sPairs[i].lcm!=NULL))
2710        {
2711          l = sPairs[i].syzind;
2712          tres[index+1]->m[l] =
2713            syMinimizeP(l,syzstr,ordn,index,Strip);
2714        }
2715      }
2716      delete Strip;
2717      Strip = NULL;
2718    }
2719  }
2720  currcomponents = syzstr->truecomponents[0];
2721  tres[1] = idInit(IDELEMS(syzstr->res[1]),syzstr->res[1]->rank);
2722  sPairs = syzstr->resPairs[0];
2723  for (i=(*syzstr->Tl)[0]-1;i>=0;i--)
2724  {
2725    if (sPairs[i].syzind>=0)
2726    {
2727      tres[1]->m[sPairs[i].syzind] = pCopy(syzstr->res[1]->m[sPairs[i].syzind]);
2728    }
2729  }
2730/*--- changes to the original ring------------------*/
2731  if (ord!=NULL)
2732  {
2733    //pChangeRing(pVariables,currRing->OrdSgn,currRing->order,
2734    //currRing->block0,currRing->block1,currRing->wvhdl);
2735    rChangeCurrRing(origR,TRUE);
2736  }
2737  else
2738  {
2739    pSetm=oldSetm;
2740    pComp0=oldComp0;
2741  }
2742  tres = syReorder(tres,syzstr->length,syzstr,FALSE,syzstr->res);
2743  syKillEmptyEntres(tres,syzstr->length);
2744  idSkipZeroes(tres[0]);
2745  return tres;
2746}
2747
2748syStrategy syMinimize(syStrategy syzstr)
2749{
2750  if (syzstr->minres==NULL)
2751  {
2752    if (syzstr->resPairs!=NULL)
2753    {
2754      syzstr->minres = syReadOutMinimalRes(syzstr);
2755    }
2756    else if (syzstr->fullres!=NULL)
2757    {
2758      syMinimizeResolvente(syzstr->fullres,syzstr->length,1);
2759      syzstr->minres = syzstr->fullres;
2760      syzstr->fullres = NULL;
2761      syLoadResTrad(syzstr);
2762    }
2763  }
2764  (syzstr->references)++;
2765  return syzstr;
2766}
2767
2768static void sySetHighdeg()
2769{
2770#ifdef __MWERKS__
2771  const double m=(double)INT_MAX;
2772  double t=1.0;
2773  unsigned int h_d=1;
2774  unsigned int h_n=1+pVariables;
2775  loop
2776  {
2777    t *=(double)h_n;
2778    t /=(double)h_d;
2779    if (t>=m) break;
2780    h_d++;
2781    h_n++;
2782  }
2783  h_d--;
2784  highdeg = h_d;
2785#else
2786  long long t=1, h_d=1;
2787  long long h_n=1+pVariables;
2788  while ((t=((t*h_n)/h_d))<INT_MAX)
2789  {
2790    h_d++;
2791    h_n++;
2792  }
2793  h_d--;
2794  highdeg = h_d;
2795#endif
2796  //Print("max deg=%d\n",highdeg);
2797}
2798
2799/*2
2800* implementation of LaScala's algorithm
2801* assumes that the given module is homogeneous
2802* works with slanted degree, uses syChosePairs
2803*/
2804syStrategy syLaScala3(ideal arg,int * length)
2805{
2806  BOOLEAN noPair=FALSE;
2807  int i,j,* ord,*b0,*b1,actdeg=32000,index=0,reg=-1;
2808  int startdeg,howmuch;
2809  poly p;
2810  ideal temp;
2811  SSet nextPairs;
2812  syStrategy syzstr=(syStrategy)Alloc0(sizeof(ssyStrategy));
2813  sip_sring tmpR;
2814  ring origR = currRing;
2815
2816  if ((idIs0(arg)) ||
2817      ((idRankFreeModule(arg)>0) && (!idHomModule(arg,NULL,&(syzstr->cw)))))
2818  {
2819    syzstr->minres = (resolvente)Alloc0(sizeof(ideal));
2820    syzstr->length = 1;
2821    syzstr->minres[0] = idInit(1,arg->rank);
2822    return syzstr;
2823  }
2824  pSetmProc oldSetm=pSetm;
2825  pCompProc oldComp0=pComp0;
2826
2827  //crit = 0;
2828  //zeroRed = 0;
2829  //simple = 0;
2830  //dsim = 0;
2831  euler = -1;
2832  redpol = pInit();
2833  //orderingdepth = new intvec(pVariables+1);
2834  syzstr->length = *length = pVariables+2;
2835  if (idIs0(arg)) return NULL;
2836  if ((currRing->order[0]==ringorder_dp)
2837  &&  (currRing->order[1]==ringorder_C)
2838  &&  (currRing->order[2]==0))
2839  {
2840    ord=NULL;
2841  }
2842/*--- changes to a dpC-ring with special comp0------*/
2843  else
2844  {
2845    ord = (int*)Alloc0(3*sizeof(int));
2846    b0 = (int*)Alloc0(3*sizeof(int));
2847    b1 = (int*)Alloc0(3*sizeof(int));
2848    ord[0] = ringorder_dp;
2849    ord[1] = ringorder_C;
2850    b0[1] = 1;
2851    b1[0] = pVariables;
2852    tmpR  = *origR;
2853    tmpR.order = ord;
2854    tmpR.block0 = b0;
2855    tmpR.block1 = b1;
2856    rComplete(&tmpR);
2857    //pChangeRing(pVariables,1,ord,b0,b1,currRing->wvhdl);
2858    rChangeCurrRing(&tmpR, TRUE);
2859  }
2860/*--- initializes the data structures---------------*/
2861  syzstr->Tl = new intvec(*length);
2862  temp = idInit(IDELEMS(arg),arg->rank);
2863  for (i=0;i<IDELEMS(arg);i++)
2864  {
2865    temp->m[i] = pOrdPolyInsertSetm(pCopy(arg->m[i]));
2866    if (temp->m[i]!=NULL)
2867    {
2868      j = pTotaldegree(temp->m[i]);
2869      if (j<actdeg) actdeg = j;
2870    }
2871  }
2872  idTest(temp);
2873  idSkipZeroes(temp);
2874  idTest(temp);
2875  sySetHighdeg();
2876  binomials = (int*)Alloc(pVariables*(highdeg+1)*sizeof(int));
2877  syBinomSet();
2878#if ! defined(HAVE_SY_VECTOR) || defined(SY_VEC_DEBUG)
2879  pSetm =syzSetm;
2880  for (i=0;i<IDELEMS(temp);i++)
2881  {
2882    p = temp->m[i];
2883    while (p!=NULL)
2884    {
2885      pSetm(p);
2886      pIter(p);
2887    }
2888  }
2889#else
2890  SetSpolyProc();
2891#endif
2892  pComp0 = syzcomp2dpc;
2893  currcomponents = (int*)Alloc0((arg->rank+1)*sizeof(int));
2894  for (i=0;i<=arg->rank;i++)
2895    currcomponents[i] = i;
2896  syzstr->resPairs = syInitRes(temp,length,syzstr->Tl,syzstr->cw);
2897  Free((ADDRESS)currcomponents,(arg->rank+1)*sizeof(int));
2898  syzstr->res = (resolvente)Alloc0((*length+1)*sizeof(ideal));
2899  syzstr->orderedRes = (resolvente)Alloc0((*length+1)*sizeof(ideal));
2900  syzstr->truecomponents = (int**)Alloc0((*length+1)*sizeof(int*));
2901  syzstr->backcomponents = (int**)Alloc0((*length+1)*sizeof(int*));
2902  syzstr->Howmuch = (int**)Alloc0((*length+1)*sizeof(int*));
2903  syzstr->Firstelem = (int**)Alloc0((*length+1)*sizeof(int*));
2904  int len0=idRankFreeModule(arg)+1;
2905  //syzstr->truecomponents[0] = (int*)Alloc(len0*sizeof(int));
2906  //syzstr->backcomponents[0] = (int*)Alloc(len0*sizeof(int));
2907  //syzstr->Howmuch[0] = (int*)Alloc(len0*sizeof(int));
2908  //syzstr->Firstelem[0] = (int*)Alloc(len0*sizeof(int));
2909//Print("sort %d has now size %d\n",0,len0);
2910  startdeg = actdeg;
2911  nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2912  //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2913/*--- computes the resolution ----------------------*/
2914  while (nextPairs!=NULL)
2915  {
2916    if (TEST_OPT_PROT) Print("%d",actdeg);
2917    if (TEST_OPT_PROT) Print("(m%d)",index);
2918    if (index==0)
2919      i = syInitSyzMod(syzstr,index,len0);
2920    else
2921      i = syInitSyzMod(syzstr,index);
2922    currcomponents = syzstr->truecomponents[max(index-1,0)];
2923    j = syInitSyzMod(syzstr,index+1);
2924    if (index>0)
2925    {
2926      syRedNextPairs(nextPairs,syzstr,howmuch,index);
2927      syCompactifyPairSet(syzstr->resPairs[index],(*syzstr->Tl)[index],0);
2928    }
2929    else
2930      syRedGenerOfCurrDeg(syzstr,actdeg,index+1);
2931/*--- creates new pairs -----------------------------*/
2932    syCreateNewPairs(syzstr,index,i);
2933    if (index<(*length)-1)
2934    {
2935      syCreateNewPairs(syzstr,index+1,j);
2936      //currcomponents = syzstr->truecomponents[index];
2937      //sySyzTail(syzstr,index+1,j);
2938      //currcomponents = syzstr->truecomponents[index-1];
2939    }
2940    index++;
2941    nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2942    //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2943  }
2944  if (temp!=NULL) idDelete(&temp);
2945  if (ord!=NULL)
2946  {
2947    //pChangeRing(pVariables,currRing->OrdSgn,currRing->order,
2948    //currRing->block0,currRing->block1,currRing->wvhdl);
2949    rChangeCurrRing(origR,TRUE);
2950  }
2951  else
2952  {
2953    pSetm=oldSetm;
2954    pComp0=oldComp0;
2955  }
2956  if (ord!=NULL)
2957  {
2958    Free((ADDRESS)ord,3*sizeof(int));
2959    Free((ADDRESS)b0,3*sizeof(int));
2960    Free((ADDRESS)b1,3*sizeof(int));
2961  }
2962  syzstr->binom = binomials;
2963  syzstr->highdeg_1 = highdeg_1;
2964  pDelete1(&redpol);
2965  if (TEST_OPT_PROT) PrintLn();
2966  return syzstr;
2967}
Note: See TracBrowser for help on using the repository browser.