source: git/Singular/syz1.cc @ 97454d

spielwiese
Last change on this file since 97454d was fca547, checked in by Hans Schönemann <hannes@…>, 26 years ago
*** empty log message *** git-svn-id: file:///usr/local/Singular/svn/trunk@1317 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 78.8 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: syz1.cc,v 1.24 1998-04-03 17:38:45 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=pNew();
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            //Print("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            //Print("Hilfe!!!!!!!\n");
875            //Print("Fehler in Modul %d bei Elem %d\n",index,j);
876            //Print("Poly p: ");pWrite(hn);
877            //Print("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//Print("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
1038/*3
1039* reduces all pairs of degree deg in the module index
1040* put the reduced generators to the resolvente which contains
1041* the truncated std
1042*/
1043static void syRedNextPairs(SSet nextPairs, syStrategy syzstr,
1044               int howmuch, int index)
1045{
1046  int i=howmuch-1,j,k=IDELEMS(syzstr->res[index]);
1047  int ks=IDELEMS(syzstr->res[index+1]),kk,l,ll;
1048  int ** Fin=syzstr->Firstelem;
1049  int ** Hin=syzstr->Howmuch;
1050  int ** bin=syzstr->backcomponents;
1051  number coefgcd,n;
1052  ideal o_r=syzstr->orderedRes[index+1];
1053  polyset redset=syzstr->orderedRes[index]->m;
1054  poly p=NULL,q;
1055  BOOLEAN isDivisible;
1056  SObject tso;
1057
1058  if ((nextPairs==NULL) || (howmuch==0)) return;
1059  while ((k>0) && (syzstr->res[index]->m[k-1]==NULL)) k--;
1060  while ((ks>0) && (syzstr->res[index+1]->m[ks-1]==NULL)) ks--;
1061  while (i>=0)
1062  {
1063    tso = nextPairs[i];
1064    isDivisible = FALSE;
1065    if (syzstr->res[index+1]!=NULL)
1066    {
1067      l = Fin[index][pGetComp(tso.lcm)]-1;
1068      if (l>=0)
1069      {
1070        ll = l+Hin[index][pGetComp(tso.lcm)];
1071        while ((l<ll) && (!isDivisible))
1072        {
1073          if (o_r->m[l]!=NULL)
1074          {
1075            isDivisible = isDivisible || 
1076              pDivisibleBy2(o_r->m[l],tso.lcm);
1077          }
1078          l++;
1079        }
1080      }
1081    }
1082    if (!isDivisible)
1083    {
1084      tso.p = 
1085        sySPoly(tso.p1, tso.p2,tso.lcm);
1086      coefgcd = 
1087        nGcd(pGetCoeff(tso.p1),pGetCoeff(tso.p1));
1088      tso.syz = pHead(tso.lcm);
1089      pSetm(tso.syz);
1090      p = tso.syz;
1091      pSetCoeff(p,nDiv(pGetCoeff(tso.p1),coefgcd));
1092      pGetCoeff(p) = nNeg(pGetCoeff(p));
1093      pSetComp(p,tso.ind2+1);
1094      pNext(p) = pHead(tso.lcm);
1095      pIter(p);
1096      pSetm(p);
1097      pSetComp(p,tso.ind1+1);
1098      pSetCoeff(p,nDiv(pGetCoeff(tso.p2),coefgcd));
1099      nDelete(&coefgcd);
1100      if (tso.p != NULL)
1101      {
1102        q = tso.p;
1103        j = Fin[index-1][pGetComp(q)]-1;
1104        int pos = j+Hin[index-1][pGetComp(q)];
1105        loop
1106        {
1107          if (j<0) break;
1108          if (pDivisibleBy2(redset[j],q))
1109          {
1110            //int syL=syLength(redset[j]);
1111            //Print("r");
1112//for(int jj=j+1;jj<k;jj++)
1113//{
1114  //if (syDivisibleBy(redset[jj],q))
1115  //{
1116    //int syL1=syLength(redset[jj]);
1117    //if (syL1<syL)
1118    //{
1119      //j = jj;
1120      //syL = syL1;
1121      //Print("take poly %d with %d monomials\n",j,syL);
1122      //Print("have poly %d with %d monomials\n",jj,syL1);
1123    //}
1124  //}
1125//}
1126            pNext(p) = pHead(q);
1127            pIter(p);
1128            pSetComp(p,bin[index][j]+1);
1129            pGetCoeff(p) = nNeg(pGetCoeff(p));
1130            q = sySPolyRed(q,redset[j]);
1131            if (q==NULL) break;
1132            j = Fin[index-1][pGetComp(q)]-1;
1133            pos = j+Hin[index-1][pGetComp(q)];
1134          }
1135          else
1136          {
1137            j++;
1138            if (j==pos) break;
1139          }
1140        }
1141        tso.p = q;
1142      }
1143      if (tso.p != NULL)
1144      {
1145        if (TEST_OPT_PROT) Print("g");
1146        if (k==IDELEMS((syzstr->res)[index]))
1147        {
1148          pEnlargeSet(&(syzstr->res[index]->m),IDELEMS(syzstr->res[index]),16);
1149          syzstr->truecomponents[index]=(int*)ReAlloc((ADDRESS)syzstr->truecomponents[index],
1150                                       (IDELEMS(syzstr->res[index])+1)*sizeof(int),
1151                                       (IDELEMS(syzstr->res[index])+17)*sizeof(int));
1152          syzstr->backcomponents[index]=(int*)ReAlloc((ADDRESS)syzstr->backcomponents[index],
1153                                       (IDELEMS(syzstr->res[index])+1)*sizeof(int),
1154                                       (IDELEMS(syzstr->res[index])+17)*sizeof(int));
1155          syzstr->Howmuch[index]=(int*)ReAlloc((ADDRESS)syzstr->Howmuch[index],
1156                                       (IDELEMS(syzstr->res[index])+1)*sizeof(int),
1157                                       (IDELEMS(syzstr->res[index])+17)*sizeof(int));
1158          syzstr->Firstelem[index]=(int*)ReAlloc((ADDRESS)syzstr->Firstelem[index],
1159                                       (IDELEMS(syzstr->res[index])+1)*sizeof(int),
1160                                       (IDELEMS(syzstr->res[index])+17)*sizeof(int));
1161        int mk;
1162        for (mk=IDELEMS(syzstr->res[index])+1;mk<IDELEMS(syzstr->res[index])+17;mk++)
1163        {
1164          syzstr->Howmuch[index][mk] = 0;
1165          syzstr->Firstelem[index][mk] = 0;
1166        }
1167//Print("sort %d has now size %d\n",index,IDELEMS(res[index])+17);
1168          IDELEMS(syzstr->res[index]) += 16;
1169          pEnlargeSet(&(syzstr->orderedRes[index]->m),IDELEMS(syzstr->orderedRes[index]),16);
1170          IDELEMS(syzstr->orderedRes[index]) += 16;
1171          redset=syzstr->orderedRes[index]->m;
1172        }
1173        pNext(p) = pHead(tso.p);
1174        pIter(p);
1175        if (p!=NULL)
1176        {
1177          k++;
1178          pSetComp(p,k);
1179          pGetCoeff(p) = nNeg(pGetCoeff(p));
1180        }
1181        if (tso.p!=NULL)
1182        {
1183          syzstr->res[index]->m[k-1] = tso.p;
1184          pNorm(syzstr->res[index]->m[k-1]);
1185          syOrder(syzstr->res[index]->m[k-1],syzstr,index,k);
1186        }
1187        tso.isNotMinimal = p;
1188        tso.p = NULL;
1189      }
1190      else
1191      {
1192        if (TEST_OPT_PROT) Print(".");
1193        if (index % 2==0)
1194          euler++;
1195        else 
1196          euler--;
1197      }
1198      if (ks==IDELEMS(syzstr->res[index+1]))
1199      {
1200        pEnlargeSet(&(syzstr->res[index+1]->m),IDELEMS(syzstr->res[index+1]),16);
1201        syzstr->truecomponents[index+1]=(int*)ReAlloc((ADDRESS)syzstr->truecomponents[index+1],
1202                                       (IDELEMS(syzstr->res[index+1])+1)*sizeof(int),
1203                                       (IDELEMS(syzstr->res[index+1])+17)*sizeof(int));
1204        syzstr->backcomponents[index+1]=(int*)ReAlloc((ADDRESS)syzstr->backcomponents[index+1],
1205                                       (IDELEMS(syzstr->res[index+1])+1)*sizeof(int),
1206                                       (IDELEMS(syzstr->res[index+1])+17)*sizeof(int));
1207        syzstr->Howmuch[index+1]=(int*)ReAlloc((ADDRESS)syzstr->Howmuch[index+1],
1208                                       (IDELEMS(syzstr->res[index+1])+1)*sizeof(int),
1209                                       (IDELEMS(syzstr->res[index+1])+17)*sizeof(int));
1210        syzstr->Firstelem[index+1]=(int*)ReAlloc((ADDRESS)syzstr->Firstelem[index+1],
1211                                       (IDELEMS(syzstr->res[index+1])+1)*sizeof(int),
1212                                       (IDELEMS(syzstr->res[index+1])+17)*sizeof(int));
1213        int mk;
1214        for (mk=IDELEMS(syzstr->res[index+1])+1;mk<IDELEMS(syzstr->res[index+1])+17;mk++)
1215        {
1216          syzstr->Howmuch[index+1][mk] = 0;
1217          syzstr->Firstelem[index+1][mk] = 0;
1218        }
1219//Print("sort %d has now size %d\n",index+1,IDELEMS(res[index+1])+17);
1220        IDELEMS(syzstr->res[index+1]) += 16;
1221        pEnlargeSet(&(syzstr->orderedRes[index+1]->m),IDELEMS(syzstr->orderedRes[index+1]),16);
1222        IDELEMS(syzstr->orderedRes[index+1]) += 16;
1223      }
1224      currcomponents = syzstr->truecomponents[index];
1225      syzstr->res[index+1]->m[ks] = syRedtail(tso.syz,syzstr,index+1);
1226      currcomponents = syzstr->truecomponents[index-1];
1227      syzstr->res[index+1]->m[ks] = tso.syz;
1228      pNorm(syzstr->res[index+1]->m[ks]);
1229      tso.syz =NULL;
1230      tso.syzind = ks;
1231      syOrder(syzstr->res[index+1]->m[ks],syzstr,index+1,ks+1);
1232      ks++;
1233      p = NULL;
1234      nextPairs[i] = tso;
1235    }
1236    else
1237    {
1238      syDeletePair(&nextPairs[i]);
1239      //crit++;
1240    }
1241    i--;
1242  }
1243} 
1244
1245/*3
1246* reduces the generators of the module index in degree deg
1247* (which are actual syzygies of the module index-1)
1248* wrt. the ideal generated by elements of lower degrees
1249*/
1250static void syRedGenerOfCurrDeg(syStrategy syzstr, int deg, int index)
1251{
1252  ideal res=syzstr->res[index];
1253  int i=0,j,k=IDELEMS(res),kk;
1254  SSet sPairs=syzstr->resPairs[index-1];
1255
1256  while ((k>0) && (res->m[k-1]==NULL)) k--;
1257  while ((i<(*syzstr->Tl)[index-1]) && (((sPairs)[i].syz==NULL) || 
1258          ((sPairs)[i].order<deg)))
1259    i++;
1260  if ((i>=(*syzstr->Tl)[index-1]) || ((sPairs)[i].order>deg)) return;
1261  while ((i<(*syzstr->Tl)[index-1]) && (((sPairs)[i].syz==NULL) ||
1262         ((sPairs)[i].order==deg))) 
1263  {
1264    if ((sPairs)[i].syz!=NULL)
1265    {
1266      j = k-1;
1267      while ((j>=0) && (res->m[j]!=NULL) && 
1268             ((sPairs)[i].syz!=NULL))
1269      {
1270        if (pDivisibleBy1(res->m[j],(sPairs)[i].syz))
1271        {
1272          //Print("r");
1273          (sPairs)[i].syz = 
1274            //spSpolyRed(res->m[j],(sPairs)[i].syz,NULL);
1275            sySPolyRed((sPairs)[i].syz,res->m[j]);
1276          j = k-1;
1277        }
1278        else
1279        {
1280          j--;
1281        }
1282      }
1283      if ((sPairs)[i].syz != NULL)
1284      {
1285        if (k==IDELEMS(res))
1286        {
1287          pEnlargeSet(&(res->m),IDELEMS(res),16);
1288          syzstr->truecomponents[index]=(int*)ReAlloc((ADDRESS)syzstr->truecomponents[index],
1289                                       (IDELEMS(res)+1)*sizeof(int),
1290                                       (IDELEMS(res)+17)*sizeof(int));
1291          syzstr->backcomponents[index]=(int*)ReAlloc((ADDRESS)syzstr->backcomponents[index],
1292                                       (IDELEMS(res)+1)*sizeof(int),
1293                                       (IDELEMS(res)+17)*sizeof(int));
1294          syzstr->Howmuch[index]=(int*)ReAlloc((ADDRESS)syzstr->Howmuch[index],
1295                                       (IDELEMS(res)+1)*sizeof(int),
1296                                       (IDELEMS(res)+17)*sizeof(int));
1297          syzstr->Firstelem[index]=(int*)ReAlloc((ADDRESS)syzstr->Firstelem[index],
1298                                       (IDELEMS(res)+1)*sizeof(int),
1299                                       (IDELEMS(res)+17)*sizeof(int));
1300        int mk;
1301        for (mk=IDELEMS(res)+1;mk<IDELEMS(res)+17;mk++)
1302        {
1303          syzstr->Howmuch[index][mk] = 0;
1304          syzstr->Firstelem[index][mk] = 0;
1305        }
1306//Print("sort %d has now size %d\n",index,IDELEMS(res[index])+17);
1307          IDELEMS(res) += 16;
1308          pEnlargeSet(&(syzstr->orderedRes[index]->m),IDELEMS(syzstr->orderedRes[index]),16);
1309          IDELEMS(syzstr->orderedRes[index]) += 16;
1310        }
1311        if (BTEST1(6))
1312        {
1313          if ((sPairs)[i].isNotMinimal==NULL)
1314          {
1315            PrintLn();
1316            Print("minimal generator: ");pWrite((syzstr->resPairs[index-1])[i].syz);
1317            Print("comes from: ");pWrite((syzstr->resPairs[index-1])[i].p1);
1318            Print("and: ");pWrite((syzstr->resPairs[index-1])[i].p2);
1319          }
1320        }
1321        //res->m[k] = (sPairs)[i].syz;
1322        res->m[k] = syRedtail((sPairs)[i].syz,syzstr,index);
1323        (sPairs)[i].syzind = k;
1324        pNorm(res->m[k]);
1325  //      (sPairs)[i].syz = NULL;
1326        k++;
1327        syOrder(res->m[k-1],syzstr,index,k);
1328        euler++;
1329      }
1330      else
1331        (sPairs)[i].syzind = -1;
1332    }
1333    i++;
1334  }
1335}
1336
1337/*3
1338* puts a pair into the right place in resPairs
1339*/
1340static void syEnterPair(SSet sPairs, SObject * so, int * sPlength,int index)
1341{
1342  int ll,k,no=(*so).order,sP=*sPlength,i;
1343  poly p=(*so).lcm;
1344
1345  if ((sP==0) || (sPairs[sP-1].order<=no))
1346    ll = sP;
1347  else if (sP==1)
1348    ll = 0;
1349  else
1350  {
1351    int an=0,en=sP-1;
1352    loop
1353    {
1354      if (an>=en-1)
1355      {
1356        if ((sPairs[an].order<=no) && (sPairs[an+1].order>no))
1357        {
1358          ll = an+1;
1359          break;
1360        }
1361        else if ((sPairs[en].order<=no) && (sPairs[en+1].order>no))
1362        {
1363          ll = en+1;
1364          break;
1365        }
1366        else if (sPairs[an].order>no)
1367        {
1368          ll = an;
1369          break;
1370        }
1371        else
1372        {
1373          Print("Hier ist was faul!\n");
1374          break;
1375        }
1376      }
1377      i=(an+en) / 2;
1378      if (sPairs[i].order <= no)
1379        an=i;
1380      else
1381        en=i;
1382    }
1383  }
1384  for (k=(*sPlength);k>ll;k--)
1385  {
1386    syCopyPair(&sPairs[k-1],&sPairs[k]);
1387  }
1388  syCopyPair(so,&sPairs[ll]);
1389  (*sPlength)++;
1390}
1391
1392/*3
1393* computes pairs from the new elements (beginning with the element newEl)
1394* in the module index
1395*/
1396static void syCreateNewPairs(syStrategy syzstr, int index, int newEl)
1397{
1398  SSet temp;
1399  SObject tso;
1400  int i,ii,j,k=IDELEMS(syzstr->res[index]),l=(*syzstr->Tl)[index],ll;
1401  int qc,first,pos,jj,j1;
1402  int * bci=syzstr->backcomponents[index];
1403  poly p,q;
1404  polyset rs=syzstr->res[index]->m,nPm;
1405
1406  while ((k>0) && (rs[k-1]==NULL)) k--;
1407  if (newEl>=k) return;
1408  ideal nP=idInit(k,syzstr->res[index]->rank);
1409  nPm=nP->m;
1410  while ((l>0) && ((syzstr->resPairs[index])[l-1].p1==NULL)) l--;
1411//Print("new pairs in module %d\n",index);
1412  for (j=newEl;j<k;j++)
1413  {
1414    q = rs[j];
1415    qc = pGetComp(q);
1416    first = syzstr->Firstelem[index-1][pGetComp(q)]-1;
1417    pos = first+syzstr->Howmuch[index-1][pGetComp(q)];
1418    for (i=first;i<pos;i++)
1419    {
1420      jj = bci[i];
1421      if (jj>=j) break;
1422      p = pOne();
1423      pLcm(rs[jj],q,p);
1424      pSetComp(p,j+1);
1425      ii = first;
1426      loop
1427      {
1428        j1 = bci[ii];
1429        if (nPm[j1]!=NULL)
1430        {
1431          if (pDivisibleBy2(nPm[j1],p))
1432          {
1433            pDelete(&p);
1434            break;
1435          }
1436          else if (pDivisibleBy2(p,nPm[j1]))
1437          {
1438            pDelete(&(nPm[j1]));
1439            break;
1440          }
1441        }
1442        ii++;
1443        if (ii>=pos) break;
1444      }
1445      if (p!=NULL)
1446      {
1447        nPm[jj] = p;
1448      }
1449    }
1450    //for (i=0;i<j;i++)
1451    for (i=first;i<pos;i++)
1452    {
1453      ii = bci[i];
1454      if (nPm[ii]!=NULL)
1455      {
1456        if (l>=(*syzstr->Tl)[index])
1457        {
1458          temp = (SSet)Alloc0(((*syzstr->Tl)[index]+16)*sizeof(SObject));
1459          for (ll=0;ll<(*syzstr->Tl)[index];ll++)
1460          {
1461            temp[ll].p = (syzstr->resPairs[index])[ll].p;
1462            temp[ll].p1 = (syzstr->resPairs[index])[ll].p1;
1463            temp[ll].p2 = (syzstr->resPairs[index])[ll].p2;
1464            temp[ll].syz = (syzstr->resPairs[index])[ll].syz;
1465            temp[ll].lcm = (syzstr->resPairs[index])[ll].lcm;
1466            temp[ll].ind1 = (syzstr->resPairs[index])[ll].ind1;
1467            temp[ll].ind2 = (syzstr->resPairs[index])[ll].ind2;
1468            temp[ll].syzind = (syzstr->resPairs[index])[ll].syzind;
1469            temp[ll].order = (syzstr->resPairs[index])[ll].order;
1470            temp[ll].isNotMinimal = (syzstr->resPairs[index])[ll].isNotMinimal;
1471          }
1472          Free((ADDRESS)syzstr->resPairs[index],(*syzstr->Tl)[index]*sizeof(SObject));
1473          (*syzstr->Tl)[index] += 16;
1474          syzstr->resPairs[index] = temp;
1475        }
1476        tso.lcm = p = nPm[ii];
1477        nPm[ii] = NULL;
1478        tso.order = pGetOrder(p) = pTotaldegree(p);
1479        if ((syzstr->cw!=NULL) && (index>0) && (pGetComp(q)>0))
1480        {
1481          int ii=index-1,jj=pGetComp(q);
1482          while (ii>0) 
1483          {
1484            jj = pGetComp(syzstr->res[ii]->m[jj-1]);
1485            ii--;
1486          }
1487          tso.order += (*syzstr->cw)[jj-1];
1488        }
1489        tso.p1 = rs[ii];
1490        tso.p2 = q;
1491        tso.ind1 = ii;
1492        tso.ind2 = j;
1493        tso.syzind = -1;
1494        tso.isNotMinimal = NULL;
1495        tso.p = NULL;
1496        tso.syz = NULL;
1497        syEnterPair(syzstr->resPairs[index],&tso,&l,index);
1498      }
1499    }
1500  }
1501  idDelete(&nP);
1502}
1503
1504static void sySyzTail(syStrategy syzstr, int index, int newEl)
1505{
1506  int j,ll,k=IDELEMS((syzstr->res)[index]);
1507  while ((k>0) && ((syzstr->res)[index]->m[k-1]==NULL)) k--;
1508  for (j=newEl;j<k;j++)
1509  {
1510    ll = 0;
1511    while ((ll<(*syzstr->Tl)[index]) && (syzstr->resPairs[index][ll].p1!=NULL) &&
1512           (syzstr->resPairs[index][ll].ind1!=j) && (syzstr->resPairs[index][ll].ind2!=j))
1513      ll++;
1514    if ((ll<(*syzstr->Tl)[index]) && (syzstr->resPairs[index][ll].p1!=NULL))
1515      syzstr->res[index]->m[j] = syRedtail(syzstr->res[index]->m[j],syzstr,index);
1516  }
1517}
1518
1519static SSet syChosePairsPutIn(syStrategy syzstr, int *index,
1520               int *howmuch, int * actdeg, int an, int en)
1521{
1522  int newdeg=*actdeg,newindex=-1,i,t,sldeg;
1523  poly p;
1524  SSet result;
1525  SRes resPairs=syzstr->resPairs;
1526 
1527  if (an>syzstr->length) return NULL;
1528  if (en>syzstr->length) en=syzstr->length;
1529  while (*index<en)
1530  {
1531    if (resPairs[*index]!=NULL)
1532    {
1533      sldeg = (*actdeg)+*index;
1534      i = 0;
1535      if (*index!=0)
1536      {
1537        while ((i<(*syzstr->Tl)[*index]))
1538        {
1539          if ((resPairs[*index])[i].lcm!=NULL)
1540          {
1541            if ((resPairs[*index])[i].order == sldeg)
1542            {
1543              result = &(resPairs[*index])[i];
1544              *howmuch =1;
1545              i++;
1546              while ((i<(*syzstr->Tl)[*index]) && ((resPairs[*index])[i].lcm!=NULL)
1547                      && ((resPairs[*index])[i].order == sldeg))
1548              {
1549                i++;
1550                (*howmuch)++;
1551              }
1552              return result;
1553            }
1554          }
1555          i++;
1556        }
1557      }
1558      else
1559      {
1560        while ((i<(*syzstr->Tl)[*index]))
1561        {
1562          if ((resPairs[*index])[i].syz!=NULL)
1563          {
1564            if ((resPairs[*index])[i].order == sldeg)
1565            {
1566              result = &(resPairs[*index])[i];
1567              (*howmuch) =1;
1568              i++;
1569              while ((i<(*syzstr->Tl)[*index]) && ((resPairs[*index])[i].syz!=NULL)
1570                      && ((resPairs[*index])[i].order == *actdeg))
1571              {
1572                i++;
1573                (*howmuch)++;
1574              }
1575              return result;
1576            }
1577          }
1578          i++;
1579        }
1580      }
1581    }
1582    (*index)++;
1583  }
1584  *index = an;
1585  //if (TEST_OPT_PROT) Print("(Euler:%d)",euler);
1586  while (*index<en)
1587  {
1588    if (resPairs[*index]!=NULL)
1589    {
1590      i = 0;
1591      while ((i<(*syzstr->Tl)[*index]))
1592      {
1593        t = *actdeg+*index;
1594        if (((resPairs[*index])[i].lcm!=NULL) || 
1595              ((resPairs[*index])[i].syz!=NULL))
1596        {
1597          if ((resPairs[*index])[i].order > t)
1598            t = (resPairs[*index])[i].order;
1599        }
1600        if ((t>*actdeg+*index) && ((newdeg==*actdeg) || (t<newdeg+*index)))
1601        {
1602          newdeg = t-*index;
1603          newindex = *index;
1604          break;
1605        }
1606        i++;
1607      } 
1608    }
1609    (*index)++;
1610  }
1611  if (newdeg>*actdeg)
1612  {
1613    *actdeg = newdeg;
1614    *index = newindex;
1615    return syChosePairsPutIn(syzstr,index,howmuch,actdeg,an,en);
1616  }
1617  else return NULL;
1618}
1619
1620/*3
1621* FOR THE HOMOGENEOUS CASE ONLY!
1622* looks through the pair set and the given module for
1623* remaining pairs or generators to consider
1624* returns a pointer to the first pair and the number of them in the given module
1625* works with slanted degree (i.e. deg=realdeg-index)
1626*/
1627static SSet syChosePairs(syStrategy syzstr, int *index,
1628               int *howmuch, int * actdeg)
1629{
1630  return syChosePairsPutIn(syzsts,index,howmuch,actdeg,0,syzstr->length);
1631}
1632
1633/*3
1634* FOR THE INHOMOGENEOUS CASE ONLY!
1635* looks through the pair set and the given module for
1636* remaining pairs or generators to consider
1637* returns a pointer to the first pair and the number of them in the given module
1638* works with slanted degree (i.e. deg=realdeg-index)
1639* looks first through the 0 and 1 module then through the other
1640*/
1641static SSet syChosePairsIH(syStrategy syzstr, int *index,
1642               int *howmuch, int * actdeg, int mindeg)
1643{
1644  SSet result=NULL;
1645
1646  result = syChosePairsPutIn(syzstr,index,howmuch,actdeg,0,2);
1647  if (result == NULL)
1648  {
1649    *actdeg = mindeg;
1650    result = syChosePairsPutIn(syzstr,index,howmuch,actdeg,2,syzstr->length);
1651  }
1652  return result;
1653}
1654
1655/*3
1656* looks through the pair set and the given module for
1657* remaining pairs or generators to consider
1658* returns a pointer to the first pair and the number of them in the given module
1659* works deg by deg
1660*/
1661/*
1662*static SSet syChosePairs1(SRes resPairs,intvec * Tl, int *index, int *howmuch,
1663*                   int length,int * actdeg)
1664*{
1665*  int newdeg=*actdeg,newindex=-1,i,t;
1666*  SSet result;
1667* 
1668*  while (*index>=0)
1669*  {
1670*    if (resPairs[*index]!=NULL)
1671*    {
1672*      i = 0;
1673*      if (*index!=0)
1674*      {
1675*        while ((i<(*Tl)[*index]))
1676*        {
1677*          if ((resPairs[*index])[i].lcm!=NULL)
1678*          {
1679*            if (pGetOrder((resPairs[*index])[i].lcm) == *actdeg)
1680*            {
1681*              result = &(resPairs[*index])[i];
1682*              *howmuch =1;
1683*              i++;
1684*              while ((i<(*Tl)[*index]) && ((resPairs[*index])[i].lcm!=NULL)
1685*                      && (pGetOrder((resPairs[*index])[i].lcm) == *actdeg))
1686*              {
1687*                i++;
1688*                (*howmuch)++;
1689*              }
1690*              return result;
1691*            }
1692*          }
1693*          i++;
1694*        }
1695*      }
1696*      else
1697*      {
1698*        while ((i<(*Tl)[*index]))
1699*        {
1700*          if ((resPairs[*index])[i].syz!=NULL)
1701*          {
1702*            if ((resPairs[*index])[i].order == *actdeg)
1703*            {
1704*              result = &(resPairs[*index])[i];
1705*              (*howmuch) =1;
1706*              i++;
1707*              while ((i<(*Tl)[*index]) && ((resPairs[*index])[i].syz!=NULL)
1708*                      && ((resPairs[*index])[i].order == *actdeg))
1709*              {
1710*                i++;
1711*                (*howmuch)++;
1712*              }
1713*              return result;
1714*            }
1715*          }
1716*          i++;
1717*        }
1718*      }
1719*    }
1720*    (*index)--;
1721*  }
1722*  *index = length-1;
1723*  while (*index>=0)
1724*  {
1725*    if (resPairs[*index]!=NULL)
1726*    {
1727*      i = 0;
1728*      while ((i<(*Tl)[*index]))
1729*      {
1730*        t = *actdeg;
1731*        if ((resPairs[*index])[i].lcm!=NULL)
1732*        {
1733*          if (pGetOrder((resPairs[*index])[i].lcm) > *actdeg)
1734*            t = pGetOrder((resPairs[*index])[i].lcm);
1735*        }
1736*        else if ((resPairs[*index])[i].syz!=NULL)
1737*        {
1738*          if ((resPairs[*index])[i].order > *actdeg)
1739*            t = (resPairs[*index])[i].order;
1740*        }
1741*        if ((t>*actdeg) && ((newdeg==*actdeg) || (t<newdeg)))
1742*        {
1743*          newdeg = t;
1744*          newindex = *index;
1745*          break;
1746*        }
1747*        i++;
1748*      }
1749*    }
1750*    (*index)--;
1751*  }
1752*  if (newdeg>*actdeg)
1753*  {
1754*    *actdeg = newdeg;
1755*    *index = newindex;
1756*    return syChosePairs1(resPairs,Tl,index,howmuch,length,actdeg);
1757*  }
1758*  else return NULL;
1759*}
1760*/
1761/*3
1762* statistics of the resolution
1763*/
1764static void syStatistics(resolvente res,int length)
1765{
1766  int i,j=1,k,deg=0;
1767
1768  PrintLn();
1769  while ((j<length) && (res[j]!=NULL))
1770  {
1771    Print("In module %d: \n",j);
1772    k = 0;
1773    while ((k<IDELEMS(res[j])) && (res[j]->m[k]!=NULL))
1774    {
1775      i = 1;
1776      deg = pGetOrder(res[j]->m[k]);
1777      k++;
1778      while ((k<IDELEMS(res[j])) && (res[j]->m[k]!=NULL) &&
1779              (pGetOrder(res[j]->m[k])==deg))
1780      {
1781        i++;
1782        k++;
1783      }
1784      Print("%d elements of degree %d\n",i,deg);
1785    }
1786    j++;
1787  }
1788}
1789
1790/*3
1791* initialize a module
1792*/
1793static int syInitSyzMod(syStrategy syzstr, int index, int init=17)
1794{
1795  int result;
1796
1797  if (syzstr->res[index]==NULL) 
1798  {
1799    syzstr->res[index] = idInit(init-1,1);
1800    syzstr->truecomponents[index] = (int*)Alloc0(init*sizeof(int));
1801    if (index==0)
1802    {
1803      for (int i=0;i<init;i++)
1804        syzstr->truecomponents[0][i] = i;
1805    }
1806    syzstr->backcomponents[index] = (int*)Alloc0(init*sizeof(int));
1807    syzstr->Howmuch[index] = (int*)Alloc0(init*sizeof(int));
1808    syzstr->Firstelem[index] = (int*)Alloc0(init*sizeof(int));
1809//Print("sort %d has now size %d\n",index,init);
1810    syzstr->orderedRes[index] = idInit(init-1,1);
1811    result = 0;
1812  }
1813  else
1814  {
1815    result = IDELEMS(syzstr->res[index]);
1816    while ((result>0) && (syzstr->res[index]->m[result-1]==NULL)) result--;
1817  }
1818  return result;
1819}
1820
1821void syKillComputation(syStrategy syzstr)
1822{
1823//Print("ref: %d\n",syzstr->references);
1824  if (syzstr->references>0)
1825  {
1826    (syzstr->references)--;
1827  }
1828  else
1829  {
1830    int i,j;
1831 
1832    if (syzstr->resPairs!=NULL)
1833    {
1834      for (i=0;i<syzstr->length;i++)
1835      {
1836        for (j=0;j<(*syzstr->Tl)[i];j++)
1837        {
1838          if ((syzstr->resPairs[i])[j].lcm!=NULL)
1839            pDelete(&((syzstr->resPairs[i])[j].lcm));
1840        }
1841        if (syzstr->orderedRes[i]!=NULL)
1842        {
1843          for (j=0;j<IDELEMS(syzstr->orderedRes[i]);j++)
1844          {
1845            syzstr->orderedRes[i]->m[j] = NULL;
1846          }
1847        }
1848        idDelete(&(syzstr->orderedRes[i]));
1849        if (syzstr->truecomponents[i]!=NULL)
1850        {
1851          Free((ADDRESS)syzstr->truecomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1852          syzstr->truecomponents[i]=NULL;
1853        }
1854        if (syzstr->backcomponents[i]!=NULL)
1855        {
1856          Free((ADDRESS)syzstr->backcomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1857          syzstr->backcomponents[i]=NULL;
1858        }
1859        if (syzstr->Howmuch[i]!=NULL)
1860        {
1861          Free((ADDRESS)syzstr->Howmuch[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1862          syzstr->Howmuch[i]=NULL;
1863        }
1864        if (syzstr->Firstelem[i]!=NULL)
1865        {
1866          Free((ADDRESS)syzstr->Firstelem[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1867          syzstr->Firstelem[i]=NULL;
1868        }
1869        if (syzstr->res[i]!=NULL)
1870        {
1871          for (j=0;j<IDELEMS(syzstr->res[i]);j++)
1872          {
1873            if (syzstr->res[i]->m[j]!=NULL)
1874              pDelete(&(syzstr->res[i]->m[j]));
1875          }
1876        }
1877        idDelete(&(syzstr->res[i]));
1878        Free((ADDRESS)syzstr->resPairs[i],(*syzstr->Tl)[i]*sizeof(SObject));
1879      }
1880      Free((ADDRESS)syzstr->resPairs,syzstr->length*sizeof(SObject*));
1881      Free((ADDRESS)syzstr->res,(syzstr->length+1)*sizeof(ideal));
1882      Free((ADDRESS)syzstr->orderedRes,(syzstr->length+1)*sizeof(ideal));
1883      Free((ADDRESS)syzstr->truecomponents,(syzstr->length+1)*sizeof(int*));
1884      Free((ADDRESS)syzstr->backcomponents,(syzstr->length+1)*sizeof(int*));
1885      Free((ADDRESS)syzstr->Howmuch,(syzstr->length+1)*sizeof(int*));
1886      Free((ADDRESS)syzstr->Firstelem,(syzstr->length+1)*sizeof(int*));
1887      Free((ADDRESS)syzstr->binom,pVariables*(syzstr->highdeg_1)*sizeof(int));
1888    }
1889    if (syzstr->minres!=NULL)
1890    {
1891      for (i=0;i<syzstr->length;i++)
1892      {
1893        if (syzstr->minres[i]!=NULL)
1894        {
1895          for (j=0;j<IDELEMS(syzstr->minres[i]);j++)
1896          {
1897            if (syzstr->minres[i]->m[j]!=NULL)
1898              pDelete(&(syzstr->minres[i]->m[j]));
1899          }
1900        }
1901        idDelete(&(syzstr->minres[i]));
1902      }
1903      Free((ADDRESS)syzstr->minres,(syzstr->length+1)*sizeof(ideal));
1904    }
1905    if (syzstr->fullres!=NULL)
1906    {
1907      for (i=0;i<syzstr->length;i++)
1908      {
1909        if (syzstr->fullres[i]!=NULL)
1910        {
1911          for (j=0;j<IDELEMS(syzstr->fullres[i]);j++)
1912          {
1913            if (syzstr->fullres[i]->m[j]!=NULL)
1914              pDelete(&(syzstr->fullres[i]->m[j]));
1915          }
1916        }
1917        idDelete(&(syzstr->fullres[i]));
1918      }
1919      Free((ADDRESS)syzstr->fullres,(syzstr->length+1)*sizeof(ideal));
1920    }
1921    if (syzstr->cw!=NULL)
1922      delete syzstr->cw;
1923    if (syzstr->resolution!=NULL)
1924      delete syzstr->resolution;
1925    Free((ADDRESS)syzstr,sizeof(ssyStrategy));
1926  }
1927}
1928
1929intvec * syBettiOfComputation(syStrategy syzstr)
1930{
1931  int dummy;
1932  if (syzstr->resPairs!=NULL)
1933  {
1934    int i,j=-1,jj=-1,l;
1935    SRes rP=syzstr->resPairs;
1936   
1937    l = syzstr->length;
1938    while ((l>0) && (rP[l-1]==NULL)) l--;
1939    if (l==0) return NULL;
1940    l--;
1941    while (l>=0)
1942    {
1943      i = 0;
1944      while ((i<(*syzstr->Tl)[l]) && 
1945        ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)))
1946      {
1947        if (rP[l][i].isNotMinimal==NULL) 
1948        {
1949          if (j<rP[l][i].order-l)
1950            j = rP[l][i].order-l;
1951          if (jj<l)
1952            jj = l;
1953        }
1954        i++;
1955      }
1956      l--;
1957    }
1958    jj=jj+2;
1959    intvec *result=new intvec(j,jj,0);
1960    IMATELEM(*result,1,1) = max(1,idRankFreeModule(syzstr->res[1]));
1961    for (i=0;i<jj;i++)
1962    {
1963      j = 0;
1964      while ((j<(*syzstr->Tl)[i]) && 
1965        ((rP[i][j].lcm!=NULL) || (rP[i][j].syz!=NULL)))
1966      {
1967        if (rP[i][j].isNotMinimal==NULL)
1968          IMATELEM(*result,rP[i][j].order-i,i+2)++;
1969        j++;
1970      }
1971    }
1972    return result;
1973  }
1974  else if (syzstr->fullres!=NULL)
1975    return syBetti(syzstr->fullres,syzstr->length,&dummy);
1976  else
1977    return syBetti(syzstr->minres,syzstr->length,&dummy);
1978}
1979
1980int syLength(syStrategy syzstr)
1981{
1982  return syzstr->length;
1983}
1984
1985int sySize(syStrategy syzstr)
1986{
1987  resolvente r=syzstr->res;
1988  if (r==NULL)
1989    r = syzstr->fullres;
1990  if (r==NULL)
1991    r = syzstr->minres;
1992  if (r==NULL)
1993  {
1994    WerrorS("No resolution found");
1995    return 0;
1996  }
1997  int i=syzstr->length;
1998  while ((i>0) && (r[i-1]==NULL)) i--;
1999  return i;
2000}
2001
2002int syDim(syStrategy syzstr)
2003{
2004  int i,j=-1,l;
2005  if (syzstr->resPairs!=NULL)
2006  {
2007    SRes rP=syzstr->resPairs;
2008   
2009    l = syzstr->length;
2010    while ((l>0) && (rP[l-1]==NULL)) l--;
2011    if (l==0) return -1;
2012    l--;
2013    while (l>=0)
2014    {
2015      i = 0;
2016      while ((i<(*syzstr->Tl)[l]) && 
2017        ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)) &&
2018        (rP[l][i].isNotMinimal!=NULL))
2019      {
2020        i++;
2021      }
2022      if ((i<(*syzstr->Tl)[l]) &&
2023        ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)) &&
2024        (rP[l][i].isNotMinimal==NULL))
2025        return l;
2026      l--;
2027    }
2028    return l;
2029  }
2030  else 
2031    return sySize(syzstr);
2032}
2033
2034syStrategy syCopy(syStrategy syzstr)
2035{
2036  syStrategy result=syzstr;
2037  (result->references)++;
2038  return result;
2039}
2040
2041static void syPrintEmptySpaces(int i)
2042{
2043  if (i!=0)
2044  {
2045    Print(" ");
2046    syPrintEmptySpaces(i/10);
2047  }
2048}
2049
2050static void syPrintEmptySpaces1(int i)
2051{
2052  if (i!=0)
2053  {
2054    Print(" ");
2055    syPrintEmptySpaces1(i-1);
2056  }
2057}
2058
2059static int syLengthInt(int i)
2060{
2061  int j=0;
2062
2063  if (i==0) return 1;
2064  while (i!=0)
2065  {
2066    j++;
2067    i = i/10;
2068  }
2069  return j;
2070}
2071
2072void syPrint(syStrategy syzstr)
2073{
2074  if ((syzstr->resPairs==NULL) && (syzstr->fullres==NULL) 
2075     && (syzstr->minres==NULL))
2076  {
2077    Print("No resolution defined\n");
2078    return;
2079  }
2080  int l=0;
2081  if (syzstr->resolution==NULL)
2082  {
2083    int j;
2084    if (syzstr->resPairs!=NULL)
2085    {
2086      syzstr->resolution = new intvec(syzstr->length+1);
2087      SRes rP=syzstr->resPairs;
2088      (*syzstr->resolution)[0] = max(1,idRankFreeModule(syzstr->res[1]));
2089      while ((l<syzstr->length) && (rP[l]!=NULL))
2090      {
2091        j=0;
2092        while ((j<(*syzstr->Tl)[l]) && 
2093          ((rP[l][j].lcm!=NULL) || (rP[l][j].syz!=NULL)))
2094        {
2095          if (rP[l][j].isNotMinimal==NULL)
2096            ((*syzstr->resolution)[l+1])++;
2097          j++;
2098        }
2099        l++;
2100      }
2101    }
2102    else
2103    {
2104      resolvente rr;
2105      syzstr->resolution = new intvec(syzstr->length+2);
2106      if (syzstr->minres!=NULL)
2107        rr = syzstr->minres;
2108      else
2109        rr = syzstr->fullres;
2110      (*syzstr->resolution)[0] = max(1,idRankFreeModule(rr[0]));
2111      while ((l<syzstr->length) && (rr[l]!=NULL))
2112      {
2113        j = IDELEMS(rr[l]);
2114        while ((l>0) && (rr[l]->m[j-1]==NULL)) j--;
2115        ((*syzstr->resolution)[l+1]) = j;
2116        l++;
2117      }
2118    }
2119  }
2120  char *sn=currRingHdl->id;
2121  int sl=strlen(sn);
2122  syPrintEmptySpaces1(sl);
2123  l = 0;
2124  loop
2125  {
2126    Print("%d",(*syzstr->resolution)[l]);
2127    if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0))
2128      break;
2129    syPrintEmptySpaces1(sl+5);
2130    l++;
2131  }
2132  PrintLn();
2133  l = 0;
2134  loop
2135  {
2136    Print(sn);
2137    if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0))
2138      break;
2139    syPrintEmptySpaces((*syzstr->resolution)[l]);
2140    Print(" <-- ");
2141    l++;
2142  }
2143  PrintLn();
2144  PrintLn();
2145  l = 0;
2146  loop
2147  {
2148    Print("%d",l);
2149    if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0))
2150      break;
2151    syPrintEmptySpaces1(sl+5+syLengthInt((*syzstr->resolution)[l])-
2152                         syLengthInt(l));
2153    l++;
2154  }
2155  PrintLn();
2156  if (syzstr->minres==NULL)
2157  {
2158    Print("resolution not minimized yet");
2159    PrintLn();
2160  }
2161}
2162
2163static resolvente syReorder(resolvente res,int length,
2164        syStrategy syzstr,BOOLEAN toCopy=TRUE,resolvente totake=NULL)
2165{
2166  int i,j,l;
2167  poly p,q,tq;
2168  polyset ri1;
2169  resolvente fullres;
2170  fullres = (resolvente)Alloc0((length+1)*sizeof(ideal));
2171  if (totake==NULL) 
2172    totake = res;
2173  for (i=length-1;i>0;i--)
2174  {
2175    if (res[i]!=NULL)
2176    {
2177      if (i>1)
2178      {
2179        j = IDELEMS(res[i-1]);
2180        while ((j>0) && (res[i-1]->m[j-1]==NULL)) j--;
2181        fullres[i-1] = idInit(IDELEMS(res[i]),j);
2182        ri1 = totake[i-1]->m;
2183        for (j=IDELEMS(res[i])-1;j>=0;j--)
2184        {
2185          p = res[i]->m[j];
2186          q = NULL;
2187          while (p!=NULL)
2188          {
2189            if (toCopy)
2190            {
2191              tq = pHead(p);
2192              pIter(p);
2193            }
2194            else
2195            {
2196              tq = p;
2197              pIter(p);
2198              pNext(tq) = NULL;
2199            }
2200            for (l=pVariables;l>0;l--)
2201              pSubExp(tq,l, pGetExp(ri1[pGetComp(tq)-1],l));
2202            pSetm(tq);
2203            q = pAdd(q,tq);
2204          }
2205          fullres[i-1]->m[j] = q;
2206        }
2207      }
2208      else
2209      {
2210        if (toCopy)
2211          fullres[i-1] = idCopy(res[i]);
2212        else
2213          fullres[i-1] = res[i];
2214        for (j=IDELEMS(res[i])-1;j>=0;j--)
2215          fullres[i-1]->m[j] = pOrdPolyInsertSetm(fullres[i-1]->m[j]);
2216      }
2217    }
2218  }
2219  if (!toCopy)
2220    Free((ADDRESS)res,(length+1)*sizeof(ideal));
2221  //syzstr->length = length;
2222  return fullres;
2223}
2224
2225lists syConvRes(syStrategy syzstr)
2226{
2227  if ((syzstr->fullres==NULL) && (syzstr->minres==NULL))
2228  {
2229    syzstr->fullres = syReorder(syzstr->res,syzstr->length,syzstr);
2230  }
2231  resolvente tr;
2232  int typ0=IDEAL_CMD;
2233  if (syzstr->minres!=NULL)
2234    tr = syzstr->minres;
2235  else
2236    tr = syzstr->fullres;
2237  resolvente trueres=NULL;
2238  if (syzstr->length>0)
2239  {
2240    trueres=(resolvente)Alloc0((syzstr->length)*sizeof(ideal));
2241    for (int i=(syzstr->length)-1;i>=0;i--)
2242    {
2243      if (tr[i]!=NULL)
2244      {
2245        trueres[i] = idCopy(tr[i]);
2246      }
2247    }
2248    if (idRankFreeModule(trueres[0])>0)
2249      typ0 = MODUL_CMD;
2250  }   
2251  return liMakeResolv(trueres,syzstr->length,-1,typ0,NULL);
2252}
2253
2254syStrategy syConvList(lists li)
2255{
2256  int typ0;
2257  syStrategy result=(syStrategy)Alloc0(sizeof(ssyStrategy));
2258
2259  resolvente fr = liFindRes(li,&(result->length),&typ0);
2260  result->fullres = (resolvente)Alloc0((result->length+1)*sizeof(ideal));
2261  for (int i=result->length-1;i>=0;i--)
2262  {
2263    if (fr[i]!=NULL)
2264      result->fullres[i] = idCopy(fr[i]);
2265  }
2266  Free((ADDRESS)fr,(result->length)*sizeof(ideal));
2267  return result;
2268}
2269
2270syStrategy syMakeResolution(resolvente r, int length, 
2271           intvec ** weights)
2272{
2273  syStrategy result=(syStrategy)Alloc0(sizeof(ssyStrategy));
2274
2275  length = max(length,0);
2276  int i=0;
2277 
2278  while (i<length)
2279  {
2280    if (r[i]!=NULL)
2281    {
2282      if (i!=0)
2283      {
2284        int rank=IDELEMS(r[i-1]);
2285        if (idIs0(r[i-1]))
2286        {
2287          idDelete(&(r[i]));
2288          r[i]=idFreeModule(rank);
2289        }
2290        else
2291        {
2292          r[i]->rank=max(rank,idRankFreeModule(r[i]));
2293        }
2294        idSkipZeroes(r[i]);
2295      }
2296    }
2297    else
2298    {
2299      // should not happen:
2300      Warn("internal NULL in resolvente");
2301      r[i]=idInit(1,1);
2302    }
2303    i++;
2304  }
2305  result->fullres = r;
2306  result->length = length;
2307  return result;
2308}
2309
2310syStrategy syForceMin(lists li)
2311{
2312  int typ0;
2313  syStrategy result=(syStrategy)Alloc0(sizeof(ssyStrategy));
2314
2315  resolvente fr = liFindRes(li,&(result->length),&typ0);
2316  result->minres = (resolvente)Alloc0((result->length+1)*sizeof(ideal));
2317  for (int i=result->length-1;i>=0;i--)
2318  {
2319    if (fr[i]!=NULL)
2320      result->minres[i] = idCopy(fr[i]);
2321  }
2322  Free((ADDRESS)fr,(result->length)*sizeof(ideal));
2323  return result;
2324}
2325
2326static poly syStripOut(poly p,intvec * toStrip)
2327{
2328  if (toStrip==NULL) return p;
2329  poly pp=p;
2330 
2331  while ((pp!=NULL) && ((*toStrip)[pGetComp(pp)]!=0))
2332    pDelete1(&pp);
2333  p = pp;
2334  if (pp!=NULL) 
2335  {
2336    while (pNext(pp)!=NULL)
2337    {
2338      if ((*toStrip)[pGetComp(pNext(pp))]!=0)
2339        pDelete1(&pNext(pp));
2340      else
2341        pIter(pp);
2342    }
2343  }
2344  return p;
2345}
2346
2347static poly syMinimizeP(poly toMin,syStrategy syzstr,int pNum,int index,
2348                        intvec * toStrip)
2349{
2350  int i,j,tc,lastin,newin=pNum-1;
2351  poly p,pp=pCopy(toMin),q=NULL,tq,pisN;
2352  SSet sPairs=syzstr->resPairs[index];
2353
2354  pp = syStripOut(pp,toStrip);
2355  while (newin>=0)
2356  {
2357    lastin = newin;
2358    while ((newin>=0) && (sPairs[lastin].order==sPairs[newin].order))
2359      newin--;
2360//Print("Hier lastin:%d newin:%d\n",lastin,newin);
2361    for (i=newin+1;i<=lastin;i++)
2362    {
2363      if (sPairs[i].isNotMinimal!=NULL)
2364      {
2365        pisN = sPairs[i].isNotMinimal;
2366        tc = pGetComp(pisN);
2367        p = pp;
2368        while (p!=NULL)
2369        {
2370          if (pGetComp(p)==tc)
2371          {
2372            tq = pInit();
2373            for(j=pVariables; j>0; j--)
2374              pSetExp(tq,j, pGetExp(p,j)-pGetExp(pisN,j));
2375            pSetComp(tq, 0);
2376            pSetCoeff0(tq,nDiv(pGetCoeff(p),pGetCoeff(pisN)));
2377            pGetCoeff(tq) = nNeg(pGetCoeff(tq));
2378            q = syAdd(q,syStripOut(syMultT1(syzstr->res[index+1]->m[sPairs[i].syzind],tq),toStrip));
2379          } 
2380          pIter(p);
2381        }
2382        if (q!=NULL)
2383        {
2384          pp = syAdd(pp,q);
2385          q = NULL;
2386        }
2387      }
2388    }
2389  }
2390  return pp;
2391}
2392
2393static void syKillEmptyEntres(resolvente res,int length)
2394{
2395  int i,j,jj,k,rj;
2396  intvec * changes;
2397  poly p;
2398  ideal ri;
2399
2400  for (i=0;i<length;i++)
2401  {
2402    ri = res[i];
2403    if (ri!=NULL)
2404    {
2405      rj = IDELEMS(ri);
2406      changes = new intvec(rj+1,1,-1);
2407      while ((rj>0) && (ri->m[rj-1]==NULL)) rj--;
2408      j = k = 0;
2409      while (j+k<rj)
2410      {
2411        if (ri->m[j+k]!=NULL)
2412        {
2413          ri->m[j] = ri->m[j+k];
2414          (*changes)[j+k+1] = j+1; 
2415          j++;
2416        }
2417        else
2418        {
2419          k++;
2420        }
2421      }
2422      for (jj=j;jj<rj;jj++)
2423        ri->m[jj] = NULL;
2424      if (res[i+1]!=NULL)
2425      {
2426        ri = res[i+1];
2427        for (j=IDELEMS(ri)-1;j>=0;j--)
2428        {
2429          p = ri->m[j];
2430          while (p!=NULL)
2431          {
2432            pSetComp(p,(*changes)[pGetComp(p)]);
2433            pIter(p);
2434          }
2435        }
2436      }
2437    }
2438  }
2439}
2440
2441static intvec * syToStrip(syStrategy syzstr, int index)
2442{
2443  intvec * result=NULL;
2444
2445  if ((syzstr->resPairs[index-1]!=NULL) && (!idIs0(syzstr->res[index])))
2446  {
2447    result=new intvec(IDELEMS(syzstr->res[index])+1);
2448    for (int i=(*syzstr->Tl)[index-1]-1;i>=0;i--)
2449    {
2450      if (syzstr->resPairs[index-1][i].isNotMinimal!=NULL)
2451      {
2452        (*result)[syzstr->resPairs[index-1][i].syzind+1] = 1;
2453      }
2454    }
2455  }
2456  return result;
2457}
2458
2459static resolvente syReadOutMinimalRes(syStrategy syzstr, 
2460           BOOLEAN computeStd=FALSE)
2461{
2462  intvec * Strip;
2463  resolvente tres=(resolvente)Alloc0((syzstr->length+1)*sizeof(ideal));
2464  if (computeStd)
2465  {
2466    tres[0] = syzstr->res[1];
2467    syzstr->res[1] = idInit(IDELEMS(tres[0]),tres[0]->rank);
2468    return tres;
2469  }
2470  int i,j,l,index,o1,ii,i1;
2471  poly p;
2472  ideal rs;
2473  SSet sPairs;
2474  int * ord,*b0,*b1;
2475  pSetmProc oldSetm=pSetm;
2476  pCompProc oldComp0=pComp0;
2477 
2478  if ((currRing->order[0]==ringorder_dp)
2479  &&  (currRing->order[1]==ringorder_C)
2480  &&  (currRing->order[2]==0))
2481  {
2482    ord=NULL;
2483  }
2484/*--- changes to a dpC-ring with special comp0------*/
2485  else
2486  {
2487    ord = (int*)Alloc0(3*sizeof(int));
2488    b0 = (int*)Alloc0(3*sizeof(int));
2489    b1 = (int*)Alloc0(3*sizeof(int));
2490    ord[0] = ringorder_dp;
2491    ord[1] = ringorder_C;
2492    b0[1] = 1;
2493    b1[0] = pVariables;
2494    pChangeRing(pVariables,1,ord,b0,b1,currRing->wvhdl);
2495  }
2496#if ! defined(HAVE_SY_VECTOR) || defined(SY_VEC_DEBUG) 
2497  pSetm =syzSetm;
2498#endif
2499  pComp0 = syzcomp2dpc;
2500  binomials = syzstr->binom;
2501  highdeg_1 = syzstr->highdeg_1;
2502  for (index=syzstr->length-1;index>0;index--)
2503  {
2504    if (syzstr->resPairs[index]!=NULL)
2505    {
2506      currcomponents = syzstr->truecomponents[index];
2507      sPairs = syzstr->resPairs[index];
2508      Strip = syToStrip(syzstr,index);
2509      tres[index+1] = idInit(IDELEMS(syzstr->res[index+1]),syzstr->res[index+1]->rank);
2510      i1 = (*syzstr->Tl)[index];
2511      for (i=0;i<i1;i++)
2512      {
2513        if ((sPairs[i].isNotMinimal==NULL) && (sPairs[i].lcm!=NULL))
2514        {
2515          o1 = sPairs[i].order;
2516          ii = i;
2517          while ((ii<i1) && (sPairs[ii].lcm!=NULL) && (sPairs[ii].order==o1))
2518            ii++;
2519          l = sPairs[i].syzind;
2520          tres[index+1]->m[l] =
2521            syMinimizeP(syzstr->res[index+1]->m[l],syzstr,ii,index,Strip);
2522        }
2523      }
2524      delete Strip;
2525      Strip = NULL;
2526    }
2527  }
2528  currcomponents = syzstr->truecomponents[0];
2529  tres[1] = idInit(IDELEMS(syzstr->res[1]),syzstr->res[1]->rank);
2530  sPairs = syzstr->resPairs[0];
2531  for (i=(*syzstr->Tl)[0]-1;i>=0;i--)
2532  {
2533    if (sPairs[i].syzind>=0)
2534    {
2535      tres[1]->m[sPairs[i].syzind] = pCopy(syzstr->res[1]->m[sPairs[i].syzind]);
2536    }
2537  }
2538/*--- changes to the original ring------------------*/
2539  if (ord!=NULL)
2540  {
2541    pChangeRing(pVariables,currRing->OrdSgn,currRing->order,
2542    currRing->block0,currRing->block1,currRing->wvhdl);
2543  }
2544  else
2545  {
2546    pSetm=oldSetm;
2547    pComp0=oldComp0;
2548  }
2549  tres = syReorder(tres,syzstr->length,syzstr,FALSE,syzstr->res);
2550  syKillEmptyEntres(tres,syzstr->length);
2551  idSkipZeroes(tres[0]);
2552  return tres;
2553}
2554
2555syStrategy syMinimize(syStrategy syzstr)
2556{
2557  if (syzstr->minres==NULL)
2558  {
2559    if (syzstr->resPairs!=NULL)
2560    {
2561      syzstr->minres = syReadOutMinimalRes(syzstr);
2562    }
2563    else if (syzstr->fullres!=NULL)
2564    {
2565      syMinimizeResolvente(syzstr->fullres,syzstr->length,1);
2566      syzstr->minres = syzstr->fullres;
2567      syzstr->fullres = NULL;
2568    }
2569  }
2570  (syzstr->references)++;
2571  return syzstr;
2572}
2573
2574static void sySetHighdeg()
2575{
2576  long long t=1, h_d=1;
2577  long long h_n=1+pVariables;
2578  while ((t=((t*h_n)/h_d))<INT_MAX)
2579  {
2580    h_d++;
2581    h_n++;
2582  }
2583  h_d--;
2584  highdeg = h_d;
2585  //Print("max deg=%d\n",highdeg);
2586}
2587
2588#if THROW_IT_AWAY_EVENTUALLY
2589/*2
2590* implementation of LaScala's algorithm
2591* assumes that the given module is homogeneous
2592* works with slanted degree, uses syChosePairs
2593*/
2594//syStrategy syLaScala1(ideal arg,int * length)
2595resolvente syLaScala1(ideal arg,int * length)
2596{
2597  BOOLEAN noPair=FALSE;
2598  int i,j,* ord,*b0,*b1,actdeg=32000,index=0,reg=-1;
2599  int startdeg,howmuch;
2600  poly p;
2601  ideal temp;
2602  SSet nextPairs;
2603  syStrategy syzstr=(syStrategy)Alloc0(sizeof(ssyStrategy));
2604  pSetmProc oldSetm=pSetm;
2605  pCompProc oldComp0=pComp0;
2606
2607  //crit = 0;
2608  //zeroRed = 0;
2609  //simple = 0;
2610  //dsim = 0;
2611  euler = -1;
2612  redpol = pInit();
2613  //orderingdepth = new intvec(pVariables+1);
2614  if (*length<=0) *length = pVariables+2;
2615  syzstr->length = *length;
2616  if (idIs0(arg)) return NULL;
2617  if ((currRing->order[0]==ringorder_dp)
2618  &&  (currRing->order[1]==ringorder_C)
2619  &&  (currRing->order[2]==0))
2620  {
2621    ord=NULL;
2622  } 
2623/*--- changes to a dpC-ring with special comp0------*/
2624  else
2625  {
2626    ord = (int*)Alloc0(3*sizeof(int));
2627    b0 = (int*)Alloc0(3*sizeof(int));
2628    b1 = (int*)Alloc0(3*sizeof(int));
2629    ord[0] = ringorder_dp;
2630    ord[1] = ringorder_C;
2631    b0[1] = 1;
2632    b1[0] = pVariables;
2633    pChangeRing(pVariables,1,ord,b0,b1,currRing->wvhdl);
2634  } 
2635/*--- initializes the data structures---------------*/
2636  syzstr->Tl = new intvec(*length);
2637  temp = idInit(IDELEMS(arg),arg->rank);
2638  for (i=0;i<IDELEMS(arg);i++)
2639  {
2640    temp->m[i] = pOrdPolyInsertSetm(pCopy(arg->m[i]));
2641    if (temp->m[i]!=NULL) 
2642    {
2643      j = pTotaldegree(temp->m[i]);
2644      if (j<actdeg) actdeg = j;
2645    }
2646  }
2647  sySetHighdeg();
2648  binomials = (int*)Alloc(pVariables*(highdeg+1)*sizeof(int));
2649  syBinomSet();
2650  pSetm =syzSetm;
2651  for (i=0;i<IDELEMS(arg);i++)
2652  {
2653    p = temp->m[i];
2654    while (p!=NULL)
2655    {
2656      pSetm(p);
2657      pIter(p);
2658    }
2659  }
2660  pComp0 = syzcomp2dpc;
2661  syzstr->resPairs = syInitRes(temp,length,syzstr->Tl);
2662  syzstr->res = (resolvente)Alloc0((*length+1)*sizeof(ideal));
2663  syzstr->orderedRes = (resolvente)Alloc0((*length+1)*sizeof(ideal));
2664  syzstr->truecomponents = (int**)Alloc0((*length+1)*sizeof(int*));
2665  syzstr->backcomponents = (int**)Alloc0((*length+1)*sizeof(int*));
2666  syzstr->Howmuch = (int**)Alloc0((*length+1)*sizeof(int*));
2667  syzstr->Firstelem = (int**)Alloc0((*length+1)*sizeof(int*));
2668  int len0=idRankFreeModule(arg)+1;
2669  syzstr->truecomponents[0] = (int*)Alloc(len0*sizeof(int));
2670  syzstr->backcomponents[0] = (int*)Alloc(len0*sizeof(int));
2671  syzstr->Howmuch[0] = (int*)Alloc(len0*sizeof(int));
2672  syzstr->Firstelem[0] = (int*)Alloc(len0*sizeof(int));
2673//Print("sort %d has now size %d\n",0,len0);
2674  for (i=0;i<len0;i++)
2675    syzstr->truecomponents[0][i] = i;
2676  startdeg = actdeg;
2677  nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2678  //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2679/*--- computes the resolution ----------------------*/ 
2680  while (nextPairs!=NULL)
2681  {
2682    if (TEST_OPT_PROT) Print("%d",actdeg);
2683    if (TEST_OPT_PROT) Print("(m%d)",index);
2684    currcomponents = syzstr->truecomponents[max(index-1,0)];
2685    i = syInitSyzMod(syzstr,index);
2686    j = syInitSyzMod(syzstr,index+1);
2687    if (index>0)
2688    {
2689      syRedNextPairs(nextPairs,syzstr,howmuch,index);
2690      syCompactifyPairSet(syzstr->resPairs[index],(*syzstr->Tl)[index],0);
2691    }
2692    else
2693      syRedGenerOfCurrDeg(syzstr,actdeg,index+1);
2694/*--- creates new pairs -----------------------------*/     
2695    syCreateNewPairs(syzstr,index,i);
2696    if (index<(*length)-1) 
2697    {
2698      syCreateNewPairs(syzstr,index+1,j);
2699      //currcomponents = syzstr->truecomponents[index];
2700      //sySyzTail(syzstr,index+1,j);
2701      //currcomponents = syzstr->truecomponents[index-1];
2702    }
2703    index++;
2704    nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2705    //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2706  }
2707  //return syzstr;
2708//}
2709/*--- deletes temporary data structures-------------*/
2710  idDelete(&temp);
2711  for (i=0;i<*length;i++)
2712  {
2713    for (j=0;j<(*syzstr->Tl)[i];j++)
2714    {
2715      if ((syzstr->resPairs[i])[j].lcm!=NULL)
2716        pDelete(&((syzstr->resPairs[i])[j].lcm));
2717    }
2718    if (syzstr->orderedRes[i]!=NULL)
2719    {
2720      for (j=0;j<IDELEMS(syzstr->orderedRes[i]);j++)
2721        syzstr->orderedRes[i]->m[j] = NULL;
2722    }
2723    idDelete(&(syzstr->orderedRes[i]));
2724    if (syzstr->truecomponents[i]!=NULL)
2725    {
2726      Free((ADDRESS)syzstr->truecomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
2727      syzstr->truecomponents[i]=NULL;
2728    }
2729    if (syzstr->backcomponents[i]!=NULL)
2730    {
2731      Free((ADDRESS)syzstr->backcomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
2732      syzstr->backcomponents[i]=NULL;
2733    }
2734    if (syzstr->Howmuch[i]!=NULL)
2735    {
2736      Free((ADDRESS)syzstr->Howmuch[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
2737      syzstr->Howmuch[i]=NULL;
2738    }
2739    if (syzstr->Firstelem[i]!=NULL)
2740    {
2741      Free((ADDRESS)syzstr->Firstelem[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
2742      syzstr->Firstelem[i]=NULL;
2743    }
2744    Free((ADDRESS)syzstr->resPairs[i],(*syzstr->Tl)[i]*sizeof(SObject));
2745  }
2746  Free((ADDRESS)syzstr->resPairs,*length*sizeof(SObject*));
2747  Free((ADDRESS)syzstr->orderedRes,(*length+1)*sizeof(ideal));
2748  Free((ADDRESS)syzstr->truecomponents,(*length+1)*sizeof(int*));
2749  Free((ADDRESS)syzstr->backcomponents,(*length+1)*sizeof(int*));
2750  Free((ADDRESS)syzstr->Howmuch,(*length+1)*sizeof(int*));
2751  Free((ADDRESS)syzstr->Firstelem,(*length+1)*sizeof(int*));
2752  syzstr->truecomponents = NULL;
2753  syzstr->backcomponents = NULL;
2754  syzstr->Howmuch = NULL;
2755  syzstr->Firstelem = NULL;
2756  if (BTEST1(6)) syStatistics(syzstr->res,(*length+1));
2757  (*length)++;
2758/*--- changes to the original ring------------------*/
2759  if (ord!=NULL)
2760  {
2761    pChangeRing(pVariables,currRing->OrdSgn,currRing->order,
2762    currRing->block0,currRing->block1,currRing->wvhdl);
2763  }
2764  else
2765  {
2766    pSetm=oldSetm;
2767    pComp0=oldComp0;
2768  }
2769  syReOrderResolventFB(syzstr->res,*length,2);
2770  for (i=0;i<*length-1;i++)
2771  {
2772    syzstr->res[i] = syzstr->res[i+1];
2773    if (syzstr->res[i]!=NULL)
2774    {
2775      polyset rsi = syzstr->res[i]->m;
2776      if (i>0)
2777      {
2778        for (j=IDELEMS(syzstr->res[i])-1;j>=0;j--)
2779        {
2780          rsi[j] = syOrdPolySchreyer(rsi[j]);
2781        }
2782      }
2783      else
2784      {
2785        if (ord!=NULL)
2786        {
2787          for (j=IDELEMS(syzstr->res[i])-1;j>=0;j--)
2788          {
2789            rsi[j] = pOrdPolyInsertSetm(rsi[j]);
2790          }
2791        }
2792        else
2793        {
2794          for (j=IDELEMS(syzstr->res[i])-1;j>=0;j--)
2795          {
2796            p = rsi[j];
2797            while (p!=NULL)
2798            {
2799              pSetm(p);
2800              pIter(p);
2801            }
2802          }
2803        }
2804      }
2805      idSkipZeroes(syzstr->res[i]);
2806    }
2807  }
2808  syzstr->res[*length-1] = NULL;
2809  if (ord!=NULL)
2810  {
2811    Free((ADDRESS)ord,3*sizeof(int));
2812    Free((ADDRESS)b0,3*sizeof(int));
2813    Free((ADDRESS)b1,3*sizeof(int));
2814  } 
2815  Free((ADDRESS)binomials,pVariables*(highdeg_1)*sizeof(int));
2816  pDelete1(&redpol);
2817  if (TEST_OPT_PROT) 
2818  {
2819    //Print("simple: %d\n",simple);
2820    //Print("dsim: %d\n",dsim);
2821    //Print("crit %d-times used \n",crit);
2822    //Print("%d reductions to zero \n",zeroRed);
2823  }
2824  //delete orderingdepth;
2825  if (TEST_OPT_PROT) PrintLn();
2826  return syzstr->res;
2827}
2828#endif
2829
2830/*2
2831* implementation of LaScala's algorithm
2832* assumes that the given module is homogeneous
2833* works with slanted degree, uses syChosePairs
2834*/
2835syStrategy syLaScala3(ideal arg,int * length)
2836{
2837  BOOLEAN noPair=FALSE;
2838  int i,j,* ord,*b0,*b1,actdeg=32000,index=0,reg=-1;
2839  int startdeg,howmuch;
2840  poly p;
2841  ideal temp;
2842  SSet nextPairs;
2843  syStrategy syzstr=(syStrategy)Alloc0(sizeof(ssyStrategy));
2844  if ((idIs0(arg)) || 
2845      ((idRankFreeModule(arg)>0) && (!idHomModule(arg,NULL,&(syzstr->cw)))))
2846  {
2847    syzstr->minres = (resolvente)Alloc0(sizeof(ideal));
2848    syzstr->length = 1;
2849    syzstr->minres[0] = idInit(1,arg->rank);
2850    return syzstr;
2851  }
2852  pSetmProc oldSetm=pSetm;
2853  pCompProc oldComp0=pComp0;
2854
2855  //crit = 0;
2856  //zeroRed = 0;
2857  //simple = 0;
2858  //dsim = 0;
2859  euler = -1;
2860  redpol = pInit();
2861  //orderingdepth = new intvec(pVariables+1);
2862  syzstr->length = *length = pVariables+2;
2863  if (idIs0(arg)) return NULL;
2864  if ((currRing->order[0]==ringorder_dp)
2865  &&  (currRing->order[1]==ringorder_C)
2866  &&  (currRing->order[2]==0))
2867  {
2868    ord=NULL;
2869  } 
2870/*--- changes to a dpC-ring with special comp0------*/
2871  else
2872  {
2873    ord = (int*)Alloc0(3*sizeof(int));
2874    b0 = (int*)Alloc0(3*sizeof(int));
2875    b1 = (int*)Alloc0(3*sizeof(int));
2876    ord[0] = ringorder_dp;
2877    ord[1] = ringorder_C;
2878    b0[1] = 1;
2879    b1[0] = pVariables;
2880    pChangeRing(pVariables,1,ord,b0,b1,currRing->wvhdl);
2881  } 
2882/*--- initializes the data structures---------------*/
2883  syzstr->Tl = new intvec(*length);
2884  temp = idInit(IDELEMS(arg),arg->rank);
2885  for (i=0;i<IDELEMS(arg);i++)
2886  {
2887    temp->m[i] = pOrdPolyInsertSetm(pCopy(arg->m[i]));
2888    if (temp->m[i]!=NULL) 
2889    {
2890      j = pTotaldegree(temp->m[i]);
2891      if (j<actdeg) actdeg = j;
2892    }
2893  }
2894  idTest(temp);
2895  idSkipZeroes(temp);
2896  idTest(temp);
2897  sySetHighdeg();
2898  binomials = (int*)Alloc(pVariables*(highdeg+1)*sizeof(int));
2899  syBinomSet();
2900#if ! defined(HAVE_SY_VECTOR) || defined(SY_VEC_DEBUG) 
2901  pSetm =syzSetm;
2902  for (i=0;i<IDELEMS(temp);i++)
2903  {
2904    p = temp->m[i];
2905    while (p!=NULL)
2906    {
2907      pSetm(p);
2908      pIter(p);
2909    }
2910  }
2911#else
2912  SetSpolyProc();
2913#endif
2914  pComp0 = syzcomp2dpc;
2915  currcomponents = (int*)Alloc0((arg->rank+1)*sizeof(int));
2916  for (i=0;i<=arg->rank;i++)
2917    currcomponents[i] = i;
2918  syzstr->resPairs = syInitRes(temp,length,syzstr->Tl,syzstr->cw);
2919  Free((ADDRESS)currcomponents,(arg->rank+1)*sizeof(int));
2920  syzstr->res = (resolvente)Alloc0((*length+1)*sizeof(ideal));
2921  syzstr->orderedRes = (resolvente)Alloc0((*length+1)*sizeof(ideal));
2922  syzstr->truecomponents = (int**)Alloc0((*length+1)*sizeof(int*));
2923  syzstr->backcomponents = (int**)Alloc0((*length+1)*sizeof(int*));
2924  syzstr->Howmuch = (int**)Alloc0((*length+1)*sizeof(int*));
2925  syzstr->Firstelem = (int**)Alloc0((*length+1)*sizeof(int*));
2926  int len0=idRankFreeModule(arg)+1;
2927  //syzstr->truecomponents[0] = (int*)Alloc(len0*sizeof(int));
2928  //syzstr->backcomponents[0] = (int*)Alloc(len0*sizeof(int));
2929  //syzstr->Howmuch[0] = (int*)Alloc(len0*sizeof(int));
2930  //syzstr->Firstelem[0] = (int*)Alloc(len0*sizeof(int));
2931//Print("sort %d has now size %d\n",0,len0);
2932  startdeg = actdeg;
2933  nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2934  //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2935/*--- computes the resolution ----------------------*/ 
2936  while (nextPairs!=NULL)
2937  {
2938    if (TEST_OPT_PROT) Print("%d",actdeg);
2939    if (TEST_OPT_PROT) Print("(m%d)",index);
2940    if (index==0)
2941      i = syInitSyzMod(syzstr,index,len0);
2942    else
2943      i = syInitSyzMod(syzstr,index);
2944    currcomponents = syzstr->truecomponents[max(index-1,0)];
2945    j = syInitSyzMod(syzstr,index+1);
2946    if (index>0)
2947    {
2948      syRedNextPairs(nextPairs,syzstr,howmuch,index);
2949      syCompactifyPairSet(syzstr->resPairs[index],(*syzstr->Tl)[index],0);
2950    }
2951    else
2952      syRedGenerOfCurrDeg(syzstr,actdeg,index+1);
2953/*--- creates new pairs -----------------------------*/     
2954    syCreateNewPairs(syzstr,index,i);
2955    if (index<(*length)-1) 
2956    {
2957      syCreateNewPairs(syzstr,index+1,j);
2958      //currcomponents = syzstr->truecomponents[index];
2959      //sySyzTail(syzstr,index+1,j);
2960      //currcomponents = syzstr->truecomponents[index-1];
2961    }
2962    index++;
2963    nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2964    //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2965  }
2966  if (temp!=NULL) idDelete(&temp);
2967  if (ord!=NULL)
2968  {
2969    pChangeRing(pVariables,currRing->OrdSgn,currRing->order,
2970    currRing->block0,currRing->block1,currRing->wvhdl);
2971  }
2972  else
2973  {
2974    pSetm=oldSetm;
2975    pComp0=oldComp0;
2976  }
2977  if (ord!=NULL)
2978  {
2979    Free((ADDRESS)ord,3*sizeof(int));
2980    Free((ADDRESS)b0,3*sizeof(int));
2981    Free((ADDRESS)b1,3*sizeof(int));
2982  } 
2983  syzstr->binom = binomials;
2984  syzstr->highdeg_1 = highdeg_1;
2985  pDelete1(&redpol);
2986  if (TEST_OPT_PROT) PrintLn();
2987  return syzstr;
2988}
2989/*2
2990* second implementation of LaScala's algorithm
2991* assumes that the given module is homogeneous
2992* works deg by deg, uses syChosePairs1
2993*/
2994/*
2995*resolvente syLaScala2(ideal arg,int * length)
2996*{
2997*  BOOLEAN noPair=FALSE;
2998*  int i,j,* ord,*b0,*b1,actdeg=32000,index=1,reg=-1;
2999*  int startdeg,howmuch;
3000*  intvec * Tl;
3001*  poly p;
3002*  ideal temp;
3003*  resolvente res,orderedRes;
3004*  SSet nextPairs;
3005*  SRes resPairs;
3006*
3007*  //crit = 0;
3008*  //zeroRed = 0;
3009*  //simple = 0;
3010*  //dsim = 0;
3011*  redpol = pNew();
3012*  //orderingdepth = new intvec(pVariables+1);
3013*  if (*length<=0) *length = pVariables+2;
3014*  if (idIs0(arg)) return NULL;
3015//--- changes to a dpC-ring with special comp0------
3016*  ord = (int*)Alloc0(3*sizeof(int));
3017*  b0 = (int*)Alloc0(3*sizeof(int));
3018*  b1 = (int*)Alloc0(3*sizeof(int));
3019*  ord[0] = ringorder_dp;
3020*  ord[1] = ringorder_C;
3021*  b0[1] = 1;
3022*  b1[0] = pVariables;
3023*  pChangeRing(pVariables,1,ord,b0,b1,currRing->wvhdl);
3024//--- initializes the data structures---------------
3025*  Tl = new intvec(*length);
3026*  temp = idInit(IDELEMS(arg),arg->rank);
3027*  for (i=0;i<IDELEMS(arg);i++)
3028*  {
3029*    temp->m[i] = pOrdPolyInsertSetm(pCopy(arg->m[i]));
3030*    if (temp->m[i]!=NULL)
3031*    {
3032*      j = pTotaldegree(temp->m[i]);
3033*      if (j<actdeg) actdeg = j;
3034*    }
3035*  }
3036*  {
3037*    highdeg=1;
3038*    long long t=1;
3039*    long long h_n=1+pVariables;
3040*    while ((t=(((long long)t*(long long)h_n)/(long long)highdeg))<INT_MAX)
3041*    {
3042*      highdeg++;
3043*      h_n++;
3044*    }
3045*    highdeg--;
3046*    Print("max deg=%d\n",highdeg);
3047*  } 
3048*  binomials = (int*)Alloc(pVariables*(highdeg+1)*sizeof(int));
3049*  syBinomSet();
3050*  pSetm =syzSetm;
3051*  for (i=0;i<IDELEMS(arg);i++)
3052*  {
3053*    p = temp->m[i];
3054*    while (p!=NULL)
3055*    {
3056*      pSetm(p);
3057*      pIter(p);
3058*    }
3059*  }
3060*  pComp0 = syzcomp2dpc;
3061*  resPairs = syInitRes(temp,length,Tl);
3062*  res = (resolvente)Alloc0((*length+1)*sizeof(ideal));
3063*  orderedRes = (resolvente)Alloc0((*length+1)*sizeof(ideal));
3064*  truecomponents = (int**)Alloc0((*length+1)*sizeof(int*));
3065*  backcomponents = (int**)Alloc0((*length+1)*sizeof(int*));
3066*  Howmuch = (int**)Alloc0((*length+1)*sizeof(int*));
3067*  Firstelem = (int**)Alloc0((*length+1)*sizeof(int*));
3068*  int len0=idRankFreeModule(arg)+1;
3069*  truecomponents[0] = (int*)Alloc(len0*sizeof(int));
3070*  backcomponents[0] = (int*)Alloc(len0*sizeof(int));
3071*  Howmuch[0] = (int*)Alloc(len0*sizeof(int));
3072*  Firstelem[0] = (int*)Alloc(len0*sizeof(int));
3073//Print("sort %d has now size %d\n",0,len0);
3074*  for (i=0;i<len0;i++)
3075*    truecomponents[0][i] = i;
3076*  startdeg = actdeg;
3077*  nextPairs = syChosePairs1(resPairs,Tl,&index,&howmuch,*length,&actdeg);
3078*  if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
3079//--- computes the resolution ----------------------
3080*  while (nextPairs!=NULL)
3081*  {
3082*    if (TEST_OPT_PROT) Print("%d",actdeg);
3083*    if (TEST_OPT_PROT) Print("(m%d)",index);
3084*    currcomponents = truecomponents[max(index-1,0)];
3085*    i = syInitSyzMod(res,orderedRes,index);
3086*    j = syInitSyzMod(res,orderedRes,index+1);
3087*    if (index>0)
3088*    {
3089*      syRedNextPairs(nextPairs,res,orderedRes,howmuch,index);
3090*      syCompactifyPairSet(resPairs[index],(*Tl)[index],0);
3091*    }
3092*    else
3093*      syRedGenerOfCurrDeg(resPairs,res,orderedRes,actdeg,index+1,Tl);
3094//--- creates new pairs -----------------------------     
3095*    syCreateNewPairs(resPairs,Tl,res,index,i);
3096*    if (index<(*length)-1)
3097*    {
3098*      syCreateNewPairs(resPairs,Tl,res,index+1,j);
3099*      currcomponents = truecomponents[index];
3100*      sySyzTail(resPairs,Tl,orderedRes,res,index+1,j);
3101*      currcomponents = truecomponents[index-1];
3102*    }
3103*    index--;
3104*    nextPairs = syChosePairs1(resPairs,Tl,&index,&howmuch,*length,&actdeg);
3105*    if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
3106*  }
3107//--- deletes temporary data structures-------------
3108*  idDelete(&temp);
3109*  for (i=0;i<*length;i++)
3110*  {
3111*    for (j=0;j<(*Tl)[i];j++)
3112*    {
3113*      if ((resPairs[i])[j].lcm!=NULL)
3114*        pDelete(&(resPairs[i])[j].lcm);
3115*    }
3116*    if (orderedRes[i]!=NULL)
3117*    {
3118*      for (j=0;j<IDELEMS(orderedRes[i]);j++)
3119*        orderedRes[i]->m[j] = NULL;
3120*    }
3121*    idDelete(&orderedRes[i]);
3122*    if (truecomponents[i]!=NULL)
3123*    {
3124*      Free((ADDRESS)truecomponents[i],(IDELEMS(res[i])+1)*sizeof(int));
3125*      truecomponents[i]=NULL;
3126*    }
3127*    if (backcomponents[i]!=NULL)
3128*    {
3129*      Free((ADDRESS)backcomponents[i],(IDELEMS(res[i])+1)*sizeof(int));
3130*      backcomponents[i]=NULL;
3131*    }
3132*    if (Howmuch[i]!=NULL)
3133*    {
3134*      Free((ADDRESS)Howmuch[i],(IDELEMS(res[i])+1)*sizeof(int));
3135*      Howmuch[i]=NULL;
3136*    }
3137*    if (Firstelem[i]!=NULL)
3138*    {
3139*      Free((ADDRESS)Firstelem[i],(IDELEMS(res[i])+1)*sizeof(int));
3140*      Firstelem[i]=NULL;
3141*    }
3142*    Free((ADDRESS)resPairs[i],(*Tl)[i]*sizeof(SObject));
3143*  }
3144*  Free((ADDRESS)resPairs,*length*sizeof(SObject*));
3145*  Free((ADDRESS)orderedRes,(*length+1)*sizeof(ideal));
3146*  Free((ADDRESS)truecomponents,(*length+1)*sizeof(int*));
3147*  Free((ADDRESS)backcomponents,(*length+1)*sizeof(int*));
3148*  Free((ADDRESS)Howmuch,(*length+1)*sizeof(int*));
3149*  Free((ADDRESS)Firstelem,(*length+1)*sizeof(int*));
3150*  truecomponents = NULL;
3151*  backcomponents = NULL;
3152*  Howmuch = NULL;
3153*  Firstelem = NULL;
3154*  if (BTEST1(6)) syStatistics(res,(*length+1));
3155*  (*length)++;
3156//--- changes to the original ring------------------
3157*  pChangeRing(pVariables,currRing->OrdSgn,currRing->order,
3158*    currRing->block0,currRing->block1,currRing->wvhdl);
3159*  syReOrderResolventFB(res,*length,2);
3160*  for (i=0;i<*length-1;i++)
3161*  {
3162*    res[i] = res[i+1];
3163*    if (res[i]!=NULL)
3164*    {
3165*      if (i>0)
3166*      {
3167*        for (j=0;j<IDELEMS(res[i]);j++)
3168*        {
3169*          res[i]->m[j] = syOrdPolySchreyer(res[i]->m[j]);
3170*        }
3171*        idSkipZeroes(res[i]);
3172*      }
3173*      else
3174*      {
3175*        for (j=0;j<IDELEMS(res[i]);j++)
3176*        {
3177*          p = res[i]->m[j];
3178*          while (p!=NULL)
3179*          {
3180*            pSetm(p);
3181*            pIter(p);
3182*          }
3183*        }
3184*      }
3185*    }
3186*  }
3187*  res[*length-1] = NULL;
3188*  Free((ADDRESS)ord,3*sizeof(int));
3189*  Free((ADDRESS)b0,3*sizeof(int));
3190*  Free((ADDRESS)b1,3*sizeof(int));
3191*  Free((ADDRESS)binomials,pVariables*(highdeg_1)*sizeof(int));
3192*  pDelete1(&redpol);
3193*  if (TEST_OPT_PROT)
3194*  {
3195*    //Print("simple: %d\n",simple);
3196*    //Print("dsim: %d\n",dsim);
3197*    //Print("crit %d-times used \n",crit);
3198*    //Print("%d reductions to zero \n",zeroRed);
3199*  }
3200*  //delete orderingdepth;
3201*  return res;
3202*}
3203*/
Note: See TracBrowser for help on using the repository browser.