My Project
Loading...
Searching...
No Matches
syz3.cc
Go to the documentation of this file.
1/****************************************
2* Computer Algebra System SINGULAR *
3****************************************/
4/*
5* ABSTRACT: resolutions
6*/
7
8#include "kernel/mod2.h"
9
10#include "misc/mylimits.h"
11#include "misc/options.h"
12#include "misc/intvec.h"
13
14#include "coeffs/numbers.h"
15
17#include "polys/kbuckets.h"
18#include "polys/prCopy.h"
19#include "polys/matpol.h"
20
23
26#include "kernel/GBEngine/syz.h"
27
28#include "kernel/ideals.h"
29#include "kernel/polys.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
50
51/*3
52* assumes the ideals old_ideal and new_ideal to be homogeneous
53* tests whether 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=hFirstSeries(old_ideal,NULL,NULL,NULL);
58 intvec * new_hilbs=hFirstSeries(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*/
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 {
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 = pMDivide(p,old_generators->m[jj]);
392 p2 = pMDivide(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=pMDivide(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 =*/ (void) 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 =*/ (void) 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#if 0
571// unused
572/*3
573* the complete reduction of a single pair which is just stored
574* in bucket and syz_bucket
575*/
576static BOOLEAN syRedSyzPair(syStrategy syzstr,int index,int* g_l,int* orp_l)
577{
578 kBucket_pt bucket=syzstr->bucket;
579 poly p = kBucketGetLm(bucket);
580 ideal red=syzstr->res[index],repr=syzstr->orderedRes[index];
581 int j = 0,i=IDELEMS(red)-1;
582 number n;
583 BOOLEAN isChanged=FALSE;
584
585 loop
586 {
587 if ((j>=i) || (p==NULL)) break;
588 if ((red->m[j]!=NULL) && (pDivisibleBy(red->m[j],p)))
589 {
590 sySPRedSyz_Kosz(syzstr,red->m[j],repr->m[j],p,orp_l[j]);
591 n = kBucketPolyRed(bucket,red->m[j], g_l[j], NULL);
592 nDelete(&n);
593 p = kBucketGetLm(bucket);
594 isChanged = TRUE;
595 j = 0;
596 }
597 else
598 j++;
599 }
600 return isChanged;
601}
602#endif
603
604/*3
605* the tailreduction for generators (which includes the correction of
606* the corresponding representation)
607*/
608#if 0 /*unused*/
609static void syRedTailSyzPair(SObject tso,syStrategy syzstr,int index,
610 int * gen_length,int* orp_l,int * tored_l,int * syzred_l)
611{
612 int num_mon,num_tail,syz_l;
613 poly h,hn;
614 BOOLEAN dummy;
615
616 h = tso.p;
617 kBucketInit(syzstr->syz_bucket,tso.syz,*syzred_l);
618 if (h!=NULL)
619 {
620 num_mon = 1;
621 hn = pNext(h);
622 num_tail = *tored_l-1;
623 while (hn!=NULL)
624 {
625 kBucketInit(syzstr->bucket,hn,num_tail);
626 dummy = syRedSyzPair(syzstr,index,gen_length,orp_l);
627 kBucketClear(syzstr->bucket,&hn,&num_tail);
628 pNext(h) = hn;
629 if (hn==NULL)
630 break;
631 else
632 {
633 pIter(h);
634 pIter(hn);
635 num_mon++;
636 num_tail--;
637 }
638 }
639 *tored_l = num_mon+num_tail;
640 }
641 kBucketClear(syzstr->syz_bucket,&tso.syz,&syz_l);
642 assume(pLength(tso.syz)==syz_l);
643 assume(pLength(tso.p)==*tored_l);
644}
645#endif
646
647/*3
648* the reduction of a pair in the 0-th module
649*/
650static void redOnePair(SSet resPairs,int itso,int l, ideal syzygies,
651 int crit_comp, syStrategy syzstr,int index,ideal new_generators,
652 ideal new_repr,int * ogm_l,int * orp_l)
653{
654 SObject tso = resPairs[itso];
655 assume (tso.lcm!=NULL);
656 ideal old_generators=syzstr->res[index];
657 ideal old_repr=syzstr->orderedRes[index];
658 int og_idel=IDELEMS(old_generators),ng_place=IDELEMS(new_generators);
659 int toReplace=0;
660 int i,j,syz_l;
661 number /*coefgcd,*/n;
662 polyset ogm=old_generators->m;
663 poly p;
664 BOOLEAN deleteP=FALSE;
665#ifdef EXPERIMENT1
666 poly syzp;
667#endif
668 int syz_place=IDELEMS(syzygies);
669
670 while ((syz_place>0) && (syzygies->m[syz_place-1]==NULL)) syz_place--;
671 while ((ng_place>0) && (new_generators->m[ng_place-1]==NULL)) ng_place--;
672 while ((og_idel>0) && (old_generators->m[og_idel-1]==NULL)) og_idel--;
673 assume (tso.ind1<og_idel);
674 assume (tso.ind2<og_idel);
675 assume (tso.ind1!=tso.ind2);
676 assume (tso.p1 == old_generators->m[tso.ind1]);
677 assume (tso.p2 == old_generators->m[tso.ind2]);
678 tso.p1 = old_generators->m[tso.ind1];
679 tso.p2 = old_generators->m[tso.ind2];
680 if ((tso.p1!=NULL) && (tso.p2!=NULL))
681 {
682 if (TEST_OPT_PROT)
683 PrintS(".");
684 if (index==0)
685 {
686/*--- tests whether a generator must be replaced (lt(f1)|lt(f2)!)--*/
687 if (p_FDeg(tso.p1,currRing)==p_FDeg(tso.lcm,currRing))
688 toReplace = tso.ind1+1;
689 else if (p_FDeg(tso.p2,currRing)==p_FDeg(tso.lcm,currRing))
690 toReplace = tso.ind2+1;
691 }
692#ifdef EXPERIMENT3
693/*--- tests whether the product criterion applies --------------*/
694 if ((index==0) && (old_generators->rank==1) &&
695 (p_FDeg(tso.p1,currRing)+p_FDeg(tso.p2,currRing)==tso.order))
696 {
697 tso.p = NULL;
698 p = pCopy(tso.p1);
699 p_Shift(&p,-1,currRing);
700#ifdef WITH_BUCKET
701 poly pp;
702 pp = pMult_mm(pCopy(old_repr->m[tso.ind2]),p);
703 kBucketInit(syzstr->syz_bucket,pp,-1);
704 pLmDelete(&p);
705 p = pNeg(p);
706 pp = pCopy(old_repr->m[tso.ind2]);
707 int il=-1;
708 while (p!=NULL)
709 {
711 pLmDelete(&p);
712 }
713 pDelete(&pp);
714 p = pCopy(tso.p2);
715 p_Shift(&p,-1,currRing);
716 pp = pCopy(old_repr->m[tso.ind1]);
717 il=-1;
718 while (p!=NULL)
719 {
721 pLmDelete(&p);
722 }
723 pDelete(&pp);
724 kBucketClear(syzstr->syz_bucket,&tso.syz,&j);
725#else
726 tso.syz = pMult(p,pCopy(old_repr->m[tso.ind2]));
727 p = pCopy(tso.p2);
728 p_Shift(&p,-1,currRing);
729 tso.syz = pSub(tso.syz,pMult(p,pCopy(old_repr->m[tso.ind1])));
730#endif
731 }
732 else
733#endif
734/*--- the product criterion does not apply --------------------*/
735 {
736 tso.p = ksOldCreateSpoly(tso.p2,tso.p1);
737 number coefgcd = n_Gcd(pGetCoeff(tso.p1),pGetCoeff(tso.p2),currRing->cf);
738 assume (old_repr->m[tso.ind1]!=NULL);
739 tso.syz = pCopy(old_repr->m[tso.ind1]);
740 poly tt = pMDivide(tso.lcm,tso.p1);
741 pSetComp(tt,0);
742 pSetmComp(tt);
743 pSetCoeff(tt,nDiv(pGetCoeff(tso.p1),coefgcd));
744 tso.syz = pMult_mm(tso.syz,tt);
745 pDelete(&tt);
746 coefgcd = nInpNeg(coefgcd);
747 assume (old_repr->m[tso.ind2]!=NULL);
748 p = pCopy(old_repr->m[tso.ind2]);
749 tt = pMDivide(tso.lcm,tso.p2);
750 pSetComp(tt,0);
751 pSetmComp(tt);
752 pSetCoeff(tt,nDiv(pGetCoeff(tso.p2),coefgcd));
753 p = pMult_mm(p,tt);
754 pDelete(&tt);
755 tso.syz = pAdd(p,tso.syz);
756#ifdef EXPERIMENT2
757 if ((tso.syz!=NULL) && (pGetComp(tso.syz)<=crit_comp))
758 {
759/*--- breaks when the leading component is less than crit_comp ------*/
760 deleteP = TRUE;
762 }
763#endif
764 nDelete(&coefgcd);
765 } //End of the else-part of EXPERIMENT3
766#ifdef SHOW_PROT
767Print("reduziere Paar im Module %d mit: \n",index);
768PrintS("poly1: ");pWrite(tso.p1);
769PrintS("poly2: ");pWrite(tso.p2);
770PrintS("syz: ");pWrite(tso.syz);
771PrintS("sPoly: ");pWrite(tso.p);
772#endif
773 assume(tso.syz!=NULL);
774 kBucketInit(syzstr->syz_bucket,tso.syz,-1);
775 if ((tso.p!=NULL) && (!deleteP))
776 {
777 kBucketInit(syzstr->bucket,tso.p,-1);
778 p = kBucketGetLm(syzstr->bucket);
779 j = 0;
780 loop
781 {
782 if (j>=og_idel)
783 {
784/*--- reduction with generators computed in this procedure ---*/
785 j = 0;
786 while ((j<ng_place) && (!pDivisibleBy(new_generators->m[j],p))) j++;
787 if (j>=ng_place) break;
788 assume (new_repr->m[j]!=NULL);
789 sySPRedSyz_Kosz(syzstr,new_generators->m[j],new_repr->m[j],p);
790 n = kBucketPolyRed(syzstr->bucket,new_generators->m[j],
791 pLength(new_generators->m[j]), NULL);
792 p = kBucketGetLm(syzstr->bucket);
793#ifdef EXPERIMENT1
794 syzp = kBucketGetLm(syzstr->syz_bucket);
795 if ((syzp!=NULL) && (pGetComp(syzp)<=crit_comp))
796 {
797 deleteP =TRUE;
798 break;
799 }
800 //if (syzp==NULL)
801 //assume(p==NULL);
802 //else
803 //if (pGetComp(syzp)<=crit_comp) short_pairs++;
804#endif
805 if (p==NULL) break;
806 j = 0;
807 }
808 if (pDivisibleBy(ogm[j],p))
809 {
810/*--- reduction with general old generators ---------------------*/
811 assume (old_repr->m[j]!=NULL);
812 sySPRedSyz_Kosz(syzstr,ogm[j],old_repr->m[j],p,orp_l[j]);
813 n = kBucketPolyRed(syzstr->bucket,ogm[j],ogm_l[j], NULL);
814 p = kBucketGetLm(syzstr->bucket);
815#ifdef EXPERIMENT1
816 syzp = kBucketGetLm(syzstr->syz_bucket);
817 if ((syzp!=NULL) && (pGetComp(syzp)<=crit_comp))
818 {
819 break;
820 deleteP =TRUE;
821 }
822 //if (syzp==NULL)
823 //assume(p==NULL);
824 //else
825 //if ((pGetComp(syzp)<=crit_comp) && (p!=NULL)) short_pairs++;
826#endif
827 if (p==NULL) break;
828 j = 0;
829 }
830 else
831 j++;
832 }
833 kBucketClear(syzstr->bucket,&tso.p,&tso.length);
834 }
835 kBucketClear(syzstr->syz_bucket,&tso.syz,&syz_l);
836 if (deleteP)
837 {
838 pDelete(&tso.p);
839 pDelete(&tso.syz);
840 }
841 }
842 else
843 {
844 PrintS("Shit happens!\n");
845 }
846#ifdef SHOW_PROT
847Print("erhalte Paar im Module %d mit: \n",index);
848PrintS("syz: ");pWrite(tso.syz);
849PrintS("sPoly: ");pWrite(tso.p);
850PrintLn();
851#endif
852 if (toReplace)
853 {
854/*-- replaces the generator if necessary ------------------*/
855 pDelete(&old_generators->m[toReplace-1]);
856 pDelete(&old_repr->m[toReplace-1]);
857 for (i=toReplace-1;i<og_idel-1;i++)
858 {
859 old_generators->m[i] = old_generators->m[i+1];
860 old_repr->m[i] = old_repr->m[i+1];
861 }
862 old_generators->m[og_idel-1] = NULL;
863 old_repr->m[og_idel-1] = NULL;
864 for (i=itso+1;i<l;i++)
865 {
866 if (resPairs[i].lcm!=NULL)
867 {
868 if ((resPairs[i].ind1==toReplace-1)||(resPairs[i].ind2==toReplace-1))
869 syDeletePair(&resPairs[i]);
870 else
871 {
872 if (resPairs[i].ind1>=toReplace)
873 (resPairs[i].ind1)--;
874 if (resPairs[i].ind2>=toReplace)
875 (resPairs[i].ind2)--;
876 }
877 }
878 }
879 syCompactifyPairSet(resPairs,l,itso+1);
880 }
881 if (tso.p!=NULL)
882 {
883/*-- stores the new generator ---------------------------------*/
884 //syRedTailSyzPair(tso,syzstr,index,ogm_l,orp_l,&tso.length,&syz_l);
885 if (ng_place>=IDELEMS(new_generators))
886 {
887 pEnlargeSet(&new_generators->m,IDELEMS(new_generators),16);
888 IDELEMS(new_generators) += 16;
889 pEnlargeSet(&new_repr->m,IDELEMS(new_repr),16);
890 IDELEMS(new_repr) += 16;
891 }
892 if (!nIsOne(pGetCoeff(tso.p)))
893 {
894 n=nInvers(pGetCoeff(tso.p));
895 pNorm(tso.p);
896 tso.syz=__p_Mult_nn(tso.syz,n,currRing);
897 nDelete(&n);
898 }
899 new_generators->m[ng_place] = tso.p;
900 tso.p = NULL;
901 new_repr->m[ng_place] = tso.syz;
902 tso.syz = NULL;
903 }
904 else
905 {
906/*--- takes the syzygy as new generator of the next module ---*/
907 if (tso.syz==NULL)
908 {
909#ifndef EXPERIMENT2
910#ifdef EXPERIMENT3
911 short_pairs++;
912#endif
913#endif
914 }
915 else if (pGetComp(tso.syz)<=crit_comp)
916 {
917 pDelete(&tso.syz);
918 }
919 else
920 {
921 if (syz_place>=IDELEMS(syzygies))
922 {
923 pEnlargeSet(&syzygies->m,IDELEMS(syzygies),16);
924 IDELEMS(syzygies) += 16;
925 }
926 syzygies->m[syz_place] = tso.syz;
927 tso.syz = NULL;
928 pNorm(syzygies->m[syz_place]);
929 }
930 }
931 resPairs[itso] = tso;
932 syDeletePair(&resPairs[itso]);
933 syTestPairs(resPairs,l,old_generators);
934}
935
936/*3
937* reduction of all pairs of a fixed degree of the 0-th module
938*/
939static BOOLEAN redPairs(SSet resPairs,int l_pairs, ideal syzygies,
940 ideal new_generators,ideal new_repr, int crit_comp,syStrategy syzstr,
941 int index)
942{
943 if (resPairs[0].lcm==NULL) return TRUE;
944 int i,j,actdeg=resPairs[0].order;
945 int * ogm_l=(int*)omAlloc0(IDELEMS(syzstr->res[index])*sizeof(int));
946 int * orp_l=(int*)omAlloc0(IDELEMS(syzstr->orderedRes[index])*sizeof(int));
947 // int t1=IDELEMS(syzstr->res[index]),t2=IDELEMS(syzstr->orderedRes[index]);
948
949 for (j=IDELEMS(syzstr->res[index])-1;j>=0;j--)
950 {
951 if (syzstr->res[index]->m[j]!=NULL)
952 ogm_l[j] = pLength(syzstr->res[index]->m[j]);
953 }
954 for (j=IDELEMS(syzstr->orderedRes[index])-1;j>=0;j--)
955 {
956 if (syzstr->orderedRes[index]->m[j]!=NULL)
957 orp_l[j] = pLength(syzstr->orderedRes[index]->m[j]);
958 }
959 loop
960 {
961 i = 0;
962 if (TEST_OPT_PROT)
963 Print("(%d,%d)",index,resPairs[0].order);
964 while (resPairs[i].order==actdeg)
965 {
966 syTestPairs(resPairs,l_pairs,syzstr->res[index]);
967 redOnePair(resPairs,i,l_pairs,syzygies,crit_comp,syzstr,index,
968 new_generators, new_repr,ogm_l,orp_l);
969 i++;
970 syTestPairs(resPairs,l_pairs,syzstr->res[index]);
971 }
972 syTestPairs(resPairs,l_pairs,syzstr->res[index]);
973 syCompactifyPairSet(resPairs,l_pairs,0);
974 syTestPairs(resPairs,l_pairs,syzstr->res[index]);
975 if (!idIs0(new_generators))
976 break;
977 else if (resPairs[0].lcm==NULL) //there are no pairs left and no new_gens
978 {
979 omFreeSize((ADDRESS)ogm_l,IDELEMS(syzstr->res[index])*sizeof(int));
980 omFreeSize((ADDRESS)orp_l,IDELEMS(syzstr->orderedRes[index])*sizeof(int));
981 return TRUE;
982 }
983 else
984 actdeg = resPairs[0].order;
985 }
986 syTestPairs(resPairs,l_pairs,syzstr->res[index]);
987 omFreeSize((ADDRESS)ogm_l,IDELEMS(syzstr->res[index])*sizeof(int));
988 omFreeSize((ADDRESS)orp_l,IDELEMS(syzstr->orderedRes[index])*sizeof(int));
989 return FALSE;
990}
991
992/*3
993* extends the standard basis old_generators with new_generators;
994* returns the syzygies which involve the new elements;
995* assumes that the components of the new_generators are sperated
996* from those of old_generators, i.e. whenever the leading term
997* of a syzygy lies in the part of the old_generators, the syzygy
998* lie just in the module old_generators
999* assumes that the new_generators are reduced w.r.t. old_generators
1000*/
1001static ideal kosz_std(ideal new_generators,ideal new_repr,syStrategy syzstr,
1002 int index,int next_comp)
1003{
1004 int og_idel=IDELEMS(syzstr->res[index]);
1005 int l_pairs=2*og_idel;
1006 ideal syzygies=idInit(16,syzstr->res[index]->rank+1);
1007 if ((idIs0(new_generators)) || (new_generators->m[0]==NULL))
1008 {
1009 WerrorS("Hier ist was faul!\n");
1010 return NULL;
1011 }
1012 SSet resPairs=(SSet)omAlloc0(l_pairs*sizeof(SObject));
1013 loop
1014 {
1015 updatePairs(&resPairs,&l_pairs,syzstr,index,
1016 new_generators,new_repr,next_comp);
1017 if (redPairs(resPairs,l_pairs,syzygies, new_generators,new_repr,
1018 next_comp,syzstr,index)) break;
1019 }
1020 omFreeSize((SSet)resPairs,l_pairs*sizeof(SObject));
1021 return syzygies;
1022}
1023
1024/*3
1025* normalizes the incoming generators
1026*/
1027static poly normalize(poly next_p,ideal add_generators, syStrategy syzstr,
1028 int * g_l,int * p_l,int crit_comp)
1029{
1030 int j=0,i=IDELEMS(add_generators);
1031 kBucketInit(syzstr->bucket,next_p,pLength(next_p));
1032 poly p = kBucketGetLm(syzstr->bucket),result;
1033 number n;
1034
1035 loop
1036 {
1037 if ((j>=i) || (p==NULL) || (pGetComp(p)<=crit_comp)) break;
1038 if ((add_generators->m[j]!=NULL) && (pDivisibleBy(add_generators->m[j],p)))
1039 {
1040 n = kBucketPolyRed(syzstr->bucket,add_generators->m[j], g_l[j],
1041 NULL);
1042 nDelete(&n);
1043 p = kBucketGetLm(syzstr->bucket);
1044 j = 0;
1045 }
1046 else
1047 j++;
1048 }
1049 kBucketClear(syzstr->bucket,&result,p_l);
1050 return result;
1051}
1052
1053/*3
1054* updates the pairs in the higher modules
1055*/
1056static void updatePairsHIndex(SSet *resPairs,int *l_pairs,syStrategy /*syzstr*/,
1057 int index,ideal add_generators,ideal /*add_repr*/,ideal /*new_generators*/,
1058 ideal /*new_repr*/,int /*crit_comp*/,int* first_new)
1059{
1060 int i=*first_new,l=*l_pairs,j,ll,j1,add_idel=IDELEMS(add_generators);
1061 ideal pairs=idInit(add_idel,add_generators->rank);
1062 polyset prs=pairs->m;
1063 poly p=NULL;
1064 SObject tso;
1065
1066 syInitializePair(&tso);
1067 while ((l>0) && ((*resPairs)[l-1].lcm==NULL)) l--;
1068 while ((i<add_idel) && (add_generators->m[i]!=NULL))
1069 {
1070 for (j=0;j<i;j++)
1071 {
1072 if (pGetComp(add_generators->m[j]) == pGetComp(add_generators->m[i]))
1073 {
1074 p = pOne();
1075 pLcm(add_generators->m[j],add_generators->m[i],p);
1076 pSetComp(p,i+1);
1077 pSetm(p);
1078 j1 = 0;
1079 while (j1<j)
1080 {
1081 if (prs[j1]!=NULL)
1082 {
1083 if (pLmDivisibleByNoComp(prs[j1],p))
1084 {
1085 pDelete(&p);
1086 break;
1087 }
1088 else if (pLmDivisibleByNoComp(p,prs[j1]))
1089 {
1090 pDelete(&(prs[j1]));
1091 }
1092#ifdef USE_CHAINCRIT
1093 else
1094 {
1095 poly p1,p2;
1096 int ip=(currRing->N);
1097 p1 = pMDivide(p,add_generators->m[j]);
1098 p2 = pMDivide(prs[j1],add_generators->m[j1]);
1099 while ((ip>0) && (pGetExp(p1,ip)*pGetExp(p2,ip)==0)) ip--;
1100 if (ip==0)
1101 {
1102 int ti=0;
1103 while ((ti<l) && (((*resPairs)[ti].ind1!=j1)|| ((*resPairs)[ti].ind2!=j))) ti++;
1104 if (ti<l)
1105 {
1106 if (TEST_OPT_PROT) PrintS("cc");
1107 syDeletePair(&(*resPairs)[ti]);
1108 syCompactifyPairSet(*resPairs,*l_pairs,ti);
1109 l--;
1110 }
1111 }
1112 pDelete(&p1);
1113 pDelete(&p2);
1114 }
1115#endif
1116 }
1117 j1++;
1118 }
1119 if (p!=NULL)
1120 prs[j] = p;
1121 }
1122 }
1123 for (j=0;j<i;j++)
1124 {
1125 if (prs[j] !=NULL)
1126 {
1127 if (l>=*l_pairs)
1128 {
1129 SSet temp = (SSet)omAlloc0((*l_pairs+16)*sizeof(SObject));
1130 for (ll=0;ll<*l_pairs;ll++)
1131 {
1132 temp[ll].p = (*resPairs)[ll].p;
1133 temp[ll].p1 = (*resPairs)[ll].p1;
1134 temp[ll].p2 = (*resPairs)[ll].p2;
1135 temp[ll].syz = (*resPairs)[ll].syz;
1136 temp[ll].lcm = (*resPairs)[ll].lcm;
1137 temp[ll].ind1 = (*resPairs)[ll].ind1;
1138 temp[ll].ind2 = (*resPairs)[ll].ind2;
1139 temp[ll].syzind = (*resPairs)[ll].syzind;
1140 temp[ll].order = (*resPairs)[ll].order;
1141 temp[ll].isNotMinimal = (*resPairs)[ll].isNotMinimal;
1142 }
1143 omFreeSize((ADDRESS)(*resPairs),*l_pairs*sizeof(SObject));
1144 *l_pairs += 16;
1145 (*resPairs) = temp;
1146 }
1147 tso.lcm = prs[j];
1148 prs[j] = NULL;
1149 tso.order = p_FDeg(tso.lcm,currRing);
1150 tso.p1 = add_generators->m[j];
1151 tso.p2 = add_generators->m[i];
1152 tso.ind1 = j;
1153 tso.ind2 = i;
1154 tso.syzind = -1;
1155 tso.isNotMinimal = NULL;
1156 tso.p = NULL;
1157 tso.syz = NULL;
1158 SSet rP=*resPairs;
1159#ifdef SHOW_PROT
1160Print("erzeuge Paar im Modul %d,%d mit: \n",index,tso.order);
1161PrintS("poly1: ");pWrite(tso.p1);
1162PrintS("poly2: ");pWrite(tso.p2);
1163PrintS("syz: ");pWrite(tso.syz);
1164PrintS("sPoly: ");pWrite(tso.p);
1165PrintLn();
1166#endif
1167 syEnterPair(rP,&tso,&l,index);
1168 syInitializePair(&tso);
1169 }
1170 }
1171 i++;
1172 }
1173 *first_new = i;
1174 idDelete(&pairs);
1175}
1176
1177/*3
1178* reduction of a single pair in the higher moduls
1179*/
1180#ifdef SHOW_PROT
1181static void redOnePairHIndex(SSet resPairs,int itso, int crit_comp,
1182 syStrategy syzstr,int index,ideal add_generators, ideal add_repr,
1183 ideal new_generators, ideal new_repr,int * next_place_add,int ** g_l,
1184 poly deg_soc)
1185#else
1186static void redOnePairHIndex(SSet resPairs,int itso, int crit_comp,
1187 syStrategy syzstr,int /*index*/,ideal add_generators, ideal add_repr,
1188 ideal new_generators, ideal new_repr,int * next_place_add,int ** g_l,
1189 poly deg_soc)
1190#endif
1191{
1192 SObject tso = resPairs[itso];
1193 assume (tso.lcm!=NULL);
1194 int ng_place=IDELEMS(new_generators);
1195 int i,j;
1196 number n;
1197 poly p;
1198#ifdef EXPERIMENT1
1199 poly syzp;
1200#endif
1201
1202 assume (tso.ind1<*next_place_add);
1203 assume (tso.ind2<*next_place_add);
1204 assume (tso.ind1!=tso.ind2);
1205 assume (tso.p1 == add_generators->m[tso.ind1]);
1206 assume (tso.p2 == add_generators->m[tso.ind2]);
1207 tso.p1 = add_generators->m[tso.ind1];
1208 tso.p2 = add_generators->m[tso.ind2];
1209 if ((tso.p1!=NULL) && (tso.p2!=NULL))
1210 {
1211 if (TEST_OPT_PROT)
1212 PrintS(".");
1213#ifdef USE_PROD_CRIT
1214 if (p_FDeg(tso.p1,currRing)+p_FDeg(tso.p2,currRing)==tso.order+p_FDeg(deg_soc,currRing))
1215 {
1216 if (TEST_OPT_PROT) PrintS("pc");
1217 int ac=pGetComp(tso.p1);
1218 assume(ac=pGetComp(tso.p2));
1219 poly p1=pCopy(tso.p1);
1220 poly p2=pCopy(tso.p2);
1221 poly pp1,pp2,tp1,tp2;
1222 poly sp1=pCopy(add_repr->m[tso.ind1]),sp2=pCopy(add_repr->m[tso.ind2]);
1223 pp1 = p1;
1224 pp2 = p2;
1225 loop
1226 {
1227 assume(pp1!=NULL);
1228 for(i=(int)(currRing->N); i; i--)
1229 pSetExp(pp1,i, pGetExp(pp1,i)- pGetExp(deg_soc,i));
1230 pSetComp(pp1, 0);
1231 pSetm(pp1);
1232 if ((pNext(pp1)!=NULL) && (pGetComp(pNext(pp1))!=ac)) break;
1233 pIter(pp1);
1234 }
1235 loop
1236 {
1237 assume(pp2!=NULL);
1238 for(i=(int)(currRing->N); i; i--)
1239 pSetExp(pp2,i, pGetExp(pp2,i)- pGetExp(deg_soc,i));
1240 pSetComp(pp2, 0);
1241 pSetm(pp2);
1242 if ((pNext(pp2)!=NULL) && (pGetComp(pNext(pp2))!=ac)) break;
1243 pIter(pp2);
1244 }
1245 tp1 = pNext(pp1);
1246 tp2 = pNext(pp2);
1247 pNext(pp1) = NULL;
1248 pNext(pp2) = NULL;
1249 //p_Shift(&p1,-ac,currRing);
1250 //p_Shift(&p2,-ac,currRing);
1251 tp1 = pMult(tp1,pCopy(p2));
1252 tp2 = pMult(tp2,pCopy(p1));
1253 sp1 = pMult(p2,sp1);
1254 sp2 = pMult(p1,sp2);
1255 tso.p = pSub(tp1,tp2);
1256 tso.syz = pSub(sp1,sp2);
1257 }
1258 else
1259#endif
1260 {
1261 tso.p = ksOldCreateSpoly(tso.p2,tso.p1);
1262 number coefgcd = n_Gcd(pGetCoeff(tso.p1),pGetCoeff(tso.p2),currRing->cf);
1263 assume (add_repr->m[tso.ind1]!=NULL);
1264 tso.syz = pCopy(add_repr->m[tso.ind1]);
1265 poly tt = pMDivide(tso.lcm,tso.p1);
1266 pSetComp(tt,0);
1267 pSetmComp(tt);
1268 pSetCoeff(tt,nDiv(pGetCoeff(tso.p1),coefgcd));
1269 tso.syz = pMult_mm(tso.syz,tt);
1270 pDelete(&tt);
1271 coefgcd = nInpNeg(coefgcd);
1272 assume (add_repr->m[tso.ind2]!=NULL);
1273 p = pCopy(add_repr->m[tso.ind2]);
1274 tt = pMDivide(tso.lcm,tso.p2);
1275 pSetComp(tt,0);
1276 pSetmComp(tt);
1277 pSetCoeff(tt,nDiv(pGetCoeff(tso.p2),coefgcd));
1278 p = pMult_mm(p,tt);
1279 pDelete(&tt);
1280 tso.syz = pAdd(p,tso.syz);
1281 nDelete(&coefgcd);
1282 }
1283#ifdef SHOW_PROT
1284Print("reduziere Paar im Module %d mit: \n",index);
1285PrintS("poly1: ");pWrite(tso.p1);
1286PrintS("poly2: ");pWrite(tso.p2);
1287PrintS("syz: ");pWrite(tso.syz);
1288PrintS("sPoly: ");pWrite(tso.p);
1289#endif
1290 assume(tso.syz!=NULL);
1291 kBucketInit(syzstr->syz_bucket,tso.syz,-1);
1292 if (tso.p!=NULL)
1293 {
1294 kBucketInit(syzstr->bucket,tso.p,-1);
1295 p = kBucketGetLm(syzstr->bucket);
1296 j = 0;
1297 loop
1298 {
1299 if (j>=*next_place_add) break;
1300 if (pDivisibleBy(add_generators->m[j],p))
1301 {
1302 assume (add_repr->m[j]!=NULL);
1303 sySPRedSyz_Kosz(syzstr,add_generators->m[j],add_repr->m[j],p);
1304 n = kBucketPolyRed(syzstr->bucket,add_generators->m[j],
1305 pLength(add_generators->m[j]), NULL);
1306 p = kBucketGetLm(syzstr->bucket);
1307 if ((p==NULL) || (pGetComp(p)<=crit_comp)) break;
1308 j = 0;
1309 }
1310 else
1311 j++;
1312 }
1313 kBucketClear(syzstr->bucket,&tso.p,&tso.length);
1314 }
1315 kBucketClear(syzstr->syz_bucket,&tso.syz,&j);
1316 }
1317 else
1318 {
1319 PrintS("Shit happens!\n");
1320 }
1321#ifdef SHOW_PROT
1322Print("erhalte Paar im Module %d mit: \n",index);
1323PrintS("syz: ");pWrite(tso.syz);
1324PrintS("sPoly: ");pWrite(tso.p);
1325PrintLn();
1326#endif
1327 if (tso.p!=NULL)
1328 {
1329 if (!nIsOne(pGetCoeff(tso.p)))
1330 {
1331 n=nInvers(pGetCoeff(tso.p));
1332 pNorm(tso.p);
1333 tso.syz=__p_Mult_nn(tso.syz,n,currRing);
1334 nDelete(&n);
1335 }
1336 }
1337 if ((TEST_OPT_PROT) && (tso.syz==NULL)) PrintS("null");
1338 if ((tso.p!=NULL) && (pGetComp(tso.p)>crit_comp))
1339 {
1340 if (*next_place_add>=IDELEMS(add_generators))
1341 {
1342 pEnlargeSet(&add_generators->m,IDELEMS(add_generators),16);
1343 pEnlargeSet(&add_repr->m,IDELEMS(add_repr),16);
1344 *g_l = (int*)omRealloc0Size((ADDRESS)*g_l, IDELEMS(add_generators)*sizeof(int),
1345 (IDELEMS(add_generators)+16)*sizeof(int));
1346 IDELEMS(add_generators) += 16;
1347 IDELEMS(add_repr) += 16;
1348 }
1349 assume(add_repr->m[*next_place_add]==NULL);
1350 add_generators->m[*next_place_add] = tso.p;
1351 add_repr->m[*next_place_add] = tso.syz;
1352 (*g_l)[*next_place_add] = tso.length;
1353 (*next_place_add)++;
1354 }
1355 else
1356 {
1357 while ((ng_place>0) && (new_generators->m[ng_place-1]==NULL) &&
1358 (new_repr->m[ng_place-1]==NULL)) ng_place--;
1359 if (ng_place>=IDELEMS(new_generators))
1360 {
1361 pEnlargeSet(&new_generators->m,IDELEMS(new_generators),16);
1362 IDELEMS(new_generators) += 16;
1363 pEnlargeSet(&new_repr->m,IDELEMS(new_repr),16);
1364 IDELEMS(new_repr) += 16;
1365 }
1366 new_generators->m[ng_place] = tso.p;
1367 new_repr->m[ng_place] = tso.syz;
1368 }
1369 tso.p = NULL;
1370 tso.syz = NULL;
1371 resPairs[itso] = tso;
1372 syDeletePair(&resPairs[itso]);
1373}
1374
1375/*3
1376* reduction of all pairs of a fixed degree of a fixed module
1377*/
1378static BOOLEAN reducePairsHIndex(SSet resPairs,int l_pairs,syStrategy syzstr,
1379 int index,ideal add_generators,ideal add_repr,ideal new_generators,
1380 ideal new_repr,int crit_comp,int * red_deg,int * next_place_add,int **g_l,
1381 resolvente totake)
1382{
1383 if (resPairs[0].lcm==NULL) return FALSE;
1384 int i=0;
1385 poly deg_soc;
1386
1387 if (TEST_OPT_PROT)
1388 Print("(%d,%d)",index,resPairs[0].order);
1389 while ((i<l_pairs) && (resPairs[i].order==*red_deg))
1390 {
1391 assume(totake[index-1]!=NULL);
1392 assume(pGetComp(resPairs[i].p1)<=IDELEMS(totake[index-1]));
1393 assume(totake[index-1]->m[pGetComp(resPairs[i].p1)-1]!=NULL);
1394 deg_soc = totake[index-1]->m[pGetComp(resPairs[i].p1)-1];
1395 redOnePairHIndex(resPairs,i,crit_comp,syzstr,index, add_generators,add_repr,
1396 new_generators, new_repr,next_place_add,g_l,deg_soc);
1397 i++;
1398 }
1399 syCompactifyPairSet(resPairs,l_pairs,0);
1400 if (resPairs[0].lcm==NULL) //there are no pairs left and no new_gens
1401 return FALSE;
1402 else
1403 *red_deg = resPairs[0].order;
1404 return TRUE;
1405}
1406
1407/*3
1408* we proceed the generators of the next module;
1409* they are stored in add_generators and add_repr;
1410* if the normal form of a new generators w.r.t. add_generators has
1411* pGetComp<crit_comp it is skipped from the reduction;
1412* new_generators and new_repr (which are empty) stores the result of the
1413* reduction which is normalized afterwards
1414*/
1415static void procedeNextGenerators(ideal temp_generators,ideal /*temp_repr*/,
1416 ideal new_generators, ideal new_repr, ideal add_generators,
1417 ideal add_repr, syStrategy syzstr,int index, int crit_comp,
1418 resolvente totake)
1419{
1420 int i=0,j,next_new_el;
1421 int idel_temp=IDELEMS(temp_generators);
1422 int next_place_add;
1423 int p_length,red_deg,l_pairs=IDELEMS(add_generators);
1424 poly next_p;
1425 int * gen_length=(int*)omAlloc0(IDELEMS(add_generators)*sizeof(int));
1426 int * secgen_length=(int*)omAlloc0(IDELEMS(syzstr->res[index])*sizeof(int));
1427 BOOLEAN pairs_left;
1428 SSet resPairs=(SSet)omAlloc0(l_pairs*sizeof(SObject));
1429
1430 for (j=IDELEMS(syzstr->res[index])-1;j>=0;j--)
1431 {
1432 if (syzstr->res[index]->m[j]!=NULL)
1433 secgen_length[j] = pLength(syzstr->res[index]->m[j]);
1434 }
1435 assume(idIs0(new_generators));
1436 next_place_add = IDELEMS(add_generators);
1437 while ((next_place_add>0) && (add_generators->m[next_place_add-1]==NULL))
1438 next_place_add--;
1439 int next_deg = p_FDeg(temp_generators->m[i],currRing);
1440 next_new_el = next_place_add;
1441/*--- loop about all all elements-----------------------------------*/
1442 while ((i<idel_temp) && (temp_generators->m[i]!=NULL))
1443 {
1444/*--- separates elements of equal degree----------------------------*/
1445#ifdef USE_REGULARITY
1446 if (syzstr->regularity>0)
1447 {
1448 if (next_deg >= syzstr->regularity+index)
1449 {
1450 while ((i<idel_temp) && (temp_generators->m[i]!=NULL))
1451 {
1452 pDelete(&temp_generators->m[i]);
1453 i++;
1454 }
1455 break;
1456 }
1457 }
1458#endif
1459 while ((i<idel_temp) && (p_FDeg(temp_generators->m[i],currRing)==next_deg))
1460 {
1461 next_p = temp_generators->m[i];
1462 temp_generators->m[i] = NULL;
1463 next_p = normalize(next_p,add_generators,syzstr,gen_length,&p_length,
1464 crit_comp);
1465 if (next_p!=NULL)
1466 {
1467 if (pGetComp(next_p)<=crit_comp)
1468 {
1469 pDelete(&next_p);
1470 //if (TEST_OPT_PROT) Print("u(%d)",index);
1471 }
1472 else
1473 {
1474 next_p = syRedTailSyz(next_p,add_generators,syzstr->res[index],crit_comp,syzstr,
1475 gen_length,secgen_length,&p_length);
1476 if (!nIsOne(pGetCoeff(next_p)))
1477 pNorm(next_p);
1478 if (next_place_add>=IDELEMS(add_generators))
1479 {
1480 pEnlargeSet(&add_generators->m,IDELEMS(add_generators),16);
1481 pEnlargeSet(&add_repr->m,IDELEMS(add_repr),16);
1482 gen_length = (int*)omRealloc0Size((ADDRESS)gen_length, IDELEMS(add_generators)*sizeof(int),
1483 (IDELEMS(add_generators)+16)*sizeof(int));
1484 IDELEMS(add_generators) += 16;
1485 IDELEMS(add_repr) += 16;
1486 }
1487 add_generators->m[next_place_add] = next_p;
1488 if (totake[index]==NULL)
1489 totake[index] = idInit(16,new_generators->rank);
1490 if ((*syzstr->Tl)[index]==IDELEMS(totake[index]))
1491 {
1492 pEnlargeSet(&totake[index]->m,IDELEMS(totake[index]),
1493 (*syzstr->Tl)[index]+16-IDELEMS(totake[index]));
1494 for (j=IDELEMS(totake[index]);j<(*syzstr->Tl)[index]+16;j++)
1495 totake[index]->m[j] = NULL;
1496 IDELEMS(totake[index]) = (*syzstr->Tl)[index]+16;
1497 }
1498#ifdef FULL_TOTAKE
1499 totake[index]->m[(*syzstr->Tl)[index]] = pCopy(next_p);
1500#else
1501 totake[index]->m[(*syzstr->Tl)[index]] = pHead(next_p);
1502#endif
1503 assume(add_repr->m[next_place_add]==NULL);
1504#ifdef WITH_SCHREYER_ORD
1505 add_repr->m[next_place_add] = pHead(add_generators->m[next_place_add]);
1506#else
1507 add_repr->m[next_place_add] = pOne();
1508#endif
1509 ((*syzstr->Tl)[index])++;
1510 pSetComp(add_repr->m[next_place_add],(*syzstr->Tl)[index]);
1511 pSetmComp(add_repr->m[next_place_add]);
1512 gen_length[next_place_add] = p_length;
1513 next_place_add++;
1514 }
1515 }
1516 i++;
1517 } //end inner loop
1518 red_deg = next_deg;
1519 if (i<idel_temp)
1520 next_deg = p_FDeg(temp_generators->m[i],currRing);
1521 else
1522 next_deg = -1;
1523 if ((next_place_add>next_new_el) || (next_deg<0)) //there are new generators or pairs
1524 {
1525/*-reducing and generating pairs until the degree of the next generators-*/
1526 pairs_left = TRUE;
1527 while (pairs_left && ((next_deg<0) || (red_deg<= next_deg)))
1528 {
1529 updatePairsHIndex(&resPairs,&l_pairs,syzstr,index,add_generators,
1530 add_repr,new_generators,new_repr,crit_comp,&next_new_el);
1531 pairs_left = reducePairsHIndex(resPairs,l_pairs,syzstr,index,add_generators,
1532 add_repr,new_generators,new_repr,crit_comp,&red_deg,&next_place_add,&gen_length,
1533 totake);
1534 }
1535 }
1536 }
1537 omFreeSize((SSet)resPairs,l_pairs*sizeof(SObject));
1538 omFreeSize((ADDRESS)gen_length,IDELEMS(add_generators)*sizeof(int));
1539 omFreeSize((ADDRESS)secgen_length,IDELEMS(syzstr->res[index])*sizeof(int));
1540}
1541
1542/*3
1543* normalizes the part of the next reduction lying within the block
1544* of former generators (old_generators);
1545*/
1546static ideal normalizeOldPart(ideal new_generators,ideal new_repr,
1547 syStrategy syzstr,int index,int /*crit_comp*/)
1548{
1549 ideal old_generators= syzstr->res[index];
1550 ideal old_repr= syzstr->orderedRes[index];
1551 int i,j=0,ii=IDELEMS(old_generators)-1,dummy;
1552 poly p;
1553 number n;
1554 int * g_l=(int*)omAlloc0(IDELEMS(old_generators)*sizeof(int));
1555
1556 for (i=0;i<IDELEMS(old_generators);i++)
1557 {
1558 if (old_generators->m[i]!=NULL)
1559 {
1560 g_l[i] = pLength(old_generators->m[i]);
1561 }
1562 }
1563 for (i=IDELEMS(new_generators)-1;i>=0;i--)
1564 {
1565 if (new_generators->m[i]!=NULL)
1566 {
1567 kBucketInit(syzstr->bucket,new_generators->m[i],
1568 pLength(new_generators->m[i]));
1569 kBucketInit(syzstr->syz_bucket,new_repr->m[i],
1570 pLength(new_repr->m[i]));
1571 p = kBucketGetLm(syzstr->bucket);
1572 loop
1573 {
1574 if ((j>=ii) || (p==NULL)) break;
1575 if ((old_generators->m[j]!=NULL) &&
1576 (pDivisibleBy(old_generators->m[j],p)))
1577 {
1578 sySPRedSyz_Kosz(syzstr,old_generators->m[j],old_repr->m[j],p);
1579 n = kBucketPolyRed(syzstr->bucket,old_generators->m[j], g_l[j],
1580 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 representations:\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 }
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 id_Shift(temp,1,currRing);
1792 }
1793 idSkipZeroes(temp);
1794#ifdef WITH_SORT
1795 if (temp->m[0]!=NULL)
1796 {
1797 int md;
1798 int maxdeg=p_FDeg(temp->m[IDELEMS(temp)-1],currRing);
1799 ideal temp1=idInit(IDELEMS(temp),temp->rank);
1800 for (j=IDELEMS(temp)-2;j>=0;j--)
1801 {
1802 jj = p_FDeg(temp->m[j],currRing);
1803 if (jj>maxdeg) maxdeg = jj;
1804 }
1805 while (!idIs0(temp))
1806 {
1807 md = maxdeg;
1808 for (j=IDELEMS(temp)-1;j>=0;j--)
1809 {
1810 if (temp->m[j]!=NULL)
1811 {
1812 jj = p_FDeg(temp->m[j],currRing);
1813 if (jj<md) md = jj;
1814 }
1815 }
1816 for (j=0;j<IDELEMS(temp);j++)
1817 {
1818 if ((temp->m[j]!=NULL) && (p_FDeg(temp->m[j],currRing)==md))
1819 {
1820 temp1->m[k] = temp->m[j];
1821 temp->m[j] = NULL;
1822 k++;
1823 }
1824 }
1825 }
1826 idDelete(&temp);
1827 temp = temp1;
1828 temp1 = NULL;
1829 }
1830#endif
1831#ifdef USE_REGULARITY
1832 int last_generator=IDELEMS(temp)-1;
1833 while ((last_generator>=0) && (temp->m[last_generator]==NULL))
1834 last_generator--;
1835#endif
1836 syzstr->res = (resolvente)omAlloc0((*length+1)*sizeof(ideal));
1837 syzstr->orderedRes = (resolvente)omAlloc0((*length+1)*sizeof(ideal));
1838 resolvente totake=(resolvente)omAlloc0((*length+1)*sizeof(ideal));
1839 syzstr->Tl = new intvec(*length+1);
1840 syzstr->bucket = kBucketCreate(currRing);
1842 ideal new_generators=idInit(1,si_max(rk_arg,1));
1843 ideal temp_gens,old_std;
1844 syzstr->res[0] = idInit(1,1);
1845 if (rk_arg>1) syzstr->res[0]->rank = rk_arg;
1846 syzstr->orderedRes[0] = idInit(1,1);
1847/*--- computes the resolution ----------------------*/
1848 i = 0;
1849 while (i<IDELEMS(temp))
1850 {
1851 if (temp->m[i]!=NULL)
1852 {
1853 new_generators->m[0] = kNF(syzstr->res[0],currRing->qideal,temp->m[i]);
1854 if (!nIsOne(pGetCoeff(new_generators->m[0])))
1855 pNorm(new_generators->m[0]);
1856 next_deg = p_FDeg(new_generators->m[0],currRing);
1857 next_gen = pCopy(new_generators->m[0]);
1858 }
1859 if (!idIs0(new_generators))
1860 {
1861 index = 0;
1862 while (index<=*length)
1863 {
1864 if (index==0)
1865 {
1866 old_ideal = idCopy(syzstr->res[0]);
1867 old_repr = idCopy(syzstr->orderedRes[0]);
1868 old_tl = (*syzstr->Tl)[0];
1869 old_std = id_Head(syzstr->res[0],currRing);
1870 }
1871 t_comp = (*syzstr->Tl)[index];
1872 if (index==0) crit_comp = t_comp;
1873 temp_gens = syAppendSyz(new_generators,syzstr, index,crit_comp,totake);
1874 crit_comp = t_comp;
1875 if (index==0)
1876 {
1877 isRegular = syIsRegular(old_std,syzstr->res[0],next_deg);
1878#ifndef ONLY_STD
1879 if (isRegular)
1880 syCreateRegularExtension(syzstr,old_ideal,old_repr,old_tl,next_gen,
1881 totake);
1882#ifdef USE_REGULARITY
1883 if ((index==0) && (!isRegular) && (i==last_generator))
1884 {
1885/*----------- we are computing the regularity -----------------------*/
1886 ideal initial=id_Head(syzstr->res[0],currRing);
1887 int len=0,reg=0;
1888 intvec *w=NULL;
1889 ring dp_C_ring = rAssure_dp_C(currRing); rChangeCurrRing(dp_C_ring);
1890 initial = idrMoveR_NoSort(initial, syzstr->syRing, dp_C_ring);
1892 intvec * dummy = syBetti(res,len,&reg, w);
1893 syzstr->regularity = reg+2;
1894 delete dummy;
1895 delete w;
1896 for (j=0;j<len;j++)
1897 {
1898 if (res[j]!=NULL) idDelete(&(res[j]));
1899 }
1900 omFreeSize((ADDRESS)res,len*sizeof(ideal));
1901 idDelete(&initial);
1902 rChangeCurrRing(syzstr->syRing);
1903 rDelete(dp_C_ring);
1904 }
1905#endif
1906#endif
1907 idDelete(&old_ideal);
1908 idDelete(&old_repr);
1909 idDelete(&old_std);
1910 if (TEST_OPT_PROT)
1911 {
1912 if (isRegular)
1913 PrintS("\n regular\n");
1914 else
1915 PrintS("\n not regular\n");
1916 }
1917 if (next_gen!=NULL)
1918 pDelete(&next_gen);
1919 if (isRegular)
1920 {
1921 idDelete(&temp_gens);
1922 break;
1923 }
1924 }
1925 idDelete(&new_generators);
1926 new_generators = temp_gens;
1927#ifdef ONLY_STD
1928 break;
1929#endif
1930 if (idIs0(new_generators)) break;
1931 index++;
1932 }
1933 if (!idIs0(new_generators))
1934 {
1935 for (j=0;j<IDELEMS(new_generators);j++)
1936 {
1937 if (new_generators->m[j]!=NULL)
1938 {
1939 pDelete(&new_generators->m[j]);
1940 new_generators->m[j] = NULL;
1941 }
1942 }
1943 }
1944 }
1945 i++;
1946 }
1947 if (idIs0(new_generators) && new_generators!=NULL) idDelete(&new_generators);
1948 if (temp!=NULL) idDelete(&temp);
1949 kBucketDestroy(&(syzstr->bucket));
1950 kBucketDestroy(&(syzstr->syz_bucket));
1951 index = 0;
1952 syzstr->fullres = syzstr->res;
1953 syzstr->res = NULL;
1954 index = 0;
1955 while ((index<=*length) && (syzstr->fullres[index]!=NULL))
1956 {
1957#ifdef SHOW_RESULT
1958 Print("The %d-th syzygy-module is now:\n",index);
1959 ideal ttt=id_Head(syzstr->fullres[index],currRing);
1960 idShow(ttt);
1961 idDelete(&ttt);
1962 //if (index>0)
1963 //{
1964 //Print("The related module is: \n");
1965 //idPrint(totake[index-1]);
1966 //}
1967 //Print("The %d-th module of the minimal resolution is:\n",index);
1968 if (!idIs0(totake[index]))
1969 idShow(totake[index]);
1970 //Print("with standard basis:\n");
1971 //idPrint(syzstr->fullres[index]);
1972 //if ((index<*length) && (totake[index+1]!=NULL))
1973 //{
1974 //Print("The %d-th syzygy-module is now:\n",index+1);
1975 //idPrint(totake[index+1]);
1976 //matrix m1=idModule2Matrix(totake[index]);
1977 //matrix m2=idModule2Matrix(totake[index+1]);
1978 //matrix m3=mpMult(m1,m2);
1979 //idPrint((ideal)m3);
1980 //}
1981#endif
1982 if (!idIs0(totake[index]))
1983 {
1984 for(i=0;i<IDELEMS(totake[index]);i++)
1985 {
1986 if (totake[index]->m[i]!=NULL)
1987 {
1988 j=0;
1989 while ((j<IDELEMS(syzstr->fullres[index])) &&
1990 ((syzstr->fullres[index]->m[j]==NULL) ||
1991 (!pLmEqual(syzstr->fullres[index]->m[j],totake[index]->m[i])))) j++;
1992 if (j<IDELEMS(syzstr->fullres[index]))
1993 {
1994 pDelete(&totake[index]->m[i]);
1995 totake[index]->m[i] = syzstr->fullres[index]->m[j];
1996 syzstr->fullres[index]->m[j] = NULL;
1997 }
1998 else
1999 {
2000 PrintS("Da ist was faul!!!\n");
2001 Print("Aber: Regularitaet %d, Grad %ld\n",
2002 syzstr->regularity,p_FDeg(totake[index]->m[i],currRing));
2003 }
2004 }
2005 }
2006 idDelete(&syzstr->fullres[index]);
2007 syzstr->fullres[index] = totake[index];
2008 }
2009#ifdef SHOW_RESULT
2010 idShow(syzstr->fullres[index]);
2011#endif
2012 index++;
2013 }
2014 syReorder_Kosz(syzstr);
2015 index = 0;
2016 while ((index<=*length) && (syzstr->orderedRes[index]!=NULL))
2017 {
2018 idDelete(&(syzstr->orderedRes[index]));
2019 index++;
2020 }
2021 if (origR!=syzstr->syRing)
2022 {
2023 rChangeCurrRing(origR);
2024 index = 0;
2025 while ((index<=*length) && (syzstr->fullres[index]!=NULL))
2026 {
2027 syzstr->fullres[index] = idrMoveR(syzstr->fullres[index],syzstr->syRing, origR);
2028 index++;
2029 }
2030 }
2031 delete syzstr->Tl;
2032 syzstr->Tl = NULL;
2033 rDelete(syzstr->syRing);
2034 syzstr->syRing = NULL;
2035 omFreeSize((ADDRESS)totake,(*length+1)*sizeof(ideal));
2036 omFreeSize((ADDRESS)syzstr->orderedRes,(*length+1)*sizeof(ideal));
2037//Print("Pairs to discard: %d\n",discard_pairs);
2038//Print("Pairs shorter reduced: %d\n",short_pairs);
2039//discard_pairs = 0;
2040//short_pairs = 0;
2041 return syzstr;
2042}
2043
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
void * ADDRESS
Definition: auxiliary.h:119
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4078
Definition: intvec.h:23
int length() const
Definition: intvec.h:94
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of 'a' and 'b' in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ,...
Definition: coeffs.h:661
#define Print
Definition: emacs.cc:80
return result
Definition: facAbsBiFact.cc:75
CanonicalForm res
Definition: facAbsFact.cc:60
const CanonicalForm & w
Definition: facAbsFact.cc:51
int j
Definition: facHensel.cc:110
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define VAR
Definition: globaldefs.h:5
intvec * hFirstSeries(ideal A, intvec *module_w, ideal Q, intvec *wdegree)
Definition: hilb.cc:2036
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
#define idPrint(id)
Definition: ideals.h:46
ideal idCopy(ideal A)
Definition: ideals.h:60
ideal * resolvente
Definition: ideals.h:18
poly initial(const poly p, const ring r, const gfan::ZVector &w)
Returns the initial form of p with respect to w.
Definition: initial.cc:30
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
STATIC_VAR Poly * h
Definition: janet.cc:971
KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether, ring r)
Definition: kInline.h:1196
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:521
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
Definition: kbuckets.cc:722
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:216
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:493
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:209
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition: kbuckets.cc:1071
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:506
poly p
Definition: kbuckets.h:186
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3182
void pairs()
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
#define assume(x)
Definition: mod2.h:389
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:44
#define nDiv(a, b)
Definition: numbers.h:32
#define nDelete(n)
Definition: numbers.h:16
#define nInpNeg(n)
Definition: numbers.h:21
#define nInvers(a)
Definition: numbers.h:33
#define nIsOne(n)
Definition: numbers.h:25
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define omRealloc0Size(addr, o_size, size)
Definition: omAllocDecl.h:221
#define NULL
Definition: omList.c:12
#define TEST_OPT_PROT
Definition: options.h:104
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition: p_polys.cc:4706
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3696
static int pLength(poly a)
Definition: p_polys.h:188
static long p_FDeg(const poly p, const ring r)
Definition: p_polys.h:378
#define __p_Mult_nn(p, n, r)
Definition: p_polys.h:969
void rChangeCurrRing(ring r)
Definition: polys.cc:15
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Compatibility layer for legacy polynomial operations (over currRing)
#define pAdd(p, q)
Definition: polys.h:203
#define pDelete(p_ptr)
Definition: polys.h:186
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition: polys.h:67
#define pSetm(p)
Definition: polys.h:271
#define pNeg(p)
Definition: polys.h:198
#define pLmEqual(p1, p2)
Definition: polys.h:111
#define pGetComp(p)
Component.
Definition: polys.h:37
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
void pNorm(poly p)
Definition: polys.h:362
#define pSub(a, b)
Definition: polys.h:287
#define ppMult_qq(p, q)
Definition: polys.h:208
#define pSetComp(p, v)
Definition: polys.h:38
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
#define pMult(p, q)
Definition: polys.h:207
void pWrite(poly p)
Definition: polys.h:308
#define pGetExp(p, i)
Exponent.
Definition: polys.h:41
#define pSetmComp(p)
TODO:
Definition: polys.h:273
#define pMult_mm(p, m)
Definition: polys.h:202
#define pDivisibleBy(a, b)
returns TRUE, if leading monom of a divides leading monom of b i.e., if there exists a expvector c > ...
Definition: polys.h:138
#define pSetExp(p, i, v)
Definition: polys.h:42
#define pMDivide(a, b)
Definition: polys.h:293
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185
#define pOne()
Definition: polys.h:315
poly * polyset
Definition: polys.h:259
#define pLcm(a, b, m)
Definition: polys.h:295
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
Definition: polys.h:142
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:248
ideal idrCopyR(ideal id, ring src_r, ring dest_r)
Definition: prCopy.cc:192
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:261
void PrintS(const char *s)
Definition: reporter.cc:284
void PrintLn()
Definition: reporter.cc:310
ring rAssure_C_dp(const ring r)
Definition: ring.cc:4985
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:450
ring rAssure_dp_C(const ring r)
Definition: ring.cc:4980
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
void idShow(const ideal id, const ring lmRing, const ring tailRing, const int debugPrint)
Definition: simpleideals.cc:57
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
void id_Shift(ideal M, int s, const ring r)
#define IDELEMS(i)
Definition: simpleideals.h:23
#define loop
Definition: structs.h:75
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
static ideal syAppendSyz(ideal new_generators, syStrategy syzstr, int index, int crit_comp, resolvente totake)
Definition: syz3.cc:1690
static void syCreateRegularExtension(syStrategy syzstr, ideal old_ideal, ideal old_repr, int old_tl, poly next_generator, resolvente totake)
Definition: syz3.cc:111
void syReorder_Kosz(syStrategy syzstr)
Definition: syz3.cc:261
static BOOLEAN syRedSyz(kBucket_pt bucket, ideal red, int crit_comp, int *g_l)
Definition: syz3.cc:487
static ideal normalizeOldPart(ideal new_generators, ideal new_repr, syStrategy syzstr, int index, int)
Definition: syz3.cc:1546
static void redOnePairHIndex(SSet resPairs, int itso, int crit_comp, syStrategy syzstr, int, ideal add_generators, ideal add_repr, ideal new_generators, ideal new_repr, int *next_place_add, int **g_l, poly deg_soc)
Definition: syz3.cc:1186
syStrategy syKosz(ideal arg, int *length)
Definition: syz3.cc:1766
static void syTestPairs(SSet resPairs, int length, ideal old_generators)
Definition: syz3.cc:239
static void redOnePair(SSet resPairs, int itso, int l, ideal syzygies, int crit_comp, syStrategy syzstr, int index, ideal new_generators, ideal new_repr, int *ogm_l, int *orp_l)
Definition: syz3.cc:650
static BOOLEAN reducePairsHIndex(SSet resPairs, int l_pairs, syStrategy syzstr, int index, ideal add_generators, ideal add_repr, ideal new_generators, ideal new_repr, int crit_comp, int *red_deg, int *next_place_add, int **g_l, resolvente totake)
Definition: syz3.cc:1378
static BOOLEAN redPairs(SSet resPairs, int l_pairs, ideal syzygies, ideal new_generators, ideal new_repr, int crit_comp, syStrategy syzstr, int index)
Definition: syz3.cc:939
VAR int short_pairs
Definition: syz3.cc:49
static void updatePairs(SSet *resPairs, int *l_pairs, syStrategy syzstr, int index, ideal new_generators, ideal new_repr, int crit_comp)
Definition: syz3.cc:307
static void updatePairsHIndex(SSet *resPairs, int *l_pairs, syStrategy, int index, ideal add_generators, ideal, ideal, ideal, int, int *first_new)
Definition: syz3.cc:1056
static void procedeNextGenerators(ideal temp_generators, ideal, ideal new_generators, ideal new_repr, ideal add_generators, ideal add_repr, syStrategy syzstr, int index, int crit_comp, resolvente totake)
Definition: syz3.cc:1415
void sySPRedSyz_Kosz(syStrategy syzstr, poly redWith, poly syz, poly q=NULL, int l_syz=-1)
Definition: syz3.cc:473
static ideal kosz_std(ideal new_generators, ideal new_repr, syStrategy syzstr, int index, int next_comp)
Definition: syz3.cc:1001
static poly syRedTailSyz(poly tored, ideal red, ideal sec_red, int crit_comp, syStrategy syzstr, int *gen_length, int *secgen_length, int *tored_length)
Definition: syz3.cc:514
VAR int discard_pairs
Definition: syz3.cc:48
static BOOLEAN syIsRegular(ideal old_ideal, ideal new_ideal, int deg)
Definition: syz3.cc:55
static ideal kosz_ext(ideal new_generators, ideal new_repr, syStrategy syzstr, int index, int next_comp, resolvente totake)
Definition: syz3.cc:1608
intvec * syBetti(resolvente res, int length, int *regularity, intvec *weights, BOOLEAN tomin, int *row_shift)
Definition: syz.cc:770
resolvente sySchreyerResolvente(ideal arg, int maxlength, int *length, BOOLEAN isMonomial=FALSE, BOOLEAN notReplace=FALSE)
Definition: syz0.cc:855
ring syRing
Definition: syz.h:56
void syCompactifyPairSet(SSet sPairs, int sPlength, int first)
Definition: syz1.cc:104
kBucket_pt syz_bucket
Definition: syz.h:55
resolvente res
Definition: syz.h:47
resolvente fullres
Definition: syz.h:57
intvec * Tl
Definition: syz.h:50
ssyStrategy * syStrategy
Definition: syz.h:36
resolvente orderedRes
Definition: syz.h:48
void syEnterPair(syStrategy syzstr, SObject *so, int *sPlength, int index)
Definition: syz1.cc:1035
void syInitializePair(SObject *so)
Definition: syz1.cc:63
int length
Definition: syz.h:60
int regularity
Definition: syz.h:61
kBucket_pt bucket
Definition: syz.h:54
void syDeletePair(SObject *so)
Definition: syz1.cc:44
SObject * SSet
Definition: syz.h:32