My Project
Loading...
Searching...
No Matches
ideals.cc
Go to the documentation of this file.
1/****************************************
2* Computer Algebra System SINGULAR *
3****************************************/
4/*
5* ABSTRACT - all basic methods to manipulate ideals
6*/
7
8/* includes */
9
10#include "kernel/mod2.h"
11
12#include "misc/options.h"
13#include "misc/intvec.h"
14
15#include "coeffs/coeffs.h"
16#include "coeffs/numbers.h"
17// #include "coeffs/longrat.h"
18
19
21#include "polys/matpol.h"
22#include "polys/weight.h"
23#include "polys/sparsmat.h"
24#include "polys/prCopy.h"
25#include "polys/nc/nc.h"
26
27
28#include "kernel/ideals.h"
29
30#include "kernel/polys.h"
31
34#include "kernel/GBEngine/tgb.h"
35#include "kernel/GBEngine/syz.h"
36#include "Singular/ipshell.h" // iiCallLibProc1
37#include "Singular/ipid.h" // ggetid
38
39
40#if 0
41#include "Singular/ipprint.h" // ipPrint_MA0
42#endif
43
44/* #define WITH_OLD_MINOR */
45
46/*0 implementation*/
47
48/*2
49*returns a minimized set of generators of h1
50*/
51ideal idMinBase (ideal h1, ideal *SB)
52{
53 ideal h2, h3,h4,e;
54 int j,k;
55 int i,l,ll;
56 intvec * wth;
57 BOOLEAN homog;
59 {
60 WarnS("minbase applies only to the local or homogeneous case over coefficient fields");
61 e=idCopy(h1);
62 return e;
63 }
64 homog = idHomModule(h1,currRing->qideal,&wth);
66 {
67 if(!homog)
68 {
69 WarnS("minbase applies only to the local or homogeneous case over coefficient fields");
70 e=idCopy(h1);
71 return e;
72 }
73 else
74 {
75 ideal re=kMin_std(h1,currRing->qideal,(tHomog)homog,&wth,h2,NULL,0,3);
76 idDelete(&re);
77 return h2;
78 }
79 }
80 e=idInit(1,h1->rank);
81 if (idIs0(h1))
82 {
83 return e;
84 }
85 h2 = kStd(h1,currRing->qideal,isNotHomog,NULL);
86 if (SB!=NULL) *SB=h2;
87 h3 = idMaxIdeal(1);
88 h4=idMult(h2,h3);
89 idDelete(&h3);
90 h3=kStd(h4,currRing->qideal,isNotHomog,NULL);
91 k = IDELEMS(h3);
92 while ((k > 0) && (h3->m[k-1] == NULL)) k--;
93 j = -1;
94 l = IDELEMS(h2);
95 while ((l > 0) && (h2->m[l-1] == NULL)) l--;
96 for (i=l-1; i>=0; i--)
97 {
98 if (h2->m[i] != NULL)
99 {
100 ll = 0;
101 while ((ll < k) && ((h3->m[ll] == NULL)
102 || !pDivisibleBy(h3->m[ll],h2->m[i])))
103 ll++;
104 if (ll >= k)
105 {
106 j++;
107 if (j > IDELEMS(e)-1)
108 {
109 pEnlargeSet(&(e->m),IDELEMS(e),16);
110 IDELEMS(e) += 16;
111 }
112 e->m[j] = pCopy(h2->m[i]);
113 }
114 }
115 }
116 if (SB==NULL) idDelete(&h2);
117 idDelete(&h3);
118 idDelete(&h4);
119 if (currRing->qideal!=NULL)
120 {
121 h3=idInit(1,e->rank);
122 h2=kNF(h3,currRing->qideal,e);
123 idDelete(&h3);
124 idDelete(&e);
125 e=h2;
126 }
127 idSkipZeroes(e);
128 return e;
129}
130
131
132static ideal idSectWithElim (ideal h1,ideal h2, GbVariant alg)
133// does not destroy h1,h2
134{
135 if (TEST_OPT_PROT) PrintS("intersect by elimination method\n");
136 assume(!idIs0(h1));
137 assume(!idIs0(h2));
138 assume(IDELEMS(h1)<=IDELEMS(h2));
141 // add a new variable:
142 int j;
143 ring origRing=currRing;
144 ring r=rCopy0(origRing);
145 r->N++;
146 r->block0[0]=1;
147 r->block1[0]= r->N;
148 omFree(r->order);
149 r->order=(rRingOrder_t*)omAlloc0(3*sizeof(rRingOrder_t));
150 r->order[0]=ringorder_dp;
151 r->order[1]=ringorder_C;
152 char **names=(char**)omAlloc0(rVar(r) * sizeof(char_ptr));
153 for (j=0;j<r->N-1;j++) names[j]=r->names[j];
154 names[r->N-1]=omStrDup("@");
155 omFree(r->names);
156 r->names=names;
157 rComplete(r,TRUE);
158 // fetch h1, h2
159 ideal h;
160 h1=idrCopyR(h1,origRing,r);
161 h2=idrCopyR(h2,origRing,r);
162 // switch to temp. ring r
164 // create 1-t, t
165 poly omt=p_One(currRing);
166 p_SetExp(omt,r->N,1,currRing);
167 p_Setm(omt,currRing);
168 poly t=p_Copy(omt,currRing);
169 omt=p_Neg(omt,currRing);
170 omt=p_Add_q(omt,pOne(),currRing);
171 // compute (1-t)*h1
172 h1=(ideal)mp_MultP((matrix)h1,omt,currRing);
173 // compute t*h2
174 h2=(ideal)mp_MultP((matrix)h2,pCopy(t),currRing);
175 // (1-t)h1 + t*h2
176 h=idInit(IDELEMS(h1)+IDELEMS(h2),1);
177 int l;
178 for (l=IDELEMS(h1)-1; l>=0; l--)
179 {
180 h->m[l] = h1->m[l]; h1->m[l]=NULL;
181 }
182 j=IDELEMS(h1);
183 for (l=IDELEMS(h2)-1; l>=0; l--)
184 {
185 h->m[l+j] = h2->m[l]; h2->m[l]=NULL;
186 }
187 idDelete(&h1);
188 idDelete(&h2);
189 // eliminate t:
190 ideal res=idElimination(h,t,NULL,alg);
191 // cleanup
192 idDelete(&h);
193 pDelete(&t);
194 if (res!=NULL) res=idrMoveR(res,r,origRing);
195 rChangeCurrRing(origRing);
196 rDelete(r);
197 return res;
198}
199
200static ideal idGroebner(ideal temp,int syzComp,GbVariant alg, intvec* hilb=NULL, intvec* w=NULL, tHomog hom=testHomog)
201{
202 //Print("syz=%d\n",syzComp);
203 //PrintS(showOption());
204 //PrintLn();
205 ideal res=NULL;
206 if (w==NULL)
207 {
208 if (hom==testHomog)
209 hom=(tHomog)idHomModule(temp,currRing->qideal,&w); //sets w to weight vector or NULL
210 }
211 else
212 {
213 w=ivCopy(w);
214 hom=isHomog;
215 }
216#ifdef HAVE_SHIFTBBA
217 if (rIsLPRing(currRing)) alg = GbStd;
218#endif
219 if ((alg==GbStd)||(alg==GbDefault))
220 {
221 if (TEST_OPT_PROT &&(alg==GbStd)) { PrintS("std:"); mflush(); }
222 res = kStd(temp,currRing->qideal,hom,&w,hilb,syzComp);
223 idDelete(&temp);
224 }
225 else if (alg==GbSlimgb)
226 {
227 if (TEST_OPT_PROT) { PrintS("slimgb:"); mflush(); }
228 res = t_rep_gb(currRing, temp, syzComp);
229 idDelete(&temp);
230 }
231 else if (alg==GbGroebner)
232 {
233 if (TEST_OPT_PROT) { PrintS("groebner:"); mflush(); }
234 BOOLEAN err;
235 res=(ideal)iiCallLibProc1("groebner",temp,MODUL_CMD,err);
236 if (err)
237 {
238 Werror("error %d in >>groebner<<",err);
239 res=idInit(1,1);
240 }
241 }
242 else if (alg==GbModstd)
243 {
244 if (TEST_OPT_PROT) { PrintS("modStd:"); mflush(); }
245 BOOLEAN err;
246 void *args[]={temp,(void*)1,NULL};
247 int arg_t[]={MODUL_CMD,INT_CMD,0};
248 leftv temp0=ii_CallLibProcM("modStd",args,arg_t,currRing,err);
249 res=(ideal)temp0->data;
251 if (err)
252 {
253 Werror("error %d in >>modStd<<",err);
254 res=idInit(1,1);
255 }
256 }
257 else if (alg==GbSba)
258 {
259 if (TEST_OPT_PROT) { PrintS("sba:"); mflush(); }
260 res = kSba(temp,currRing->qideal,hom,&w,1,0,NULL);
261 if (w!=NULL) delete w;
262 }
263 else if (alg==GbStdSat)
264 {
265 if (TEST_OPT_PROT) { PrintS("std:sat:"); mflush(); }
266 BOOLEAN err;
267 // search for 2nd block of vars
268 int i=0;
269 int block=-1;
270 loop
271 {
272 if ((currRing->order[i]!=ringorder_c)
273 && (currRing->order[i]!=ringorder_C)
274 && (currRing->order[i]!=ringorder_s))
275 {
276 if (currRing->order[i]==0) { err=TRUE;break;}
277 block++;
278 if (block==1) { block=i; break;}
279 }
280 i++;
281 }
282 if (block>0)
283 {
284 if (TEST_OPT_PROT)
285 {
286 Print("sat(%d..%d)\n",currRing->block0[block],currRing->block1[block]);
287 mflush();
288 }
289 ideal v=idInit(currRing->block1[block]-currRing->block0[block]+1,1);
290 for(i=currRing->block0[block];i<=currRing->block1[block];i++)
291 {
292 v->m[i-currRing->block0[block]]=pOne();
293 pSetExp(v->m[i-currRing->block0[block]],i,1);
294 pSetm(v->m[i-currRing->block0[block]]);
295 }
296 void *args[]={temp,v,NULL};
297 int arg_t[]={MODUL_CMD,IDEAL_CMD,0};
298 leftv temp0=ii_CallLibProcM("satstd",args,arg_t,currRing,err);
299 res=(ideal)temp0->data;
301 }
302 if (err)
303 {
304 Werror("error %d in >>satstd<<",err);
305 res=idInit(1,1);
306 }
307 }
308 if (w!=NULL) delete w;
309 return res;
310}
311
312/*2
313* h3 := h1 intersect h2
314*/
315ideal idSect (ideal h1,ideal h2, GbVariant alg)
316{
317 int i,j,k;
318 unsigned length;
319 int flength = id_RankFreeModule(h1,currRing);
320 int slength = id_RankFreeModule(h2,currRing);
321 int rank=si_max(h1->rank,h2->rank);
322 if ((idIs0(h1)) || (idIs0(h2))) return idInit(1,rank);
323
324 BITSET save_opt;
325 SI_SAVE_OPT1(save_opt);
327
328 ideal first,second,temp,temp1,result;
329 poly p,q;
330
331 if (IDELEMS(h1)<IDELEMS(h2))
332 {
333 first = h1;
334 second = h2;
335 }
336 else
337 {
338 first = h2;
339 second = h1;
340 int t=flength; flength=slength; slength=t;
341 }
342 length = si_max(flength,slength);
343 if (length==0)
344 {
345 if ((currRing->qideal==NULL)
346 && (currRing->OrdSgn==1)
349 return idSectWithElim(first,second,alg);
350 else length = 1;
351 }
352 if (TEST_OPT_PROT) PrintS("intersect by syzygy methods\n");
353 j = IDELEMS(first);
354
355 ring orig_ring=currRing;
356 ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
357 rSetSyzComp(length,syz_ring);
358 rChangeCurrRing(syz_ring);
359
360 while ((j>0) && (first->m[j-1]==NULL)) j--;
361 temp = idInit(j /*IDELEMS(first)*/+IDELEMS(second),length+j);
362 k = 0;
363 for (i=0;i<j;i++)
364 {
365 if (first->m[i]!=NULL)
366 {
367 if (syz_ring==orig_ring)
368 temp->m[k] = pCopy(first->m[i]);
369 else
370 temp->m[k] = prCopyR(first->m[i], orig_ring, syz_ring);
371 q = pOne();
372 pSetComp(q,i+1+length);
373 pSetmComp(q);
374 if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
375 p = temp->m[k];
376 while (pNext(p)!=NULL) pIter(p);
377 pNext(p) = q;
378 k++;
379 }
380 }
381 for (i=0;i<IDELEMS(second);i++)
382 {
383 if (second->m[i]!=NULL)
384 {
385 if (syz_ring==orig_ring)
386 temp->m[k] = pCopy(second->m[i]);
387 else
388 temp->m[k] = prCopyR(second->m[i], orig_ring,currRing);
389 if (slength==0) p_Shift(&(temp->m[k]),1,currRing);
390 k++;
391 }
392 }
393 intvec *w=NULL;
394
395 if ((alg!=GbDefault)
396 && (alg!=GbGroebner)
397 && (alg!=GbModstd)
398 && (alg!=GbSlimgb)
399 && (alg!=GbStd))
400 {
401 WarnS("wrong algorithm for GB");
402 alg=GbDefault;
403 }
404 temp1=idGroebner(temp,length,alg);
405
406 if(syz_ring!=orig_ring)
407 rChangeCurrRing(orig_ring);
408
409 result = idInit(IDELEMS(temp1),rank);
410 j = 0;
411 for (i=0;i<IDELEMS(temp1);i++)
412 {
413 if ((temp1->m[i]!=NULL)
414 && (__p_GetComp(temp1->m[i],syz_ring)>length))
415 {
416 if(syz_ring==orig_ring)
417 {
418 p = temp1->m[i];
419 }
420 else
421 {
422 p = prMoveR(temp1->m[i], syz_ring,orig_ring);
423 }
424 temp1->m[i]=NULL;
425 while (p!=NULL)
426 {
427 q = pNext(p);
428 pNext(p) = NULL;
429 k = pGetComp(p)-1-length;
430 pSetComp(p,0);
431 pSetmComp(p);
432 /* Warning! multiply only from the left! it's very important for Plural */
433 result->m[j] = pAdd(result->m[j],pMult(p,pCopy(first->m[k])));
434 p = q;
435 }
436 j++;
437 }
438 }
439 if(syz_ring!=orig_ring)
440 {
441 rChangeCurrRing(syz_ring);
442 idDelete(&temp1);
443 rChangeCurrRing(orig_ring);
444 rDelete(syz_ring);
445 }
446 else
447 {
448 idDelete(&temp1);
449 }
450
452 SI_RESTORE_OPT1(save_opt);
454 {
455 w=NULL;
456 temp1=kStd(result,currRing->qideal,testHomog,&w);
457 if (w!=NULL) delete w;
459 idSkipZeroes(temp1);
460 return temp1;
461 }
462 //else
463 // temp1=kInterRed(result,currRing->qideal);
464 return result;
465}
466
467/*2
468* ideal/module intersection for a list of objects
469* given as 'resolvente'
470*/
472{
473 int i,j=0,k=0,l,maxrk=-1,realrki;
474 unsigned syzComp;
475 ideal bigmat,tempstd,result;
476 poly p;
477 int isIdeal=0;
478
479 /* find 0-ideals and max rank -----------------------------------*/
480 for (i=0;i<length;i++)
481 {
482 if (!idIs0(arg[i]))
483 {
484 realrki=id_RankFreeModule(arg[i],currRing);
485 k++;
486 j += IDELEMS(arg[i]);
487 if (realrki>maxrk) maxrk = realrki;
488 }
489 else
490 {
491 if (arg[i]!=NULL)
492 {
493 return idInit(1,arg[i]->rank);
494 }
495 }
496 }
497 if (maxrk == 0)
498 {
499 isIdeal = 1;
500 maxrk = 1;
501 }
502 /* init -----------------------------------------------------------*/
503 j += maxrk;
504 syzComp = k*maxrk;
505
506 ring orig_ring=currRing;
507 ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
508 rSetSyzComp(syzComp,syz_ring);
509 rChangeCurrRing(syz_ring);
510
511 bigmat = idInit(j,(k+1)*maxrk);
512 /* create unit matrices ------------------------------------------*/
513 for (i=0;i<maxrk;i++)
514 {
515 for (j=0;j<=k;j++)
516 {
517 p = pOne();
518 pSetComp(p,i+1+j*maxrk);
519 pSetmComp(p);
520 bigmat->m[i] = pAdd(bigmat->m[i],p);
521 }
522 }
523 /* enter given ideals ------------------------------------------*/
524 i = maxrk;
525 k = 0;
526 for (j=0;j<length;j++)
527 {
528 if (arg[j]!=NULL)
529 {
530 for (l=0;l<IDELEMS(arg[j]);l++)
531 {
532 if (arg[j]->m[l]!=NULL)
533 {
534 if (syz_ring==orig_ring)
535 bigmat->m[i] = pCopy(arg[j]->m[l]);
536 else
537 bigmat->m[i] = prCopyR(arg[j]->m[l], orig_ring,currRing);
538 p_Shift(&(bigmat->m[i]),k*maxrk+isIdeal,currRing);
539 i++;
540 }
541 }
542 k++;
543 }
544 }
545 /* std computation --------------------------------------------*/
546 if ((alg!=GbDefault)
547 && (alg!=GbGroebner)
548 && (alg!=GbModstd)
549 && (alg!=GbSlimgb)
550 && (alg!=GbStd))
551 {
552 WarnS("wrong algorithm for GB");
553 alg=GbDefault;
554 }
555 tempstd=idGroebner(bigmat,syzComp,alg);
556
557 if(syz_ring!=orig_ring)
558 rChangeCurrRing(orig_ring);
559
560 /* interpret result ----------------------------------------*/
561 result = idInit(IDELEMS(tempstd),maxrk);
562 k = 0;
563 for (j=0;j<IDELEMS(tempstd);j++)
564 {
565 if ((tempstd->m[j]!=NULL) && (__p_GetComp(tempstd->m[j],syz_ring)>syzComp))
566 {
567 if (syz_ring==orig_ring)
568 p = pCopy(tempstd->m[j]);
569 else
570 p = prCopyR(tempstd->m[j], syz_ring,currRing);
571 p_Shift(&p,-syzComp-isIdeal,currRing);
572 result->m[k] = p;
573 k++;
574 }
575 }
576 /* clean up ----------------------------------------------------*/
577 if(syz_ring!=orig_ring)
578 rChangeCurrRing(syz_ring);
579 idDelete(&tempstd);
580 if(syz_ring!=orig_ring)
581 {
582 rChangeCurrRing(orig_ring);
583 rDelete(syz_ring);
584 }
586 return result;
587}
588
589/*2
590*computes syzygies of h1,
591*if quot != NULL it computes in the quotient ring modulo "quot"
592*works always in a ring with ringorder_s
593*/
594/* construct a "matrix" (h11 may be NULL)
595 * h1 h11
596 * E_n 0
597 * and compute a (column) GB of it, with a syzComp=rows(h1)=rows(h11)
598 * currRing must be a syz-ring with syzComp set
599 * result is a "matrix":
600 * G 0
601 * T S
602 * where G: GB of (h1+h11)
603 * T: G/h11=h1*T
604 * S: relative syzygies(h1) modulo h11
605 * if V_IDLIFT is set, ignore/do not return S
606 */
607static ideal idPrepare (ideal h1, ideal h11, tHomog hom, int syzcomp, intvec **w, GbVariant alg)
608{
609 ideal h2,h22;
610 int j,k;
611 poly p,q;
612
613 assume(!idIs0(h1));
615 if (h11!=NULL)
616 {
617 k = si_max(k,(int)id_RankFreeModule(h11,currRing));
618 h22=idCopy(h11);
619 }
620 h2=idCopy(h1);
621 int i = IDELEMS(h2);
622 if (h11!=NULL) i+=IDELEMS(h22);
623 if (k == 0)
624 {
625 id_Shift(h2,1,currRing);
626 if (h11!=NULL) id_Shift(h22,1,currRing);
627 k = 1;
628 }
629 if (syzcomp<k)
630 {
631 Warn("syzcomp too low, should be %d instead of %d",k,syzcomp);
632 syzcomp = k;
634 }
635 h2->rank = syzcomp+i;
636
637 //if (hom==testHomog)
638 //{
639 // if(idHomIdeal(h1,currRing->qideal))
640 // {
641 // hom=TRUE;
642 // }
643 //}
644
645 for (j=0; j<IDELEMS(h2); j++)
646 {
647 p = h2->m[j];
648 q = pOne();
649#ifdef HAVE_SHIFTBBA
650 // non multiplicative variable
651 if (rIsLPRing(currRing))
652 {
653 pSetExp(q, currRing->isLPring - currRing->LPncGenCount + j + 1, 1);
654 p_Setm(q, currRing);
655 }
656#endif
657 pSetComp(q,syzcomp+1+j);
658 pSetmComp(q);
659 if (p!=NULL)
660 {
661#ifdef HAVE_SHIFTBBA
662 if (rIsLPRing(currRing))
663 {
664 h2->m[j] = pAdd(p, q);
665 }
666 else
667#endif
668 {
669 while (pNext(p)) pIter(p);
670 p->next = q;
671 }
672 }
673 else
674 h2->m[j]=q;
675 }
676 if (h11!=NULL)
677 {
678 ideal h=id_SimpleAdd(h2,h22,currRing);
679 id_Delete(&h2,currRing);
680 id_Delete(&h22,currRing);
681 h2=h;
682 }
683
684 idTest(h2);
685 #if 0
687 PrintS(" --------------before std------------------------\n");
688 ipPrint_MA0(TT,"T");
689 PrintLn();
690 idDelete((ideal*)&TT);
691 #endif
692
693 if ((alg!=GbDefault)
694 && (alg!=GbGroebner)
695 && (alg!=GbModstd)
696 && (alg!=GbSlimgb)
697 && (alg!=GbStd))
698 {
699 WarnS("wrong algorithm for GB");
700 alg=GbDefault;
701 }
702
703 ideal h3;
704 if (w!=NULL) h3=idGroebner(h2,syzcomp,alg,NULL,*w,hom);
705 else h3=idGroebner(h2,syzcomp,alg,NULL,NULL,hom);
706 return h3;
707}
708
709ideal idExtractG_T_S(ideal s_h3,matrix *T,ideal *S,long syzComp,
710 int h1_size,BOOLEAN inputIsIdeal,const ring oring, const ring sring)
711{
712 // now sort the result, SB : leave in s_h3
713 // T: put in s_h2 (*T as a matrix)
714 // syz: put in *S
715 idSkipZeroes(s_h3);
716 ideal s_h2 = idInit(IDELEMS(s_h3), s_h3->rank); // will become T
717
718 #if 0
720 Print("after std: --------------syzComp=%d------------------------\n",syzComp);
721 ipPrint_MA0(TT,"T");
722 PrintLn();
723 idDelete((ideal*)&TT);
724 #endif
725
726 int j, i=0;
727 for (j=0; j<IDELEMS(s_h3); j++)
728 {
729 if (s_h3->m[j] != NULL)
730 {
731 if (pGetComp(s_h3->m[j]) <= syzComp) // syz_ring == currRing
732 {
733 i++;
734 poly q = s_h3->m[j];
735 while (pNext(q) != NULL)
736 {
737 if (pGetComp(pNext(q)) > syzComp)
738 {
739 s_h2->m[i-1] = pNext(q);
740 pNext(q) = NULL;
741 }
742 else
743 {
744 pIter(q);
745 }
746 }
747 if (!inputIsIdeal) p_Shift(&(s_h3->m[j]), -1,currRing);
748 }
749 else
750 {
751 // we a syzygy here:
752 if (S!=NULL)
753 {
754 p_Shift(&s_h3->m[j], -syzComp,currRing);
755 (*S)->m[j]=s_h3->m[j];
756 s_h3->m[j]=NULL;
757 }
758 else
759 p_Delete(&(s_h3->m[j]),currRing);
760 }
761 }
762 }
763 idSkipZeroes(s_h3);
764
765 #if 0
767 PrintS("T: ----------------------------------------\n");
768 ipPrint_MA0(TT,"T");
769 PrintLn();
770 idDelete((ideal*)&TT);
771 #endif
772
773 if (S!=NULL) idSkipZeroes(*S);
774
775 if (sring!=oring)
776 {
777 rChangeCurrRing(oring);
778 }
779
780 if (T!=NULL)
781 {
782 *T = mpNew(h1_size,i);
783
784 for (j=0; j<i; j++)
785 {
786 if (s_h2->m[j] != NULL)
787 {
788 poly q = prMoveR( s_h2->m[j], sring,oring);
789 s_h2->m[j] = NULL;
790
791 if (q!=NULL)
792 {
793 q=pReverse(q);
794 while (q != NULL)
795 {
796 poly p = q;
797 pIter(q);
798 pNext(p) = NULL;
799 int t=pGetComp(p);
800 pSetComp(p,0);
801 pSetmComp(p);
802 MATELEM(*T,t-syzComp,j+1) = pAdd(MATELEM(*T,t-syzComp,j+1),p);
803 }
804 }
805 }
806 }
807 }
808 id_Delete(&s_h2,sring);
809
810 for (i=0; i<IDELEMS(s_h3); i++)
811 {
812 s_h3->m[i] = prMoveR_NoSort(s_h3->m[i], sring,oring);
813 }
814 if (S!=NULL)
815 {
816 for (i=0; i<IDELEMS(*S); i++)
817 {
818 (*S)->m[i] = prMoveR_NoSort((*S)->m[i], sring,oring);
819 }
820 }
821 return s_h3;
822}
823
824/*2
825* compute the syzygies of h1 in R/quot,
826* weights of components are in w
827* if setRegularity, return the regularity in deg
828* do not change h1, w
829*/
830ideal idSyzygies (ideal h1, tHomog h,intvec **w, BOOLEAN setSyzComp,
831 BOOLEAN setRegularity, int *deg, GbVariant alg)
832{
833 ideal s_h1;
834 int j, k, length=0,reg;
835 BOOLEAN isMonomial=TRUE;
836 int ii, idElemens_h1;
837
838 assume(h1 != NULL);
839
840 idElemens_h1=IDELEMS(h1);
841#ifdef PDEBUG
842 for(ii=0;ii<idElemens_h1 /*IDELEMS(h1)*/;ii++) pTest(h1->m[ii]);
843#endif
844 if (idIs0(h1))
845 {
846 ideal result=idFreeModule(idElemens_h1/*IDELEMS(h1)*/);
847 return result;
848 }
849 int slength=(int)id_RankFreeModule(h1,currRing);
850 k=si_max(1,slength /*id_RankFreeModule(h1)*/);
851
852 assume(currRing != NULL);
853 ring orig_ring=currRing;
854 ring syz_ring=rAssure_SyzComp(orig_ring,TRUE);
855 if (setSyzComp) rSetSyzComp(k,syz_ring);
856
857 if (orig_ring != syz_ring)
858 {
859 rChangeCurrRing(syz_ring);
860 s_h1=idrCopyR_NoSort(h1,orig_ring,syz_ring);
861 }
862 else
863 {
864 s_h1 = h1;
865 }
866
867 idTest(s_h1);
868
869 BITSET save_opt;
870 SI_SAVE_OPT1(save_opt);
872
873 ideal s_h3=idPrepare(s_h1,NULL,h,k,w,alg); // main (syz) GB computation
874
875 SI_RESTORE_OPT1(save_opt);
876
877 if (orig_ring != syz_ring)
878 {
879 idDelete(&s_h1);
880 for (j=0; j<IDELEMS(s_h3); j++)
881 {
882 if (s_h3->m[j] != NULL)
883 {
884 if (p_MinComp(s_h3->m[j],syz_ring) > k)
885 p_Shift(&s_h3->m[j], -k,syz_ring);
886 else
887 p_Delete(&s_h3->m[j],syz_ring);
888 }
889 }
890 idSkipZeroes(s_h3);
891 s_h3->rank -= k;
892 rChangeCurrRing(orig_ring);
893 s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
894 rDelete(syz_ring);
895 #ifdef HAVE_PLURAL
896 if (rIsPluralRing(orig_ring))
897 {
898 id_DelMultiples(s_h3,orig_ring);
899 idSkipZeroes(s_h3);
900 }
901 #endif
902 idTest(s_h3);
903 return s_h3;
904 }
905
906 ideal e = idInit(IDELEMS(s_h3), s_h3->rank);
907
908 for (j=IDELEMS(s_h3)-1; j>=0; j--)
909 {
910 if (s_h3->m[j] != NULL)
911 {
912 if (p_MinComp(s_h3->m[j],syz_ring) <= k)
913 {
914 e->m[j] = s_h3->m[j];
915 isMonomial=isMonomial && (pNext(s_h3->m[j])==NULL);
916 p_Delete(&pNext(s_h3->m[j]),syz_ring);
917 s_h3->m[j] = NULL;
918 }
919 }
920 }
921
922 idSkipZeroes(s_h3);
923 idSkipZeroes(e);
924
925 if ((deg != NULL)
926 && (!isMonomial)
928 && (setRegularity)
929 && (h==isHomog)
932 )
933 {
934 assume(orig_ring==syz_ring);
935 ring dp_C_ring = rAssure_dp_C(syz_ring); // will do rChangeCurrRing later
936 if (dp_C_ring != syz_ring)
937 {
938 rChangeCurrRing(dp_C_ring);
939 e = idrMoveR_NoSort(e, syz_ring, dp_C_ring);
940 }
942 intvec * dummy = syBetti(res,length,&reg, *w);
943 *deg = reg+2;
944 delete dummy;
945 for (j=0;j<length;j++)
946 {
947 if (res[j]!=NULL) idDelete(&(res[j]));
948 }
949 omFreeSize((ADDRESS)res,length*sizeof(ideal));
950 idDelete(&e);
951 if (dp_C_ring != orig_ring)
952 {
953 rChangeCurrRing(orig_ring);
954 rDelete(dp_C_ring);
955 }
956 }
957 else
958 {
959 idDelete(&e);
960 }
961 assume(orig_ring==currRing);
962 idTest(s_h3);
963 if (currRing->qideal != NULL)
964 {
965 ideal ts_h3=kStd(s_h3,currRing->qideal,h,w);
966 idDelete(&s_h3);
967 s_h3 = ts_h3;
968 }
969 return s_h3;
970}
971
972/*
973*computes a standard basis for h1 and stores the transformation matrix
974* in ma
975*/
976ideal idLiftStd (ideal h1, matrix* T, tHomog hi, ideal * S, GbVariant alg,
977 ideal h11)
978{
979 int inputIsIdeal=id_RankFreeModule(h1,currRing);
980 long k;
981 intvec *w=NULL;
982
983 idDelete((ideal*)T);
984 BOOLEAN lift3=FALSE;
985 if (S!=NULL) { lift3=TRUE; idDelete(S); }
986 if (idIs0(h1))
987 {
988 *T=mpNew(1,IDELEMS(h1));
989 if (lift3)
990 {
991 *S=idFreeModule(IDELEMS(h1));
992 }
993 return idInit(1,h1->rank);
994 }
995
996 BITSET save2;
997 SI_SAVE_OPT2(save2);
998
999 k=si_max(1,inputIsIdeal);
1000
1001 if ((!lift3)&&(!TEST_OPT_RETURN_SB)) si_opt_2 |=Sy_bit(V_IDLIFT);
1002
1003 ring orig_ring = currRing;
1004 ring syz_ring = rAssure_SyzOrder(orig_ring,TRUE);
1005 rSetSyzComp(k,syz_ring);
1006 rChangeCurrRing(syz_ring);
1007
1008 ideal s_h1;
1009
1010 if (orig_ring != syz_ring)
1011 s_h1 = idrCopyR_NoSort(h1,orig_ring,syz_ring);
1012 else
1013 s_h1 = h1;
1014 ideal s_h11=NULL;
1015 if (h11!=NULL)
1016 {
1017 s_h11=idrCopyR_NoSort(h11,orig_ring,syz_ring);
1018 }
1019
1020
1021 ideal s_h3=idPrepare(s_h1,s_h11,hi,k,&w,alg); // main (syz) GB computation
1022
1023
1024 if (w!=NULL) delete w;
1025 if (syz_ring!=orig_ring)
1026 {
1027 idDelete(&s_h1);
1028 if (s_h11!=NULL) idDelete(&s_h11);
1029 }
1030
1031 if (S!=NULL) (*S)=idInit(IDELEMS(s_h3),IDELEMS(h1));
1032
1033 s_h3=idExtractG_T_S(s_h3,T,S,k,IDELEMS(h1),inputIsIdeal,orig_ring,syz_ring);
1034
1035 if (syz_ring!=orig_ring) rDelete(syz_ring);
1036 s_h3->rank=h1->rank;
1037 SI_RESTORE_OPT2(save2);
1038 return s_h3;
1039}
1040
1041static void idPrepareStd(ideal s_temp, int k)
1042{
1043 int j,rk=id_RankFreeModule(s_temp,currRing);
1044 poly p,q;
1045
1046 if (rk == 0)
1047 {
1048 for (j=0; j<IDELEMS(s_temp); j++)
1049 {
1050 if (s_temp->m[j]!=NULL) pSetCompP(s_temp->m[j],1);
1051 }
1052 k = si_max(k,1);
1053 }
1054 for (j=0; j<IDELEMS(s_temp); j++)
1055 {
1056 if (s_temp->m[j]!=NULL)
1057 {
1058 p = s_temp->m[j];
1059 q = pOne();
1060 //pGetCoeff(q)=nInpNeg(pGetCoeff(q)); //set q to -1
1061 pSetComp(q,k+1+j);
1062 pSetmComp(q);
1063#ifdef HAVE_SHIFTBBA
1064 // non multiplicative variable
1065 if (rIsLPRing(currRing))
1066 {
1067 pSetExp(q, currRing->isLPring - currRing->LPncGenCount + j + 1, 1);
1068 p_Setm(q, currRing);
1069 s_temp->m[j] = pAdd(p, q);
1070 }
1071 else
1072#endif
1073 {
1074 while (pNext(p)) pIter(p);
1075 pNext(p) = q;
1076 }
1077 }
1078 }
1079 s_temp->rank = k+IDELEMS(s_temp);
1080}
1081
1082static void idLift_setUnit(int e_mod, matrix *unit)
1083{
1084 if (unit!=NULL)
1085 {
1086 *unit=mpNew(e_mod,e_mod);
1087 // make sure that U is a diagonal matrix of units
1088 for(int i=e_mod;i>0;i--)
1089 {
1090 MATELEM(*unit,i,i)=pOne();
1091 }
1092 }
1093}
1094/*2
1095*computes a representation of the generators of submod with respect to those
1096* of mod
1097*/
1098/// represents the generators of submod in terms of the generators of mod
1099/// (Matrix(SM)*U-Matrix(rest)) = Matrix(M)*Matrix(result)
1100/// goodShape: maximal non-zero index in generators of SM <= that of M
1101/// isSB: generators of M form a Groebner basis
1102/// divide: allow SM not to be a submodule of M
1103/// U is an diagonal matrix of units (non-constant only in local rings)
1104/// rest is: 0 if SM in M, SM if not divide, NF(SM,std(M)) if divide
1105ideal idLift(ideal mod, ideal submod,ideal *rest, BOOLEAN goodShape,
1106 BOOLEAN isSB, BOOLEAN divide, matrix *unit, GbVariant alg)
1107{
1108 int lsmod =id_RankFreeModule(submod,currRing), j, k;
1109 int comps_to_add=0;
1110 int idelems_mod=IDELEMS(mod);
1111 int idelems_submod=IDELEMS(submod);
1112 poly p;
1113
1114 if (idIs0(submod))
1115 {
1116 if (rest!=NULL)
1117 {
1118 *rest=idInit(1,mod->rank);
1119 }
1120 idLift_setUnit(idelems_submod,unit);
1121 return idInit(1,idelems_mod);
1122 }
1123 if (idIs0(mod)) /* and not idIs0(submod) */
1124 {
1125 if (rest!=NULL)
1126 {
1127 *rest=idCopy(submod);
1128 idLift_setUnit(idelems_submod,unit);
1129 return idInit(1,idelems_mod);
1130 }
1131 else
1132 {
1133 WerrorS("2nd module does not lie in the first");
1134 return NULL;
1135 }
1136 }
1137 if (unit!=NULL)
1138 {
1139 comps_to_add = idelems_submod;
1140 while ((comps_to_add>0) && (submod->m[comps_to_add-1]==NULL))
1141 comps_to_add--;
1142 }
1144 if ((k!=0) && (lsmod==0)) lsmod=1;
1145 k=si_max(k,(int)mod->rank);
1146 if (k<submod->rank) { WarnS("rk(submod) > rk(mod) ?");k=submod->rank; }
1147
1148 ring orig_ring=currRing;
1149 ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
1150 rSetSyzComp(k,syz_ring);
1151 rChangeCurrRing(syz_ring);
1152
1153 ideal s_mod, s_temp;
1154 if (orig_ring != syz_ring)
1155 {
1156 s_mod = idrCopyR_NoSort(mod,orig_ring,syz_ring);
1157 s_temp = idrCopyR_NoSort(submod,orig_ring,syz_ring);
1158 }
1159 else
1160 {
1161 s_mod = mod;
1162 s_temp = idCopy(submod);
1163 }
1164 BITSET save2;
1165 SI_SAVE_OPT2(save2);
1166
1167 if ((rest==NULL)
1169 && (!rIsNCRing(currRing))
1170 && (!TEST_OPT_RETURN_SB))
1172 else
1174 ideal s_h3;
1175 if (isSB && !TEST_OPT_IDLIFT)
1176 {
1177 s_h3 = idCopy(s_mod);
1178 idPrepareStd(s_h3, k+comps_to_add);
1179 }
1180 else
1181 {
1182 s_h3 = idPrepare(s_mod,NULL,(tHomog)FALSE,k+comps_to_add,NULL,alg);
1183 }
1184 SI_RESTORE_OPT2(save2);
1185
1186 if (!goodShape)
1187 {
1188 for (j=0;j<IDELEMS(s_h3);j++)
1189 {
1190 if ((s_h3->m[j] != NULL) && (pMinComp(s_h3->m[j]) > k))
1191 p_Delete(&(s_h3->m[j]),currRing);
1192 }
1193 }
1194 idSkipZeroes(s_h3);
1195 if (lsmod==0)
1196 {
1197 id_Shift(s_temp,1,currRing);
1198 }
1199 if (unit!=NULL)
1200 {
1201 for(j = 0;j<comps_to_add;j++)
1202 {
1203 p = s_temp->m[j];
1204 if (p!=NULL)
1205 {
1206 while (pNext(p)!=NULL) pIter(p);
1207 pNext(p) = pOne();
1208 pIter(p);
1209 pSetComp(p,1+j+k);
1210 pSetmComp(p);
1211 p = pNeg(p);
1212 }
1213 }
1214 s_temp->rank += (k+comps_to_add);
1215 }
1216 ideal s_result = kNF(s_h3,currRing->qideal,s_temp,k);
1217 s_result->rank = s_h3->rank;
1218 ideal s_rest = idInit(IDELEMS(s_result),k);
1219 idDelete(&s_h3);
1220 idDelete(&s_temp);
1221
1222 for (j=0;j<IDELEMS(s_result);j++)
1223 {
1224 if (s_result->m[j]!=NULL)
1225 {
1226 if (pGetComp(s_result->m[j])<=k)
1227 {
1228 if (!divide)
1229 {
1230 if (rest==NULL)
1231 {
1232 if (isSB)
1233 {
1234 WarnS("first module not a standardbasis\n"
1235 "// ** or second not a proper submodule");
1236 }
1237 else
1238 WerrorS("2nd module does not lie in the first");
1239 }
1240 idDelete(&s_result);
1241 idDelete(&s_rest);
1242 if(syz_ring!=orig_ring)
1243 {
1244 idDelete(&s_mod);
1245 rChangeCurrRing(orig_ring);
1246 rDelete(syz_ring);
1247 }
1248 if (unit!=NULL)
1249 {
1250 idLift_setUnit(idelems_submod,unit);
1251 }
1252 if (rest!=NULL) *rest=idCopy(submod);
1253 s_result=idInit(idelems_submod,idelems_mod);
1254 return s_result;
1255 }
1256 else
1257 {
1258 p = s_rest->m[j] = s_result->m[j];
1259 while ((pNext(p)!=NULL) && (pGetComp(pNext(p))<=k)) pIter(p);
1260 s_result->m[j] = pNext(p);
1261 pNext(p) = NULL;
1262 }
1263 }
1264 p_Shift(&(s_result->m[j]),-k,currRing);
1265 pNeg(s_result->m[j]);
1266 }
1267 }
1268 if ((lsmod==0) && (s_rest!=NULL))
1269 {
1270 for (j=IDELEMS(s_rest);j>0;j--)
1271 {
1272 if (s_rest->m[j-1]!=NULL)
1273 {
1274 p_Shift(&(s_rest->m[j-1]),-1,currRing);
1275 }
1276 }
1277 }
1278 if(syz_ring!=orig_ring)
1279 {
1280 idDelete(&s_mod);
1281 rChangeCurrRing(orig_ring);
1282 s_result = idrMoveR_NoSort(s_result, syz_ring, orig_ring);
1283 s_rest = idrMoveR_NoSort(s_rest, syz_ring, orig_ring);
1284 rDelete(syz_ring);
1285 }
1286 if (rest!=NULL)
1287 {
1288 s_rest->rank=mod->rank;
1289 *rest = s_rest;
1290 }
1291 else
1292 idDelete(&s_rest);
1293 if (unit!=NULL)
1294 {
1295 *unit=mpNew(idelems_submod,idelems_submod);
1296 int i;
1297 for(i=0;i<IDELEMS(s_result);i++)
1298 {
1299 poly p=s_result->m[i];
1300 poly q=NULL;
1301 while(p!=NULL)
1302 {
1303 if(pGetComp(p)<=comps_to_add)
1304 {
1305 pSetComp(p,0);
1306 if (q!=NULL)
1307 {
1308 pNext(q)=pNext(p);
1309 }
1310 else
1311 {
1312 pIter(s_result->m[i]);
1313 }
1314 pNext(p)=NULL;
1315 MATELEM(*unit,i+1,i+1)=pAdd(MATELEM(*unit,i+1,i+1),p);
1316 if(q!=NULL) p=pNext(q);
1317 else p=s_result->m[i];
1318 }
1319 else
1320 {
1321 q=p;
1322 pIter(p);
1323 }
1324 }
1325 p_Shift(&s_result->m[i],-comps_to_add,currRing);
1326 }
1327 }
1328 s_result->rank=idelems_mod;
1329 return s_result;
1330}
1331
1332/*2
1333*computes division of P by Q with remainder up to (w-weighted) degree n
1334*P, Q, and w are not changed
1335*/
1336void idLiftW(ideal P,ideal Q,int n,matrix &T, ideal &R,int *w)
1337{
1338 long N=0;
1339 int i;
1340 for(i=IDELEMS(Q)-1;i>=0;i--)
1341 if(w==NULL)
1342 N=si_max(N,p_Deg(Q->m[i],currRing));
1343 else
1344 N=si_max(N,p_DegW(Q->m[i],w,currRing));
1345 N+=n;
1346
1347 T=mpNew(IDELEMS(Q),IDELEMS(P));
1348 R=idInit(IDELEMS(P),P->rank);
1349
1350 for(i=IDELEMS(P)-1;i>=0;i--)
1351 {
1352 poly p;
1353 if(w==NULL)
1354 p=ppJet(P->m[i],N);
1355 else
1356 p=ppJetW(P->m[i],N,w);
1357
1358 int j=IDELEMS(Q)-1;
1359 while(p!=NULL)
1360 {
1361 if(pDivisibleBy(Q->m[j],p))
1362 {
1363 poly p0=p_DivideM(pHead(p),pHead(Q->m[j]),currRing);
1364 if(w==NULL)
1365 p=pJet(pSub(p,ppMult_mm(Q->m[j],p0)),N);
1366 else
1367 p=pJetW(pSub(p,ppMult_mm(Q->m[j],p0)),N,w);
1368 pNormalize(p);
1369 if(((w==NULL)&&(p_Deg(p0,currRing)>n))||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
1370 p_Delete(&p0,currRing);
1371 else
1372 MATELEM(T,j+1,i+1)=pAdd(MATELEM(T,j+1,i+1),p0);
1373 j=IDELEMS(Q)-1;
1374 }
1375 else
1376 {
1377 if(j==0)
1378 {
1379 poly p0=p;
1380 pIter(p);
1381 pNext(p0)=NULL;
1382 if(((w==NULL)&&(p_Deg(p0,currRing)>n))
1383 ||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
1384 p_Delete(&p0,currRing);
1385 else
1386 R->m[i]=pAdd(R->m[i],p0);
1387 j=IDELEMS(Q)-1;
1388 }
1389 else
1390 j--;
1391 }
1392 }
1393 }
1394}
1395
1396/*2
1397*computes the quotient of h1,h2 : internal routine for idQuot
1398*BEWARE: the returned ideals may contain incorrectly ordered polys !
1399*
1400*/
1401static ideal idInitializeQuot (ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN *addOnlyOne, int *kkmax)
1402{
1403 idTest(h1);
1404 idTest(h2);
1405
1406 ideal temph1;
1407 poly p,q = NULL;
1408 int i,l,ll,k,kkk,kmax;
1409 int j = 0;
1410 int k1 = id_RankFreeModule(h1,currRing);
1411 int k2 = id_RankFreeModule(h2,currRing);
1412 tHomog hom=isNotHomog;
1413 k=si_max(k1,k2);
1414 if (k==0)
1415 k = 1;
1416 if ((k2==0) && (k>1)) *addOnlyOne = FALSE;
1417 intvec * weights;
1418 hom = (tHomog)idHomModule(h1,currRing->qideal,&weights);
1419 if /**addOnlyOne &&*/ (/*(*/ !h1IsStb /*)*/)
1420 temph1 = kStd(h1,currRing->qideal,hom,&weights,NULL);
1421 else
1422 temph1 = idCopy(h1);
1423 if (weights!=NULL) delete weights;
1424 idTest(temph1);
1425/*--- making a single vector from h2 ---------------------*/
1426 for (i=0; i<IDELEMS(h2); i++)
1427 {
1428 if (h2->m[i] != NULL)
1429 {
1430 p = pCopy(h2->m[i]);
1431 if (k2 == 0)
1432 p_Shift(&p,j*k+1,currRing);
1433 else
1434 p_Shift(&p,j*k,currRing);
1435 q = pAdd(q,p);
1436 j++;
1437 }
1438 }
1439 *kkmax = kmax = j*k+1;
1440/*--- adding a monomial for the result (syzygy) ----------*/
1441 p = q;
1442 while (pNext(p)!=NULL) pIter(p);
1443 pNext(p) = pOne();
1444 pIter(p);
1445 pSetComp(p,kmax);
1446 pSetmComp(p);
1447/*--- constructing the big matrix ------------------------*/
1448 ideal h4 = idInit(k,kmax+k-1);
1449 h4->m[0] = q;
1450 if (k2 == 0)
1451 {
1452 for (i=1; i<k; i++)
1453 {
1454 if (h4->m[i-1]!=NULL)
1455 {
1456 p = p_Copy_noCheck(h4->m[i-1], currRing); /*h4->m[i-1]!=NULL*/
1457 p_Shift(&p,1,currRing);
1458 h4->m[i] = p;
1459 }
1460 else break;
1461 }
1462 }
1463 idSkipZeroes(h4);
1464 kkk = IDELEMS(h4);
1465 i = IDELEMS(temph1);
1466 for (l=0; l<i; l++)
1467 {
1468 if(temph1->m[l]!=NULL)
1469 {
1470 for (ll=0; ll<j; ll++)
1471 {
1472 p = pCopy(temph1->m[l]);
1473 if (k1 == 0)
1474 p_Shift(&p,ll*k+1,currRing);
1475 else
1476 p_Shift(&p,ll*k,currRing);
1477 if (kkk >= IDELEMS(h4))
1478 {
1479 pEnlargeSet(&(h4->m),IDELEMS(h4),16);
1480 IDELEMS(h4) += 16;
1481 }
1482 h4->m[kkk] = p;
1483 kkk++;
1484 }
1485 }
1486 }
1487/*--- if h2 goes in as single vector - the h1-part is just SB ---*/
1488 if (*addOnlyOne)
1489 {
1490 idSkipZeroes(h4);
1491 p = h4->m[0];
1492 for (i=0;i<IDELEMS(h4)-1;i++)
1493 {
1494 h4->m[i] = h4->m[i+1];
1495 }
1496 h4->m[IDELEMS(h4)-1] = p;
1497 }
1498 idDelete(&temph1);
1499 //idTest(h4);//see remark at the beginning
1500 return h4;
1501}
1502
1503/*2
1504*computes the quotient of h1,h2
1505*/
1506ideal idQuot (ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN resultIsIdeal)
1507{
1508 // first check for special case h1:(0)
1509 if (idIs0(h2))
1510 {
1511 ideal res;
1512 if (resultIsIdeal)
1513 {
1514 res = idInit(1,1);
1515 res->m[0] = pOne();
1516 }
1517 else
1518 res = idFreeModule(h1->rank);
1519 return res;
1520 }
1521 int i, kmax;
1522 BOOLEAN addOnlyOne=TRUE;
1523 tHomog hom=isNotHomog;
1524 intvec * weights1;
1525
1526 ideal s_h4 = idInitializeQuot (h1,h2,h1IsStb,&addOnlyOne,&kmax);
1527
1528 hom = (tHomog)idHomModule(s_h4,currRing->qideal,&weights1);
1529
1530 ring orig_ring=currRing;
1531 ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
1532 rSetSyzComp(kmax-1,syz_ring);
1533 rChangeCurrRing(syz_ring);
1534 if (orig_ring!=syz_ring)
1535 // s_h4 = idrMoveR_NoSort(s_h4,orig_ring, syz_ring);
1536 s_h4 = idrMoveR(s_h4,orig_ring, syz_ring);
1537 idTest(s_h4);
1538
1539 #if 0
1540 matrix m=idModule2Matrix(idCopy(s_h4));
1541 PrintS("start:\n");
1542 ipPrint_MA0(m,"Q");
1543 idDelete((ideal *)&m);
1544 PrintS("last elem:");wrp(s_h4->m[IDELEMS(s_h4)-1]);PrintLn();
1545 #endif
1546
1547 ideal s_h3;
1548 BITSET old_test1;
1549 SI_SAVE_OPT1(old_test1);
1551 if (addOnlyOne)
1552 {
1554 s_h3 = kStd(s_h4,currRing->qideal,hom,&weights1,NULL,0/*kmax-1*/,IDELEMS(s_h4)-1);
1555 }
1556 else
1557 {
1558 s_h3 = kStd(s_h4,currRing->qideal,hom,&weights1,NULL,kmax-1);
1559 }
1560 SI_RESTORE_OPT1(old_test1);
1561
1562 #if 0
1563 // only together with the above debug stuff
1564 idSkipZeroes(s_h3);
1565 m=idModule2Matrix(idCopy(s_h3));
1566 Print("result, kmax=%d:\n",kmax);
1567 ipPrint_MA0(m,"S");
1568 idDelete((ideal *)&m);
1569 #endif
1570
1571 idTest(s_h3);
1572 if (weights1!=NULL) delete weights1;
1573 idDelete(&s_h4);
1574
1575 for (i=0;i<IDELEMS(s_h3);i++)
1576 {
1577 if ((s_h3->m[i]!=NULL) && (pGetComp(s_h3->m[i])>=kmax))
1578 {
1579 if (resultIsIdeal)
1580 p_Shift(&s_h3->m[i],-kmax,currRing);
1581 else
1582 p_Shift(&s_h3->m[i],-kmax+1,currRing);
1583 }
1584 else
1585 p_Delete(&s_h3->m[i],currRing);
1586 }
1587 if (resultIsIdeal)
1588 s_h3->rank = 1;
1589 else
1590 s_h3->rank = h1->rank;
1591 if(syz_ring!=orig_ring)
1592 {
1593 rChangeCurrRing(orig_ring);
1594 s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
1595 rDelete(syz_ring);
1596 }
1597 idSkipZeroes(s_h3);
1598 idTest(s_h3);
1599 return s_h3;
1600}
1601
1602/*2
1603* eliminate delVar (product of vars) in h1
1604*/
1605ideal idElimination (ideal h1,poly delVar,intvec *hilb, GbVariant alg)
1606{
1607 int i,j=0,k,l;
1608 ideal h,hh, h3;
1609 rRingOrder_t *ord;
1610 int *block0,*block1;
1611 int ordersize=2;
1612 int **wv;
1613 tHomog hom;
1614 intvec * w;
1615 ring tmpR;
1616 ring origR = currRing;
1617
1618 if (delVar==NULL)
1619 {
1620 return idCopy(h1);
1621 }
1622 if ((currRing->qideal!=NULL) && rIsPluralRing(origR))
1623 {
1624 WerrorS("cannot eliminate in a qring");
1625 return NULL;
1626 }
1627 if (idIs0(h1)) return idInit(1,h1->rank);
1628#ifdef HAVE_PLURAL
1629 if (rIsPluralRing(origR))
1630 /* in the NC case, we have to check the admissibility of */
1631 /* the subalgebra to be intersected with */
1632 {
1633 if ((ncRingType(origR) != nc_skew) && (ncRingType(origR) != nc_exterior)) /* in (quasi)-commutative algebras every subalgebra is admissible */
1634 {
1635 if (nc_CheckSubalgebra(delVar,origR))
1636 {
1637 WerrorS("no elimination is possible: subalgebra is not admissible");
1638 return NULL;
1639 }
1640 }
1641 }
1642#endif
1643 hom=(tHomog)idHomModule(h1,NULL,&w); //sets w to weight vector or NULL
1644 h3=idInit(16,h1->rank);
1645 ordersize=rBlocks(origR)+1;
1646#if 0
1647 if (rIsPluralRing(origR)) // we have too keep the odering: it may be needed
1648 // for G-algebra
1649 {
1650 for (k=0;k<ordersize-1; k++)
1651 {
1652 block0[k+1] = origR->block0[k];
1653 block1[k+1] = origR->block1[k];
1654 ord[k+1] = origR->order[k];
1655 if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1656 }
1657 }
1658 else
1659 {
1660 block0[1] = 1;
1661 block1[1] = (currRing->N);
1662 if (origR->OrdSgn==1) ord[1] = ringorder_wp;
1663 else ord[1] = ringorder_ws;
1664 wv[1]=(int*)omAlloc0((currRing->N)*sizeof(int));
1665 double wNsqr = (double)2.0 / (double)(currRing->N);
1667 int *x= (int * )omAlloc(2 * ((currRing->N) + 1) * sizeof(int));
1668 int sl=IDELEMS(h1) - 1;
1669 wCall(h1->m, sl, x, wNsqr);
1670 for (sl = (currRing->N); sl!=0; sl--)
1671 wv[1][sl-1] = x[sl + (currRing->N) + 1];
1672 omFreeSize((ADDRESS)x, 2 * ((currRing->N) + 1) * sizeof(int));
1673
1674 ord[2]=ringorder_C;
1675 ord[3]=0;
1676 }
1677#else
1678#endif
1679 if ((hom==TRUE) && (origR->OrdSgn==1) && (!rIsPluralRing(origR)))
1680 {
1681 #if 1
1682 // we change to an ordering:
1683 // aa(1,1,1,...,0,0,0),wp(...),C
1684 // this seems to be better than version 2 below,
1685 // according to Tst/../elimiate_[3568].tat (- 17 %)
1686 ord=(rRingOrder_t*)omAlloc0(4*sizeof(rRingOrder_t));
1687 block0=(int*)omAlloc0(4*sizeof(int));
1688 block1=(int*)omAlloc0(4*sizeof(int));
1689 wv=(int**) omAlloc0(4*sizeof(int**));
1690 block0[0] = block0[1] = 1;
1691 block1[0] = block1[1] = rVar(origR);
1692 wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1693 // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1694 // ignore it
1695 ord[0] = ringorder_aa;
1696 for (j=0;j<rVar(origR);j++)
1697 if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1698 BOOLEAN wp=FALSE;
1699 for (j=0;j<rVar(origR);j++)
1700 if (p_Weight(j+1,origR)!=1) { wp=TRUE;break; }
1701 if (wp)
1702 {
1703 wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1704 for (j=0;j<rVar(origR);j++)
1705 wv[1][j]=p_Weight(j+1,origR);
1706 ord[1] = ringorder_wp;
1707 }
1708 else
1709 ord[1] = ringorder_dp;
1710 #else
1711 // we change to an ordering:
1712 // a(w1,...wn),wp(1,...0.....),C
1713 ord=(int*)omAlloc0(4*sizeof(int));
1714 block0=(int*)omAlloc0(4*sizeof(int));
1715 block1=(int*)omAlloc0(4*sizeof(int));
1716 wv=(int**) omAlloc0(4*sizeof(int**));
1717 block0[0] = block0[1] = 1;
1718 block1[0] = block1[1] = rVar(origR);
1719 wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1720 wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1721 ord[0] = ringorder_a;
1722 for (j=0;j<rVar(origR);j++)
1723 wv[0][j]=pWeight(j+1,origR);
1724 ord[1] = ringorder_wp;
1725 for (j=0;j<rVar(origR);j++)
1726 if (pGetExp(delVar,j+1)!=0) wv[1][j]=1;
1727 #endif
1728 ord[2] = ringorder_C;
1729 ord[3] = (rRingOrder_t)0;
1730 }
1731 else
1732 {
1733 // we change to an ordering:
1734 // aa(....),orig_ordering
1735 ord=(rRingOrder_t*)omAlloc0(ordersize*sizeof(rRingOrder_t));
1736 block0=(int*)omAlloc0(ordersize*sizeof(int));
1737 block1=(int*)omAlloc0(ordersize*sizeof(int));
1738 wv=(int**) omAlloc0(ordersize*sizeof(int**));
1739 for (k=0;k<ordersize-1; k++)
1740 {
1741 block0[k+1] = origR->block0[k];
1742 block1[k+1] = origR->block1[k];
1743 ord[k+1] = origR->order[k];
1744 if (origR->wvhdl[k]!=NULL)
1745 #ifdef HAVE_OMALLOC
1746 wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1747 #else
1748 {
1749 int l=(origR->block1[k]-origR->block0[k]+1)*sizeof(int);
1750 if (origR->order[k]==ringorder_a64) l*=2;
1751 wv[k+1]=(int*)omalloc(l);
1752 memcpy(wv[k+1],origR->wvhdl[k],l);
1753 }
1754 #endif
1755 }
1756 block0[0] = 1;
1757 block1[0] = rVar(origR);
1758 wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1759 for (j=0;j<rVar(origR);j++)
1760 if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1761 // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1762 // ignore it
1763 ord[0] = ringorder_aa;
1764 }
1765 // fill in tmp ring to get back the data later on
1766 tmpR = rCopy0(origR,FALSE,FALSE); // qring==NULL
1767 //rUnComplete(tmpR);
1768 tmpR->p_Procs=NULL;
1769 tmpR->order = ord;
1770 tmpR->block0 = block0;
1771 tmpR->block1 = block1;
1772 tmpR->wvhdl = wv;
1773 rComplete(tmpR, 1);
1774
1775#ifdef HAVE_PLURAL
1776 /* update nc structure on tmpR */
1777 if (rIsPluralRing(origR))
1778 {
1779 if ( nc_rComplete(origR, tmpR, false) ) // no quotient ideal!
1780 {
1781 WerrorS("no elimination is possible: ordering condition is violated");
1782 // cleanup
1783 rDelete(tmpR);
1784 if (w!=NULL)
1785 delete w;
1786 return NULL;
1787 }
1788 }
1789#endif
1790 // change into the new ring
1791 //pChangeRing((currRing->N),currRing->OrdSgn,ord,block0,block1,wv);
1792 rChangeCurrRing(tmpR);
1793
1794 //h = idInit(IDELEMS(h1),h1->rank);
1795 // fetch data from the old ring
1796 //for (k=0;k<IDELEMS(h1);k++) h->m[k] = prCopyR( h1->m[k], origR);
1797 h=idrCopyR(h1,origR,currRing);
1798 if (origR->qideal!=NULL)
1799 {
1800 WarnS("eliminate in q-ring: experimental");
1801 ideal q=idrCopyR(origR->qideal,origR,currRing);
1802 ideal s=idSimpleAdd(h,q);
1803 idDelete(&h);
1804 idDelete(&q);
1805 h=s;
1806 }
1807 // compute GB
1808 if ((alg!=GbDefault)
1809 && (alg!=GbGroebner)
1810 && (alg!=GbModstd)
1811 && (alg!=GbSlimgb)
1812 && (alg!=GbSba)
1813 && (alg!=GbStd))
1814 {
1815 WarnS("wrong algorithm for GB");
1816 alg=GbDefault;
1817 }
1818 hh=idGroebner(h,0,alg,hilb);
1819 // go back to the original ring
1820 rChangeCurrRing(origR);
1821 i = IDELEMS(hh)-1;
1822 while ((i >= 0) && (hh->m[i] == NULL)) i--;
1823 j = -1;
1824 // fetch data from temp ring
1825 for (k=0; k<=i; k++)
1826 {
1827 l=(currRing->N);
1828 while ((l>0) && (p_GetExp( hh->m[k],l,tmpR)*pGetExp(delVar,l)==0)) l--;
1829 if (l==0)
1830 {
1831 j++;
1832 if (j >= IDELEMS(h3))
1833 {
1834 pEnlargeSet(&(h3->m),IDELEMS(h3),16);
1835 IDELEMS(h3) += 16;
1836 }
1837 h3->m[j] = prMoveR( hh->m[k], tmpR,origR);
1838 hh->m[k] = NULL;
1839 }
1840 }
1841 id_Delete(&hh, tmpR);
1842 idSkipZeroes(h3);
1843 rDelete(tmpR);
1844 if (w!=NULL)
1845 delete w;
1846 return h3;
1847}
1848
1849#ifdef WITH_OLD_MINOR
1850/*2
1851* compute the which-th ar-minor of the matrix a
1852*/
1853poly idMinor(matrix a, int ar, unsigned long which, ideal R)
1854{
1855 int i,j/*,k,size*/;
1856 unsigned long curr;
1857 int *rowchoise,*colchoise;
1858 BOOLEAN rowch,colch;
1859 // ideal result;
1860 matrix tmp;
1861 poly p,q;
1862
1863 rowchoise=(int *)omAlloc(ar*sizeof(int));
1864 colchoise=(int *)omAlloc(ar*sizeof(int));
1865 tmp=mpNew(ar,ar);
1866 curr = 0; /* index of current minor */
1867 idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1868 while (!rowch)
1869 {
1870 idInitChoise(ar,1,a->cols(),&colch,colchoise);
1871 while (!colch)
1872 {
1873 if (curr == which)
1874 {
1875 for (i=1; i<=ar; i++)
1876 {
1877 for (j=1; j<=ar; j++)
1878 {
1879 MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1880 }
1881 }
1882 p = mp_DetBareiss(tmp,currRing);
1883 if (p!=NULL)
1884 {
1885 if (R!=NULL)
1886 {
1887 q = p;
1888 p = kNF(R,currRing->qideal,q);
1889 p_Delete(&q,currRing);
1890 }
1891 }
1892 /*delete the matrix tmp*/
1893 for (i=1; i<=ar; i++)
1894 {
1895 for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1896 }
1897 idDelete((ideal*)&tmp);
1898 omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1899 omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1900 return (p);
1901 }
1902 curr++;
1903 idGetNextChoise(ar,a->cols(),&colch,colchoise);
1904 }
1905 idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1906 }
1907 return (poly) 1;
1908}
1909
1910/*2
1911* compute all ar-minors of the matrix a
1912*/
1913ideal idMinors(matrix a, int ar, ideal R)
1914{
1915 int i,j,/*k,*/size;
1916 int *rowchoise,*colchoise;
1917 BOOLEAN rowch,colch;
1918 ideal result;
1919 matrix tmp;
1920 poly p,q;
1921
1922 i = binom(a->rows(),ar);
1923 j = binom(a->cols(),ar);
1924 size=i*j;
1925
1926 rowchoise=(int *)omAlloc(ar*sizeof(int));
1927 colchoise=(int *)omAlloc(ar*sizeof(int));
1928 result=idInit(size,1);
1929 tmp=mpNew(ar,ar);
1930 // k = 0; /* the index in result*/
1931 idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1932 while (!rowch)
1933 {
1934 idInitChoise(ar,1,a->cols(),&colch,colchoise);
1935 while (!colch)
1936 {
1937 for (i=1; i<=ar; i++)
1938 {
1939 for (j=1; j<=ar; j++)
1940 {
1941 MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1942 }
1943 }
1944 p = mp_DetBareiss(tmp,currRing);
1945 if (p!=NULL)
1946 {
1947 if (R!=NULL)
1948 {
1949 q = p;
1950 p = kNF(R,currRing->qideal,q);
1951 p_Delete(&q,currRing);
1952 }
1953 }
1954 if (k>=size)
1955 {
1956 pEnlargeSet(&result->m,size,32);
1957 size += 32;
1958 }
1959 result->m[k] = p;
1960 k++;
1961 idGetNextChoise(ar,a->cols(),&colch,colchoise);
1962 }
1963 idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1964 }
1965 /*delete the matrix tmp*/
1966 for (i=1; i<=ar; i++)
1967 {
1968 for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1969 }
1970 idDelete((ideal*)&tmp);
1971 if (k==0)
1972 {
1973 k=1;
1974 result->m[0]=NULL;
1975 }
1976 omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1977 omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1979 IDELEMS(result) = k;
1980 return (result);
1981}
1982#else
1983
1984
1985/// compute all ar-minors of the matrix a
1986/// the caller of mpRecMin
1987/// the elements of the result are not in R (if R!=NULL)
1988ideal idMinors(matrix a, int ar, ideal R)
1989{
1990
1991 const ring origR=currRing;
1992 id_Test((ideal)a, origR);
1993
1994 const int r = a->nrows;
1995 const int c = a->ncols;
1996
1997 if((ar<=0) || (ar>r) || (ar>c))
1998 {
1999 Werror("%d-th minor, matrix is %dx%d",ar,r,c);
2000 return NULL;
2001 }
2002
2003 ideal h = id_Matrix2Module(mp_Copy(a,origR),origR);
2004 long bound = sm_ExpBound(h,c,r,ar,origR);
2005 id_Delete(&h, origR);
2006
2007 ring tmpR = sm_RingChange(origR,bound);
2008
2009 matrix b = mpNew(r,c);
2010
2011 for (int i=r*c-1;i>=0;i--)
2012 if (a->m[i] != NULL)
2013 b->m[i] = prCopyR(a->m[i],origR,tmpR);
2014
2015 id_Test( (ideal)b, tmpR);
2016
2017 if (R!=NULL)
2018 {
2019 R = idrCopyR(R,origR,tmpR); // TODO: overwrites R? memory leak?
2020 //if (ar>1) // otherwise done in mpMinorToResult
2021 //{
2022 // matrix bb=(matrix)kNF(R,currRing->qideal,(ideal)b);
2023 // bb->rank=b->rank; bb->nrows=b->nrows; bb->ncols=b->ncols;
2024 // idDelete((ideal*)&b); b=bb;
2025 //}
2026 id_Test( R, tmpR);
2027 }
2028
2029 int size=binom(r,ar)*binom(c,ar);
2030 ideal result = idInit(size,1);
2031
2032 int elems = 0;
2033
2034 if(ar>1)
2035 mp_RecMin(ar-1,result,elems,b,r,c,NULL,R,tmpR);
2036 else
2037 mp_MinorToResult(result,elems,b,r,c,R,tmpR);
2038
2039 id_Test( (ideal)b, tmpR);
2040
2041 id_Delete((ideal *)&b, tmpR);
2042
2043 if (R!=NULL) id_Delete(&R,tmpR);
2044
2045 rChangeCurrRing(origR);
2046 result = idrMoveR(result,tmpR,origR);
2047 sm_KillModifiedRing(tmpR);
2048 idTest(result);
2049 return result;
2050}
2051#endif
2052
2053/*2
2054*returns TRUE if id1 is a submodule of id2
2055*/
2056BOOLEAN idIsSubModule(ideal id1,ideal id2)
2057{
2058 int i;
2059 poly p;
2060
2061 if (idIs0(id1)) return TRUE;
2062 for (i=0;i<IDELEMS(id1);i++)
2063 {
2064 if (id1->m[i] != NULL)
2065 {
2066 p = kNF(id2,currRing->qideal,id1->m[i]);
2067 if (p != NULL)
2068 {
2070 return FALSE;
2071 }
2072 }
2073 }
2074 return TRUE;
2075}
2076
2078{
2079 if ((Q!=NULL) && (!idHomIdeal(Q,NULL))) { PrintS(" Q not hom\n"); return FALSE;}
2080 if (idIs0(m)) return TRUE;
2081
2082 int cmax=-1;
2083 int i;
2084 poly p=NULL;
2085 int length=IDELEMS(m);
2086 polyset P=m->m;
2087 for (i=length-1;i>=0;i--)
2088 {
2089 p=P[i];
2090 if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
2091 }
2092 if (w != NULL)
2093 if (w->length()+1 < cmax)
2094 {
2095 // Print("length: %d - %d \n", w->length(),cmax);
2096 return FALSE;
2097 }
2098
2099 if(w!=NULL)
2101
2102 for (i=length-1;i>=0;i--)
2103 {
2104 p=P[i];
2105 if (p!=NULL)
2106 {
2107 int d=currRing->pFDeg(p,currRing);
2108 loop
2109 {
2110 pIter(p);
2111 if (p==NULL) break;
2112 if (d!=currRing->pFDeg(p,currRing))
2113 {
2114 //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
2115 if(w!=NULL)
2117 return FALSE;
2118 }
2119 }
2120 }
2121 }
2122
2123 if(w!=NULL)
2125
2126 return TRUE;
2127}
2128
2129ideal idSeries(int n,ideal M,matrix U,intvec *w)
2130{
2131 for(int i=IDELEMS(M)-1;i>=0;i--)
2132 {
2133 if(U==NULL)
2134 M->m[i]=pSeries(n,M->m[i],NULL,w);
2135 else
2136 {
2137 M->m[i]=pSeries(n,M->m[i],MATELEM(U,i+1,i+1),w);
2138 MATELEM(U,i+1,i+1)=NULL;
2139 }
2140 }
2141 if(U!=NULL)
2142 idDelete((ideal*)&U);
2143 return M;
2144}
2145
2147{
2148 int e=MATCOLS(i)*MATROWS(i);
2150 r->rank=i->rank;
2151 int j;
2152 for(j=0; j<e; j++)
2153 {
2154 r->m[j]=pDiff(i->m[j],k);
2155 }
2156 return r;
2157}
2158
2159matrix idDiffOp(ideal I, ideal J,BOOLEAN multiply)
2160{
2161 matrix r=mpNew(IDELEMS(I),IDELEMS(J));
2162 int i,j;
2163 for(i=0; i<IDELEMS(I); i++)
2164 {
2165 for(j=0; j<IDELEMS(J); j++)
2166 {
2167 MATELEM(r,i+1,j+1)=pDiffOp(I->m[i],J->m[j],multiply);
2168 }
2169 }
2170 return r;
2171}
2172
2173/*3
2174*handles for some ideal operations the ring/syzcomp management
2175*returns all syzygies (componentwise-)shifted by -syzcomp
2176*or -syzcomp-1 (in case of ideals as input)
2177static ideal idHandleIdealOp(ideal arg,int syzcomp,int isIdeal=FALSE)
2178{
2179 ring orig_ring=currRing;
2180 ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE); rChangeCurrRing(syz_ring);
2181 rSetSyzComp(length, syz_ring);
2182
2183 ideal s_temp;
2184 if (orig_ring!=syz_ring)
2185 s_temp=idrMoveR_NoSort(arg,orig_ring, syz_ring);
2186 else
2187 s_temp=arg;
2188
2189 ideal s_temp1 = kStd(s_temp,currRing->qideal,testHomog,&w,NULL,length);
2190 if (w!=NULL) delete w;
2191
2192 if (syz_ring!=orig_ring)
2193 {
2194 idDelete(&s_temp);
2195 rChangeCurrRing(orig_ring);
2196 }
2197
2198 idDelete(&temp);
2199 ideal temp1=idRingCopy(s_temp1,syz_ring);
2200
2201 if (syz_ring!=orig_ring)
2202 {
2203 rChangeCurrRing(syz_ring);
2204 idDelete(&s_temp1);
2205 rChangeCurrRing(orig_ring);
2206 rDelete(syz_ring);
2207 }
2208
2209 for (i=0;i<IDELEMS(temp1);i++)
2210 {
2211 if ((temp1->m[i]!=NULL)
2212 && (pGetComp(temp1->m[i])<=length))
2213 {
2214 pDelete(&(temp1->m[i]));
2215 }
2216 else
2217 {
2218 p_Shift(&(temp1->m[i]),-length,currRing);
2219 }
2220 }
2221 temp1->rank = rk;
2222 idSkipZeroes(temp1);
2223
2224 return temp1;
2225}
2226*/
2227
2228#ifdef HAVE_SHIFTBBA
2229ideal idModuloLP (ideal h2,ideal h1, tHomog, intvec ** w, matrix *T, GbVariant alg)
2230{
2231 intvec *wtmp=NULL;
2232 if (T!=NULL) idDelete((ideal*)T);
2233
2234 int i,k,rk,flength=0,slength,length;
2235 poly p,q;
2236
2237 if (idIs0(h2))
2238 return idFreeModule(si_max(1,h2->ncols));
2239 if (!idIs0(h1))
2240 flength = id_RankFreeModule(h1,currRing);
2241 slength = id_RankFreeModule(h2,currRing);
2242 length = si_max(flength,slength);
2243 if (length==0)
2244 {
2245 length = 1;
2246 }
2247 ideal temp = idInit(IDELEMS(h2),length+IDELEMS(h2));
2248 if ((w!=NULL)&&((*w)!=NULL))
2249 {
2250 //Print("input weights:");(*w)->show(1);PrintLn();
2251 int d;
2252 int k;
2253 wtmp=new intvec(length+IDELEMS(h2));
2254 for (i=0;i<length;i++)
2255 ((*wtmp)[i])=(**w)[i];
2256 for (i=0;i<IDELEMS(h2);i++)
2257 {
2258 poly p=h2->m[i];
2259 if (p!=NULL)
2260 {
2261 d = p_Deg(p,currRing);
2262 k= pGetComp(p);
2263 if (slength>0) k--;
2264 d +=((**w)[k]);
2265 ((*wtmp)[i+length]) = d;
2266 }
2267 }
2268 //Print("weights:");wtmp->show(1);PrintLn();
2269 }
2270 for (i=0;i<IDELEMS(h2);i++)
2271 {
2272 temp->m[i] = pCopy(h2->m[i]);
2273 q = pOne();
2274 // non multiplicative variable
2275 pSetExp(q, currRing->isLPring - currRing->LPncGenCount + i + 1, 1);
2276 p_Setm(q, currRing);
2277 pSetComp(q,i+1+length);
2278 pSetmComp(q);
2279 if(temp->m[i]!=NULL)
2280 {
2281 if (slength==0) p_Shift(&(temp->m[i]),1,currRing);
2282 p = temp->m[i];
2283 temp->m[i] = pAdd(p, q);
2284 }
2285 else
2286 temp->m[i]=q;
2287 }
2288 rk = k = IDELEMS(h2);
2289 if (!idIs0(h1))
2290 {
2291 pEnlargeSet(&(temp->m),IDELEMS(temp),IDELEMS(h1));
2292 IDELEMS(temp) += IDELEMS(h1);
2293 for (i=0;i<IDELEMS(h1);i++)
2294 {
2295 if (h1->m[i]!=NULL)
2296 {
2297 temp->m[k] = pCopy(h1->m[i]);
2298 if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
2299 k++;
2300 }
2301 }
2302 }
2303
2304 ring orig_ring=currRing;
2305 ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE);
2306 rSetSyzComp(length,syz_ring);
2307 rChangeCurrRing(syz_ring);
2308 // we can use OPT_RETURN_SB only, if syz_ring==orig_ring,
2309 // therefore we disable OPT_RETURN_SB for modulo:
2310 // (see tr. #701)
2311 //if (TEST_OPT_RETURN_SB)
2312 // rSetSyzComp(IDELEMS(h2)+length, syz_ring);
2313 //else
2314 // rSetSyzComp(length, syz_ring);
2315 ideal s_temp;
2316
2317 if (syz_ring != orig_ring)
2318 {
2319 s_temp = idrMoveR_NoSort(temp, orig_ring, syz_ring);
2320 }
2321 else
2322 {
2323 s_temp = temp;
2324 }
2325
2326 idTest(s_temp);
2327 unsigned save_opt,save_opt2;
2328 SI_SAVE_OPT1(save_opt);
2329 SI_SAVE_OPT2(save_opt2);
2332 ideal s_temp1 = idGroebner(s_temp,length,alg);
2333 SI_RESTORE_OPT1(save_opt);
2334 SI_RESTORE_OPT2(save_opt2);
2335
2336 //if (wtmp!=NULL) Print("output weights:");wtmp->show(1);PrintLn();
2337 if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
2338 {
2339 delete *w;
2340 *w=new intvec(IDELEMS(h2));
2341 for (i=0;i<IDELEMS(h2);i++)
2342 ((**w)[i])=(*wtmp)[i+length];
2343 }
2344 if (wtmp!=NULL) delete wtmp;
2345
2346 if (T==NULL)
2347 {
2348 for (i=0;i<IDELEMS(s_temp1);i++)
2349 {
2350 if (s_temp1->m[i]!=NULL)
2351 {
2352 if (((int)pGetComp(s_temp1->m[i]))<=length)
2353 {
2354 p_Delete(&(s_temp1->m[i]),currRing);
2355 }
2356 else
2357 {
2358 p_Shift(&(s_temp1->m[i]),-length,currRing);
2359 }
2360 }
2361 }
2362 }
2363 else
2364 {
2365 *T=mpNew(IDELEMS(s_temp1),IDELEMS(h2));
2366 for (i=0;i<IDELEMS(s_temp1);i++)
2367 {
2368 if (s_temp1->m[i]!=NULL)
2369 {
2370 if (((int)pGetComp(s_temp1->m[i]))<=length)
2371 {
2372 do
2373 {
2374 p_LmDelete(&(s_temp1->m[i]),currRing);
2375 } while((int)pGetComp(s_temp1->m[i])<=length);
2376 poly q = prMoveR( s_temp1->m[i], syz_ring,orig_ring);
2377 s_temp1->m[i] = NULL;
2378 if (q!=NULL)
2379 {
2380 q=pReverse(q);
2381 do
2382 {
2383 poly p = q;
2384 long t=pGetComp(p);
2385 pIter(q);
2386 pNext(p) = NULL;
2387 pSetComp(p,0);
2388 pSetmComp(p);
2389 pTest(p);
2390 MATELEM(*T,(int)t-length,i) = pAdd(MATELEM(*T,(int)t-length,i),p);
2391 } while (q != NULL);
2392 }
2393 }
2394 else
2395 {
2396 p_Shift(&(s_temp1->m[i]),-length,currRing);
2397 }
2398 }
2399 }
2400 }
2401 s_temp1->rank = rk;
2402 idSkipZeroes(s_temp1);
2403
2404 if (syz_ring!=orig_ring)
2405 {
2406 rChangeCurrRing(orig_ring);
2407 s_temp1 = idrMoveR_NoSort(s_temp1, syz_ring, orig_ring);
2408 rDelete(syz_ring);
2409 // Hmm ... here seems to be a memory leak
2410 // However, simply deleting it causes memory trouble
2411 // idDelete(&s_temp);
2412 }
2413 idTest(s_temp1);
2414 return s_temp1;
2415}
2416#endif
2417
2418/*2
2419* represents (h1+h2)/h2=h1/(h1 intersect h2)
2420*/
2421//ideal idModulo (ideal h2,ideal h1)
2422ideal idModulo (ideal h2,ideal h1, tHomog hom, intvec ** w, matrix *T, GbVariant alg)
2423{
2424#ifdef HAVE_SHIFTBBA
2425 if (rIsLPRing(currRing))
2426 return idModuloLP(h2,h1,hom,w,T,alg);
2427#endif
2428 intvec *wtmp=NULL;
2429 if (T!=NULL) idDelete((ideal*)T);
2430
2431 int i,flength=0,slength,length;
2432
2433 if (idIs0(h2))
2434 return idFreeModule(si_max(1,h2->ncols));
2435 if (!idIs0(h1))
2436 flength = id_RankFreeModule(h1,currRing);
2437 slength = id_RankFreeModule(h2,currRing);
2438 length = si_max(flength,slength);
2439 BOOLEAN inputIsIdeal=FALSE;
2440 if (length==0)
2441 {
2442 length = 1;
2443 inputIsIdeal=TRUE;
2444 }
2445 if ((w!=NULL)&&((*w)!=NULL))
2446 {
2447 //Print("input weights:");(*w)->show(1);PrintLn();
2448 int d;
2449 int k;
2450 wtmp=new intvec(length+IDELEMS(h2));
2451 for (i=0;i<length;i++)
2452 ((*wtmp)[i])=(**w)[i];
2453 for (i=0;i<IDELEMS(h2);i++)
2454 {
2455 poly p=h2->m[i];
2456 if (p!=NULL)
2457 {
2458 d = p_Deg(p,currRing);
2459 k= pGetComp(p);
2460 if (slength>0) k--;
2461 d +=((**w)[k]);
2462 ((*wtmp)[i+length]) = d;
2463 }
2464 }
2465 //Print("weights:");wtmp->show(1);PrintLn();
2466 }
2467 ideal s_temp1;
2468 ring orig_ring=currRing;
2469 ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE);
2470 rSetSyzComp(length,syz_ring);
2471 {
2472 rChangeCurrRing(syz_ring);
2473 ideal s1,s2;
2474
2475 if (syz_ring != orig_ring)
2476 {
2477 s1 = idrCopyR_NoSort(h1, orig_ring, syz_ring);
2478 s2 = idrCopyR_NoSort(h2, orig_ring, syz_ring);
2479 }
2480 else
2481 {
2482 s1=idCopy(h1);
2483 s2=idCopy(h2);
2484 }
2485
2486 unsigned save_opt,save_opt2;
2487 SI_SAVE_OPT1(save_opt);
2488 SI_SAVE_OPT2(save_opt2);
2489 if (T==NULL) si_opt_1 |= Sy_bit(OPT_REDTAIL);
2491 s_temp1 = idPrepare(s2,s1,testHomog,length,w,alg);
2492 SI_RESTORE_OPT1(save_opt);
2493 SI_RESTORE_OPT2(save_opt2);
2494 }
2495
2496 //if (wtmp!=NULL) Print("output weights:");wtmp->show(1);PrintLn();
2497 if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
2498 {
2499 delete *w;
2500 *w=new intvec(IDELEMS(h2));
2501 for (i=0;i<IDELEMS(h2);i++)
2502 ((**w)[i])=(*wtmp)[i+length];
2503 }
2504 if (wtmp!=NULL) delete wtmp;
2505
2506 ideal result=idInit(IDELEMS(s_temp1),IDELEMS(h2));
2507 s_temp1=idExtractG_T_S(s_temp1,T,&result,length,IDELEMS(h2),inputIsIdeal,orig_ring,syz_ring);
2508
2509 idDelete(&s_temp1);
2510 if (syz_ring!=orig_ring)
2511 {
2512 rDelete(syz_ring);
2513 }
2514 idTest(h2);
2515 idTest(h1);
2516 idTest(result);
2517 if (T!=NULL) idTest((ideal)*T);
2518 return result;
2519}
2520
2521/*
2522*computes module-weights for liftings of homogeneous modules
2523*/
2524#if 0
2525static intvec * idMWLift(ideal mod,intvec * weights)
2526{
2527 if (idIs0(mod)) return new intvec(2);
2528 int i=IDELEMS(mod);
2529 while ((i>0) && (mod->m[i-1]==NULL)) i--;
2530 intvec *result = new intvec(i+1);
2531 while (i>0)
2532 {
2533 (*result)[i]=currRing->pFDeg(mod->m[i],currRing)+(*weights)[pGetComp(mod->m[i])];
2534 }
2535 return result;
2536}
2537#endif
2538
2539/*2
2540*sorts the kbase for idCoef* in a special way (lexicographically
2541*with x_max,...,x_1)
2542*/
2543ideal idCreateSpecialKbase(ideal kBase,intvec ** convert)
2544{
2545 int i;
2546 ideal result;
2547
2548 if (idIs0(kBase)) return NULL;
2549 result = idInit(IDELEMS(kBase),kBase->rank);
2550 *convert = idSort(kBase,FALSE);
2551 for (i=0;i<(*convert)->length();i++)
2552 {
2553 result->m[i] = pCopy(kBase->m[(**convert)[i]-1]);
2554 }
2555 return result;
2556}
2557
2558/*2
2559*returns the index of a given monom in the list of the special kbase
2560*/
2561int idIndexOfKBase(poly monom, ideal kbase)
2562{
2563 int j=IDELEMS(kbase);
2564
2565 while ((j>0) && (kbase->m[j-1]==NULL)) j--;
2566 if (j==0) return -1;
2567 int i=(currRing->N);
2568 while (i>0)
2569 {
2570 loop
2571 {
2572 if (pGetExp(monom,i)>pGetExp(kbase->m[j-1],i)) return -1;
2573 if (pGetExp(monom,i)==pGetExp(kbase->m[j-1],i)) break;
2574 j--;
2575 if (j==0) return -1;
2576 }
2577 if (i==1)
2578 {
2579 while(j>0)
2580 {
2581 if (pGetComp(monom)==pGetComp(kbase->m[j-1])) return j-1;
2582 if (pGetComp(monom)>pGetComp(kbase->m[j-1])) return -1;
2583 j--;
2584 }
2585 }
2586 i--;
2587 }
2588 return -1;
2589}
2590
2591/*2
2592*decomposes the monom in a part of coefficients described by the
2593*complement of how and a monom in variables occurring in how, the
2594*index of which in kbase is returned as integer pos (-1 if it don't
2595*exists)
2596*/
2597poly idDecompose(poly monom, poly how, ideal kbase, int * pos)
2598{
2599 int i;
2600 poly coeff=pOne(), base=pOne();
2601
2602 for (i=1;i<=(currRing->N);i++)
2603 {
2604 if (pGetExp(how,i)>0)
2605 {
2606 pSetExp(base,i,pGetExp(monom,i));
2607 }
2608 else
2609 {
2610 pSetExp(coeff,i,pGetExp(monom,i));
2611 }
2612 }
2613 pSetComp(base,pGetComp(monom));
2614 pSetm(base);
2615 pSetCoeff(coeff,nCopy(pGetCoeff(monom)));
2616 pSetm(coeff);
2617 *pos = idIndexOfKBase(base,kbase);
2618 if (*pos<0)
2619 p_Delete(&coeff,currRing);
2620 p_Delete(&base,currRing);
2621 return coeff;
2622}
2623
2624/*2
2625*returns a matrix A of coefficients with kbase*A=arg
2626*if all monomials in variables of how occur in kbase
2627*the other are deleted
2628*/
2629matrix idCoeffOfKBase(ideal arg, ideal kbase, poly how)
2630{
2631 matrix result;
2632 ideal tempKbase;
2633 poly p,q;
2634 intvec * convert;
2635 int i=IDELEMS(kbase),j=IDELEMS(arg),k,pos;
2636#if 0
2637 while ((i>0) && (kbase->m[i-1]==NULL)) i--;
2638 if (idIs0(arg))
2639 return mpNew(i,1);
2640 while ((j>0) && (arg->m[j-1]==NULL)) j--;
2641 result = mpNew(i,j);
2642#else
2643 result = mpNew(i, j);
2644 while ((j>0) && (arg->m[j-1]==NULL)) j--;
2645#endif
2646
2647 tempKbase = idCreateSpecialKbase(kbase,&convert);
2648 for (k=0;k<j;k++)
2649 {
2650 p = arg->m[k];
2651 while (p!=NULL)
2652 {
2653 q = idDecompose(p,how,tempKbase,&pos);
2654 if (pos>=0)
2655 {
2656 MATELEM(result,(*convert)[pos],k+1) =
2657 pAdd(MATELEM(result,(*convert)[pos],k+1),q);
2658 }
2659 else
2660 p_Delete(&q,currRing);
2661 pIter(p);
2662 }
2663 }
2664 idDelete(&tempKbase);
2665 return result;
2666}
2667
2668static void idDeleteComps(ideal arg,int* red_comp,int del)
2669// red_comp is an array [0..args->rank]
2670{
2671 int i,j;
2672 poly p;
2673
2674 for (i=IDELEMS(arg)-1;i>=0;i--)
2675 {
2676 p = arg->m[i];
2677 while (p!=NULL)
2678 {
2679 j = pGetComp(p);
2680 if (red_comp[j]!=j)
2681 {
2682 pSetComp(p,red_comp[j]);
2683 pSetmComp(p);
2684 }
2685 pIter(p);
2686 }
2687 }
2688 (arg->rank) -= del;
2689}
2690
2691/*3
2692* searches for the next unit in the components of the module arg and
2693* returns the first one;
2694*/
2695static int id_ReadOutPivot(ideal arg,int* comp, const ring r)
2696{
2697 int i=0,j, generator=-1;
2698 int rk_arg=arg->rank; //idRankFreeModule(arg);
2699 int * componentIsUsed =(int *)omAlloc((rk_arg+1)*sizeof(int));
2700 poly p;
2701
2702 while ((generator<0) && (i<IDELEMS(arg)))
2703 {
2704 memset(componentIsUsed,0,(rk_arg+1)*sizeof(int));
2705 p = arg->m[i];
2706 if (rField_is_Ring(r))
2707 {
2708 while (p!=NULL)
2709 {
2710 j = __p_GetComp(p,r);
2711 if (componentIsUsed[j]==0)
2712 {
2713 if (p_LmIsConstantComp(p,r) &&
2714 n_IsUnit(pGetCoeff(p),r->cf))
2715 {
2716 generator = i;
2717 componentIsUsed[j] = 1;
2718 }
2719 else
2720 {
2721 componentIsUsed[j] = -1;
2722 }
2723 }
2724 else if (componentIsUsed[j]>0)
2725 {
2726 (componentIsUsed[j])++;
2727 }
2728 pIter(p);
2729 }
2730 }
2731 else
2732 {
2733 while (p!=NULL)
2734 {
2735 j = __p_GetComp(p,r);
2736 if (componentIsUsed[j]==0)
2737 {
2738 if (p_LmIsConstantComp(p,r))
2739 {
2740 generator = i;
2741 componentIsUsed[j] = 1;
2742 }
2743 else
2744 {
2745 componentIsUsed[j] = -1;
2746 }
2747 }
2748 else if (componentIsUsed[j]>0)
2749 {
2750 (componentIsUsed[j])++;
2751 }
2752 pIter(p);
2753 }
2754 }
2755 i++;
2756 }
2757 i = 0;
2758 *comp = -1;
2759 for (j=0;j<=rk_arg;j++)
2760 {
2761 if (componentIsUsed[j]>0)
2762 {
2763 if ((*comp==-1) || (componentIsUsed[j]<i))
2764 {
2765 *comp = j;
2766 i= componentIsUsed[j];
2767 }
2768 }
2769 }
2770 omFree(componentIsUsed);
2771 return generator;
2772}
2773
2774/*2
2775* returns the presentation of an isomorphic, minimally
2776* embedded module (arg represents the quotient!)
2777*/
2778static ideal idMinEmbedding1(ideal arg,BOOLEAN inPlace, intvec **w,
2779 int* red_comp, int &del)
2780{
2781 if (idIs0(arg)) return idInit(1,arg->rank);
2782 int i,next_gen,next_comp;
2783 ideal res=arg;
2784 if (!inPlace) res = idCopy(arg);
2786 for (i=res->rank;i>=0;i--) red_comp[i]=i;
2787
2788 loop
2789 {
2790 next_gen = id_ReadOutPivot(res, &next_comp, currRing);
2791 if (next_gen<0) break;
2792 del++;
2793 syGaussForOne(res,next_gen,next_comp,0,IDELEMS(res));
2794 for(i=next_comp+1;i<=arg->rank;i++) red_comp[i]--;
2795 if ((w !=NULL)&&(*w!=NULL))
2796 {
2797 for(i=next_comp;i<(*w)->length();i++) (**w)[i-1]=(**w)[i];
2798 }
2799 }
2800
2802
2803 if ((w !=NULL)&&(*w!=NULL) &&(del>0))
2804 {
2805 int nl=si_max((*w)->length()-del,1);
2806 intvec *wtmp=new intvec(nl);
2807 for(i=0;i<nl;i++) (*wtmp)[i]=(**w)[i];
2808 delete *w;
2809 *w=wtmp;
2810 }
2811 return res;
2812}
2813
2814ideal idMinEmbedding(ideal arg,BOOLEAN inPlace, intvec **w)
2815{
2816 int *red_comp=(int*)omAlloc((arg->rank+1)*sizeof(int));
2817 int del=0;
2818 ideal res=idMinEmbedding1(arg,inPlace,w,red_comp,del);
2819 idDeleteComps(res,red_comp,del);
2820 omFree(red_comp);
2821 return res;
2822}
2823
2824ideal idMinEmbedding_with_map(ideal arg,intvec **w, ideal &trans)
2825{
2826 int *red_comp=(int*)omAlloc((arg->rank+1)*sizeof(int));
2827 int del=0;
2828 ideal res=idMinEmbedding1(arg,FALSE,w,red_comp,del);
2829 trans=idLift(arg,res,NULL,TRUE,FALSE,FALSE,NULL);
2830 //idDeleteComps(res,red_comp,del);
2831 omFree(red_comp);
2832 return res;
2833}
2834
2835ideal idMinEmbedding_with_map_v(ideal arg,intvec **w, ideal &trans, int* g)
2836{
2837 if (idIs0(arg))
2838 {
2839 trans=idFreeModule(arg->rank);
2840 if (g!=NULL)
2841 {
2842 for(int i=0;i<arg->rank;i++) g[i]=i+1;
2843 }
2844 return arg;
2845 }
2846 int *red_comp=(int*)omAlloc((arg->rank+1)*sizeof(int));
2847 int del=0;
2848 ideal res=idMinEmbedding1(arg,FALSE,w,red_comp,del);
2849 trans=idLift(arg,res,NULL,TRUE,FALSE,FALSE,NULL);
2850 for(int i=1;i<=arg->rank;i++)
2851 {
2852 g[i-1]=red_comp[i];
2853 }
2854 idDeleteComps(res,red_comp,del);
2855 return res;
2856}
2857
2858extern void ipPrint_MA0(matrix m, const char *name);
2859#if 0 // unused
2860ideal idMinEmbedding_with_map0(ideal arg,intvec **w, ideal &trans)
2861{
2862 ideal a=idCopy(arg);
2863 // add unit matrix to a
2864 int k=a->rank+1;
2865 const int rk=a->rank;
2866 poly p;
2867 int i;
2868 for(i=0;i<IDELEMS(a);i++,k++)
2869 {
2870 p=pOne();
2872 a->m[i]=p_Add_q(a->m[i],p,currRing);
2873 }
2874 // search a unit in orig part of a
2875 // and subtract, start at start
2876 int start=0;
2877 loop
2878 {
2879 PrintS("matrix:\n");
2880 ipPrint_MA0((matrix)a,"a");
2881 i=start;
2882 if (i>=IDELEMS(a)) break;
2883 p=a->m[i];
2884 start=IDELEMS(a);
2885 while((p!=NULL)&&(pGetComp(p)<=rk)&&(p_Totaldegree(p,currRing)>0)) pIter(p);
2886 if ((p!=NULL)&&(pGetComp(p)<=rk)&&(p_Totaldegree(p,currRing)==0))
2887 { // found const in vector i, comp k
2888 k=pGetComp(p);
2889 // normalize:
2890 number n=nCopy(pGetCoeff(p));
2891 n=nInpNeg(n);
2892 a->m[i]=p_Div_nn(p,n,currRing);
2893 // subtract
2894 BOOLEAN changed=FALSE;
2895 for(int j=IDELEMS(a)-1;j>=0;j--)
2896 {
2897 if (j!=i)
2898 {
2899 poly q=p_Vec2Poly(a->m[j],k,currRing);
2900 if (q!=NULL)
2901 {
2902 start=j; // changed entries start at j
2903 changed=TRUE;
2904 poly s=p_Mult_q(a->m[i],q,currRing);
2905 a->m[j]=p_Add_q(a->m[j],s,currRing);
2906 }
2907 }
2908 }
2909 if(changed) continue;
2910 }
2911 else i++;
2912 }
2913 // a -> result,trans
2914 trans=idInit(IDELEMS(a),IDELEMS(a));
2915 ideal result=idInit(IDELEMS(a),rk);
2916 for(i=0;i<IDELEMS(a);i++)
2917 {
2918 while(a->m[i]!=NULL)
2919 {
2920 poly p=a->m[i];
2921 a->m[i]=p->next;
2922 p->next=NULL;
2923 if(pGetComp(p)<=rk)
2924 {
2925 result->m[i]=p_Add_q(result->m[i],p,currRing);
2926 }
2927 else
2928 {
2929 p_Shift(&p,-rk,currRing);
2930 trans->m[i]=p_Add_q(trans->m[i],p,currRing);
2931 }
2932 }
2933 }
2934 PrintS("prune:\n");
2936 PrintS("trans:\n");
2937 ipPrint_MA0((matrix)trans,"T");
2938 idDelete(&a);
2939 return result;
2940}
2941#endif
2942#include "polys/clapsing.h"
2943
2944#if 0
2945poly id_GCD(poly f, poly g, const ring r)
2946{
2947 ring save_r=currRing;
2948 rChangeCurrRing(r);
2949 ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2950 intvec *w = NULL;
2951 ideal S=idSyzygies(I,testHomog,&w);
2952 if (w!=NULL) delete w;
2953 poly gg=pTakeOutComp(&(S->m[0]),2);
2954 idDelete(&S);
2955 poly gcd_p=singclap_pdivide(f,gg,r);
2956 p_Delete(&gg,r);
2957 rChangeCurrRing(save_r);
2958 return gcd_p;
2959}
2960#else
2961poly id_GCD(poly f, poly g, const ring r)
2962{
2963 ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2964 intvec *w = NULL;
2965
2966 ring save_r = currRing;
2967 rChangeCurrRing(r);
2968 ideal S=idSyzygies(I,testHomog,&w);
2969 rChangeCurrRing(save_r);
2970
2971 if (w!=NULL) delete w;
2972 poly gg=p_TakeOutComp(&(S->m[0]), 2, r);
2973 id_Delete(&S, r);
2974 poly gcd_p=singclap_pdivide(f,gg, r);
2975 p_Delete(&gg, r);
2976
2977 return gcd_p;
2978}
2979#endif
2980
2981#if 0
2982/*2
2983* xx,q: arrays of length 0..rl-1
2984* xx[i]: SB mod q[i]
2985* assume: char=0
2986* assume: q[i]!=0
2987* destroys xx
2988*/
2989ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring R)
2990{
2991 int cnt=IDELEMS(xx[0])*xx[0]->nrows;
2992 ideal result=idInit(cnt,xx[0]->rank);
2993 result->nrows=xx[0]->nrows; // for lifting matrices
2994 result->ncols=xx[0]->ncols; // for lifting matrices
2995 int i,j;
2996 poly r,h,hh,res_p;
2997 number *x=(number *)omAlloc(rl*sizeof(number));
2998 for(i=cnt-1;i>=0;i--)
2999 {
3000 res_p=NULL;
3001 loop
3002 {
3003 r=NULL;
3004 for(j=rl-1;j>=0;j--)
3005 {
3006 h=xx[j]->m[i];
3007 if ((h!=NULL)
3008 &&((r==NULL)||(p_LmCmp(r,h,R)==-1)))
3009 r=h;
3010 }
3011 if (r==NULL) break;
3012 h=p_Head(r, R);
3013 for(j=rl-1;j>=0;j--)
3014 {
3015 hh=xx[j]->m[i];
3016 if ((hh!=NULL) && (p_LmCmp(r,hh, R)==0))
3017 {
3018 x[j]=p_GetCoeff(hh, R);
3019 hh=p_LmFreeAndNext(hh, R);
3020 xx[j]->m[i]=hh;
3021 }
3022 else
3023 x[j]=n_Init(0, R->cf); // is R->cf really n_Q???, yes!
3024 }
3025
3026 number n=n_ChineseRemainder(x,q,rl, R->cf);
3027
3028 for(j=rl-1;j>=0;j--)
3029 {
3030 x[j]=NULL; // nlInit(0...) takes no memory
3031 }
3032 if (n_IsZero(n, R->cf)) p_Delete(&h, R);
3033 else
3034 {
3035 p_SetCoeff(h,n, R);
3036 //Print("new mon:");pWrite(h);
3037 res_p=p_Add_q(res_p, h, R);
3038 }
3039 }
3040 result->m[i]=res_p;
3041 }
3042 omFree(x);
3043 for(i=rl-1;i>=0;i--) id_Delete(&(xx[i]), R);
3044 omFree(xx);
3045 return result;
3046}
3047#endif
3048/* currently unused:
3049ideal idChineseRemainder(ideal *xx, intvec *iv)
3050{
3051 int rl=iv->length();
3052 number *q=(number *)omAlloc(rl*sizeof(number));
3053 int i;
3054 for(i=0; i<rl; i++)
3055 {
3056 q[i]=nInit((*iv)[i]);
3057 }
3058 return idChineseRemainder(xx,q,rl);
3059}
3060*/
3061/*
3062 * lift ideal with coeffs over Z (mod N) to Q via Farey
3063 */
3064ideal id_Farey(ideal x, number N, const ring r)
3065{
3066 int cnt=IDELEMS(x)*x->nrows;
3067 ideal result=idInit(cnt,x->rank);
3068 result->nrows=x->nrows; // for lifting matrices
3069 result->ncols=x->ncols; // for lifting matrices
3070
3071 int i;
3072 for(i=cnt-1;i>=0;i--)
3073 {
3074 result->m[i]=p_Farey(x->m[i],N,r);
3075 }
3076 return result;
3077}
3078
3079
3080
3081
3082// uses glabl vars via pSetModDeg
3083/*
3084BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
3085{
3086 if ((Q!=NULL) && (!idHomIdeal(Q,NULL))) { PrintS(" Q not hom\n"); return FALSE;}
3087 if (idIs0(m)) return TRUE;
3088
3089 int cmax=-1;
3090 int i;
3091 poly p=NULL;
3092 int length=IDELEMS(m);
3093 poly* P=m->m;
3094 for (i=length-1;i>=0;i--)
3095 {
3096 p=P[i];
3097 if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
3098 }
3099 if (w != NULL)
3100 if (w->length()+1 < cmax)
3101 {
3102 // Print("length: %d - %d \n", w->length(),cmax);
3103 return FALSE;
3104 }
3105
3106 if(w!=NULL)
3107 p_SetModDeg(w, currRing);
3108
3109 for (i=length-1;i>=0;i--)
3110 {
3111 p=P[i];
3112 poly q=p;
3113 if (p!=NULL)
3114 {
3115 int d=p_FDeg(p,currRing);
3116 loop
3117 {
3118 pIter(p);
3119 if (p==NULL) break;
3120 if (d!=p_FDeg(p,currRing))
3121 {
3122 //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
3123 if(w!=NULL)
3124 p_SetModDeg(NULL, currRing);
3125 return FALSE;
3126 }
3127 }
3128 }
3129 }
3130
3131 if(w!=NULL)
3132 p_SetModDeg(NULL, currRing);
3133
3134 return TRUE;
3135}
3136*/
3137
3138/// keeps the first k (>= 1) entries of the given ideal
3139/// (Note that the kept polynomials may be zero.)
3140void idKeepFirstK(ideal id, const int k)
3141{
3142 for (int i = IDELEMS(id)-1; i >= k; i--)
3143 {
3144 if (id->m[i] != NULL) pDelete(&id->m[i]);
3145 }
3146 int kk=k;
3147 if (k==0) kk=1; /* ideals must have at least one element(0)*/
3148 pEnlargeSet(&(id->m), IDELEMS(id), kk-IDELEMS(id));
3149 IDELEMS(id) = kk;
3150}
3151
3152typedef struct
3153{
3154 poly p;
3156} poly_sort;
3157
3158int pCompare_qsort(const void *a, const void *b)
3159{
3160 return (p_Compare(((poly_sort *)a)->p, ((poly_sort *)b)->p,currRing));
3161}
3162
3163void idSort_qsort(poly_sort *id_sort, int idsize)
3164{
3165 qsort(id_sort, idsize, sizeof(poly_sort), pCompare_qsort);
3166}
3167
3168/*2
3169* ideal id = (id[i])
3170* if id[i] = id[j] then id[j] is deleted for j > i
3171*/
3172void idDelEquals(ideal id)
3173{
3174 int idsize = IDELEMS(id);
3175 poly_sort *id_sort = (poly_sort *)omAlloc0(idsize*sizeof(poly_sort));
3176 for (int i = 0; i < idsize; i++)
3177 {
3178 id_sort[i].p = id->m[i];
3179 id_sort[i].index = i;
3180 }
3181 idSort_qsort(id_sort, idsize);
3182 int index, index_i, index_j;
3183 int i = 0;
3184 for (int j = 1; j < idsize; j++)
3185 {
3186 if (id_sort[i].p != NULL && pEqualPolys(id_sort[i].p, id_sort[j].p))
3187 {
3188 index_i = id_sort[i].index;
3189 index_j = id_sort[j].index;
3190 if (index_j > index_i)
3191 {
3192 index = index_j;
3193 }
3194 else
3195 {
3196 index = index_i;
3197 i = j;
3198 }
3199 pDelete(&id->m[index]);
3200 }
3201 else
3202 {
3203 i = j;
3204 }
3205 }
3206 omFreeSize((ADDRESS)(id_sort), idsize*sizeof(poly_sort));
3207}
3208
3210
3212{
3213 BOOLEAN b = FALSE; // set b to TRUE, if spoly was changed,
3214 // let it remain FALSE otherwise
3215 if (strat->P.t_p==NULL)
3216 {
3217 poly p=strat->P.p;
3218
3219 // iterate over all terms of p and
3220 // compute the minimum mm of all exponent vectors
3221 int *mm=(int*)omAlloc((1+rVar(currRing))*sizeof(int));
3222 int *m0=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
3223 p_GetExpV(p,mm,currRing);
3224 bool nonTrivialSaturationToBeDone=true;
3225 for (; p!=NULL; pIter(p))
3226 {
3227 nonTrivialSaturationToBeDone=false;
3228 p_GetExpV(p,m0,currRing);
3229 for (int i=rVar(currRing); i>0; i--)
3230 {
3232 {
3233 mm[i]=si_min(mm[i],m0[i]);
3234 if (mm[i]>0) nonTrivialSaturationToBeDone=true;
3235 }
3236 else mm[i]=0;
3237 }
3238 // abort if the minimum is zero in each component
3239 if (!nonTrivialSaturationToBeDone) break;
3240 }
3241 if (nonTrivialSaturationToBeDone)
3242 {
3243 // std::cout << "simplifying!" << std::endl;
3244 if (TEST_OPT_PROT) { PrintS("S"); mflush(); }
3245 p=p_Copy(strat->P.p,currRing);
3246 //pWrite(p);
3247 // for (int i=rVar(currRing); i>0; i--)
3248 // if (mm[i]!=0) Print("x_%d:%d ",i,mm[i]);
3249 //PrintLn();
3250 strat->P.Init(strat->tailRing);
3251 //memset(&strat->P,0,sizeof(strat->P));
3252 //strat->P.tailRing = strat->tailRing; // done by Init
3253 strat->P.p=p;
3254 while(p!=NULL)
3255 {
3256 for (int i=rVar(currRing); i>0; i--)
3257 {
3258 p_SubExp(p,i,mm[i],currRing);
3259 }
3260 p_Setm(p,currRing);
3261 pIter(p);
3262 }
3263 b = TRUE;
3264 }
3265 omFree(mm);
3266 omFree(m0);
3267 }
3268 else
3269 {
3270 poly p=strat->P.t_p;
3271
3272 // iterate over all terms of p and
3273 // compute the minimum mm of all exponent vectors
3274 int *mm=(int*)omAlloc((1+rVar(currRing))*sizeof(int));
3275 int *m0=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
3276 p_GetExpV(p,mm,strat->tailRing);
3277 bool nonTrivialSaturationToBeDone=true;
3278 for (; p!=NULL; pIter(p))
3279 {
3280 nonTrivialSaturationToBeDone=false;
3281 p_GetExpV(p,m0,strat->tailRing);
3282 for(int i=rVar(currRing); i>0; i--)
3283 {
3285 {
3286 mm[i]=si_min(mm[i],m0[i]);
3287 if (mm[i]>0) nonTrivialSaturationToBeDone = true;
3288 }
3289 else mm[i]=0;
3290 }
3291 // abort if the minimum is zero in each component
3292 if (!nonTrivialSaturationToBeDone) break;
3293 }
3294 if (nonTrivialSaturationToBeDone)
3295 {
3296 if (TEST_OPT_PROT) { PrintS("S"); mflush(); }
3297 p=p_Copy(strat->P.t_p,strat->tailRing);
3298 //p_Write(p,strat->tailRing);
3299 // for (int i=rVar(currRing); i>0; i--)
3300 // if (mm[i]!=0) Print("x_%d:%d ",i,mm[i]);
3301 //PrintLn();
3302 strat->P.Init(strat->tailRing);
3303 //memset(&strat->P,0,sizeof(strat->P));
3304 //strat->P.tailRing = strat->tailRing;// done by Init
3305 strat->P.t_p=p;
3306 while(p!=NULL)
3307 {
3308 for(int i=rVar(currRing); i>0; i--)
3309 {
3310 p_SubExp(p,i,mm[i],strat->tailRing);
3311 }
3312 p_Setm(p,strat->tailRing);
3313 pIter(p);
3314 }
3315 strat->P.GetP();
3316 b = TRUE;
3317 }
3318 omFree(mm);
3319 omFree(m0);
3320 }
3321 return b; // return TRUE if sp was changed, FALSE if not
3322}
3323
3324ideal id_Satstd(const ideal I, ideal J, const ring r)
3325{
3326 ring save=currRing;
3327 if (currRing!=r) rChangeCurrRing(r);
3328 idSkipZeroes(J);
3329 id_satstdSaturatingVariables=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
3330 int k=IDELEMS(J);
3331 if (k>1)
3332 {
3333 for (int i=0; i<k; i++)
3334 {
3335 poly x = J->m[i];
3336 int li = p_Var(x,r);
3337 if (li>0)
3339 else
3340 {
3341 if (currRing!=save) rChangeCurrRing(save);
3342 WerrorS("ideal generators must be variables");
3343 return NULL;
3344 }
3345 }
3346 }
3347 else
3348 {
3349 poly x = J->m[0];
3350 if (pNext(x)!=NULL)
3351 {
3352 Werror("generator must be a monomial");
3353 if (currRing!=save) rChangeCurrRing(save);
3354 return NULL;
3355 }
3356 for (int i=1; i<=r->N; i++)
3357 {
3358 int li = p_GetExp(x,i,r);
3359 if (li==1)
3361 else if (li>1)
3362 {
3363 if (currRing!=save) rChangeCurrRing(save);
3364 Werror("exponent(x(%d)^%d) must be 0 or 1",i,li);
3365 return NULL;
3366 }
3367 }
3368 }
3369 ideal res=kStd(I,r->qideal,testHomog,NULL,NULL,0,0,NULL,id_sat_vars_sp);
3372 if (currRing!=save) rChangeCurrRing(save);
3373 return res;
3374}
3375
3376ideal id_Sat_principal(ideal I, ideal J, const ring origR)
3377{
3378 rRingOrder_t *ord;
3379 int *block0,*block1;
3380 int **wv;
3381
3382 // construction extension ring
3383 ord=(rRingOrder_t*)omAlloc0(4*sizeof(rRingOrder_t));
3384 block0=(int*)omAlloc0(4*sizeof(int));
3385 block1=(int*)omAlloc0(4*sizeof(int));
3386 wv=(int**) omAlloc0(4*sizeof(int**));
3387 wv[0]=(int*)omAlloc0((rVar(origR) + 2)*sizeof(int));
3388 block0[0] = block0[1] = 1;
3389 block1[0] = block1[1] = rVar(origR)+1;
3390 // use this special ordering: like ringorder_a, except that pFDeg, pWeights
3391 // ignore it
3392 ord[0] = ringorder_aa;
3393 wv[0][rVar(origR)]=1;
3394 BOOLEAN wp=FALSE;
3395 for (int j=0;j<rVar(origR);j++)
3396 if (p_Weight(j+1,origR)!=1) { wp=TRUE;break; }
3397 if (wp)
3398 {
3399 wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
3400 for (int j=0;j<rVar(origR);j++)
3401 wv[1][j]=p_Weight(j+1,origR);
3402 ord[1] = ringorder_wp;
3403 }
3404 else
3405 ord[1] = ringorder_dp;
3406 ord[2] = ringorder_C;
3407 ord[3] = (rRingOrder_t)0;
3408 char **names=(char**)omAlloc0((origR->N+1) * sizeof(char *));
3409 for (int j=0;j<rVar(origR);j++)
3410 names[j]=origR->names[j];
3411 names[rVar(origR)]=(char*)"@";
3412 ring tmpR=rDefault(nCopyCoeff(origR->cf),rVar(origR)+1,names,4,ord,block0,block1,wv);
3413 omFree(names);
3414 rComplete(tmpR, 1);
3415 rChangeCurrRing(tmpR);
3416 // map I
3417 ideal II=idrCopyR(I,origR,tmpR);
3418 // map J
3419 ideal JJ=idrCopyR(J,origR,tmpR);
3420 // J[1]*t-1
3421 poly t=pOne();
3422 p_SetExp(t,rVar(tmpR),1,tmpR);
3423 p_Setm(t,tmpR);
3424 poly p=JJ->m[0];
3425 p_Norm(p,currRing);
3426 p=p_Mult_q(p,t,tmpR);
3427 p=p_Sub(p,pOne(),tmpR);
3428 JJ->m[0]=p;
3429 ideal T=id_SimpleAdd(II,JJ,tmpR);
3430 idTest(T);
3431 id_Delete(&II,tmpR);
3432 id_Delete(&JJ,tmpR);
3433 // elimination
3434 t=pOne();
3435 p_SetExp(t,rVar(tmpR),1,tmpR);
3436 p_Setm(t,tmpR);
3437 ideal TT=idGroebner(T,0,GbStd);
3438 p_Delete(&t,tmpR);
3439 for(int j=0;j<IDELEMS(TT);j++)
3440 {
3441 if ((TT->m[j]!=NULL)
3442 && (p_GetExp(TT->m[j],rVar(tmpR),tmpR)>0))
3443 {
3444 p_Delete(&TT->m[j],tmpR);
3445 }
3446 }
3447 // map back
3448 ideal TTT=idrCopyR(TT,tmpR,origR);
3449 id_Delete(&TT,tmpR);
3450 rChangeCurrRing(origR);
3451 rDelete(tmpR);
3452 idSkipZeroes(TTT);
3453 return TTT;
3454}
3455
3456ideal idSaturate(ideal I, ideal J, int &k, BOOLEAN isIdeal)
3457{
3458 if(idIs0(J))
3459 {
3460 ideal res;
3461 if(isIdeal)
3462 {
3463 res=idInit(1,1);
3464 res->m[0]=pOne();
3465 }
3466 else
3467 {
3468 res=idFreeModule(I->rank);
3469 }
3470 k=1;
3471 return(res);
3472 }
3473 //if (idElem(J)==1)
3474 //{
3475 // idSkipZeroes(J);
3476 // return id_Sat_principal(I,J,currRing);
3477 //}
3478 //---------------------------------------------------
3479 BOOLEAN only_vars=TRUE; // enabled for I:x_i
3480 if (idElem(J)==1)
3481 {
3482 for(int j=IDELEMS(J)-1;j>=0;j--)
3483 {
3484 poly p=J->m[j];
3485 if (p!=NULL)
3486 {
3487 if (pVar(p)==0)
3488 {
3489 only_vars=FALSE;
3490 break;
3491 }
3492 }
3493 }
3494 }
3495 if (only_vars && isIdeal && rOrd_is_Totaldegree_Ordering(currRing) && idElem(J) == 1)
3496 {
3497 ideal Iquot,Istd;
3498 intvec *w=NULL;
3499 Istd=id_Satstd(I,J,currRing);
3500 k=0;
3501 loop
3502 {
3503 k++;
3504 Iquot=idQuot(Istd,J,TRUE,isIdeal);
3505 ideal tmp=kNF(Istd,currRing->qideal,Iquot,5);
3506 int elem=idElem(tmp);
3507 id_Delete(&tmp,currRing);
3508 id_Delete(&Istd,currRing);
3509 Istd=Iquot;
3510 w=NULL;
3511 Istd=kStd(Iquot,currRing->qideal,testHomog,&w);
3512 if (w!=NULL) delete w;
3513 id_Delete(&Iquot,currRing);
3514 if (elem==0) break;
3515 }
3516 k--;
3517 idSkipZeroes(Istd);
3518 //PrintS("\nSatstd:\n");
3519 //iiWriteMatrix((matrix)I,"I",1,currRing,0); PrintLn();
3520 //iiWriteMatrix((matrix)J,"J",1,currRing,0); PrintLn();
3521 //iiWriteMatrix((matrix)Istd,"res",1,currRing,0);PrintLn();
3522 //id_Delete(&Istd,currRing);
3523 return Istd;
3524 }
3525 //--------------------------------------------------
3526 ideal Iquot,Istd;
3527 intvec *w=NULL;
3528 Istd=idCopy(I);
3529 k=0;
3530 loop
3531 {
3532 k++;
3533 Iquot=idQuot(Istd,J,FALSE,isIdeal);
3534 ideal tmp=kNF(Istd,currRing->qideal,Iquot,5);
3535 int elem=idElem(tmp);
3536 id_Delete(&tmp,currRing);
3537 id_Delete(&Istd,currRing);
3538 Istd=Iquot;
3539 if (elem==0) break;
3540 }
3541 k--;
3542 Istd=kStd(Iquot,currRing->qideal,testHomog,&w);
3543 idSkipZeroes(Istd);
3544 //if (only_vars)
3545 //{
3546 // iiWriteMatrix((matrix)Istd,"org",1,currRing,0);
3547 //}
3548 return Istd;
3549}
3550
3551ideal id_Homogenize(ideal I, int var_num, const ring r)
3552{
3553 ideal II=id_Copy(I,r);
3554 if (var_num==1)
3555 {
3556 ring tmpR=rAssure_Dp_C(r);
3557 if (tmpR!=r)
3558 {
3559 rChangeCurrRing(tmpR);
3560 II=idrMoveR(II,r,tmpR);
3561 }
3562 ideal III=id_Homogen(II,1,tmpR);
3563 id_Delete(&II,tmpR);
3564 intvec *ww=NULL;
3565 II=kStd(III,currRing->qideal,(tHomog)TRUE,&ww);
3566 if (ww!=NULL) delete ww;
3567 id_Delete(&III,tmpR);
3568 if (tmpR!=r)
3569 {
3570 rChangeCurrRing(r);
3571 II=idrMoveR(II,tmpR,r);
3572 }
3573 return II;
3574 }
3575 ideal III=idInit(IDELEMS(II),1);
3576 int *perm=(int*)omAlloc0((rVar(r)+1)*sizeof(int));
3577 for(int i=rVar(r)-1; i>0; i--) perm[i]=i;
3578 perm[var_num]=1;
3579 perm[1]=var_num;
3580 for(int i=IDELEMS(II)-1; i>=0;i--)
3581 {
3582 III->m[i]=p_PermPoly(II->m[i],perm,r,r,ndCopyMap,NULL,0,FALSE);
3583 }
3584 id_Delete(&II,r);
3585 II=id_Homogenize(III,1,r);
3586 id_Delete(&III,r);
3587 III=idInit(IDELEMS(II),1);
3588 for(int i=IDELEMS(II)-1; i>=0;i--)
3589 {
3590 III->m[i]=p_PermPoly(II->m[i],perm,r,r,ndCopyMap,NULL,0,FALSE);
3591 }
3592 id_Delete(&II,r);
3593 return III;
3594}
3595
3596ideal id_HomogenizeW(ideal I, int var_num, intvec *w,const ring r)
3597{
3598 ideal II=id_Copy(I,r);
3599 if (var_num==1)
3600 {
3601 ring tmpR=rAssure_Wp_C(r,w);
3602 if (tmpR!=r)
3603 {
3604 rChangeCurrRing(tmpR);
3605 II=idrMoveR(II,r,tmpR);
3606 }
3607 ideal III=id_Homogen(II,1,tmpR);
3608 id_Delete(&II,tmpR);
3609 intvec *ww=NULL;
3610 II=kStd(III,currRing->qideal,(tHomog)TRUE,&ww);
3611 if (ww!=NULL) delete ww;
3612 id_Delete(&III,tmpR);
3613 if (tmpR!=r)
3614 {
3615 rChangeCurrRing(r);
3616 II=idrMoveR(II,tmpR,r);
3617 }
3618 return II;
3619 }
3620 ideal III=idInit(IDELEMS(II),1);
3621 int *perm=(int*)omAlloc0((rVar(r)+1)*sizeof(int));
3622 for(int i=rVar(r)-1; i>0; i--) perm[i]=i;
3623 perm[var_num]=1;
3624 perm[1]=var_num;
3625 for(int i=IDELEMS(II)-1; i>=0;i--)
3626 {
3627 III->m[i]=p_PermPoly(II->m[i],perm,r,r,ndCopyMap,NULL,0,FALSE);
3628 }
3629 id_Delete(&II,r);
3630 II=id_HomogenizeW(III,1,w,r);
3631 id_Delete(&III,r);
3632 III=idInit(IDELEMS(II),1);
3633 for(int i=IDELEMS(II)-1; i>=0;i--)
3634 {
3635 III->m[i]=p_PermPoly(II->m[i],perm,r,r,ndCopyMap,NULL,0,FALSE);
3636 }
3637 id_Delete(&II,r);
3638 return III;
3639}
3640
3641GbVariant syGetAlgorithm(char *n, const ring r, const ideal /*M*/)
3642{
3643 GbVariant alg=GbDefault;
3644 if (strcmp(n,"default")==0) alg=GbDefault;
3645 else if (strcmp(n,"slimgb")==0) alg=GbSlimgb;
3646 else if (strcmp(n,"std")==0) alg=GbStd;
3647 else if (strcmp(n,"sba")==0) alg=GbSba;
3648 else if (strcmp(n,"singmatic")==0) alg=GbSingmatic;
3649 else if (strcmp(n,"groebner")==0) alg=GbGroebner;
3650 else if (strcmp(n,"modstd")==0) alg=GbModstd;
3651 else if (strcmp(n,"ffmod")==0) alg=GbFfmod;
3652 else if (strcmp(n,"nfmod")==0) alg=GbNfmod;
3653 else if (strcmp(n,"std:sat")==0) alg=GbStdSat;
3654 else Warn(">>%s<< is an unknown algorithm",n);
3655
3656 if (alg==GbSlimgb) // test conditions for slimgb
3657 {
3658 if(rHasGlobalOrdering(r)
3659 &&(!rIsNCRing(r))
3660 &&(r->qideal==NULL)
3661 &&(!rField_is_Ring(r)))
3662 {
3663 return GbSlimgb;
3664 }
3665 if (TEST_OPT_PROT)
3666 WarnS("requires: coef:field, commutative, global ordering, not qring");
3667 }
3668 else if (alg==GbSba) // cond. for sba
3669 {
3670 if(rField_is_Domain(r)
3671 &&(!rIsNCRing(r))
3672 &&(rHasGlobalOrdering(r)))
3673 {
3674 return GbSba;
3675 }
3676 if (TEST_OPT_PROT)
3677 WarnS("requires: coef:domain, commutative, global ordering");
3678 }
3679 else if (alg==GbGroebner) // cond. for groebner
3680 {
3681 return GbGroebner;
3682 }
3683 else if(alg==GbModstd) // cond for modstd: Q or Q(a)
3684 {
3685 if(ggetid("modStd")==NULL)
3686 {
3687 WarnS(">>modStd<< not found");
3688 }
3689 else if(rField_is_Q(r)
3690 &&(!rIsNCRing(r))
3691 &&(rHasGlobalOrdering(r)))
3692 {
3693 return GbModstd;
3694 }
3695 if (TEST_OPT_PROT)
3696 WarnS("requires: coef:QQ, commutative, global ordering");
3697 }
3698 else if(alg==GbStdSat) // cond for std:sat: 2 blocks of variables
3699 {
3700 if(ggetid("satstd")==NULL)
3701 {
3702 WarnS(">>satstd<< not found");
3703 }
3704 else
3705 {
3706 return GbStdSat;
3707 }
3708 }
3709
3710 return GbStd; // no conditions for std
3711}
3712//----------------------------------------------------------------------------
3713// GB-algorithms and their pre-conditions
3714// std slimgb sba singmatic modstd ffmod nfmod groebner
3715// + + + - + - - + coeffs: QQ
3716// + + + + - - - + coeffs: ZZ/p
3717// + + + - ? - + + coeffs: K[a]/f
3718// + + + - ? + - + coeffs: K(a)
3719// + - + - - - - + coeffs: domain, not field
3720// + - - - - - - + coeffs: zero-divisors
3721// + + + + - ? ? + also for modules: C
3722// + + - + - ? ? + also for modules: all orderings
3723// + + - - - - - + exterior algebra
3724// + + - - - - - + G-algebra
3725// + + + + + + + + degree ordering
3726// + - + + + + + + non-degree ordering
3727// - - - + + + + + parallel
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
static int si_min(const int a, const int b)
Definition auxiliary.h:125
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
int l
Definition cfEzgcd.cc:100
int m
Definition cfEzgcd.cc:128
int i
Definition cfEzgcd.cc:132
int k
Definition cfEzgcd.cc:99
Variable x
Definition cfModGcd.cc:4090
int p
Definition cfModGcd.cc:4086
g
Definition cfModGcd.cc:4098
CanonicalForm b
Definition cfModGcd.cc:4111
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
FILE * f
Definition checklibs.c:9
poly singclap_pdivide(poly f, poly g, const ring r)
Definition clapsing.cc:624
int nrows
Definition matpol.h:20
long rank
Definition matpol.h:19
int ncols
Definition matpol.h:21
poly * m
Definition matpol.h:18
int & cols()
Definition matpol.h:24
int & rows()
Definition matpol.h:23
ring tailRing
Definition kutil.h:343
LObject P
Definition kutil.h:302
void * data
Definition subexpr.h:88
Coefficient rings, fields and other domains suitable for Singular polynomials.
number ndCopyMap(number a, const coeffs src, const coeffs dst)
Definition numbers.cc:287
static FORCE_INLINE BOOLEAN n_IsUnit(number n, const coeffs r)
TRUE iff n has a multiplicative inverse in the given coeff field/ring r.
Definition coeffs.h:519
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition coeffs.h:468
static FORCE_INLINE coeffs nCopyCoeff(const coeffs r)
"copy" coeffs, i.e. increment ref
Definition coeffs.h:437
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition coeffs.h:539
#define Print
Definition emacs.cc:80
#define Warn
Definition emacs.cc:77
#define WarnS
Definition emacs.cc:78
return result
const CanonicalForm int s
Definition facAbsFact.cc:51
CanonicalForm res
Definition facAbsFact.cc:60
const CanonicalForm & w
Definition facAbsFact.cc:51
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
int j
Definition facHensel.cc:110
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
void WerrorS(const char *s)
Definition feFopen.cc:24
#define STATIC_VAR
Definition globaldefs.h:7
@ IDEAL_CMD
Definition grammar.cc:285
@ MODUL_CMD
Definition grammar.cc:288
GbVariant syGetAlgorithm(char *n, const ring r, const ideal)
Definition ideals.cc:3641
static ideal idMinEmbedding1(ideal arg, BOOLEAN inPlace, intvec **w, int *red_comp, int &del)
Definition ideals.cc:2778
int index
Definition ideals.cc:3155
static void idPrepareStd(ideal s_temp, int k)
Definition ideals.cc:1041
matrix idCoeffOfKBase(ideal arg, ideal kbase, poly how)
Definition ideals.cc:2629
void idLiftW(ideal P, ideal Q, int n, matrix &T, ideal &R, int *w)
Definition ideals.cc:1336
static void idLift_setUnit(int e_mod, matrix *unit)
Definition ideals.cc:1082
ideal idSyzygies(ideal h1, tHomog h, intvec **w, BOOLEAN setSyzComp, BOOLEAN setRegularity, int *deg, GbVariant alg)
Definition ideals.cc:830
matrix idDiff(matrix i, int k)
Definition ideals.cc:2146
ideal id_Sat_principal(ideal I, ideal J, const ring origR)
Definition ideals.cc:3376
BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
Definition ideals.cc:2077
ideal id_Homogenize(ideal I, int var_num, const ring r)
Definition ideals.cc:3551
ideal idLiftStd(ideal h1, matrix *T, tHomog hi, ideal *S, GbVariant alg, ideal h11)
Definition ideals.cc:976
void idDelEquals(ideal id)
Definition ideals.cc:3172
int pCompare_qsort(const void *a, const void *b)
Definition ideals.cc:3158
ideal idQuot(ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN resultIsIdeal)
Definition ideals.cc:1506
ideal id_HomogenizeW(ideal I, int var_num, intvec *w, const ring r)
Definition ideals.cc:3596
ideal idMinors(matrix a, int ar, ideal R)
compute all ar-minors of the matrix a the caller of mpRecMin the elements of the result are not in R ...
Definition ideals.cc:1988
ideal idSaturate(ideal I, ideal J, int &k, BOOLEAN isIdeal)
Definition ideals.cc:3456
void ipPrint_MA0(matrix m, const char *name)
Definition ipprint.cc:57
BOOLEAN idIsSubModule(ideal id1, ideal id2)
Definition ideals.cc:2056
ideal idSeries(int n, ideal M, matrix U, intvec *w)
Definition ideals.cc:2129
static ideal idGroebner(ideal temp, int syzComp, GbVariant alg, intvec *hilb=NULL, intvec *w=NULL, tHomog hom=testHomog)
Definition ideals.cc:200
ideal idMinEmbedding_with_map_v(ideal arg, intvec **w, ideal &trans, int *g)
Definition ideals.cc:2835
ideal idCreateSpecialKbase(ideal kBase, intvec **convert)
Definition ideals.cc:2543
static ideal idPrepare(ideal h1, ideal h11, tHomog hom, int syzcomp, intvec **w, GbVariant alg)
Definition ideals.cc:607
poly id_GCD(poly f, poly g, const ring r)
Definition ideals.cc:2961
int idIndexOfKBase(poly monom, ideal kbase)
Definition ideals.cc:2561
poly idDecompose(poly monom, poly how, ideal kbase, int *pos)
Definition ideals.cc:2597
matrix idDiffOp(ideal I, ideal J, BOOLEAN multiply)
Definition ideals.cc:2159
void idSort_qsort(poly_sort *id_sort, int idsize)
Definition ideals.cc:3163
static ideal idInitializeQuot(ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN *addOnlyOne, int *kkmax)
Definition ideals.cc:1401
ideal idElimination(ideal h1, poly delVar, intvec *hilb, GbVariant alg)
Definition ideals.cc:1605
static ideal idSectWithElim(ideal h1, ideal h2, GbVariant alg)
Definition ideals.cc:132
ideal idSect(ideal h1, ideal h2, GbVariant alg)
Definition ideals.cc:315
ideal idMultSect(resolvente arg, int length, GbVariant alg)
Definition ideals.cc:471
void idKeepFirstK(ideal id, const int k)
keeps the first k (>= 1) entries of the given ideal (Note that the kept polynomials may be zero....
Definition ideals.cc:3140
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
STATIC_VAR int * id_satstdSaturatingVariables
Definition ideals.cc:3209
ideal idExtractG_T_S(ideal s_h3, matrix *T, ideal *S, long syzComp, int h1_size, BOOLEAN inputIsIdeal, const ring oring, const ring sring)
Definition ideals.cc:709
static void idDeleteComps(ideal arg, int *red_comp, int del)
Definition ideals.cc:2668
ideal idModulo(ideal h2, ideal h1, tHomog hom, intvec **w, matrix *T, GbVariant alg)
Definition ideals.cc:2422
ideal idMinEmbedding_with_map(ideal arg, intvec **w, ideal &trans)
Definition ideals.cc:2824
ideal idMinBase(ideal h1, ideal *SB)
Definition ideals.cc:51
ideal id_Farey(ideal x, number N, const ring r)
Definition ideals.cc:3064
ideal id_Satstd(const ideal I, ideal J, const ring r)
Definition ideals.cc:3324
static int id_ReadOutPivot(ideal arg, int *comp, const ring r)
Definition ideals.cc:2695
ideal idModuloLP(ideal h2, ideal h1, tHomog, intvec **w, matrix *T, GbVariant alg)
Definition ideals.cc:2229
static BOOLEAN id_sat_vars_sp(kStrategy strat)
Definition ideals.cc:3211
ideal idMinEmbedding(ideal arg, BOOLEAN inPlace, intvec **w)
Definition ideals.cc:2814
int binom(int n, int r)
GbVariant
Definition ideals.h:119
@ GbGroebner
Definition ideals.h:126
@ GbModstd
Definition ideals.h:127
@ GbStdSat
Definition ideals.h:130
@ GbSlimgb
Definition ideals.h:123
@ GbFfmod
Definition ideals.h:128
@ GbNfmod
Definition ideals.h:129
@ GbDefault
Definition ideals.h:120
@ GbStd
Definition ideals.h:122
@ GbSingmatic
Definition ideals.h:131
@ GbSba
Definition ideals.h:124
#define idDelete(H)
delete an ideal
Definition ideals.h:29
#define idSimpleAdd(A, B)
Definition ideals.h:42
void idGetNextChoise(int r, int end, BOOLEAN *endch, int *choise)
ideal id_Copy(ideal h1, const ring r)
copy an ideal
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
#define idTest(id)
Definition ideals.h:47
static BOOLEAN idHomIdeal(ideal id, ideal Q=NULL)
Definition ideals.h:91
static ideal idMult(ideal h1, ideal h2)
hh := h1 * h2
Definition ideals.h:84
ideal idCopy(ideal A)
Definition ideals.h:60
#define idMaxIdeal(D)
initialise the maximal ideal (at 0)
Definition ideals.h:33
ideal * resolvente
Definition ideals.h:18
void idInitChoise(int r, int beg, int end, BOOLEAN *endch, int *choise)
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition ideals.h:187
ideal idFreeModule(int i)
Definition ideals.h:111
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
intvec * ivCopy(const intvec *o)
Definition intvec.h:145
idhdl ggetid(const char *n)
Definition ipid.cc:560
EXTERN_VAR omBin sleftv_bin
Definition ipid.h:145
leftv ii_CallLibProcM(const char *n, void **args, int *arg_types, const ring R, BOOLEAN &err)
args: NULL terminated array of arguments arg_types: 0 terminated array of corresponding types
Definition iplib.cc:710
void * iiCallLibProc1(const char *n, void *arg, int arg_type, BOOLEAN &err)
Definition iplib.cc:636
STATIC_VAR jList * T
Definition janet.cc:30
STATIC_VAR Poly * h
Definition janet.cc:971
void p_TakeOutComp(poly *p, long comp, poly *q, int *lq, const ring r)
Definition p_polys.cc:3516
ideal kMin_std(ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb, int syzComp, int reduced)
Definition kstd1.cc:3086
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition kstd1.cc:3237
ideal kSba(ideal F, ideal Q, tHomog h, intvec **w, int sbaOrder, int arri, intvec *hilb, int syzComp, int newIdeal, intvec *vw)
Definition kstd1.cc:2688
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition kstd1.cc:2484
@ nc_skew
Definition nc.h:16
@ nc_exterior
Definition nc.h:21
static nc_type & ncRingType(nc_struct *p)
Definition nc.h:159
BOOLEAN nc_CheckSubalgebra(poly PolyVar, ring r)
matrix mpNew(int r, int c)
create a r x c zero-matrix
Definition matpol.cc:37
matrix mp_MultP(matrix a, poly p, const ring R)
multiply a matrix 'a' by a poly 'p', destroy the args
Definition matpol.cc:141
matrix mp_Copy(matrix a, const ring r)
copies matrix a (from ring r to r)
Definition matpol.cc:57
void mp_MinorToResult(ideal result, int &elems, matrix a, int r, int c, ideal R, const ring)
entries of a are minors and go to result (only if not in R)
Definition matpol.cc:1500
void mp_RecMin(int ar, ideal result, int &elems, matrix a, int lr, int lc, poly barDiv, ideal R, const ring r)
produces recursively the ideal of all arxar-minors of a
Definition matpol.cc:1596
poly mp_DetBareiss(matrix a, const ring r)
returns the determinant of the matrix m; uses Bareiss algorithm
Definition matpol.cc:1669
#define MATELEM(mat, i, j)
1-based access to matrix
Definition matpol.h:29
ip_smatrix * matrix
Definition matpol.h:43
#define MATROWS(i)
Definition matpol.h:26
#define MATCOLS(i)
Definition matpol.h:27
#define assume(x)
Definition mod2.h:387
#define pIter(p)
Definition monomials.h:37
#define pNext(p)
Definition monomials.h:36
#define p_GetCoeff(p, r)
Definition monomials.h:50
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 __p_GetComp(p, r)
Definition monomials.h:63
#define nInpNeg(n)
Definition numbers.h:21
#define nCopy(n)
Definition numbers.h:15
#define omStrDup(s)
#define omFreeSize(addr, size)
#define omAlloc(size)
#define omalloc(size)
#define omFree(addr)
#define omAlloc0(size)
#define omFreeBin(addr, bin)
#define omMemDup(s)
#define NULL
Definition omList.c:12
VAR unsigned si_opt_2
Definition options.c:6
VAR unsigned si_opt_1
Definition options.c:5
#define TEST_OPT_IDLIFT
Definition options.h:131
#define SI_SAVE_OPT2(A)
Definition options.h:22
#define OPT_REDTAIL_SYZ
Definition options.h:88
#define OPT_REDTAIL
Definition options.h:92
#define OPT_SB_1
Definition options.h:96
#define SI_SAVE_OPT1(A)
Definition options.h:21
#define SI_RESTORE_OPT1(A)
Definition options.h:24
#define SI_RESTORE_OPT2(A)
Definition options.h:25
#define Sy_bit(x)
Definition options.h:31
#define TEST_OPT_RETURN_SB
Definition options.h:114
#define TEST_V_INTERSECT_ELIM
Definition options.h:146
#define TEST_V_INTERSECT_SYZ
Definition options.h:147
#define TEST_OPT_NOTREGULARITY
Definition options.h:122
#define TEST_OPT_PROT
Definition options.h:105
#define V_IDLIFT
Definition options.h:63
static int index(p_Length length, p_Ord ord)
poly p_DivideM(poly a, poly b, const ring r)
Definition p_polys.cc:1582
poly p_Farey(poly p, number N, const ring r)
Definition p_polys.cc:54
int p_Weight(int i, const ring r)
Definition p_polys.cc:706
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition p_polys.cc:4756
poly p_PermPoly(poly p, const int *perm, const ring oldRing, const ring dst, nMapFunc nMap, const int *par_perm, int OldPar, BOOLEAN use_mult)
Definition p_polys.cc:4152
poly p_Div_nn(poly p, const number n, const ring r)
Definition p_polys.cc:1506
void p_Norm(poly p1, const ring r)
Definition p_polys.cc:3740
int p_Compare(const poly a, const poly b, const ring R)
Definition p_polys.cc:4946
long p_DegW(poly p, const int *w, const ring R)
Definition p_polys.cc:691
poly p_Vec2Poly(poly v, int k, const ring r)
Definition p_polys.cc:3594
void p_SetModDeg(intvec *w, ring r)
Definition p_polys.cc:3694
int p_Var(poly m, const ring r)
Definition p_polys.cc:4706
poly p_One(const ring r)
Definition p_polys.cc:1314
poly p_Sub(poly p1, poly p2, const ring r)
Definition p_polys.cc:1994
void pEnlargeSet(poly **p, int l, int increment)
Definition p_polys.cc:3717
long p_Deg(poly a, const ring r)
Definition p_polys.cc:586
static poly p_Neg(poly p, const ring r)
Definition p_polys.h:1107
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:936
static void p_LmDelete(poly p, const ring r)
Definition p_polys.h:723
static poly p_Mult_q(poly p, poly q, const ring r)
Definition p_polys.h:1118
static long p_SubExp(poly p, int v, long ee, ring r)
Definition p_polys.h:613
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition p_polys.h:488
static long p_MinComp(poly p, ring lmRing, ring tailRing)
Definition p_polys.h:313
static void p_Setm(poly p, const ring r)
Definition p_polys.h:233
static poly p_Copy_noCheck(poly p, const ring r)
returns a copy of p (without any additional testing)
Definition p_polys.h:836
static number p_SetCoeff(poly p, number n, ring r)
Definition p_polys.h:412
static poly pReverse(poly p)
Definition p_polys.h:335
static BOOLEAN p_LmIsConstantComp(const poly p, const ring r)
Definition p_polys.h:1006
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition p_polys.h:860
static int p_LmCmp(poly p, poly q, const ring r)
Definition p_polys.h:1594
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition p_polys.h:469
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:901
static void p_GetExpV(poly p, int *ev, const ring r)
Definition p_polys.h:1534
static poly p_LmFreeAndNext(poly p, ring)
Definition p_polys.h:711
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition p_polys.h:846
static long p_Totaldegree(poly p, const ring r)
Definition p_polys.h:1521
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 pTest(p)
Definition polys.h:414
#define pDelete(p_ptr)
Definition polys.h:186
#define ppJet(p, m)
Definition polys.h:366
#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 ppMult_mm(p, m)
Definition polys.h:201
#define pSetCompP(a, i)
Definition polys.h:303
#define pGetComp(p)
Component.
Definition polys.h:37
#define pDiff(a, b)
Definition polys.h:296
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition polys.h:31
#define pVar(m)
Definition polys.h:380
#define pJet(p, m)
Definition polys.h:367
#define pSub(a, b)
Definition polys.h:287
#define pWeight(i)
Definition polys.h:280
#define ppJetW(p, m, iv)
Definition polys.h:368
#define pMaxComp(p)
Definition polys.h:299
#define pSetComp(p, v)
Definition polys.h:38
void wrp(poly p)
Definition polys.h:310
#define pMult(p, q)
Definition polys.h:207
#define pJetW(p, m, iv)
Definition polys.h:369
#define pDiffOp(a, b, m)
Definition polys.h:297
#define pSeries(n, p, u, w)
Definition polys.h:371
#define pGetExp(p, i)
Exponent.
Definition polys.h:41
#define pSetmComp(p)
TODO:
Definition polys.h:273
#define pNormalize(p)
Definition polys.h:317
#define pEqualPolys(p1, p2)
Definition polys.h:399
#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
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 pOne()
Definition polys.h:315
#define pMinComp(p)
Definition polys.h:300
poly * polyset
Definition polys.h:259
poly prMoveR(poly &p, ring src_r, ring dest_r)
Definition prCopy.cc:90
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition prCopy.cc:248
poly prCopyR(poly p, ring src_r, ring dest_r)
Definition prCopy.cc:34
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
poly prMoveR_NoSort(poly &p, ring src_r, ring dest_r)
Definition prCopy.cc:101
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
void Werror(const char *fmt,...)
Definition reporter.cc:189
#define mflush()
Definition reporter.h:58
BOOLEAN rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition ring.cc:3465
ring rAssure_SyzComp(const ring r, BOOLEAN complete)
Definition ring.cc:4466
BOOLEAN nc_rComplete(const ring src, ring dest, bool bSetupQuotient)
Definition ring.cc:5772
ring rAssure_Wp_C(const ring r, intvec *w)
Definition ring.cc:4881
ring rAssure_Dp_C(const ring r)
Definition ring.cc:5063
BOOLEAN rOrd_is_Totaldegree_Ordering(const ring r)
Definition ring.cc:2016
ring rAssure_SyzOrder(const ring r, BOOLEAN complete)
Definition ring.cc:4461
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition ring.cc:1424
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:452
ring rDefault(const coeffs cf, int N, char **n, int ord_size, rRingOrder_t *ord, int *block0, int *block1, int **wvhdl, unsigned long bitmask)
Definition ring.cc:103
void rSetSyzComp(int k, const ring r)
Definition ring.cc:5169
ring rAssure_dp_C(const ring r)
Definition ring.cc:5058
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:405
static int rBlocks(const ring r)
Definition ring.h:573
static BOOLEAN rField_is_Domain(const ring r)
Definition ring.h:492
static BOOLEAN rIsLPRing(const ring r)
Definition ring.h:416
rRingOrder_t
order stuff
Definition ring.h:68
@ ringorder_a
Definition ring.h:70
@ ringorder_a64
for int64 weights
Definition ring.h:71
@ ringorder_C
Definition ring.h:73
@ ringorder_dp
Definition ring.h:78
@ ringorder_c
Definition ring.h:72
@ ringorder_aa
for idElimination, like a, except pFDeg, pWeigths ignore it
Definition ring.h:92
@ ringorder_ws
Definition ring.h:87
@ ringorder_s
s?
Definition ring.h:76
@ ringorder_wp
Definition ring.h:81
static BOOLEAN rField_is_Q(const ring r)
Definition ring.h:511
static BOOLEAN rIsNCRing(const ring r)
Definition ring.h:426
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition ring.h:597
BOOLEAN rHasGlobalOrdering(const ring r)
Definition ring.h:766
#define rField_is_Ring(R)
Definition ring.h:490
#define block
Definition scanner.cc:646
ideal idInit(int idsize, int rank)
initialise an ideal / module
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
ideal id_Homogen(ideal h, int varnum, const ring r)
matrix id_Module2Matrix(ideal mod, const ring R)
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
void id_DelMultiples(ideal id, const ring r)
ideal id = (id[i]), c any unit if id[i] = c*id[j] then id[j] is deleted for j > i
ideal id_Matrix2Module(matrix mat, const ring R)
converts mat to module, destroys mat
ideal id_SimpleAdd(ideal h1, ideal h2, const ring R)
concat the lists h1 and h2 without zeros
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
void id_Shift(ideal M, int s, const ring r)
ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring r)
#define IDELEMS(i)
#define id_Test(A, lR)
static int idElem(const ideal F)
number of non-zero polys in F
#define R
Definition sirandom.c:27
#define M
Definition sirandom.c:25
#define Q
Definition sirandom.c:26
long sm_ExpBound(ideal m, int di, int ra, int t, const ring currRing)
Definition sparsmat.cc:188
ring sm_RingChange(const ring origR, long bound)
Definition sparsmat.cc:258
void sm_KillModifiedRing(ring r)
Definition sparsmat.cc:289
sleftv * leftv
Definition structs.h:57
char * char_ptr
Definition structs.h:53
tHomog
Definition structs.h:35
@ isHomog
Definition structs.h:37
@ testHomog
Definition structs.h:38
@ isNotHomog
Definition structs.h:36
#define BITSET
Definition structs.h:16
skStrategy * kStrategy
Definition structs.h:58
#define loop
Definition structs.h:75
void syGaussForOne(ideal syz, int elnum, int ModComp, int from, int till)
Definition syz.cc:218
intvec * syBetti(resolvente res, int length, int *regularity, intvec *weights, BOOLEAN tomin, int *row_shift)
Definition syz.cc:783
resolvente sySchreyerResolvente(ideal arg, int maxlength, int *length, BOOLEAN isMonomial=FALSE, BOOLEAN notReplace=FALSE)
Definition syz0.cc:855
int name
New type name for int.
ideal t_rep_gb(const ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode)
Definition tgb.cc:3581
@ INT_CMD
Definition tok.h:96
THREAD_VAR double(* wFunctional)(int *degw, int *lpol, int npol, double *rel, double wx, double wNsqr)
Definition weight.cc:20
void wCall(poly *s, int sl, int *x, double wNsqr, const ring R)
Definition weight.cc:108
double wFunctionalBuch(int *degw, int *lpol, int npol, double *rel, double wx, double wNsqr)
Definition weight0.cc:78