My Project
Loading...
Searching...
No Matches
syz.cc
Go to the documentation of this file.
1/****************************************
2* Computer Algebra System SINGULAR *
3****************************************/
4
5/*
6* ABSTRACT: resolutions
7*/
8
9#include "kernel/mod2.h"
10#include "misc/options.h"
11#include "kernel/polys.h"
15#include "misc/intvec.h"
16#include "coeffs/numbers.h"
17#include "kernel/ideals.h"
18#include "misc/intvec.h"
20#include "kernel/GBEngine/syz.h"
21#include "polys/prCopy.h"
22
23#include "polys/nc/sca.h"
24
26{
27 intvec *w1 = NULL;
28 int i;
30
31 if ((w==NULL) || (*w==NULL)) return w1;
32 int maxxx = (*w)->length();
33 if (maxxx==1)
34 {
35 maxxx = 2;
36 isIdeal = TRUE;
37 }
38 w1 = new intvec(maxxx+IDELEMS(arg));
39 if (!isIdeal)
40 {
41 for (i=0;i<maxxx;i++)
42 {
43 (*w1)[i] = (**w)[i];
44 }
45 }
46 for (i=maxxx;i<maxxx+IDELEMS(arg);i++)
47 {
48 if (arg->m[i-maxxx]!=NULL)
49 {
50 (*w1)[i] = p_FDeg(arg->m[i-maxxx],currRing);
51 if (pGetComp(arg->m[i-maxxx])!=0)
52 {
53 (*w1)[i]+=(**w)[pGetComp(arg->m[i-maxxx])-1];
54 }
55 }
56 }
57 delete (*w);
58 *w = new intvec(IDELEMS(arg)+1);
59 for (i=0;i<IDELEMS(arg);i++)
60 {
61 (**w)[i+1] = (*w1)[i+maxxx];
62 }
63 return w1;
64}
65
66static void syDeleteAbove(ideal up, int k)
67{
68 if (up!=NULL)
69 {
70 for (int i=0;i<IDELEMS(up);i++)
71 {
72 if (up->m[i]!=NULL)
73 pDeleteComp(&(up->m[i]),k+1);
74 }
75 }
76}
77
78/*2
79*minimizes the module mod and cancel superfluous syzygies
80*from syz
81*/
82static void syMinStep(ideal mod,ideal &syz,BOOLEAN final=FALSE,ideal up=NULL,
84{
85 poly Unit1,Unit2,actWith;
86 int len,i,j,ModComp,m,k,l;
88
89 if (TEST_OPT_PROT) PrintS("m");
90 if ((final) && (h==isHomog))
91 /*minim is TRUE, we are in the module: maxlength, maxlength <>0*/
92 {
94 id_Delete(&syz,currRing);
96 syz=deg0;
97 }
98/*--cancels empty entees and their related components above--*/
99 j = IDELEMS(syz);
100 while ((j>0) && (!syz->m[j-1])) j--;
101 k = 0;
102 while (k<j)
103 {
104 if (syz->m[k]!=NULL)
105 k++;
106 else
107 {
108 if (TEST_OPT_PROT) PrintS(".");
109 for (l=k;l<j-1;l++) syz->m[l] = syz->m[l+1];
110 syz->m[j-1] = NULL;
112 j--;
113 }
114 }
115/*--searches for syzygies coming from superfluous elements
116* in the module below--*/
121 while (searchUnit)
122 {
123 i=0;
124 j=IDELEMS(syz);
125 while ((j>0) && (syz->m[j-1]==NULL)) j--;
128 {
129 while ((i<j) && (!existsUnit))
130 {
132 i++;
133 }
134 }
135 else
136 {
137 int I=0;
138 l = 0;
139 len=0;
140 for (i=0;i<IDELEMS(syz);i++)
141 {
142 if (syz->m[i]!=NULL)
143 {
144 pVectorHasUnit(syz->m[i],&m, &l);
145 if ((len==0) ||((l>0) && (l<len)))
146 {
147 len = l;
148 ModComp = m;
149 I = i;
150 }
151 }
152 }
153//Print("Laenge ist: %d\n",len);
154 if (len>0) existsUnit = TRUE;
155 i = I+1;
156 }
157 if (existsUnit)
158 {
159 i--;
160//--takes out the founded syzygy--
161 if (TEST_OPT_PROT) PrintS("f");
162 actWith = syz->m[i];
164//Print("actWith: ");pWrite(actWith);
165 syz->m[i] = NULL;
166 for (k=i;k<j-1;k++) syz->m[k] = syz->m[k+1];
167 syz->m[j-1] = NULL;
169 j--;
170//--makes Gauss alg. for the column ModComp--
172//PrintS("actWith now: ");pWrite(actWith);
173//Print("Unit1: ");pWrite(Unit1);
174 k=0;
175//Print("j= %d",j);
176 while (k<j)
177 {
178 if (syz->m[k]!=NULL)
179 {
180 Unit2 = pTakeOutComp(&(syz->m[k]), ModComp);
181//Print("element %d: ",k);pWrite(syz->m[k]);
182//PrintS("Unit2: ");pWrite(Unit2);
183 syz->m[k] = pMult(pCopy(Unit1),syz->m[k]);
184 syz->m[k] = pSub(syz->m[k],
186 if (syz->m[k]==NULL)
187 {
188 for (l=k;l<j-1;l++)
189 syz->m[l] = syz->m[l+1];
190 syz->m[j-1] = NULL;
191 j--;
193 k--;
194 }
195 }
196 k++;
197 }
199 pDelete(&Unit1);
200//--deletes superfluous elements from the module below---
201 pDelete(&(mod->m[ModComp-1 - curr_syz_limit]));
202 for (k=ModComp-1 - curr_syz_limit;k<IDELEMS(mod)-1;k++)
203 mod->m[k] = mod->m[k+1];
204 mod->m[IDELEMS(mod)-1] = NULL;
205 }
206 else
208 }
209 if (TEST_OPT_PROT) PrintLn();
211 idSkipZeroes(syz);
212}
213
214/*2
215* make Gauss with the element elnum in the module component ModComp
216* for the generators from - till
217*/
218void syGaussForOne(ideal syz, int elnum, int ModComp,int from,int till)
219{
220 int /*k,j,i,*/lu;
221 poly unit1,unit2;
222 poly actWith=syz->m[elnum];
223
224 if (from<0) from = 0;
225 if ((till<=0) || (till>IDELEMS(syz))) till = IDELEMS(syz);
226 syz->m[elnum] = NULL;
228/*--makes Gauss alg. for the column ModComp--*/
230 while (from<till)
231 {
232 poly tmp=syz->m[from];
233 if (/*syz->m[from]*/ tmp!=NULL)
234 {
236 tmp = pMult(pCopy(unit1),tmp);
237 syz->m[from] = pSub(tmp,
239 }
240 from++;
241 }
243 pDelete(&unit1);
244}
245static void syDeleteAbove1(ideal up, int k)
246{
247 poly p/*,pp*/;
248 if (up!=NULL)
249 {
250 for (int i=0;i<IDELEMS(up);i++)
251 {
252 p = up->m[i];
253 while ((p!=NULL) && (pGetComp(p)==k))
254 {
255 /*
256 pp = pNext(p);
257 pNext(p) = NULL;
258 pDelete(&p);
259 p = pp;
260 */
261 pLmDelete(&p);
262 }
263 up->m[i] = p;
264 if (p!=NULL)
265 {
266 while (pNext(p)!=NULL)
267 {
268 if (pGetComp(pNext(p))==k)
269 {
270 /*
271 pp = pNext(pNext(p));
272 pNext(pNext(p)) = NULL;
273 pDelete(&pNext(p));
274 pNext(p) = pp;
275 */
276 pLmDelete(&pNext(p));
277 }
278 else
279 pIter(p);
280 }
281 }
282 }
283 }
284}
285/*2
286*minimizes the resolution res
287*assumes homogeneous or local case
288*/
290{
291 int i,j,k,index=0;
292 poly p;
294
295 while ((index<length) && (res[index]!=NULL))
296 {
297/*---we take out dependent elements from syz---------------------*/
298 if (res[index+1]!=NULL)
299 {
302 idDelete(&deg0);
304 for (i=0;i<IDELEMS(reddeg0);i++)
305 {
306 if (reddeg0->m[i]!=NULL)
307 {
308 j = pGetComp(reddeg0->m[i]);
309 pDelete(&(res[index]->m[j-1]));
310 /*res[index]->m[j-1] = NULL;*/
311 (*have_del)[j-1] = 1;
312 }
313 }
315 }
316 if (index>0)
317 {
318/*--- we search for units and perform Gaussian elimination------*/
319 j = to_del->length();
320 while (j>0)
321 {
322 if ((*to_del)[j-1]==1)
323 {
324 k = 0;
325 while (k<IDELEMS(res[index]))
326 {
327 p = res[index]->m[k];
328 while ((p!=NULL) && ((!pLmIsConstantComp(p)) || (pGetComp(p)!=j)))
329 pIter(p);
330 if ((p!=NULL) && (pLmIsConstantComp(p)) && (pGetComp(p)==j)) break;
331 k++;
332 }
333 if (k>=IDELEMS(res[index]))
334 {
335 PrintS("out of range\n");
336 }
338 if (res[index+1]!=NULL)
340 (*to_del)[j-1] = 0;
341 }
342 j--;
343 }
344 }
345 if (to_del!=NULL) delete to_del;
347 have_del = NULL;
348 index++;
349 }
350 if (TEST_OPT_PROT) PrintLn();
352 if (to_del!=NULL) delete to_del;
353}
354
356{
357 int syzIndex=first;
358 intvec *dummy;
359
360 if (syzIndex<1) syzIndex=1;
361 if ((syzIndex==1) && (!rIsPluralRing(currRing)) && (idHomModule(res[0],currRing->qideal,&dummy)))
362 {
364 delete dummy;
365 return;
366 }
367 while ((syzIndex<length-1) && (res[syzIndex]!=NULL) && (res[syzIndex+1]!=NULL))
368 {
370 syzIndex++;
371 }
372 if (res[syzIndex]!=NULL)
374 if (!idIs0(res[0]))
376}
377
378/*2
379* resolution of ideal/module arg, <=maxlength steps, (r[0..maxlength])
380* no limitation in length if maxlength==0
381* input:arg
382* minim: TRUE means mres cmd, FALSE nres cmd.
383* if *len!=0: module weights: weights[0]
384* (and weights is defined:weights[0..len-1]
385*
386* output:resolvente r[0..length-1],
387* module weights: weights[0..length-1]
388*/
390 intvec *** weights, BOOLEAN minim)
391{
396 intvec *w = NULL,**tempW;
397 int i,k,syzIndex = 0,j,rk_arg=si_max(1,(int)id_RankFreeModule(arg,currRing));
402 int wlength=*length;
403
404 if (maxlength!=-1) *length = maxlength+1;
405 else *length = 5;
406 if ((wlength!=0) && (*length!=wlength))
407 {
408 intvec **wtmp = (intvec**)omAlloc0((*length)*sizeof(intvec*));
409 wtmp[0]=(*weights)[0];
410 omFreeSize((ADDRESS)*weights,wlength*sizeof(intvec*));
411 *weights=wtmp;
412 }
414
415/*--- initialize the syzygy-ring -----------------------------*/
417 ring syz_ring = rAssure_SyzComp(origR, TRUE); // will do rChangeCurrRing if needed
419
420 if (syz_ring != origR)
421 {
423 res[0] = idrCopyR_NoSort(arg, origR, syz_ring);
424 }
425 else
426 {
427 res[0] = idCopy(arg);
428 }
429
430/*--- creating weights for the module components ---------------*/
431 if ((weights!=NULL) && (*weights!=NULL)&& ((*weights)[0]!=NULL))
432 {
433 if (!idTestHomModule(res[0],currRing->qideal,(*weights)[0]))
434 {
435 WarnS("wrong weights given(1):"); (*weights)[0]->show();PrintLn();
436 idHomModule(res[0],currRing->qideal,&w);
437 w->show();PrintLn();
438 *weights=NULL;
439 }
440 }
441
442 if ((weights==NULL) || (*weights==NULL) || ((*weights)[0]==NULL))
443 {
444 hom=(tHomog)idHomModule(res[0],currRing->qideal,&w);
445 if (hom==isHomog)
446 {
447 *weights = (intvec**)omAlloc0((*length)*sizeof(intvec*));
448 if (w!=NULL) (*weights)[0] = ivCopy(w);
449 }
450 }
451 else
452 {
453 if ((weights!=NULL) && (*weights!=NULL)&& ((*weights)[0]!=NULL))
454 {
455 w = ivCopy((*weights)[0]);
456 hom = isHomog;
457 }
458 }
459
460#ifdef HAVE_PLURAL
462 {
463// quick solution; need theory to apply homog GB stuff for G-Algebras
464 hom = isNotHomog;
465 }
466#endif // HAVE_PLURAL
467
468 if (hom==isHomog)
469 {
471 if (w!=NULL) { delete w;w=NULL; }
472 w = w1;
473 j = 0;
474 while ((j<IDELEMS(res[0])) && (res[0]->m[j]==NULL)) j++;
475 if (j<IDELEMS(res[0]))
476 {
477 if (p_FDeg(res[0]->m[j],currRing)!=pTotaldegree(res[0]->m[j]))
479 }
480 }
481 else
482 {
484 }
485
486/*--- the main loop --------------------------------------*/
487 while ((res[syzIndex]!=NULL) && (!idIs0(res[syzIndex])) &&
488 ((maxlength==-1) || (syzIndex<=maxlength)))
489 // (syzIndex<maxlength+(int)minim)))
490/*--- compute one step more for minimizing-----------------*/
491 {
492 if (Kstd1_deg!=0) Kstd1_deg++;
493 if (syzIndex+1==*length)
494 {
495 newres = (resolvente)omAlloc0((*length+5)*sizeof(ideal));
496 tempW = (intvec**)omAlloc0((*length+5)*sizeof(intvec*));
497 for (j=0;j<*length;j++)
498 {
499 newres[j] = res[j];
500 if (*weights!=NULL) tempW[j] = (*weights)[j];
501 /*else tempW[j] = NULL;*/
502 }
503 omFreeSize((ADDRESS)res,*length*sizeof(ideal));
504 if (*weights != NULL) omFreeSize((ADDRESS)*weights,*length*sizeof(intvec*));
505 *length += 5;
506 res=newres;
507 *weights = tempW;
508 }
509/*--- interreducing first -----------------------------------*/
510 if (syzIndex>0)
511 {
514 }
516 if (minim || (syzIndex!=0))
517 {
521 res[syzIndex] = temp;
522 }
523/*--- computing the syzygy modules --------------------------------*/
524 if ((currRing->qideal==NULL)&&(syzIndex==0)&& (!TEST_OPT_DEGBOUND))
525 {
526 res[/*syzIndex+*/1] = idSyzygies(res[0/*syzIndex*/],hom,&w,FALSE,setRegularity,&Kstd1_deg);
530 }
531 else
532 {
534 }
536 syzIndex++;
537 if (TEST_OPT_PROT) Print("[%d]\n",syzIndex);
538
540 {
541 if ((minim)||(syzIndex>1))
543 if (!completeMinim)
544 /*minim is TRUE, we are in the module: maxlength, maxlength <>0*/
545 {
547 }
548 }
549/*---creating the iterated weights for module components ---------*/
550 if ((hom == isHomog) && (res[syzIndex]!=NULL) && (!idIs0(res[syzIndex])))
551 {
552//Print("die %d Modulegewichte sind:\n",w1->length());
553//w1->show();
554//PrintLn();
557 assume(w != NULL);
558 if (w != NULL)
559 w->resize(max_comp+IDELEMS(res[syzIndex]));
560 else
562 (*weights)[syzIndex] = new intvec(k);
563 for (i=0;i<k;i++)
564 {
565 if (res[syzIndex-1]->m[i]!=NULL) // hs
566 {
568 if (pGetComp(res[syzIndex-1]->m[i])>0)
570 += (*w)[pGetComp(res[syzIndex-1]->m[i])-1];
571 (*((*weights)[syzIndex]))[i] = (*w)[i+rGetCurrSyzLimit(currRing)];
572 }
573 }
574 for (i=k;i<k+IDELEMS(res[syzIndex]);i++)
575 {
576 if (res[syzIndex]->m[i-k]!=NULL)
578 +(*w)[pGetComp(res[syzIndex]->m[i-k])-1];
579 }
580 }
581 }
582/*--- end of the main loop --------------------------------------*/
583/*--- deleting the temporare data structures --------------------*/
584 if ((syzIndex!=0) && (res[syzIndex]!=NULL) && (idIs0(res[syzIndex])))
586 if (w !=NULL) delete w;
587
589 if (!oldDegBound)
590 si_opt_1 &= ~Sy_bit(OPT_DEGBOUND);
591
592 for (i=1; i<=syzIndex; i++)
593 {
594 if ((res[i]!=NULL) && ! idIs0(res[i]))
595 {
597 res[i]->rank=idElem(res[i-1]);
598 }
599 }
600/*--- going back to the original ring -------------------------*/
601 if (origR != syz_ring)
602 {
603 rChangeCurrRing(origR); // should not be needed now?
604 for (i=0; i<=syzIndex; i++)
605 {
607 }
609 }
611 return res;
612}
613
615{
616
617#ifdef HAVE_PLURAL
618 const ideal idSaveCurrRingQuotient = currRing->qideal;
619 if( rIsSCA(currRing) )
620 {
622 {
623 currRing->qideal = SCAQuotient(currRing);
624 }
625 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
626 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
627 arg = id_KillSquares(arg, m_iFirstAltVar, m_iLastAltVar, currRing, false); // kill suares in input!
628 }
629#endif
630
632
633 if ((w!=NULL) && (!idTestHomModule(arg,currRing->qideal,w))) // is this right in SCA case???
634 {
635 WarnS("wrong weights given(2):");w->show();PrintLn();
636 idHomModule(arg,currRing->qideal,&w);
637 w->show();PrintLn();
638 w=NULL;
639 }
640 if (w!=NULL)
641 {
642 result->weights = (intvec**)omAlloc0Bin(char_ptr_bin);
643 (result->weights)[0] = ivCopy(w);
644 result->length = 1;
645 }
646 resolvente fr = syResolvente(arg,maxlength,&(result->length),&(result->weights),minim);
648 if (minim)
649 {
650 result->minres = (resolvente)omAlloc0((result->length+1)*sizeof(ideal));
651 fr1 = result->minres;
652 }
653 else
654 {
655 result->fullres = (resolvente)omAlloc0((result->length+1)*sizeof(ideal));
656 fr1 = result->fullres;
657 }
658 for (int i=result->length-1;i>=0;i--)
659 {
660 if (fr[i]!=NULL)
661 fr1[i] = fr[i];
662 fr[i] = NULL;
663 }
664 omFreeSize((ADDRESS)fr,(result->length)*sizeof(ideal));
665
666#ifdef HAVE_PLURAL
667 if( rIsSCA(currRing) )
668 {
670 {
672 }
673 id_Delete(&arg, currRing);
674 }
675#endif
676
677 return result;
678}
679
680static poly sypCopyConstant(poly inp)
681{
682 poly outp=NULL,q;
683
684 while (inp!=NULL)
685 {
687 {
688 if (outp==NULL)
689 {
690 q = outp = pHead(inp);
691 }
692 else
693 {
694 pNext(q) = pHead(inp);
695 pIter(q);
696 }
697 }
698 pIter(inp);
699 }
700 return outp;
701}
702int syDetect(ideal id,int index,BOOLEAN homog,int * degrees,int * tocancel)
703{
704 int i, j, k, subFromRank=0;
705 ideal temp;
706
707 if (idIs0(id)) return 0;
708 temp = idInit(IDELEMS(id),id->rank);
709 for (i=0;i<IDELEMS(id);i++)
710 {
711 temp->m[i] = sypCopyConstant(id->m[i]);
712 }
713 i = IDELEMS(id);
714 while ((i>0) && (temp->m[i-1]==NULL)) i--;
715 if (i==0)
716 {
717 idDelete(&temp);
718 return 0;
719 }
720 j = 0;
721 while ((j<i) && (temp->m[j]==NULL)) j++;
722 while (j<i)
723 {
724 if (homog)
725 {
726 if (index==0) k = p_FDeg(temp->m[j],currRing)+degrees[pGetComp(temp->m[j])];
727 else k = degrees[pGetComp(temp->m[j])];
728 if (k>=index) tocancel[k-index]++;
729 if ((k>=0) && (index==0)) subFromRank++;
730 }
731 else
732 {
733 tocancel[0]--;
734 }
736 j++;
737 while ((j<i) && (temp->m[j]==NULL)) j++;
738 }
739 idDelete(&temp);
740 return subFromRank;
741}
742
743void syDetect(ideal id,int index,int rsmin, BOOLEAN homog,
745{
746 int * deg=NULL;
747 int * tocan=(int*) omAlloc0(tocancel->length()*sizeof(int));
748 int i;
749
750 if (homog)
751 {
752 deg = (int*) omAlloc0(degrees->length()*sizeof(int));
753 for (i=degrees->length();i>0;i--)
754 deg[i-1] = (*degrees)[i-1]-rsmin;
755 }
756 syDetect(id,index,homog,deg,tocan);
757 for (i=tocancel->length();i>0;i--)
758 (*tocancel)[i-1] = tocan[i-1];
759 if (homog)
760 omFreeSize((ADDRESS)deg,degrees->length()*sizeof(int));
761 omFreeSize((ADDRESS)tocan,tocancel->length()*sizeof(int));
762}
763
764/*2
765* computes the betti numbers from a given resolution
766* of length 'length' (0..length-1), not necessairily minimal,
767* (if weights are given, they are used)
768* returns the int matrix of betti numbers
769* and the regularity
770*/
771intvec * syBetti(resolvente res,int length, int * regularity,
772 intvec* weights,BOOLEAN tomin,int * row_shift)
773{
774//#define BETTI_WITH_ZEROS
775 //tomin = FALSE;
776 int i,j=0,k=0,l,rows,cols,mr;
777 int *temp1,*temp2,*temp3;/*used to compute degrees*/
778 int *tocancel; /*(BOOLEAN)tocancel[i]=element is superfluous*/
779 int r0_len;
780
781 /*------ compute size --------------*/
782 *regularity = -1;
783 cols = length;
784 while ((cols>0)
785 && ((res[cols-1]==NULL)
786 || (idIs0(res[cols-1]))))
787 {
788 cols--;
789 }
790 intvec * result;
791 if (idIs0(res[0]))
792 {
793 if (res[0]==NULL)
794 result = new intvec(1,1,1);
795 else
796 result = new intvec(1,1,res[0]->rank);
797 return result;
798 }
799 intvec *w=NULL;
800 if (weights!=NULL)
801 {
802 if (!idTestHomModule(res[0],currRing->qideal,weights))
803 {
804 WarnS("wrong weights given(3):");weights->show();PrintLn();
805 idHomModule(res[0],currRing->qideal,&w);
806 if (w!=NULL) { w->show();PrintLn();}
807 weights=NULL;
808 }
809 }
810#if 0
811 if (idHomModule(res[0],currRing->qideal,&w)!=isHomog)
812 {
813 WarnS("betti-command: Input is not homogeneous!");
814 weights=NULL;
815 }
816#endif
817 if (weights==NULL) weights=w;
818 else delete w;
819 r0_len=IDELEMS(res[0]);
820 while ((r0_len>0) && (res[0]->m[r0_len-1]==NULL)) r0_len--;
821 #ifdef SHOW_W
822 PrintS("weights:");if (weights!=NULL) weights->show(); else Print("NULL"); PrintLn();
823 #endif
824 int rkl=l = si_max(id_RankFreeModule(res[0],currRing),res[0]->rank);
825 i = 0;
826 while ((i<length) && (res[i]!=NULL))
827 {
828 if (IDELEMS(res[i])>l) l = IDELEMS(res[i]);
829 i++;
830 }
831 temp1 = (int*)omAlloc0((l+1)*sizeof(int));
832 temp2 = (int*)omAlloc((l+1)*sizeof(int));
833 rows = 1;
834 mr = 1;
835 cols++;
836 for (i=0;i<cols-1;i++)
837 {
838 if ((i==0) && (weights!=NULL)) p_SetModDeg(weights, currRing);
839 memset(temp2,0,(l+1)*sizeof(int));
840 for (j=0;j<IDELEMS(res[i]);j++)
841 {
842 if (res[i]->m[j]!=NULL)
843 {
844 if ((pGetComp(res[i]->m[j])>l)
845 // usual resolutions do not the following, but artifulal built may: (tr. #763)
846 //|| ((i>1) && (res[i-1]->m[pGetComp(res[i]->m[j])-1]==NULL))
847 )
848 {
849 WerrorS("input not a resolution");
850 omFreeSize((ADDRESS)temp1,(l+1)*sizeof(int));
851 omFreeSize((ADDRESS)temp2,(l+1)*sizeof(int));
852 return NULL;
853 }
854 temp2[j+1] = p_FDeg(res[i]->m[j],currRing)+temp1[pGetComp(res[i]->m[j])];
855 if (temp2[j+1]-i>rows) rows = temp2[j+1]-i;
856 if (temp2[j+1]-i<mr) mr = temp2[j+1]-i;
857 }
858 }
859 if ((i==0) && (weights!=NULL)) p_SetModDeg(NULL, currRing);
860 temp3 = temp1;
861 temp1 = temp2;
862 temp2 = temp3;
863 }
864 mr--;
865 if (weights!=NULL)
866 {
867 for(j=0;j<weights->length();j++)
868 {
869 if (rows <(*weights)[j]+1) rows=(-mr)+(*weights)[j]+1;
870 }
871 }
872 /*------ computation betti numbers --------------*/
873 rows -= mr;
874 result = new intvec(rows+1,cols,0);
875 if (weights!=NULL)
876 {
877 for(j=0;j<weights->length();j++)
878 {
879 IMATELEM((*result),(-mr)+(*weights)[j]+1,1) ++;
880 //Print("imat(%d,%d)++ -> %d\n",(-mr)+(*weights)[j]+1, 1, IMATELEM((*result),(-mr)+(*weights)[j]+1,1));
881 }
882 }
883 else
884 {
885 (*result)[(-mr)*cols] = /*idRankFreeModule(res[0])*/ rkl;
886 if ((!idIs0(res[0])) && ((*result)[(-mr)*cols]==0))
887 (*result)[(-mr)*cols] = 1;
888 }
889 tocancel = (int*)omAlloc0((rows+1)*sizeof(int));
890 memset(temp1,0,(l+1)*sizeof(int));
891 if (weights!=NULL)
892 {
893 memset(temp2,0,l*sizeof(int));
894 p_SetModDeg(weights, currRing);
895 }
896 else
897 memset(temp2,0,l*sizeof(int));
899 if (weights!=NULL) p_SetModDeg(NULL, currRing);
900 if (tomin)
901 {
902 //(*result)[(-mr)*cols] -= dummy;
903 for(j=0;j<=rows+mr;j++)
904 {
905 //Print("tocancel[%d]=%d imat(%d,%d)=%d\n",j,tocancel[j],(-mr)+j+1,1,IMATELEM((*result),(-mr)+j+1,1));
906 IMATELEM((*result),(-mr)+j+1,1) -= tocancel[j];
907 }
908 }
909 for (i=0;i<cols-1;i++)
910 {
911 if ((i==0) && (weights!=NULL)) p_SetModDeg(weights, currRing);
912 memset(temp2,0,l*sizeof(int));
913 for (j=0;j<IDELEMS(res[i]);j++)
914 {
915 if (res[i]->m[j]!=NULL)
916 {
917 temp2[j+1] = p_FDeg(res[i]->m[j],currRing)+temp1[pGetComp(res[i]->m[j])];
918 //(*result)[i+1+(temp2[j+1]-i-1)*cols]++;
919 //if (temp2[j+1]>i) IMATELEM((*result),temp2[j+1]-i-mr,i+2)++;
920 IMATELEM((*result),temp2[j+1]-i-mr,i+2)++;
921 }
922 else if (i==0)
923 {
924 if (j<r0_len) IMATELEM((*result),-mr,2)++;
925 }
926 }
927 /*------ computation betti numbers, if res not minimal --------------*/
928 if (tomin)
929 {
930 for (j=mr;j<rows+mr;j++)
931 {
932 //(*result)[i+1+j*cols] -= tocancel[j+1];
933 IMATELEM((*result),j+1-mr,i+2) -= tocancel[j+1];
934 }
935 if ((i<length-1) && (res[i+1]!=NULL))
936 {
937 memset(tocancel,0,(rows+1)*sizeof(int));
939 for (j=0;j<rows;j++)
940 {
941 //(*result)[i+1+j*cols] -= tocancel[j];
942 IMATELEM((*result),j+1,i+2) -= tocancel[j];
943 }
944 }
945 }
946 temp3 = temp1;
947 temp1 = temp2;
948 temp2 = temp3;
949 for (j=0;j<=rows;j++)
950 {
951 // if (((*result)[i+1+j*cols]!=0) && (j>*regularity)) *regularity = j;
952 if ((IMATELEM((*result),j+1,i+2)!=0) && (j>*regularity)) *regularity = j;
953 }
954 if ((i==0) && (weights!=NULL)) p_SetModDeg(NULL, currRing);
955 }
956 // Print("nach minim:\n"); result->show(); PrintLn();
957 /*------ clean up --------------*/
958 omFreeSize((ADDRESS)tocancel,(rows+1)*sizeof(int));
959 omFreeSize((ADDRESS)temp1,(l+1)*sizeof(int));
960 omFreeSize((ADDRESS)temp2,(l+1)*sizeof(int));
961 if ((tomin) && (mr<0)) // deletes the first (zero) line
962 {
963 for (j=1;j<=rows+mr+1;j++)
964 {
965 for (k=1;k<=cols;k++)
966 {
967 IMATELEM((*result),j,k) = IMATELEM((*result),j-mr,k);
968 }
969 }
970 for (j=rows+mr+1;j<=rows+1;j++)
971 {
972 for (k=1;k<=cols;k++)
973 {
974 IMATELEM((*result),j,k) = 0;
975 }
976 }
977 }
978 j = 0;
979 k = 0;
980 for (i=1;i<=result->rows();i++)
981 {
982 for(l=1;l<=result->cols();l++)
983 if (IMATELEM((*result),i,l) != 0)
984 {
985 j = si_max(j, i-1);
986 k = si_max(k, l-1);
987 }
988 }
989 intvec * exactresult=new intvec(j+1,k+1,0);
990 for (i=0;i<exactresult->rows();i++)
991 {
992 for (j=0;j<exactresult->cols();j++)
993 {
994 IMATELEM(*exactresult,i+1,j+1) = IMATELEM(*result,i+1,j+1);
995 }
996 }
997 if (row_shift!=NULL) *row_shift = mr;
998 delete result;
999 return exactresult;
1000}
1001
1002/*2
1003* minbare via syzygies
1004*/
1006{
1007 intvec ** weights=NULL;
1008 int leng;
1009 if (idIs0(arg)) return idInit(1,arg->rank);
1010 resolvente res=syResolvente(arg,1,&leng,&weights,TRUE);
1011 ideal result=res[0];
1012 omFreeSize((ADDRESS)res,leng*sizeof(ideal));
1013 if (weights!=NULL)
1014 {
1015 if (*weights!=NULL)
1016 {
1017 delete (*weights);
1018 *weights=NULL;
1019 }
1020 if ((leng>=1) && (*(weights+1)!=NULL))
1021 {
1022 delete *(weights+1);
1023 *(weights+1)=NULL;
1024 }
1025 }
1027 return result;
1028}
1029
1030#if 0 /* currently used: syBetti */
1031/*2
1032* computes Betti-numbers from a resolvente of
1033* (non-)homogeneous objects
1034* the numbers of entrees !=NULL in res and weights must be equal
1035* and < length
1036*/
1037intvec * syNewBetti(resolvente res, intvec ** weights, int length)
1038{
1040 int i,j,k,rsmin=0,rsmax=0,rs=0;
1041 BOOLEAN homog=TRUE;
1042
1043 if (weights!=NULL) //---homogeneous Betti numbers
1044 {
1045/*--------------computes size of the field----------------------*/
1046 for (i=1;i<length;i++)
1047 {
1048 if (weights[i] != NULL)
1049 {
1050 for (j=1;j<(weights[i])->length();j++)
1051 {
1052 if ((*(weights[i]))[j]-i<rsmin) rsmin = (*(weights[i]))[j]-i;
1053 if ((*(weights[i]))[j]-i>rsmax) rsmax = (*(weights[i]))[j]-i;
1054 }
1055 }
1056 }
1057 i = 0;
1058 while (weights[i] != NULL) i++;
1059 i--;
1060 for (j=0;j<IDELEMS(res[i]);j++)
1061 {
1062 if (res[i]->m[j]!=NULL)
1063 {
1064 k = p_FDeg(res[i]->m[j],currRing)+(*(weights[i]))[pGetComp(res[i]->m[j])]-i-1;
1065 if (k>rsmax) rsmax = k;
1066 if (k<rsmin) rsmin = k;
1067 }
1068 }
1069 for (j=1;j<(weights[0])->length();j++)
1070 {
1071 if ((*weights[0])[j]>rsmax) rsmax = (*weights[0])[j];
1072 if ((*weights[0])[j]<rsmin) rsmin = (*weights[0])[j];
1073 }
1074//Print("rsmax = %d\n",rsmax);
1075//Print("rsmin = %d\n",rsmin);
1076 rs = rsmax-rsmin+1;
1077 result = new intvec(rs,i+2,0);
1078 tocancel = new intvec(rs);
1079/*-----------enter the Betti numbers-------------------------------*/
1080 if (/*idRankFreeModule(res[0])*/ res[0]->rank==0)
1081 {
1082 IMATELEM(*result,1-rsmin,1)=1;
1083 }
1084 else
1085 {
1086 for (i=1;i<(weights[0])->length();i++)
1087 IMATELEM(*result,(*weights[0])[i]+1-rsmin,1)++;
1088 }
1089 i = 1;
1090 while (weights[i]!=NULL)
1091 {
1092 for (j=1;j<(weights[i])->length();j++)
1093 {
1094 IMATELEM(*result,(*(weights[i]))[j]-i+1-rsmin,i+1)++;
1095 }
1096 i++;
1097 }
1098 i--;
1099 for (j=0;j<IDELEMS(res[i]);j++)
1100 {
1101 if (res[i]->m[j]!=NULL)
1102 {
1103 k = p_FDeg(res[i]->m[j],currRing)+(*(weights[i]))[pGetComp(res[i]->m[j])]-i;
1104 IMATELEM(*result,k-rsmin,i+2)++;
1105 }
1106 }
1107 }
1108 else //-----the non-homgeneous case
1109 {
1110 homog = FALSE;
1111 tocancel = new intvec(1);
1112 k = length;
1113 while ((k>0) && (idIs0(res[k-1]))) k--;
1114 result = new intvec(1,k+1,0);
1115 (*result)[0] = res[0]->rank;
1116 for (i=0;i<length;i++)
1117 {
1118 if (res[i]!=NULL)
1119 {
1120 for (j=0;j<IDELEMS(res[i]);j++)
1121 {
1122 if (res[i]->m[j]!=NULL) (*result)[i+1]++;
1123 }
1124 }
1125 }
1126 }
1127/*--------computes the Betti numbers for the minimized reolvente----*/
1128
1129 i = 1;
1130 while ((res[i]!=NULL) && (weights[i]!=NULL))
1131 {
1132 syDetect(res[i],i,rsmin,homog,weights[i],tocancel);
1133 if (homog)
1134 {
1135 for (j=0;j<rs-1;j++)
1136 {
1137 IMATELEM((*result),j+1,i+1) -= (*tocancel)[j];
1138 IMATELEM((*result),j+1,i+2) -= (*tocancel)[j+1];
1139 }
1140 IMATELEM((*result),rs,i+1) -= (*tocancel)[rs-1];
1141 }
1142 else
1143 {
1144 (*result)[i+1] -= (*tocancel)[0];
1145 (*result)[i+2] -= (*tocancel)[0];
1146 }
1147 i++;
1148 }
1149
1150/*--------print Betti numbers for control---------------------------*/
1151 for(i=rsmin;i<=rsmax;i++)
1152 {
1153 Print("%2d:",i);
1154 for(j=1;j<=result->cols();j++)
1155 {
1156 Print(" %5d",IMATELEM(*result,i-rsmin+1,j));
1157 }
1158 PrintLn();
1159 }
1160 return result;
1161}
1162#endif
1163
1165{
1167 ideal *r=res->minres;
1168 if (r==NULL) r=res->fullres;
1169 trans=idLift(arg,r[0],NULL,TRUE,FALSE,FALSE,NULL);
1170 return res;
1171}
1172
1174{
1175 ideal *r=res->minres;
1176 if (r==NULL) r=res->fullres;
1177 ideal org=idCopy(r[0]);
1179 r=res->minres;
1180 if (r==NULL) r=res->fullres;
1182}
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
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition cf_ops.cc:493
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
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
int length() const
void show(int mat=0, int spaces=0) const
Definition intvec.cc:149
int length() const
Definition intvec.h:94
#define Print
Definition emacs.cc:80
#define WarnS
Definition emacs.cc:78
return result
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
ideal idSyzygies(ideal h1, tHomog h, intvec **w, BOOLEAN setSyzComp, BOOLEAN setRegularity, int *deg, GbVariant alg)
Definition ideals.cc:830
BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
Definition ideals.cc:2077
ideal idLift(ideal mod, ideal submod, ideal *rest, BOOLEAN goodShape, BOOLEAN isSB, BOOLEAN divide, matrix *unit, GbVariant alg)
represents the generators of submod in terms of the generators of mod (Matrix(SM)*U-Matrix(rest)) = M...
Definition ideals.cc:1105
ideal idMinEmbedding(ideal arg, BOOLEAN inPlace, intvec **w)
Definition ideals.cc:2731
#define idDelete(H)
delete an ideal
Definition ideals.h:29
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition ideals.h:96
ideal idCopy(ideal A)
Definition ideals.h:60
ideal * resolvente
Definition ideals.h:18
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
intvec * ivCopy(const intvec *o)
Definition intvec.h:145
#define IMATELEM(M, I, J)
Definition intvec.h:85
STATIC_VAR Poly * h
Definition janet.cc:971
ideal kInterRedOld(ideal F, const ideal Q)
Definition kstd1.cc:3462
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:50
static bool rIsSCA(const ring r)
Definition nc.h:190
bool ncExtensions(int iMask)
Definition old.gring.cc:94
const int TESTSYZSCAMASK
Definition nc.h:338
ideal id_KillSquares(const ideal id, const short iFirstAltVar, const short iLastAltVar, const ring r, const bool bSkipZeroes)
Definition sca.cc:1518
#define assume(x)
Definition mod2.h:389
#define pIter(p)
Definition monomials.h:37
#define pNext(p)
Definition monomials.h:36
#define omFreeSize(addr, size)
#define omAlloc(size)
#define omAlloc0Bin(bin)
#define omAlloc0(size)
#define NULL
Definition omList.c:12
VAR unsigned si_opt_1
Definition options.c:5
#define SI_SAVE_OPT1(A)
Definition options.h:21
#define SI_RESTORE_OPT1(A)
Definition options.h:24
#define Sy_bit(x)
Definition options.h:31
#define TEST_OPT_DEGBOUND
Definition options.h:113
#define TEST_OPT_NOTREGULARITY
Definition options.h:120
#define TEST_OPT_PROT
Definition options.h:103
#define OPT_DEGBOUND
Definition options.h:90
#define TEST_OPT_NO_SYZ_MINIM
Definition options.h:124
static int index(p_Length length, p_Ord ord)
poly p_Cleardenom(poly p, const ring r)
Definition p_polys.cc:2845
void p_SetModDeg(intvec *w, ring r)
Definition p_polys.cc:3673
static long p_FDeg(const poly p, const ring r)
Definition p_polys.h:380
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)
static long pTotaldegree(poly p)
Definition polys.h:282
#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 pLmIsConstantComp(p)
like above, except that p must be != NULL
Definition polys.h:242
#define pDeleteComp(p, k)
Definition polys.h:360
#define pGetComp(p)
Component.
Definition polys.h:37
#define pSub(a, b)
Definition polys.h:287
#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
#define pVectorHasUnitB(p, k)
Definition polys.h:332
void pTakeOutComp(poly *p, long comp, poly *q, int *lq, const ring R=currRing)
Splits *p into two polys: *q which consists of all monoms with component == comp and *p of all other ...
Definition polys.h:338
#define pCopy(p)
return a copy of the poly
Definition polys.h:185
#define pVectorHasUnit(p, k, l)
Definition polys.h:333
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition prCopy.cc:261
ideal idrCopyR_NoSort(ideal id, ring src_r, ring dest_r)
Definition prCopy.cc:205
void PrintS(const char *s)
Definition reporter.cc:284
void PrintLn()
Definition reporter.cc:310
ring rAssure_SyzComp(const ring r, BOOLEAN complete)
Definition ring.cc:4449
int rGetMaxSyzComp(int i, const ring r)
return the max-comonent wchich has syzIndex i Assume: i<= syzIndex_limit
Definition ring.cc:5224
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:450
void rSetSyzComp(int k, const ring r)
Definition ring.cc:5152
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:400
static int rGetCurrSyzLimit(const ring r)
Definition ring.h:723
BOOLEAN rHasGlobalOrdering(const ring r)
Definition ring.h:761
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition ring.h:548
#define rField_is_Ring(R)
Definition ring.h:485
ideal SCAQuotient(const ring r)
Definition sca.h:10
static short scaLastAltVar(ring r)
Definition sca.h:25
static short scaFirstAltVar(ring r)
Definition sca.h:18
ideal idInit(int idsize, int rank)
initialise an ideal / module
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
ideal id_Jet(const ideal i, int d, const ring R)
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)
static int idElem(const ideal F)
number of non-zero polys in F
tHomog
Definition structs.h:35
@ isHomog
Definition structs.h:37
@ isNotHomog
Definition structs.h:36
#define BITSET
Definition structs.h:16
EXTERN_VAR omBin char_ptr_bin
Definition structs.h:77
int syDetect(ideal id, int index, BOOLEAN homog, int *degrees, int *tocancel)
Definition syz.cc:702
resolvente syResolvente(ideal arg, int maxlength, int *length, intvec ***weights, BOOLEAN minim)
Definition syz.cc:389
syStrategy syMres_with_map(ideal arg, int maxlength, intvec *w, ideal &trans)
Definition syz.cc:1164
syStrategy syResolution(ideal arg, int maxlength, intvec *w, BOOLEAN minim)
Definition syz.cc:614
static poly sypCopyConstant(poly inp)
Definition syz.cc:680
static void syMinStep1(resolvente res, int length)
Definition syz.cc:289
static void syMinStep(ideal mod, ideal &syz, BOOLEAN final=FALSE, ideal up=NULL, tHomog h=isNotHomog)
Definition syz.cc:82
ideal syMinBase(ideal arg)
Definition syz.cc:1005
static intvec * syPrepareModComp(ideal arg, intvec **w)
Definition syz.cc:25
void syMinimize_with_map(syStrategy res, ideal &trans)
Definition syz.cc:1173
void syGaussForOne(ideal syz, int elnum, int ModComp, int from, int till)
Definition syz.cc:218
static void syDeleteAbove1(ideal up, int k)
Definition syz.cc:245
static void syDeleteAbove(ideal up, int k)
Definition syz.cc:66
intvec * syBetti(resolvente res, int length, int *regularity, intvec *weights, BOOLEAN tomin, int *row_shift)
Definition syz.cc:771
void syMinimizeResolvente(resolvente res, int length, int first)
Definition syz.cc:355
syStrategy syMinimize(syStrategy syzstr)
Definition syz1.cc:2392
void syKillEmptyEntres(resolvente res, int length)
Definition syz1.cc:2198
ssyStrategy * syStrategy
Definition syz.h:36