source: git/Singular/syz3.cc @ 512a2b

spielwiese
Last change on this file since 512a2b was 512a2b, checked in by Olaf Bachmann <obachman@…>, 24 years ago
p_polys.h git-svn-id: file:///usr/local/Singular/svn/trunk@4606 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 60.4 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: syz3.cc,v 1.5 2000-09-18 09:19:37 obachman Exp $ */
5/*
6* ABSTRACT: resolutions
7*/
8 
9#include <limits.h>
10#include "mod2.h"
11#include "tok.h"
12#include "attrib.h"
13#include "omalloc.h"
14#include "polys.h"
15#include "febase.h"
16#include "kstd1.h"
17#include "kutil.h"
18#include "stairc.h"
19#include "ipid.h"
20#include "cntrlc.h"
21#include "ipid.h"
22#include "intvec.h"
23#include "ipshell.h"
24#include "limits.h"
25#include "numbers.h"
26#include "modulop.h"
27#include "ideals.h"
28#include "intvec.h"
29#include "ring.h"
30#include "lists.h"
31#include "syz.h"
32#include "kbuckets.h"
33#include "prCopy.h"
34#include "timer.h"
35#include "matpol.h"
36 
37//#define SHOW_PROT
38//#define SHOW_RED
39//#define SHOW_Kosz
40//#define SHOW_RESULT
41//#define INVERT_PAIRS
42//#define ONLY_STD
43//#define EXPERIMENT1    //Hier stimmt was mit der Anzahl der Erzeuger in xyz11 nicht!!
44#define EXPERIMENT2
45#define EXPERIMENT3
46#define WITH_BUCKET     //Use of buckets in EXPERIMENT3 (Product criterion)
47#define WITH_SCHREYER_ORD
48#define USE_CHAINCRIT
49#define USE_CHAINCRIT0
50#define USE_PROD_CRIT
51#define USE_REGULARITY
52#define WITH_SORT
53//#define FULL_TOTAKE
54int discard_pairs;
55int short_pairs;
56 
57/*3
58* assumes the ideals old_ideal and new_ideal to be homogeneous
59* tests wether the new_ideal is a regular extension of the old_ideal
60*/
61static BOOLEAN syIsRegular(ideal old_ideal,ideal new_ideal,int deg)
62{
63  intvec * old_hilbs=hHstdSeries(old_ideal,NULL,NULL,NULL);
64  intvec * new_hilbs=hHstdSeries(new_ideal,NULL,NULL,NULL);
65  int biggest_length=max(old_hilbs->length()+deg,new_hilbs->length());
66  intvec * shifted_old_hilbs=new intvec(biggest_length);
67  intvec * old_hilb1=new intvec(biggest_length);
68  intvec * new_hilb1=new intvec(biggest_length);
69  int i;
70  BOOLEAN isRegular=TRUE;
71 
72  for (i=old_hilbs->length()+deg-1;i>=deg;i--)
73    (*shifted_old_hilbs)[i] = (*old_hilbs)[i-deg];
74  for (i=old_hilbs->length()-1;i>=0;i--)
75    (*old_hilb1)[i] = (*old_hilbs)[i]-(*shifted_old_hilbs)[i];
76  for (i=old_hilbs->length()+deg-1;i>=old_hilbs->length();i--)
77    (*old_hilb1)[i] = -(*shifted_old_hilbs)[i];
78  for (i=new_hilbs->length()-1;i>=0;i--)
79    (*new_hilb1)[i] = (*new_hilbs)[i];
80  i = 0;
81  while ((i<biggest_length) && isRegular)
82  {
83    isRegular = isRegular && ((*old_hilb1)[i] == (*new_hilb1)[i]);
84    i++;
85  }
86  delete old_hilbs;
87  delete new_hilbs;
88  delete old_hilb1;
89  delete new_hilb1;
90  delete shifted_old_hilbs;
91  return isRegular;
92}
93 
94/*3
95* shows the resolution stored in syzstr->orderedRes
96*/
97static void syShowRes(syStrategy syzstr)
98{
99  int i=0;
100 
101  while ((i<syzstr->length) && (!idIs0(syzstr->res[i])))
102  {
103    Print("aktueller hoechster index ist: %d\n",(*syzstr->Tl)[i]);
104    Print("der %d-te modul ist:\n",i);
105    idPrint(syzstr->res[i]);
106    Print("Seine Darstellung:\n");
107    idPrint(syzstr->orderedRes[i]);
108    i++;
109  }
110}
111 
112/*3
113* produces the next subresolution for a regular extension
114*/
115static void syCreateRegularExtension(syStrategy syzstr,ideal old_ideal,
116            ideal old_repr,int old_tl, poly next_generator,resolvente totake)
117{
118  int index=syzstr->length-1,i,j,start,start_ttk,new_tl;
119  poly gen=pCopy(next_generator),p;
120  poly neg_gen=pCopy(next_generator);
121  ideal current_ideal,current_repr;
122  int current_tl;
123  poly w_gen=pHead(next_generator);
124  pSetComp(w_gen,0);
125  pSetmComp(w_gen);
126 
127  //syShowRes(syzstr);
128  neg_gen = pNeg(neg_gen);
129  if (pGetComp(gen)>0)
130  {
131    pShift(&gen,-1);
132    pShift(&neg_gen,-1);
133  }
134  while (index>0) 
135  {
136    if (index%2==0)
137      p = gen;
138    else
139      p = neg_gen;
140    if (index>1)
141    {
142      current_ideal = syzstr->res[index-1];
143      current_repr = syzstr->orderedRes[index-1];
144      current_tl = (*syzstr->Tl)[index-1];
145    }
146    else
147    {
148      current_ideal = old_ideal;
149      current_repr = old_repr;
150      current_tl = old_tl;
151    }
152    if (!idIs0(current_ideal))
153    {
154      if (idIs0(syzstr->res[index]))
155      {
156        syzstr->res[index] = idInit(IDELEMS(current_ideal),
157          current_ideal->rank+current_tl);
158        syzstr->orderedRes[index] = idInit(IDELEMS(current_ideal),
159          current_ideal->rank);
160        start = 0;
161      }
162      else
163      {
164        start = IDELEMS(syzstr->res[index]);
165        while ((start>0) && (syzstr->res[index]->m[start-1]==NULL)) start--;
166        if (IDELEMS(syzstr->res[index])<start+IDELEMS(current_ideal))
167        {
168          pEnlargeSet(&syzstr->res[index]->m,IDELEMS(syzstr->res[index]),
169                   IDELEMS(current_ideal));
170          IDELEMS(syzstr->res[index]) += IDELEMS(current_ideal);
171          pEnlargeSet(&syzstr->orderedRes[index]->m,IDELEMS(syzstr->orderedRes[index]),
172                   IDELEMS(current_ideal));
173          IDELEMS(syzstr->orderedRes[index]) += IDELEMS(current_ideal);
174        }
175      }
176      if (idIs0(totake[index]))
177      {
178        totake[index] = idInit(IDELEMS(current_ideal),
179          current_ideal->rank+current_tl);
180        start_ttk = 0;
181      }
182      else
183      {
184        start_ttk = IDELEMS(totake[index]);
185        while ((start_ttk>0) && (totake[index]->m[start_ttk-1]==NULL)) start_ttk--;
186        if (IDELEMS(totake[index])<start_ttk+IDELEMS(current_ideal))
187        {
188          pEnlargeSet(&totake[index]->m,IDELEMS(totake[index]),
189                   IDELEMS(current_ideal));
190          for (j=IDELEMS(totake[index]);j<IDELEMS(totake[index])+
191                                  IDELEMS(current_ideal);j++)
192            totake[index]->m[j] = NULL;
193          IDELEMS(totake[index]) += IDELEMS(current_ideal);
194        }
195      }
196      for (i=0;i<IDELEMS(current_ideal);i++)
197      {
198        if (current_ideal->m[i]!=NULL)
199        {
200          syzstr->res[index]->m[i+start] = pCopy(current_ideal->m[i]);
201          syzstr->res[index]->m[i+start] = pMult_mm(syzstr->res[index]->m[i+start],w_gen);
202          pShift(&syzstr->res[index]->m[i+start],current_tl);
203          syzstr->res[index]->m[i+start] = pAdd(syzstr->res[index]->m[i+start],
204            ppMult_qq(current_repr->m[i],p));
205          syzstr->orderedRes[index]->m[i+start] = pCopy(current_repr->m[i]);
206          syzstr->orderedRes[index]->m[i+start] = 
207            pMult_mm(syzstr->orderedRes[index]->m[i+start],w_gen);
208          if ((*syzstr->Tl)[index]!=0)
209            pShift(&syzstr->orderedRes[index]->m[i+start],(*syzstr->Tl)[index]);
210        }
211      }
212      for (i=0;i<IDELEMS(totake[index-1]);i++)
213      {
214        if (totake[index-1]->m[i]!=NULL)
215        {
216          if ((index==1) && ((i==IDELEMS(current_ideal) ||
217               (totake[index-1]->m[i+1]==NULL)))) break;
218          totake[index]->m[i+start_ttk] = 
219            pMult_mm(pCopy(totake[index-1]->m[i]),w_gen);
220          pShift(&totake[index]->m[i+start_ttk],current_tl);
221#ifdef FULL_TOTAKE
222          poly pp=pCopy(p);
223          pShift(&pp,i+1);
224          totake[index]->m[i+start_ttk] = pAdd(totake[index]->m[i+start_ttk],pp);
225#endif
226        }
227      }
228      (*syzstr->Tl)[index] += current_tl;
229    }
230    index--;
231  }
232  pDelete(&gen);
233  pDelete(&neg_gen);
234  pDelete(&w_gen);
235  //syShowRes(syzstr);
236}
237 
238/*3
239* proves the consistence of the pairset resPairs with the corresponding
240* set of generators;
241* only for tests
242*/
243static void syTestPairs(SSet resPairs,int length,ideal old_generators)
244{
245  int i=0;
246 
247  while (i<length) 
248  {
249    if (resPairs[i].lcm!=NULL)
250    {
251      if (resPairs[i].p1!=NULL)
252        assume(resPairs[i].p1==old_generators->m[resPairs[i].ind1]);
253      if (resPairs[i].p2!=NULL)
254        assume(resPairs[i].p2==old_generators->m[resPairs[i].ind2]);
255    }
256    i++;
257  }
258}
259 
260/*3
261* cancels the weight monomials given by the leading terms of totake
262* from the resolution res;
263* works in place on res, but reads only from totake
264*/
265void syReorder_Kosz(syStrategy syzstr)
266{
267  int length=syzstr->length;
268  int syzIndex=length-1,i,j;
269  resolvente res=syzstr->fullres;
270  poly p;
271 
272  while ((syzIndex!=0) && (res[syzIndex]==NULL)) syzIndex--;
273  while (syzIndex>0)
274  {
275    for(i=0;i<IDELEMS(res[syzIndex]);i++)
276    {
277#ifdef USE_REGULARITY
278      if ((syzstr->regularity>0) && (res[syzIndex]->m[i]!=NULL))
279      {
280        if (pFDeg(res[syzIndex]->m[i])>=syzstr->regularity+syzIndex)
281          pDelete(&res[syzIndex]->m[i]);
282      }
283#endif
284      p = res[syzIndex]->m[i];
285      while (p!=NULL)
286      {
287        if (res[syzIndex-1]->m[pGetComp(p)-1]!=NULL)
288        {
289          for(j=1;j<=pVariables;j++)
290          {
291            pSetExp(p,j,pGetExp(p,j)
292                        -pGetExp(res[syzIndex-1]->m[pGetComp(p)-1],j));
293          }
294        }
295        else
296          PrintS("error in the resolvent\n");
297        pSetm(p);
298        pIter(p);
299      }
300    }
301    syzIndex--;
302  }
303}
304 
305/*3
306* updates the pairset resPairs by generating all pairs including the
307* new_generators in the 0-th modul;
308* the new_generators are inserted in the old_generators;
309* new_generators is empty after the procedure;
310*/
311static void updatePairs(SSet *resPairs,int *l_pairs,syStrategy syzstr,
312       int index,ideal new_generators,ideal new_repr,int crit_comp)
313{
314  if (idIs0(new_generators)) return;
315  ideal old_generators=syzstr->res[index];
316  ideal old_repr=syzstr->orderedRes[index];
317  int i=0,j,k,kk,og_elem=0,og_idel=IDELEMS(old_generators),l=*l_pairs,jj,ll,j1;
318  int og_ini=0;
319  ideal pairs=idInit(og_idel+IDELEMS(new_generators),old_generators->rank);
320  polyset prs=pairs->m;
321  poly p=NULL;
322  SObject tso;
323 
324  syInitializePair(&tso);
325  while ((og_elem<og_idel) && (old_generators->m[og_elem]!=NULL)) 
326  {
327    if ((index>0) && (pGetComp(old_generators->m[og_elem])<=crit_comp))
328      og_ini = og_elem;
329    og_elem++;
330  }
331  while ((l>0) && ((*resPairs)[l-1].lcm==NULL)) l--;
332  while ((i<IDELEMS(new_generators)) && (new_generators->m[i]!=NULL))
333  {
334    syTestPairs(*resPairs,*l_pairs,old_generators);
335    if (IDELEMS(old_generators)==og_elem)
336    {
337      pEnlargeSet(&old_generators->m,IDELEMS(old_generators),16);
338      IDELEMS(old_generators) += 16;
339      pEnlargeSet(&old_repr->m,IDELEMS(old_repr),16);
340      IDELEMS(old_repr) += 16;
341    }
342    k = pFDeg(new_generators->m[i]);
343    kk = pGetComp(new_generators->m[i]);
344    j = og_ini;
345    while ((j<og_elem) && (old_generators->m[j]!=NULL) &&
346           (pGetComp(old_generators->m[j])<kk)) j++;
347    while ((j<og_elem) && (old_generators->m[j]!=NULL) &&
348           (pFDeg(old_generators->m[j])<=k)) j++;
349    for (jj=og_elem;jj>j;jj--)
350    {
351      old_generators->m[jj] = old_generators->m[jj-1];
352      old_repr->m[jj] = old_repr->m[jj-1];
353    }
354    old_generators->m[j] = new_generators->m[i];
355    new_generators->m[i] = NULL;
356    old_repr->m[j] = new_repr->m[i];
357    new_repr->m[i] = NULL;
358    og_elem++;
359    for (jj=0;jj<*l_pairs;jj++)
360    {
361      if ((*resPairs)[jj].lcm!=NULL)
362      {
363        if ((*resPairs)[jj].ind1>=j) (*resPairs)[jj].ind1++;
364        if ((*resPairs)[jj].ind2>=j) (*resPairs)[jj].ind2++;
365      }
366    }
367    syTestPairs(*resPairs,*l_pairs,old_generators);
368    for (jj=og_ini;jj<og_elem;jj++)
369    {
370      if ((j!=jj) && (pGetComp(old_generators->m[jj])==pGetComp(old_generators->m[j])))
371      {
372        p = pOne();
373        pLcm(old_generators->m[jj],old_generators->m[j],p);
374        pSetComp(p,j+1);
375        pSetm(p);
376        j1 = 0;
377        while (j1<jj)
378        {
379          if (prs[j1]!=NULL)
380          {
381            if (pLmDivisibleByNoComp(prs[j1],p))
382            {
383              pDelete(&p);
384              break;
385            }
386            else if (pLmDivisibleByNoComp(p,prs[j1]))
387            {
388              pDelete(&(prs[j1]));
389            }
390#ifdef USE_CHAINCRIT0
391            else
392            {
393              poly p1,p2;
394              int ip=pVariables;
395              p1 = pDivide(p,old_generators->m[jj]);
396              p2 = pDivide(prs[j1],old_generators->m[j1]);
397              while ((ip>0) && (pGetExp(p1,ip)*pGetExp(p2,ip)==0)) ip--;
398              if (ip==0)
399              {
400                int ti=0;
401                while ((ti<l) && (((*resPairs)[ti].ind1!=j1)|| ((*resPairs)[ti].ind2!=jj))) ti++;
402                if (ti<l) 
403                {
404                  if (TEST_OPT_PROT) Print("cc");
405                  syDeletePair(&(*resPairs)[ti]);
406                  syCompactifyPairSet(*resPairs,*l_pairs,ti);
407                  l--;
408                }
409              }
410              pDelete(&p1);
411              pDelete(&p2);
412            }
413#endif
414          }
415          j1++;
416        }
417        if (p!=NULL)
418          prs[jj] = p;
419      }
420    }
421    for (jj=og_ini;jj<og_elem;jj++)
422    {
423      if (prs[jj] !=NULL)
424      {
425        if (l>=*l_pairs)
426        {
427          SSet temp = (SSet)omAlloc0((*l_pairs+16)*sizeof(SObject));
428          for (ll=0;ll<*l_pairs;ll++)
429          {
430            temp[ll].p = (*resPairs)[ll].p;
431            temp[ll].p1 = (*resPairs)[ll].p1;
432            temp[ll].p2 = (*resPairs)[ll].p2;
433            temp[ll].syz = (*resPairs)[ll].syz;
434            temp[ll].lcm = (*resPairs)[ll].lcm;
435            temp[ll].ind1 = (*resPairs)[ll].ind1;
436            temp[ll].ind2 = (*resPairs)[ll].ind2;
437            temp[ll].syzind = (*resPairs)[ll].syzind;
438            temp[ll].order = (*resPairs)[ll].order;
439            temp[ll].isNotMinimal = (*resPairs)[ll].isNotMinimal;
440          }
441          omFreeSize((ADDRESS)(*resPairs),*l_pairs*sizeof(SObject));
442          *l_pairs += 16;
443          (*resPairs) = temp;
444        }
445        tso.lcm = prs[jj];
446        prs[jj] = NULL;
447        tso.order = pFDeg(tso.lcm);
448        tso.p1 = old_generators->m[jj];
449        tso.p2 = old_generators->m[j];
450        tso.ind1 = jj;
451        tso.ind2 = j;
452        tso.syzind = -1;
453        tso.isNotMinimal = NULL;
454        tso.p = NULL;
455        tso.syz = NULL;
456        SSet rP=*resPairs;
457#ifdef SHOW_PROT
458Print("erzeuge Paar im Modul %d,%d mit: \n",index,tso.order);
459Print("poly1: ");pWrite(tso.p1);
460Print("poly2: ");pWrite(tso.p2);
461Print("syz: ");pWrite(tso.syz);
462Print("sPoly: ");pWrite(tso.p);
463PrintLn();
464#endif
465        syEnterPair(rP,&tso,&l,index);
466        syInitializePair(&tso);
467      }
468    }
469    i++;
470  }
471  idDelete(&pairs);
472}
473 
474/*3
475* performs the modification of a single reduction on the syzygy-level
476*/
477inline void sySPRedSyz_Kosz(syStrategy syzstr,poly redWith,poly syz,poly q=NULL,int l_syz=-1)
478{
479  poly p=pDivide(q,redWith);
480  pSetCoeff(p,nDiv(pGetCoeff(q),pGetCoeff(redWith)));
481  kBucket_Minus_m_Mult_p(syzstr->syz_bucket,p,syz,&l_syz,NULL);
482  pDelete(&p);
483}
484 
485/*3
486* normalizes the poly bucket by the ideal;
487* stops the reduction whenever the leading component is less than the
488* crit_comp;
489* returns the changing status
490*/
491static BOOLEAN syRedSyz(kBucket_pt bucket,ideal red,int crit_comp,int* g_l)
492{
493  poly p = kBucketGetLm(bucket);
494  int j = 0,i=IDELEMS(red)-1;
495  number n;
496  BOOLEAN isChanged=FALSE;
497 
498  loop
499  {
500    if ((j>=i) || (p==NULL) || (pGetComp(p)<=crit_comp)) break;
501    if ((red->m[j]!=NULL) && (pDivisibleBy(red->m[j],p)))
502    {
503      n = kBucketPolyRed(bucket,red->m[j], g_l[j], NULL);
504      nDelete(&n);
505      p = kBucketGetLm(bucket);
506      isChanged = TRUE;
507      j = 0;
508    }
509    else
510      j++;
511  }
512  return isChanged;
513}
514 
515/*3
516* a tail reduction for the syzygies yielding new generators
517*/
518static poly syRedTailSyz(poly tored,ideal red,ideal sec_red,int crit_comp,syStrategy syzstr,
519            int * gen_length,int * secgen_length,int * tored_length)
520{
521  int i=IDELEMS(red)-1,num_mon,num_tail;
522  poly h,hn;
523  BOOLEAN dummy;
524 
525  while ((i>0) && (red->m[i-1]==NULL)) i--;
526  i--;
527  h = tored;
528  if ((h!=NULL) && (pGetComp(h)>crit_comp))
529  {
530    num_mon = 1;
531    hn = pNext(h);
532    num_tail = *tored_length-1;
533    while (hn!=NULL)
534    {
535      kBucketInit(syzstr->syz_bucket,hn,num_tail);
536      dummy = syRedSyz(syzstr->syz_bucket,red,crit_comp,gen_length);
537      kBucketClear(syzstr->syz_bucket,&hn,&num_tail);
538      pNext(h) = hn;
539      if ((hn==NULL) || (pGetComp(hn)<=crit_comp))
540        break;
541      else
542      {
543        pIter(h);
544        pIter(hn);
545        num_mon++;
546        num_tail--;
547      }
548    }
549    if (sec_red!=NULL)
550    {
551      while (hn!=NULL)
552      {
553        kBucketInit(syzstr->syz_bucket,hn,num_tail);
554        dummy = syRedSyz(syzstr->syz_bucket,sec_red,crit_comp,secgen_length);
555        kBucketClear(syzstr->syz_bucket,&hn,&num_tail);
556        pNext(h) = hn;
557        if (hn==NULL)
558          break;
559        else
560        {
561          pIter(h);
562          pIter(hn);
563          num_mon++;
564          num_tail--;
565        }
566      }
567    }
568    *tored_length = num_mon+num_tail;
569  }
570  assume(pLength(tored)==*tored_length);
571  return tored;
572}
573 
574/*3
575* the complete reduction of a single pair which is just stored
576* in bucket and syz_bucket
577*/
578static BOOLEAN syRedSyzPair(syStrategy syzstr,int index,int* g_l,int* orp_l)
579{
580  kBucket_pt bucket=syzstr->bucket;
581  poly p = kBucketGetLm(bucket);
582  ideal red=syzstr->res[index],repr=syzstr->orderedRes[index];
583  int j = 0,i=IDELEMS(red)-1;
584  number n;
585  BOOLEAN isChanged=FALSE;
586 
587  loop
588  {
589    if ((j>=i) || (p==NULL)) break;
590    if ((red->m[j]!=NULL) && (pDivisibleBy(red->m[j],p)))
591    {
592      sySPRedSyz_Kosz(syzstr,red->m[j],repr->m[j],p,orp_l[j]);
593      n = kBucketPolyRed(bucket,red->m[j], g_l[j], NULL);
594      nDelete(&n);
595      p = kBucketGetLm(bucket);
596      isChanged = TRUE;
597      j = 0;
598    }
599    else
600      j++;
601  }
602  return isChanged;
603}
604 
605/*3
606* the tailreduction for generators (which includes the correction of
607* the corresponding representation)
608*/
609static void syRedTailSyzPair(SObject tso,syStrategy syzstr,int index,
610            int * gen_length,int* orp_l,int * tored_l,int * syzred_l)
611{
612  int num_mon,num_tail,syz_l;
613  poly h,hn;
614  BOOLEAN dummy;
615 
616  h = tso.p;
617  kBucketInit(syzstr->syz_bucket,tso.syz,*syzred_l);
618  if (h!=NULL)
619  {
620    num_mon = 1;
621    hn = pNext(h);
622    num_tail = *tored_l-1;
623    while (hn!=NULL)
624    {
625      kBucketInit(syzstr->bucket,hn,num_tail);
626      dummy = syRedSyzPair(syzstr,index,gen_length,orp_l);
627      kBucketClear(syzstr->bucket,&hn,&num_tail);
628      pNext(h) = hn;
629      if (hn==NULL)
630        break;
631      else
632      {
633        pIter(h);
634        pIter(hn);
635        num_mon++;
636        num_tail--;
637      }
638    }
639    *tored_l = num_mon+num_tail;
640  }
641  kBucketClear(syzstr->syz_bucket,&tso.syz,&syz_l);
642  assume(pLength(tso.syz)==syz_l);
643  assume(pLength(tso.p)==*tored_l);
644}
645 
646/*3
647* the reduction of a pair in the 0-th module
648*/
649static void redOnePair(SSet resPairs,int itso,int l, ideal syzygies, 
650            int crit_comp, syStrategy syzstr,int index,ideal new_generators,
651            ideal new_repr,int * ogm_l,int * orp_l)
652{
653  SObject tso = resPairs[itso];
654  assume (tso.lcm!=NULL);
655  ideal old_generators=syzstr->res[index];
656  ideal old_repr=syzstr->orderedRes[index];
657  int og_idel=IDELEMS(old_generators),ng_place=IDELEMS(new_generators);
658  int toReplace=0;
659  int i,j,syz_l;
660  number coefgcd,n;
661  polyset ogm=old_generators->m;
662  poly p;
663  BOOLEAN deleteP=FALSE;
664#ifdef EXPERIMENT1
665  poly syzp;
666#endif
667  int syz_place=IDELEMS(syzygies);
668 
669  while ((syz_place>0) && (syzygies->m[syz_place-1]==NULL)) syz_place--;
670  while ((ng_place>0) && (new_generators->m[ng_place-1]==NULL)) ng_place--;
671  while ((og_idel>0) && (old_generators->m[og_idel-1]==NULL)) og_idel--;
672  assume (tso.ind1<og_idel);
673  assume (tso.ind2<og_idel);
674  assume (tso.ind1!=tso.ind2);
675  assume (tso.p1 == old_generators->m[tso.ind1]);
676  assume (tso.p2 == old_generators->m[tso.ind2]);
677  tso.p1 = old_generators->m[tso.ind1];
678  tso.p2 = old_generators->m[tso.ind2];
679  if ((tso.p1!=NULL) && (tso.p2!=NULL))
680  {
681    if (TEST_OPT_PROT)
682      Print(".");
683    if (index==0)
684    {
685/*--- tests wether a generator must be replaced (lt(f1)|lt(f2)!)--*/
686      if (pFDeg(tso.p1)==pFDeg(tso.lcm))
687        toReplace = tso.ind1+1;
688      else if (pFDeg(tso.p2)==pFDeg(tso.lcm))
689        toReplace = tso.ind2+1;
690    }
691#ifdef EXPERIMENT3
692/*--- tests wether the product criterion applies --------------*/
693    if ((index==0) && (old_generators->rank==1) && 
694        (pFDeg(tso.p1)+pFDeg(tso.p2)==tso.order))
695    {
696      tso.p = NULL;
697      p = pCopy(tso.p1);
698      pShift(&p,-1);
699#ifdef WITH_BUCKET
700      poly pp;
701      pp = pMult_mm(pCopy(old_repr->m[tso.ind2]),p);
702      kBucketInit(syzstr->syz_bucket,pp,-1);
703      pDeleteLm(&p);
704      p = pNeg(p);
705      pp = pCopy(old_repr->m[tso.ind2]);
706      int il=-1;
707      while (p!=NULL)
708      {
709        kBucket_Minus_m_Mult_p(syzstr->syz_bucket,p,pp,&il,NULL);
710        pDeleteLm(&p);
711      }
712      pDelete(&pp);
713      p = pCopy(tso.p2);
714      pShift(&p,-1);
715      pp = pCopy(old_repr->m[tso.ind1]);
716      il=-1;
717      while (p!=NULL)
718      {
719        kBucket_Minus_m_Mult_p(syzstr->syz_bucket,p,pp,&il,NULL);
720        pDeleteLm(&p);
721      }
722      pDelete(&pp);
723      kBucketClear(syzstr->syz_bucket,&tso.syz,&j);
724#else
725      tso.syz = pMult(p,pCopy(old_repr->m[tso.ind2]));
726      p = pCopy(tso.p2);
727      pShift(&p,-1);
728      tso.syz = pSub(tso.syz,pMult(p,pCopy(old_repr->m[tso.ind1])));
729#endif
730    }
731    else
732#endif
733/*--- the product criterion does not apply --------------------*/
734    {
735      tso.p = ksOldCreateSpoly(tso.p2,tso.p1);
736      number coefgcd = nGcd(pGetCoeff(tso.p1),pGetCoeff(tso.p2));
737      assume (old_repr->m[tso.ind1]!=NULL);
738      tso.syz = pCopy(old_repr->m[tso.ind1]);
739      poly tt = pDivide(tso.lcm,tso.p1);
740      pSetComp(tt,0);
741      pSetmComp(tt);
742      pSetCoeff(tt,nDiv(pGetCoeff(tso.p1),coefgcd));
743      tso.syz = pMult_mm(tso.syz,tt);
744      pDelete(&tt);
745      coefgcd = nNeg(coefgcd);
746      assume (old_repr->m[tso.ind2]!=NULL);
747      p = pCopy(old_repr->m[tso.ind2]);
748      tt = pDivide(tso.lcm,tso.p2);
749      pSetComp(tt,0);
750      pSetmComp(tt);
751      pSetCoeff(tt,nDiv(pGetCoeff(tso.p2),coefgcd));
752      p = pMult_mm(p,tt);
753      pDelete(&tt);
754      tso.syz = pAdd(p,tso.syz);
755#ifdef EXPERIMENT2
756      if ((tso.syz!=NULL) && (pGetComp(tso.syz)<=crit_comp)) 
757      {
758/*--- breaks when the leading component is less than crit_comp ------*/
759        deleteP = TRUE;
760        discard_pairs++;
761      }
762#endif
763      nDelete(&coefgcd);
764    }                             //End of the else-part of EXPERIMENT3
765#ifdef SHOW_PROT
766Print("reduziere Paar im Module %d mit: \n",index);
767Print("poly1: ");pWrite(tso.p1);
768Print("poly2: ");pWrite(tso.p2);
769Print("syz: ");pWrite(tso.syz);
770Print("sPoly: ");pWrite(tso.p);
771#endif
772    assume(tso.syz!=NULL);
773    kBucketInit(syzstr->syz_bucket,tso.syz,-1);
774    if ((tso.p!=NULL) && (!deleteP))
775    {
776      kBucketInit(syzstr->bucket,tso.p,-1);
777      p = kBucketGetLm(syzstr->bucket);
778      j = 0;
779      loop
780      {
781        if (j>=og_idel) 
782        {
783/*--- reduction with generators computed in this procedure ---*/
784          j = 0;
785          while ((j<ng_place) && (!pDivisibleBy(new_generators->m[j],p))) j++;
786          if (j>=ng_place) break;
787          assume (new_repr->m[j]!=NULL);
788          sySPRedSyz_Kosz(syzstr,new_generators->m[j],new_repr->m[j],p);
789          n = kBucketPolyRed(syzstr->bucket,new_generators->m[j],pLength(new_generators->m[j]), NULL);
790          p = kBucketGetLm(syzstr->bucket);
791#ifdef EXPERIMENT1
792          syzp = kBucketGetLm(syzstr->syz_bucket);
793          if ((syzp!=NULL) && (pGetComp(syzp)<=crit_comp))
794          {
795            deleteP =TRUE;
796            break;
797          }
798          //if (syzp==NULL)
799            //assume(p==NULL);
800          //else
801            //if (pGetComp(syzp)<=crit_comp) short_pairs++;
802#endif
803          if (p==NULL) break;
804          j = 0;
805        }
806        if (pDivisibleBy(ogm[j],p))
807        {
808/*--- reduction with general old generators ---------------------*/
809          assume (old_repr->m[j]!=NULL);
810          sySPRedSyz_Kosz(syzstr,ogm[j],old_repr->m[j],p,orp_l[j]);
811          n = kBucketPolyRed(syzstr->bucket,ogm[j],ogm_l[j], NULL);
812          p = kBucketGetLm(syzstr->bucket);
813#ifdef EXPERIMENT1
814          syzp = kBucketGetLm(syzstr->syz_bucket);
815          if ((syzp!=NULL) && (pGetComp(syzp)<=crit_comp))
816          {
817            break;
818            deleteP =TRUE;
819          }
820          //if (syzp==NULL)
821            //assume(p==NULL);
822          //else
823            //if ((pGetComp(syzp)<=crit_comp) && (p!=NULL)) short_pairs++;
824#endif
825          if (p==NULL) break;
826          j = 0;
827        }
828        else
829          j++;
830      }
831      kBucketClear(syzstr->bucket,&tso.p,&tso.length);
832    }
833    kBucketClear(syzstr->syz_bucket,&tso.syz,&syz_l);
834    if (deleteP)
835    {
836      pDelete(&tso.p);
837      pDelete(&tso.syz);
838    }
839  }
840  else
841  {
842    Print("Shit happens!\n");
843  }
844#ifdef SHOW_PROT
845Print("erhalte Paar im Module %d mit: \n",index);
846Print("syz: ");pWrite(tso.syz);
847Print("sPoly: ");pWrite(tso.p);
848PrintLn();
849#endif
850  if (toReplace)
851  {
852/*-- replaces the generator if neccesary ------------------*/
853    pDelete(&old_generators->m[toReplace-1]);
854    pDelete(&old_repr->m[toReplace-1]);
855    for (i=toReplace-1;i<og_idel-1;i++)
856    {
857      old_generators->m[i] = old_generators->m[i+1];
858      old_repr->m[i] = old_repr->m[i+1];
859    }
860    old_generators->m[og_idel-1] = NULL;
861    old_repr->m[og_idel-1] = NULL;
862    for (i=itso+1;i<l;i++)
863    {
864      if (resPairs[i].lcm!=NULL) 
865      { 
866        if ((resPairs[i].ind1==toReplace-1)||(resPairs[i].ind2==toReplace-1))
867          syDeletePair(&resPairs[i]);
868        else 
869        {
870          if (resPairs[i].ind1>=toReplace)
871            (resPairs[i].ind1)--;
872          if (resPairs[i].ind2>=toReplace)
873            (resPairs[i].ind2)--;
874        }
875      }
876    }
877    syCompactifyPairSet(resPairs,l,itso+1);
878  }
879  if (tso.p!=NULL)
880  {
881/*-- stores the new generator ---------------------------------*/
882    //syRedTailSyzPair(tso,syzstr,index,ogm_l,orp_l,&tso.length,&syz_l);
883    if (ng_place>=IDELEMS(new_generators))
884    {
885      pEnlargeSet(&new_generators->m,IDELEMS(new_generators),16);
886      IDELEMS(new_generators) += 16;
887      pEnlargeSet(&new_repr->m,IDELEMS(new_repr),16);
888      IDELEMS(new_repr) += 16;
889    }
890    if (!nIsOne(pGetCoeff(tso.p)))
891    {
892      n=nInvers(pGetCoeff(tso.p));
893      pNorm(tso.p);
894      pMult_nn(tso.syz,n);
895      nDelete(&n);
896    }
897    new_generators->m[ng_place] = tso.p;
898    tso.p = NULL;
899    new_repr->m[ng_place] = tso.syz;
900    tso.syz = NULL;
901  }
902  else
903  {
904/*--- takes the syzygy as new generator of the next module ---*/
905    if (tso.syz==NULL)
906    {
907#ifndef EXPERIMENT2
908#ifdef EXPERIMENT3
909      short_pairs++;
910#endif
911#endif
912    }
913    else if (pGetComp(tso.syz)<=crit_comp)
914    {
915      pDelete(&tso.syz);
916    }
917    else
918    {
919      if (syz_place>=IDELEMS(syzygies))
920      {
921        pEnlargeSet(&syzygies->m,IDELEMS(syzygies),16);
922        IDELEMS(syzygies) += 16;
923      }
924      syzygies->m[syz_place] = tso.syz;
925      tso.syz = NULL;
926      pNorm(syzygies->m[syz_place]);
927    }
928  }
929  resPairs[itso] = tso;
930  syDeletePair(&resPairs[itso]);
931  syTestPairs(resPairs,l,old_generators);
932}
933 
934/*3
935* reduction of all pairs of a fixed degree of the 0-th module
936*/
937static BOOLEAN redPairs(SSet resPairs,int l_pairs, ideal syzygies,
938  ideal new_generators,ideal new_repr, int crit_comp,syStrategy syzstr,
939  int index)
940{
941  if (resPairs[0].lcm==NULL) return TRUE;
942  int i,j,actdeg=resPairs[0].order;
943  int * ogm_l=(int*)omAlloc0(IDELEMS(syzstr->res[index])*sizeof(int));
944  int * orp_l=(int*)omAlloc0(IDELEMS(syzstr->orderedRes[index])*sizeof(int));
945  int t1=IDELEMS(syzstr->res[index]),t2=IDELEMS(syzstr->orderedRes[index]);
946 
947  for (j=IDELEMS(syzstr->res[index])-1;j>=0;j--) 
948  {
949    if (syzstr->res[index]->m[j]!=NULL)
950      ogm_l[j] = pLength(syzstr->res[index]->m[j]);
951  }
952  for (j=IDELEMS(syzstr->orderedRes[index])-1;j>=0;j--) 
953  {
954    if (syzstr->orderedRes[index]->m[j]!=NULL)
955      orp_l[j] = pLength(syzstr->orderedRes[index]->m[j]);
956  }
957  loop
958  {
959    i = 0;
960    if (TEST_OPT_PROT)
961      Print("(%d,%d)",index,resPairs[0].order);
962    while (resPairs[i].order==actdeg)
963    {
964      syTestPairs(resPairs,l_pairs,syzstr->res[index]);
965      redOnePair(resPairs,i,l_pairs,syzygies,crit_comp,syzstr,index,
966                 new_generators, new_repr,ogm_l,orp_l);
967      i++;
968      syTestPairs(resPairs,l_pairs,syzstr->res[index]);
969    }
970    syTestPairs(resPairs,l_pairs,syzstr->res[index]);
971    syCompactifyPairSet(resPairs,l_pairs,0);
972    syTestPairs(resPairs,l_pairs,syzstr->res[index]);
973    if (!idIs0(new_generators))
974      break;
975    else if (resPairs[0].lcm==NULL)  //there are no pairs left and no new_gens
976    {
977      omFreeSize((ADDRESS)ogm_l,IDELEMS(syzstr->res[index])*sizeof(int));
978      omFreeSize((ADDRESS)orp_l,IDELEMS(syzstr->orderedRes[index])*sizeof(int));
979      return TRUE;
980    }
981    else
982      actdeg = resPairs[0].order;
983  }
984  syTestPairs(resPairs,l_pairs,syzstr->res[index]);
985  omFreeSize((ADDRESS)ogm_l,IDELEMS(syzstr->res[index])*sizeof(int));
986  omFreeSize((ADDRESS)orp_l,IDELEMS(syzstr->orderedRes[index])*sizeof(int));
987  return FALSE;
988}
989 
990/*3
991* extends the standard basis old_generators with new_generators;
992* returns the syzygies which involve the new elements;
993* assumes that the components of the new_generators are sperated
994* from those of old_generators, i.e. whenever the leading term
995* of a syzygy lies in the part of the old_generators, the syzygy
996* lie just in the module old_generators
997* assumes that the new_generators are reduced w.r.t. old_generators
998*/
999static ideal kosz_std(ideal new_generators,ideal new_repr,syStrategy syzstr,
1000                      int index,int next_comp)
1001{
1002  int og_idel=IDELEMS(syzstr->res[index]);
1003  int l_pairs=2*og_idel;
1004  ideal syzygies=idInit(16,syzstr->res[index]->rank+1);
1005  ideal result;
1006  if ((idIs0(new_generators)) || (new_generators->m[0]==NULL))
1007  {
1008    Werror("Hier ist was faul!\n");
1009    return result;
1010  }
1011  SSet resPairs=(SSet)omAlloc0(l_pairs*sizeof(SObject));
1012  loop
1013  {
1014    updatePairs(&resPairs,&l_pairs,syzstr,index,
1015                new_generators,new_repr,next_comp);
1016    if (redPairs(resPairs,l_pairs,syzygies, new_generators,new_repr,
1017                 next_comp,syzstr,index)) break;
1018  }
1019  omFreeSize((SSet)resPairs,l_pairs*sizeof(SObject));
1020  return syzygies;
1021}
1022 
1023/*3
1024* normalizes the incoming generators
1025*/
1026static poly normalize(poly next_p,ideal add_generators, syStrategy syzstr,
1027                      int * g_l,int * p_l,int crit_comp)
1028{
1029  int j=0,i=IDELEMS(add_generators);
1030  kBucketInit(syzstr->bucket,next_p,pLength(next_p));
1031  poly p = kBucketGetLm(syzstr->bucket),result;
1032  number n;
1033 
1034  loop
1035  {
1036    if ((j>=i) || (p==NULL) || (pGetComp(p)<=crit_comp)) break;
1037    if ((add_generators->m[j]!=NULL) && (pDivisibleBy(add_generators->m[j],p)))
1038    {
1039      n = kBucketPolyRed(syzstr->bucket,add_generators->m[j], g_l[j], NULL);
1040      nDelete(&n);
1041      p = kBucketGetLm(syzstr->bucket);
1042      j = 0;
1043    }
1044    else
1045      j++;
1046  }
1047  kBucketClear(syzstr->bucket,&result,p_l);
1048  return result;
1049}
1050 
1051/*3
1052* updates the pairs inthe higher modules
1053*/
1054static void updatePairsHIndex(SSet *resPairs,int *l_pairs,syStrategy syzstr,
1055       int index,ideal add_generators,ideal add_repr,ideal new_generators,
1056       ideal new_repr,int crit_comp,int* first_new)
1057{
1058  int i=*first_new,l=*l_pairs,j,ll,j1,add_idel=IDELEMS(add_generators);
1059  ideal pairs=idInit(add_idel,add_generators->rank);
1060  polyset prs=pairs->m;
1061  poly p=NULL;
1062  SObject tso;
1063 
1064  syInitializePair(&tso);
1065  while ((l>0) && ((*resPairs)[l-1].lcm==NULL)) l--;
1066  while ((i<add_idel) && (add_generators->m[i]!=NULL))
1067  {
1068    for (j=0;j<i;j++)
1069    {
1070      if ((pGetComp(add_generators->m[j])==pGetComp(add_generators->m[i])))
1071      {
1072        p = pOne();
1073        pLcm(add_generators->m[j],add_generators->m[i],p);
1074        pSetComp(p,i+1);
1075        pSetm(p);
1076        j1 = 0;
1077        while (j1<j)
1078        {
1079          if (prs[j1]!=NULL)
1080          {
1081            if (pLmDivisibleByNoComp(prs[j1],p))
1082            {
1083              pDelete(&p);
1084              break;
1085            }
1086            else if (pLmDivisibleByNoComp(p,prs[j1]))
1087            {
1088              pDelete(&(prs[j1]));
1089            }
1090#ifdef USE_CHAINCRIT
1091            else
1092            {
1093              poly p1,p2;
1094              int ip=pVariables;
1095              p1 = pDivide(p,add_generators->m[j]);
1096              p2 = pDivide(prs[j1],add_generators->m[j1]);
1097              while ((ip>0) && (pGetExp(p1,ip)*pGetExp(p2,ip)==0)) ip--;
1098              if (ip==0)
1099              {
1100                int ti=0;
1101                while ((ti<l) && (((*resPairs)[ti].ind1!=j1)|| ((*resPairs)[ti].ind2!=j))) ti++;
1102                if (ti<l) 
1103                {
1104                  if (TEST_OPT_PROT) Print("cc");
1105                  syDeletePair(&(*resPairs)[ti]);
1106                  syCompactifyPairSet(*resPairs,*l_pairs,ti);
1107                  l--;
1108                }
1109              }
1110              pDelete(&p1);
1111              pDelete(&p2);
1112            }
1113#endif
1114          }
1115          j1++;
1116        }
1117        if (p!=NULL)
1118          prs[j] = p;
1119      }
1120    }
1121    for (j=0;j<i;j++)
1122    {
1123      if (prs[j] !=NULL)
1124      {
1125        if (l>=*l_pairs)
1126        {
1127          SSet temp = (SSet)omAlloc0((*l_pairs+16)*sizeof(SObject));
1128          for (ll=0;ll<*l_pairs;ll++)
1129          {
1130            temp[ll].p = (*resPairs)[ll].p;
1131            temp[ll].p1 = (*resPairs)[ll].p1;
1132            temp[ll].p2 = (*resPairs)[ll].p2;
1133            temp[ll].syz = (*resPairs)[ll].syz;
1134            temp[ll].lcm = (*resPairs)[ll].lcm;
1135            temp[ll].ind1 = (*resPairs)[ll].ind1;
1136            temp[ll].ind2 = (*resPairs)[ll].ind2;
1137            temp[ll].syzind = (*resPairs)[ll].syzind;
1138            temp[ll].order = (*resPairs)[ll].order;
1139            temp[ll].isNotMinimal = (*resPairs)[ll].isNotMinimal;
1140          }
1141          omFreeSize((ADDRESS)(*resPairs),*l_pairs*sizeof(SObject));
1142          *l_pairs += 16;
1143          (*resPairs) = temp;
1144        }
1145        tso.lcm = prs[j];
1146        prs[j] = NULL;
1147        tso.order = pFDeg(tso.lcm);
1148        tso.p1 = add_generators->m[j];
1149        tso.p2 = add_generators->m[i];
1150        tso.ind1 = j;
1151        tso.ind2 = i;
1152        tso.syzind = -1;
1153        tso.isNotMinimal = NULL;
1154        tso.p = NULL;
1155        tso.syz = NULL;
1156        SSet rP=*resPairs;
1157#ifdef SHOW_PROT
1158Print("erzeuge Paar im Modul %d,%d mit: \n",index,tso.order);
1159Print("poly1: ");pWrite(tso.p1);
1160Print("poly2: ");pWrite(tso.p2);
1161Print("syz: ");pWrite(tso.syz);
1162Print("sPoly: ");pWrite(tso.p);
1163PrintLn();
1164#endif
1165        syEnterPair(rP,&tso,&l,index);
1166        syInitializePair(&tso);
1167      }
1168    }
1169    i++;
1170  }
1171  *first_new = i;
1172  idDelete(&pairs);
1173}
1174 
1175/*3
1176* reduction of a single pair in the higher moduls
1177*/
1178static void redOnePairHIndex(SSet resPairs,int itso, int crit_comp, 
1179            syStrategy syzstr,int index,ideal add_generators, ideal add_repr,
1180            ideal new_generators, ideal new_repr,int * next_place_add,int ** g_l,
1181            poly deg_soc)
1182{
1183  SObject tso = resPairs[itso];
1184  assume (tso.lcm!=NULL);
1185  int ng_place=IDELEMS(new_generators);
1186  int i,j;
1187  number coefgcd,n;
1188  poly p;
1189  BOOLEAN deleteP=FALSE;
1190#ifdef EXPERIMENT1
1191  poly syzp;
1192#endif
1193 
1194  assume (tso.ind1<*next_place_add);
1195  assume (tso.ind2<*next_place_add);
1196  assume (tso.ind1!=tso.ind2);
1197  assume (tso.p1 == add_generators->m[tso.ind1]);
1198  assume (tso.p2 == add_generators->m[tso.ind2]);
1199  tso.p1 = add_generators->m[tso.ind1];
1200  tso.p2 = add_generators->m[tso.ind2];
1201  if ((tso.p1!=NULL) && (tso.p2!=NULL))
1202  {
1203    if (TEST_OPT_PROT)
1204      Print(".");
1205#ifdef USE_PROD_CRIT
1206    if (pFDeg(tso.p1)+pFDeg(tso.p2)==tso.order+pFDeg(deg_soc))
1207    {
1208      if (TEST_OPT_PROT) Print("pc");
1209      int ac=pGetComp(tso.p1);
1210      assume(ac=pGetComp(tso.p2));
1211      poly p1=pCopy(tso.p1);
1212      poly p2=pCopy(tso.p2);
1213      poly pp1,pp2,tp1,tp2;
1214      poly sp1=pCopy(add_repr->m[tso.ind1]),sp2=pCopy(add_repr->m[tso.ind2]);
1215      pp1 = p1;
1216      pp2 = p2;
1217      loop
1218      {
1219        assume(pp1!=NULL);
1220        for(i=(int)pVariables; i; i--)
1221          pSetExp(pp1,i, pGetExp(pp1,i)- pGetExp(deg_soc,i));
1222        pSetComp(pp1, 0);
1223        pSetm(pp1);
1224        if ((pNext(pp1)!=NULL) && (pGetComp(pNext(pp1))!=ac))  break;
1225        pIter(pp1);
1226      }
1227      loop
1228      {
1229        assume(pp2!=NULL);
1230        for(i=(int)pVariables; i; i--)
1231          pSetExp(pp2,i, pGetExp(pp2,i)- pGetExp(deg_soc,i));
1232        pSetComp(pp2, 0);
1233        pSetm(pp2);
1234        if ((pNext(pp2)!=NULL) && (pGetComp(pNext(pp2))!=ac)) break;
1235        pIter(pp2);
1236      }
1237      tp1 = pNext(pp1);
1238      tp2 = pNext(pp2);
1239      pNext(pp1) = NULL;
1240      pNext(pp2) = NULL;
1241      //pShift(&p1,-ac);
1242      //pShift(&p2,-ac);
1243      tp1 = pMult(tp1,pCopy(p2));
1244      tp2 = pMult(tp2,pCopy(p1));
1245      sp1 = pMult(p2,sp1);
1246      sp2 = pMult(p1,sp2);
1247      tso.p = pSub(tp1,tp2);
1248      tso.syz = pSub(sp1,sp2);
1249    }
1250    else
1251#endif
1252    {
1253      tso.p = ksOldCreateSpoly(tso.p2,tso.p1);
1254      number coefgcd = nGcd(pGetCoeff(tso.p1),pGetCoeff(tso.p2));
1255      assume (add_repr->m[tso.ind1]!=NULL);
1256      tso.syz = pCopy(add_repr->m[tso.ind1]);
1257      poly tt = pDivide(tso.lcm,tso.p1);
1258      pSetComp(tt,0);
1259      pSetmComp(tt);
1260      pSetCoeff(tt,nDiv(pGetCoeff(tso.p1),coefgcd));
1261      tso.syz = pMult_mm(tso.syz,tt);
1262      pDelete(&tt);
1263      coefgcd = nNeg(coefgcd);
1264      assume (add_repr->m[tso.ind2]!=NULL);
1265      p = pCopy(add_repr->m[tso.ind2]);
1266      tt = pDivide(tso.lcm,tso.p2);
1267      pSetComp(tt,0);
1268      pSetmComp(tt);
1269      pSetCoeff(tt,nDiv(pGetCoeff(tso.p2),coefgcd));
1270      p = pMult_mm(p,tt);
1271      pDelete(&tt);
1272      tso.syz = pAdd(p,tso.syz);
1273      nDelete(&coefgcd);
1274    }
1275#ifdef SHOW_PROT
1276Print("reduziere Paar im Module %d mit: \n",index);
1277Print("poly1: ");pWrite(tso.p1);
1278Print("poly2: ");pWrite(tso.p2);
1279Print("syz: ");pWrite(tso.syz);
1280Print("sPoly: ");pWrite(tso.p);
1281#endif
1282    assume(tso.syz!=NULL);
1283    kBucketInit(syzstr->syz_bucket,tso.syz,-1);
1284    if (tso.p!=NULL)
1285    {
1286      kBucketInit(syzstr->bucket,tso.p,-1);
1287      p = kBucketGetLm(syzstr->bucket);
1288      j = 0;
1289      loop
1290      {
1291        if (j>=*next_place_add) break;
1292        if (pDivisibleBy(add_generators->m[j],p))
1293        {
1294          assume (add_repr->m[j]!=NULL);
1295          sySPRedSyz_Kosz(syzstr,add_generators->m[j],add_repr->m[j],p);
1296          n = kBucketPolyRed(syzstr->bucket,add_generators->m[j],
1297                   pLength(add_generators->m[j]), NULL);
1298          p = kBucketGetLm(syzstr->bucket);
1299          if ((p==NULL) || (pGetComp(p)<=crit_comp)) break;
1300          j = 0;
1301        }
1302        else
1303          j++;
1304      }
1305      kBucketClear(syzstr->bucket,&tso.p,&tso.length);
1306    }
1307    kBucketClear(syzstr->syz_bucket,&tso.syz,&j);
1308  }
1309  else
1310  {
1311    Print("Shit happens!\n");
1312  }
1313#ifdef SHOW_PROT
1314Print("erhalte Paar im Module %d mit: \n",index);
1315Print("syz: ");pWrite(tso.syz);
1316Print("sPoly: ");pWrite(tso.p);
1317PrintLn();
1318#endif
1319  if (tso.p!=NULL)
1320  {
1321    if (!nIsOne(pGetCoeff(tso.p)))
1322    {
1323      n=nInvers(pGetCoeff(tso.p));
1324      pNorm(tso.p);
1325      pMult_nn(tso.syz,n);
1326      nDelete(&n);
1327    }
1328  }
1329  if ((TEST_OPT_PROT) && (tso.syz==NULL)) Print("null");
1330  if ((tso.p!=NULL) && (pGetComp(tso.p)>crit_comp))
1331  {
1332    if (*next_place_add>=IDELEMS(add_generators))
1333    {
1334      pEnlargeSet(&add_generators->m,IDELEMS(add_generators),16);
1335      pEnlargeSet(&add_repr->m,IDELEMS(add_repr),16);
1336      *g_l = (int*)omRealloc0Size((ADDRESS)*g_l, IDELEMS(add_generators)*sizeof(int),
1337                            (IDELEMS(add_generators)+16)*sizeof(int));
1338      IDELEMS(add_generators) += 16;
1339      IDELEMS(add_repr) += 16;
1340    }
1341    assume(add_repr->m[*next_place_add]==NULL);
1342    add_generators->m[*next_place_add] = tso.p;
1343    add_repr->m[*next_place_add] = tso.syz;
1344    (*g_l)[*next_place_add] = tso.length;
1345    (*next_place_add)++;
1346  }
1347  else
1348  {
1349    while ((ng_place>0) && (new_generators->m[ng_place-1]==NULL) &&
1350          (new_repr->m[ng_place-1]==NULL)) ng_place--;
1351    if (ng_place>=IDELEMS(new_generators))
1352    {
1353      pEnlargeSet(&new_generators->m,IDELEMS(new_generators),16);
1354      IDELEMS(new_generators) += 16;
1355      pEnlargeSet(&new_repr->m,IDELEMS(new_repr),16);
1356      IDELEMS(new_repr) += 16;
1357    }
1358    new_generators->m[ng_place] = tso.p;
1359    new_repr->m[ng_place] = tso.syz;
1360  }
1361  tso.p = NULL;
1362  tso.syz = NULL;
1363  resPairs[itso] = tso;
1364  syDeletePair(&resPairs[itso]);
1365}
1366 
1367/*3
1368* reduction of all pairs of a fixed degree of a fixed module
1369*/
1370static BOOLEAN reducePairsHIndex(SSet resPairs,int l_pairs,syStrategy syzstr,
1371       int index,ideal add_generators,ideal add_repr,ideal new_generators,
1372       ideal new_repr,int crit_comp,int * red_deg,int * next_place_add,int **g_l,
1373       resolvente totake)
1374{
1375  if (resPairs[0].lcm==NULL) return FALSE;
1376  int i=0,j;
1377  poly deg_soc;
1378 
1379  if (TEST_OPT_PROT)
1380    Print("(%d,%d)",index,resPairs[0].order);
1381  while ((i<l_pairs) && (resPairs[i].order==*red_deg))
1382  {
1383    assume(totake[index-1]!=NULL);
1384    assume(pGetComp(resPairs[i].p1)<=IDELEMS(totake[index-1]));
1385    assume(totake[index-1]->m[pGetComp(resPairs[i].p1)-1]!=NULL);
1386    deg_soc = totake[index-1]->m[pGetComp(resPairs[i].p1)-1];
1387    redOnePairHIndex(resPairs,i,crit_comp,syzstr,index, add_generators,add_repr,
1388                     new_generators, new_repr,next_place_add,g_l,deg_soc);
1389    i++;
1390  }
1391  syCompactifyPairSet(resPairs,l_pairs,0);
1392  if (resPairs[0].lcm==NULL)  //there are no pairs left and no new_gens
1393    return FALSE;
1394  else
1395    *red_deg = resPairs[0].order;
1396  return TRUE;
1397}
1398 
1399/*3
1400* we proceed the generators of the next module;
1401* they are stored in add_generators and add_repr;
1402* if the normal form of a new genrators w.r.t. add_generators has
1403* pGetComp<crit_comp it is skipped from the reduction;
1404* new_generators and new_repr (which are empty) stores the result of the
1405* reduction which is normalized afterwards
1406*/
1407static void procedeNextGenerators(ideal temp_generators,ideal temp_repr,
1408      ideal new_generators, ideal new_repr, ideal add_generators,
1409      ideal add_repr, syStrategy syzstr,int index, int crit_comp,
1410      resolvente totake)
1411{
1412  int i=0,j,next_new_el;
1413  int idel_temp=IDELEMS(temp_generators);
1414  int next_place_add;
1415  int p_length,red_deg,l_pairs=IDELEMS(add_generators);
1416  poly next_p;
1417  int * gen_length=(int*)omAlloc0(IDELEMS(add_generators)*sizeof(int));
1418  int * secgen_length=(int*)omAlloc0(IDELEMS(syzstr->res[index])*sizeof(int));
1419  BOOLEAN pairs_left;
1420  SSet resPairs=(SSet)omAlloc0(l_pairs*sizeof(SObject));
1421 
1422  for (j=IDELEMS(syzstr->res[index])-1;j>=0;j--)
1423  {
1424    if (syzstr->res[index]->m[j]!=NULL)
1425      secgen_length[j] = pLength(syzstr->res[index]->m[j]);
1426  }
1427  assume(idIs0(new_generators));
1428  next_place_add = IDELEMS(add_generators);
1429  while ((next_place_add>0) && (add_generators->m[next_place_add-1]==NULL))
1430    next_place_add--;
1431  int next_deg = pFDeg(temp_generators->m[i]);
1432  next_new_el = next_place_add;
1433/*--- loop about all all elements-----------------------------------*/
1434  while ((i<idel_temp) && (temp_generators->m[i]!=NULL))
1435  {
1436/*--- separates elements of equal degree----------------------------*/
1437#ifdef USE_REGULARITY
1438    if (syzstr->regularity>0)
1439    {
1440      if (next_deg >= syzstr->regularity+index) 
1441      {
1442        while ((i<idel_temp) && (temp_generators->m[i]!=NULL))
1443        {
1444          pDelete(&temp_generators->m[i]);
1445          i++;
1446        }
1447        break;
1448      }
1449    }
1450#endif
1451    while ((i<idel_temp) && (pFDeg(temp_generators->m[i])==next_deg))
1452    {
1453      next_p = temp_generators->m[i];
1454      temp_generators->m[i] = NULL;
1455      next_p = normalize(next_p,add_generators,syzstr,gen_length,&p_length,
1456                crit_comp);
1457      if (next_p!=NULL)
1458      {
1459        if (pGetComp(next_p)<=crit_comp)
1460        {
1461          pDelete(&next_p);
1462          //if (TEST_OPT_PROT) Print("u(%d)",index);
1463        }
1464        else
1465        {
1466          next_p = syRedTailSyz(next_p,add_generators,syzstr->res[index],crit_comp,syzstr,
1467            gen_length,secgen_length,&p_length);
1468          if (!nIsOne(pGetCoeff(next_p)))
1469            pNorm(next_p);
1470          if (next_place_add>=IDELEMS(add_generators))
1471          {
1472            pEnlargeSet(&add_generators->m,IDELEMS(add_generators),16);
1473            pEnlargeSet(&add_repr->m,IDELEMS(add_repr),16);
1474            gen_length = (int*)omRealloc0Size((ADDRESS)gen_length, IDELEMS(add_generators)*sizeof(int), 
1475                                        (IDELEMS(add_generators)+16)*sizeof(int));
1476            IDELEMS(add_generators) += 16;
1477            IDELEMS(add_repr) += 16;
1478          }
1479          add_generators->m[next_place_add] = next_p;
1480          if (totake[index]==NULL)
1481            totake[index] = idInit(16,new_generators->rank);
1482          if ((*syzstr->Tl)[index]==IDELEMS(totake[index]))
1483          {
1484            pEnlargeSet(&totake[index]->m,IDELEMS(totake[index]),
1485                        (*syzstr->Tl)[index]+16-IDELEMS(totake[index]));
1486            for (j=IDELEMS(totake[index]);j<(*syzstr->Tl)[index]+16;j++)
1487              totake[index]->m[j] = NULL;
1488            IDELEMS(totake[index]) = (*syzstr->Tl)[index]+16;
1489          }
1490#ifdef FULL_TOTAKE
1491          totake[index]->m[(*syzstr->Tl)[index]] = pCopy(next_p);
1492#else
1493          totake[index]->m[(*syzstr->Tl)[index]] = pHead(next_p);
1494#endif
1495          assume(add_repr->m[next_place_add]==NULL);
1496#ifdef WITH_SCHREYER_ORD
1497          add_repr->m[next_place_add] = pHead(add_generators->m[next_place_add]);
1498#else
1499          add_repr->m[next_place_add] = pOne();
1500#endif
1501          ((*syzstr->Tl)[index])++;
1502          pSetComp(add_repr->m[next_place_add],(*syzstr->Tl)[index]);
1503          pSetmComp(add_repr->m[next_place_add]);
1504          gen_length[next_place_add] = p_length;
1505          next_place_add++;
1506        }
1507      }
1508      i++;
1509    }                        //end inner loop
1510    red_deg = next_deg;
1511    if (i<idel_temp)
1512      next_deg = pFDeg(temp_generators->m[i]);
1513    else
1514      next_deg = -1;
1515    if ((next_place_add>next_new_el) || (next_deg<0))  //there are new generators or pairs
1516    {
1517/*-reducing and generating pairs untill the degree of the next generators-*/
1518      pairs_left = TRUE;
1519      while (pairs_left && ((next_deg<0) || (red_deg<= next_deg)))
1520      {
1521        updatePairsHIndex(&resPairs,&l_pairs,syzstr,index,add_generators,
1522          add_repr,new_generators,new_repr,crit_comp,&next_new_el);
1523        pairs_left = reducePairsHIndex(resPairs,l_pairs,syzstr,index,add_generators,
1524           add_repr,new_generators,new_repr,crit_comp,&red_deg,&next_place_add,&gen_length,
1525           totake);
1526      }
1527    }
1528  }
1529  omFreeSize((SSet)resPairs,l_pairs*sizeof(SObject));
1530  omFreeSize((ADDRESS)gen_length,IDELEMS(add_generators)*sizeof(int));
1531  omFreeSize((ADDRESS)secgen_length,IDELEMS(syzstr->res[index])*sizeof(int));
1532}
1533 
1534/*3
1535* normalizes the part of the next reduction lying within the block
1536* of former generators (old_generators);
1537*/
1538static ideal normalizeOldPart(ideal new_generators,ideal new_repr,
1539                      syStrategy syzstr,int index,int crit_comp)
1540{
1541  ideal old_generators= syzstr->res[index];
1542  ideal old_repr= syzstr->orderedRes[index];
1543  int i,j=0,ii=IDELEMS(old_generators)-1,dummy;
1544  poly p;
1545  number n;
1546  int * g_l=(int*)omAlloc0(IDELEMS(old_generators)*sizeof(int));
1547 
1548  for (i=0;i<IDELEMS(old_generators);i++)
1549  {
1550    if (old_generators->m[i]!=NULL)
1551    {
1552      g_l[i] = pLength(old_generators->m[i]);
1553    }
1554  }
1555  for (i=IDELEMS(new_generators)-1;i>=0;i--) 
1556  {
1557    if (new_generators->m[i]!=NULL)
1558    {
1559      kBucketInit(syzstr->bucket,new_generators->m[i],
1560                   pLength(new_generators->m[i]));
1561      kBucketInit(syzstr->syz_bucket,new_repr->m[i],
1562                   pLength(new_repr->m[i]));
1563      p = kBucketGetLm(syzstr->bucket);
1564      loop
1565      {
1566        if ((j>=ii) || (p==NULL)) break;
1567        if ((old_generators->m[j]!=NULL) && 
1568            (pDivisibleBy(old_generators->m[j],p)))
1569        {
1570          sySPRedSyz_Kosz(syzstr,old_generators->m[j],old_repr->m[j],p);
1571          n = kBucketPolyRed(syzstr->bucket,old_generators->m[j], g_l[j], NULL);
1572          nDelete(&n);
1573          p = kBucketGetLm(syzstr->bucket);
1574          j = 0;
1575        }
1576        else
1577          j++;
1578      }
1579      assume (p==NULL);
1580      kBucketClear(syzstr->bucket,&new_generators->m[i],&dummy);
1581      kBucketClear(syzstr->syz_bucket,&new_repr->m[i],&dummy);
1582    }
1583  }
1584  ideal result=idInit(IDELEMS(new_repr),new_repr->rank);
1585  for (j=IDELEMS(new_repr)-1;j>=0;j--)
1586  {
1587    result->m[j] = new_repr->m[j];
1588    if ((result->m[j]!=NULL) && (!nIsOne(pGetCoeff(result->m[j]))))
1589      pNorm(result->m[j]);
1590    new_repr->m[j] = NULL;
1591  }
1592  omFreeSize((ADDRESS)g_l,IDELEMS(old_generators)*sizeof(int));
1593  return result;
1594}
1595 
1596/*3
1597* constructs the new subresolution for a nonregular extension
1598*/
1599static ideal kosz_ext(ideal new_generators,ideal new_repr,syStrategy syzstr,
1600                      int index,int next_comp,resolvente totake)
1601{
1602  ideal temp_generators =idInit(IDELEMS(new_generators),new_generators->rank);
1603  ideal temp_repr=idInit(IDELEMS(new_repr),new_repr->rank);
1604  ideal add_generators =idInit(IDELEMS(new_generators),new_generators->rank);
1605  ideal add_repr=idInit(IDELEMS(new_repr),new_repr->rank);
1606  int min_deg=-1;
1607  int j,jj,k,deg_p,idel_temp=IDELEMS(temp_generators);
1608  poly p;
1609/*--reorder w.r.t. the degree----------------------------------------*/
1610  for (j=IDELEMS(new_generators)-1;j>=0;j--)
1611  {
1612    if (new_generators->m[j]!=NULL)
1613    {
1614      p = new_generators->m[j];
1615      new_generators->m[j] = NULL;
1616      deg_p = pFDeg(p);
1617      if (min_deg<0)
1618      {
1619        min_deg = deg_p;
1620      }
1621      else
1622      {
1623        if (deg_p<min_deg) min_deg = deg_p;
1624      }
1625      k = 0;
1626      while ((k<idel_temp) && (temp_generators->m[k]!=NULL) &&
1627             (pFDeg(temp_generators->m[k])<=deg_p)) k++;
1628      for (jj=idel_temp-1;jj>k;jj--)
1629      {
1630        temp_generators->m[jj] = temp_generators->m[jj-1];
1631      }
1632      temp_generators->m[k] = p;
1633    }
1634  }
1635/*--- computing the standard basis in the resolution of the extension -*/
1636  procedeNextGenerators(temp_generators,temp_repr,new_generators,new_repr,
1637    add_generators,add_repr,syzstr,index,next_comp,totake);
1638  j = IDELEMS(syzstr->res[index]);
1639  while ((j>0) && (syzstr->res[index]->m[j-1]==NULL)) j--;
1640  jj = IDELEMS(add_generators);
1641  while ((jj>0) && (add_generators->m[jj-1]==NULL)) jj--;
1642  if (j+jj>=IDELEMS(syzstr->res[index]))
1643  {
1644    pEnlargeSet(&syzstr->res[index]->m,IDELEMS(syzstr->res[index]),
1645                j+jj+1-IDELEMS(syzstr->res[index]));
1646    IDELEMS(syzstr->res[index]) = j+jj+1;
1647    pEnlargeSet(&syzstr->orderedRes[index]->m,IDELEMS(syzstr->orderedRes[index]),
1648                j+jj+1-IDELEMS(syzstr->orderedRes[index]));
1649    IDELEMS(syzstr->orderedRes[index]) = j+jj+1;
1650  }
1651  for (k=0;k<jj;k++)
1652  {
1653    syzstr->res[index]->m[j+k] = add_generators->m[k];
1654    syzstr->orderedRes[index]->m[j+k] = add_repr->m[k];
1655    add_generators->m[k] = NULL;
1656    add_repr->m[k] = NULL;
1657  }
1658  assume(idIs0(add_generators));
1659  assume(idIs0(add_repr));
1660  idDelete(&add_generators);
1661  idDelete(&add_repr);
1662  idDelete(&temp_generators);
1663  idDelete(&temp_repr);
1664/*--- normalizing the rest to get the syzygies ------------------------*/
1665  return normalizeOldPart(new_generators,new_repr,syzstr,index,next_comp);
1666}
1667 
1668/*
1669* this procedure assumes that the first order is C !!!
1670* INPUT: old_generators - the generators of the actual module
1671*                         computed so far (they are mixed vectors)
1672*        old_repr       - the representations of the old generators
1673*        new_generators - generators coming from reductions below,
1674*                         they must have leading terms in new components
1675*                         (they live only in the module part)
1676*  (*syzstr->Tl)[index] - the last used component in the syzygy
1677* OUTPUT: old_generators is updated
1678*         new_generators is empty
1679*         the return value is a set of new generators for the syzygies,
1680*/
1681static ideal syAppendSyz(ideal new_generators, syStrategy syzstr,int index,int crit_comp,
1682                         resolvente totake)
1683{
1684  int i,j,newIdeal;
1685  intvec * w;
1686  poly p;
1687  ideal result;
1688  int rk_new_gens = idRankFreeModule(new_generators);
1689  if (syzstr->res[index]==NULL)
1690  {
1691    syzstr->res[index] = idInit(1,max(rk_new_gens,1));
1692    syzstr->orderedRes[index] = idInit(1,max(rk_new_gens,1));
1693  }
1694  int ng_idel=IDELEMS(new_generators);
1695  ideal new_repr =idInit(ng_idel, crit_comp+ng_idel);
1696 
1697  if (index==0)
1698  {
1699    //int * og_l=(int*)omAlloc0(IDELEMS(syzstr->res[0])*sizeof(int));
1700    //for (i=IDELEMS(syzstr->res[0])-1;i>=0;i--)
1701    //{
1702      //if (syzstr->res[0]->m[i]!=NULL)
1703        //og_l[i] = pLength(syzstr->res[0]->m[i]);
1704    //}
1705    for (i=0;i<ng_idel;i++)
1706    {
1707      if (new_generators->m[i]!=NULL)
1708      {
1709        //int ng_l=pLength(new_generators->m[i]);
1710        //new_generators->m[i] = syRedTailSyz(new_generators->m[i],syzstr->res[0],NULL,0,syzstr,
1711            //og_l,NULL,&ng_l);
1712        if (totake[index]==NULL)
1713          totake[index] = idInit(16,new_generators->rank);
1714        if ((*syzstr->Tl)[index]>=IDELEMS(totake[index]))
1715        {
1716          pEnlargeSet(&totake[index]->m,IDELEMS(totake[index]),
1717                      (*syzstr->Tl)[index]+16-IDELEMS(totake[index]));
1718          for (j=IDELEMS(totake[index]);j<(*syzstr->Tl)[index]+16;j++)
1719            totake[index]->m[j] = NULL;
1720          IDELEMS(totake[index]) = (*syzstr->Tl)[index]+16;
1721        }
1722#ifdef FULL_TOTAKE
1723        totake[index]->m[(*syzstr->Tl)[index]] = pCopy(new_generators->m[i]);
1724#else
1725        totake[index]->m[(*syzstr->Tl)[index]] = pHead(new_generators->m[i]);
1726#endif
1727#ifdef WITH_SCHREYER_ORD
1728        new_repr->m[i] = pHead(new_generators->m[i]);
1729#else
1730        new_repr->m[i] = pOne();
1731#endif
1732        ((*syzstr->Tl)[index])++;
1733        pSetComp(new_repr->m[i],(*syzstr->Tl)[index]);
1734        pSetmComp(new_repr->m[i]);
1735      }
1736    }
1737    //omFreeSize((ADDRESS)og_l,IDELEMS(syzstr->res[0])*sizeof(int));
1738#ifdef SHOW_PROT
1739Print("Add new generators: \n");
1740idPrint(new_generators);
1741Print("with representaions: \n");
1742idPrint(new_repr);
1743#endif
1744    result = kosz_std(new_generators,new_repr,syzstr,index,crit_comp);
1745  }
1746  else
1747  {
1748    result = kosz_ext(new_generators,new_repr,syzstr,index,crit_comp,totake);
1749  }
1750  idSkipZeroes(result);
1751  assume(idIs0(new_repr));
1752  idDelete(&new_repr);
1753  return result;
1754}
1755 
1756/*
1757* main call of the extended Koszul-resolution
1758*/
1759syStrategy syKosz(ideal arg,int * length)
1760{
1761  int i,j,jj,k=0,index=0,rk_arg,actual_syzcomp,next_syz=0;
1762  int crit_comp,t_comp,next_deg,old_tl;
1763  ideal temp=NULL,old_ideal,old_repr;
1764  ring origR = currRing,actR;
1765  poly p,next_gen;
1766  tHomog hom=isNotHomog;
1767  BOOLEAN isRegular;
1768 
1769  discard_pairs = 0;
1770  short_pairs = 0;
1771  if (idIs0(arg)) return NULL;
1772  rk_arg = idRankFreeModule(arg);
1773  syStrategy syzstr=(syStrategy)omAlloc0(sizeof(ssyStrategy));
1774/*--- changes to a Cdp-ring ----------------------------*/
1775  syzstr->syRing = rCurrRingAssure_C_dp();
1776/*--- initializes the data structures---------------*/
1777  syzstr->length = *length = pVariables+2;
1778  syzstr->regularity = -1;
1779  if (origR!=syzstr->syRing)
1780    temp = idrCopyR(arg,origR);
1781  else
1782    temp = idCopy(arg);
1783  if (rk_arg==0)
1784  {
1785    for (j=0;j<IDELEMS(temp);j++)
1786    {
1787      if (temp->m[j]!=NULL)
1788        pShift(&temp->m[j],1);
1789    }
1790  }
1791  idSkipZeroes(temp);
1792#ifdef WITH_SORT
1793  if (temp->m[0]!=NULL)
1794  {
1795    int maxdeg=pFDeg(temp->m[IDELEMS(temp)-1]),md;
1796    ideal temp1=idInit(IDELEMS(temp),temp->rank);
1797    for (j=IDELEMS(temp)-2;j>=0;j--)
1798    {
1799      jj = pFDeg(temp->m[j]);
1800      if (jj>maxdeg) maxdeg = jj;
1801    }
1802    while (!idIs0(temp))
1803    {
1804      md = maxdeg;
1805      for (j=IDELEMS(temp)-1;j>=0;j--)
1806      {
1807        if (temp->m[j]!=NULL)
1808        {
1809          jj = pFDeg(temp->m[j]);
1810          if (jj<md) md = jj;
1811        }
1812      }
1813      for (j=0;j<IDELEMS(temp);j++)
1814      {
1815        if ((temp->m[j]!=NULL) && (pFDeg(temp->m[j])==md))
1816        {
1817          temp1->m[k] = temp->m[j];
1818          temp->m[j] = NULL;
1819          k++;
1820        }
1821      }
1822    }
1823    idDelete(&temp);
1824    temp = temp1;
1825    temp1 = NULL;
1826  }
1827#endif
1828#ifdef USE_REGULARITY
1829  int last_generator=IDELEMS(temp)-1;
1830  while ((last_generator>=0) && (temp->m[last_generator]==NULL))
1831    last_generator--;
1832#endif
1833  syzstr->res = (resolvente)omAlloc0((*length+1)*sizeof(ideal));
1834  syzstr->orderedRes = (resolvente)omAlloc0((*length+1)*sizeof(ideal));
1835  resolvente totake=(resolvente)omAlloc0((*length+1)*sizeof(ideal));
1836  syzstr->Tl = new intvec(*length+1);
1837  syzstr->bucket = kBucketCreate();
1838  syzstr->syz_bucket = kBucketCreate();
1839  ideal new_generators=idInit(1,max(rk_arg,1));
1840  ideal temp_gens,old_std;
1841  syzstr->res[0] = idInit(1,1);
1842  if (rk_arg>1) syzstr->res[0]->rank = rk_arg;
1843  syzstr->orderedRes[0] = idInit(1,1);
1844/*--- computes the resolution ----------------------*/
1845  i = 0;
1846  while (i<IDELEMS(temp))
1847  {
1848    if (temp->m[i]!=NULL)
1849    {
1850      new_generators->m[0] = kNF(syzstr->res[0],currQuotient,temp->m[i]);
1851      if (!nIsOne(pGetCoeff(new_generators->m[0])))
1852        pNorm(new_generators->m[0]);
1853      next_deg = pFDeg(new_generators->m[0]);
1854      next_gen = pCopy(new_generators->m[0]);
1855    }
1856    if (!idIs0(new_generators))
1857    {
1858      index = 0;
1859      while (index<=*length)
1860      {
1861        if (index==0)
1862        {
1863          old_ideal = idCopy(syzstr->res[0]);
1864          old_repr = idCopy(syzstr->orderedRes[0]);
1865          old_tl = (*syzstr->Tl)[0];
1866          old_std = idHead(syzstr->res[0]);
1867        }
1868        t_comp = (*syzstr->Tl)[index];
1869        if (index==0) crit_comp = t_comp;
1870        temp_gens = syAppendSyz(new_generators,syzstr, index,crit_comp,totake);
1871        crit_comp = t_comp;
1872        if (index==0)
1873        {
1874          isRegular = syIsRegular(old_std,syzstr->res[0],next_deg);
1875#ifndef ONLY_STD
1876          if (isRegular)
1877            syCreateRegularExtension(syzstr,old_ideal,old_repr,old_tl,next_gen,
1878                                     totake);
1879#ifdef USE_REGULARITY
1880        if ((index==0) && (!isRegular) && (i==last_generator))
1881        {
1882/*----------- we are computing the regularity -----------------------*/
1883          ideal initial=idHead(syzstr->res[0]);
1884          int len=0,reg=0;
1885          intvec *w=NULL;
1886          ring dp_C_ring = rCurrRingAssure_dp_C();
1887          initial = idrMoveR_NoSort(initial, syzstr->syRing);
1888          resolvente res = sySchreyerResolvente(initial,-1,&len,TRUE, TRUE);
1889          intvec * dummy = syBetti(res,len,&reg, w);
1890          syzstr->regularity = reg+2;
1891          delete dummy;
1892          delete w;
1893          for (j=0;j<len;j++)
1894          {
1895            if (res[j]!=NULL) idDelete(&(res[j]));
1896          }
1897          omFreeSize((ADDRESS)res,len*sizeof(ideal));
1898          idDelete(&initial);
1899          rChangeCurrRing(syzstr->syRing, TRUE);
1900          rKill(dp_C_ring);
1901        }
1902#endif
1903#endif
1904          idDelete(&old_ideal);
1905          idDelete(&old_repr);
1906          idDelete(&old_std);
1907          if (TEST_OPT_PROT)
1908          {
1909            if (isRegular)
1910              Print("\n regular\n");
1911            else
1912              Print("\n not regular\n");
1913          }
1914          if (next_gen!=NULL)
1915            pDelete(&next_gen);
1916          if (isRegular)
1917          {
1918            idDelete(&temp_gens);
1919            break;
1920          }
1921        }
1922        idDelete(&new_generators);
1923        new_generators = temp_gens;
1924#ifdef ONLY_STD
1925        break; 
1926#endif
1927        if (idIs0(new_generators)) break;
1928        index++;
1929      }
1930      if (!idIs0(new_generators))
1931      {
1932        for (j=0;j<IDELEMS(new_generators);j++)
1933        {
1934          if (new_generators->m[j]!=NULL)
1935          {
1936            pDelete(&new_generators->m[j]);
1937            new_generators->m[j] = NULL;
1938          }
1939        }
1940      }
1941    }
1942    i++;
1943  }
1944  if (idIs0(new_generators) && new_generators!=NULL) idDelete(&new_generators);
1945  if (temp!=NULL) idDelete(&temp);
1946  kBucketDestroy(&(syzstr->bucket));
1947  kBucketDestroy(&(syzstr->syz_bucket));
1948  index = 0;
1949  syzstr->fullres = syzstr->res;
1950  syzstr->res = NULL;
1951  index = 0;
1952  while ((index<=*length) && (syzstr->fullres[index]!=NULL))
1953  {
1954#ifdef SHOW_RESULT
1955    Print("The %d-th syzygy-module is now:\n",index);
1956    ideal ttt=idHead(syzstr->fullres[index]);
1957    idShow(ttt);
1958    idDelete(&ttt);
1959    //if (index>0)
1960    //{
1961      //Print("The related module is: \n");
1962      //idPrint(totake[index-1]);
1963    //}
1964    //Print("The %d-th module of the minimal resolution is:\n",index);
1965    if (!idIs0(totake[index]))
1966      idShow(totake[index]);
1967    //Print("with standard basis:\n");
1968    //idPrint(syzstr->fullres[index]);
1969    //if ((index<*length) && (totake[index+1]!=NULL))
1970    //{
1971      //Print("The %d-th syzygy-module is now:\n",index+1);
1972      //idPrint(totake[index+1]);
1973      //matrix m1=idModule2Matrix(totake[index]);
1974      //matrix m2=idModule2Matrix(totake[index+1]);
1975      //matrix m3=mpMult(m1,m2);
1976      //idPrint((ideal)m3);
1977    //}
1978#endif
1979    if (!idIs0(totake[index]))
1980    {
1981      for(i=0;i<IDELEMS(totake[index]);i++)
1982      {
1983        if (totake[index]->m[i]!=NULL)
1984        {
1985          j=0;
1986          while ((j<IDELEMS(syzstr->fullres[index])) &&
1987            ((syzstr->fullres[index]->m[j]==NULL) ||
1988            (!pLmEqual(syzstr->fullres[index]->m[j],totake[index]->m[i])))) j++;
1989          if (j<IDELEMS(syzstr->fullres[index]))
1990          {
1991            pDelete(&totake[index]->m[i]);
1992            totake[index]->m[i] = syzstr->fullres[index]->m[j];
1993            syzstr->fullres[index]->m[j] = NULL;
1994          }
1995          else
1996          {
1997            Print("Da ist was faul!!!\n");
1998            Print("Aber: Regularitaet %d, Grad %d\n",syzstr->regularity,pFDeg(totake[index]->m[i]));
1999          }
2000        }
2001      }
2002      idDelete(&syzstr->fullres[index]);
2003      syzstr->fullres[index] = totake[index];
2004    }
2005#ifdef SHOW_RESULT
2006    idShow(syzstr->fullres[index]);
2007#endif
2008    index++;
2009  }
2010  syReorder_Kosz(syzstr);
2011  index = 0;
2012  while ((index<=*length) && (syzstr->orderedRes[index]!=NULL))
2013  {
2014    idDelete(&(syzstr->orderedRes[index]));
2015    index++;
2016  }
2017  if (origR!=syzstr->syRing)
2018  {
2019    rChangeCurrRing(origR,TRUE);
2020    index = 0;
2021    while ((index<=*length) && (syzstr->fullres[index]!=NULL))
2022    {
2023      syzstr->fullres[index] = idrMoveR(syzstr->fullres[index],syzstr->syRing);
2024      index++;
2025    }
2026  }
2027  delete syzstr->Tl;
2028  syzstr->Tl = NULL;
2029  rKill(syzstr->syRing);
2030  syzstr->syRing = NULL;
2031  omFreeSize((ADDRESS)totake,(*length+1)*sizeof(ideal));
2032  omFreeSize((ADDRESS)syzstr->orderedRes,(*length+1)*sizeof(ideal));
2033//Print("Pairs to discard: %d\n",discard_pairs);
2034//Print("Pairs shorter reduced: %d\n",short_pairs);
2035//discard_pairs = 0;
2036//short_pairs = 0;
2037  return syzstr;
2038}
2039
Note: See TracBrowser for help on using the repository browser.