source: git/kernel/syz3.cc @ 83192d

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