source: git/Singular/syz1.cc @ f92fa13

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