source: git/kernel/syz3.cc @ 80c703

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