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)
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 pEnlargeSet(&(e->m),IDELEMS(e),15);
86 IDELEMS(e) = 16;
87 h2 = kStd(h1,currRing->qideal,isNotHomog,NULL);
88 h3 = idMaxIdeal(1);
89 h4=idMult(h2,h3);
90 idDelete(&h3);
91 h3=kStd(h4,currRing->qideal,isNotHomog,NULL);
92 k = IDELEMS(h3);
93 while ((k > 0) && (h3->m[k-1] == NULL)) k--;
94 j = -1;
95 l = IDELEMS(h2);
96 while ((l > 0) && (h2->m[l-1] == NULL)) l--;
97 for (i=l-1; i>=0; i--)
98 {
99 if (h2->m[i] != NULL)
100 {
101 ll = 0;
102 while ((ll < k) && ((h3->m[ll] == NULL)
103 || !pDivisibleBy(h3->m[ll],h2->m[i])))
104 ll++;
105 if (ll >= k)
106 {
107 j++;
108 if (j > IDELEMS(e)-1)
109 {
110 pEnlargeSet(&(e->m),IDELEMS(e),16);
111 IDELEMS(e) += 16;
112 }
113 e->m[j] = pCopy(h2->m[i]);
114 }
115 }
116 }
117 idDelete(&h2);
118 idDelete(&h3);
119 idDelete(&h4);
120 if (currRing->qideal!=NULL)
121 {
122 h3=idInit(1,e->rank);
123 h2=kNF(h3,currRing->qideal,e);
124 idDelete(&h3);
125 idDelete(&e);
126 e=h2;
127 }
128 idSkipZeroes(e);
129 return e;
130}
131
132
133static ideal idSectWithElim (ideal h1,ideal h2, GbVariant alg)
134// does not destroy h1,h2
135{
136 if (TEST_OPT_PROT) PrintS("intersect by elimination method\n");
137 assume(!idIs0(h1));
138 assume(!idIs0(h2));
139 assume(IDELEMS(h1)<=IDELEMS(h2));
142 // add a new variable:
143 int j;
144 ring origRing=currRing;
145 ring r=rCopy0(origRing);
146 r->N++;
147 r->block0[0]=1;
148 r->block1[0]= r->N;
149 omFree(r->order);
150 r->order=(rRingOrder_t*)omAlloc0(3*sizeof(rRingOrder_t));
151 r->order[0]=ringorder_dp;
152 r->order[1]=ringorder_C;
153 char **names=(char**)omAlloc0(rVar(r) * sizeof(char_ptr));
154 for (j=0;j<r->N-1;j++) names[j]=r->names[j];
155 names[r->N-1]=omStrDup("@");
156 omFree(r->names);
157 r->names=names;
158 rComplete(r,TRUE);
159 // fetch h1, h2
160 ideal h;
161 h1=idrCopyR(h1,origRing,r);
162 h2=idrCopyR(h2,origRing,r);
163 // switch to temp. ring r
165 // create 1-t, t
166 poly omt=p_One(currRing);
167 p_SetExp(omt,r->N,1,currRing);
168 p_Setm(omt,currRing);
169 poly t=p_Copy(omt,currRing);
170 omt=p_Neg(omt,currRing);
171 omt=p_Add_q(omt,pOne(),currRing);
172 // compute (1-t)*h1
173 h1=(ideal)mp_MultP((matrix)h1,omt,currRing);
174 // compute t*h2
175 h2=(ideal)mp_MultP((matrix)h2,pCopy(t),currRing);
176 // (1-t)h1 + t*h2
177 h=idInit(IDELEMS(h1)+IDELEMS(h2),1);
178 int l;
179 for (l=IDELEMS(h1)-1; l>=0; l--)
180 {
181 h->m[l] = h1->m[l]; h1->m[l]=NULL;
182 }
183 j=IDELEMS(h1);
184 for (l=IDELEMS(h2)-1; l>=0; l--)
185 {
186 h->m[l+j] = h2->m[l]; h2->m[l]=NULL;
187 }
188 idDelete(&h1);
189 idDelete(&h2);
190 // eliminate t:
191 ideal res=idElimination(h,t,NULL,alg);
192 // cleanup
193 idDelete(&h);
194 pDelete(&t);
195 if (res!=NULL) res=idrMoveR(res,r,origRing);
196 rChangeCurrRing(origRing);
197 rDelete(r);
198 return res;
199}
200
201static ideal idGroebner(ideal temp,int syzComp,GbVariant alg, intvec* hilb=NULL, intvec* w=NULL, tHomog hom=testHomog)
202{
203 //Print("syz=%d\n",syzComp);
204 //PrintS(showOption());
205 //PrintLn();
206 ideal temp1;
207 if (w==NULL)
208 {
209 if (hom==testHomog)
210 hom=(tHomog)idHomModule(temp,currRing->qideal,&w); //sets w to weight vector or NULL
211 }
212 else
213 {
214 w=ivCopy(w);
215 hom=isHomog;
216 }
217#ifdef HAVE_SHIFTBBA
218 if (rIsLPRing(currRing)) alg = GbStd;
219#endif
220 if ((alg==GbStd)||(alg==GbDefault))
221 {
222 if (TEST_OPT_PROT &&(alg==GbStd)) { PrintS("std:"); mflush(); }
223 temp1 = kStd(temp,currRing->qideal,hom,&w,hilb,syzComp);
224 idDelete(&temp);
225 }
226 else if (alg==GbSlimgb)
227 {
228 if (TEST_OPT_PROT) { PrintS("slimgb:"); mflush(); }
229 temp1 = t_rep_gb(currRing, temp, syzComp);
230 idDelete(&temp);
231 }
232 else if (alg==GbGroebner)
233 {
234 if (TEST_OPT_PROT) { PrintS("groebner:"); mflush(); }
235 BOOLEAN err;
236 temp1=(ideal)iiCallLibProc1("groebner",temp,MODUL_CMD,err);
237 if (err)
238 {
239 Werror("error %d in >>groebner<<",err);
240 temp1=idInit(1,1);
241 }
242 }
243 else if (alg==GbModstd)
244 {
245 if (TEST_OPT_PROT) { PrintS("modStd:"); mflush(); }
246 BOOLEAN err;
247 void *args[]={temp,(void*)1,NULL};
248 int arg_t[]={MODUL_CMD,INT_CMD,0};
249 leftv temp0=ii_CallLibProcM("modStd",args,arg_t,currRing,err);
250 temp1=(ideal)temp0->data;
252 if (err)
253 {
254 Werror("error %d in >>modStd<<",err);
255 temp1=idInit(1,1);
256 }
257 }
258 else if (alg==GbSba)
259 {
260 if (TEST_OPT_PROT) { PrintS("sba:"); mflush(); }
261 temp1 = kSba(temp,currRing->qideal,hom,&w,1,0,NULL);
262 if (w!=NULL) delete w;
263 }
264 else if (alg==GbStdSat)
265 {
266 if (TEST_OPT_PROT) { PrintS("std:sat:"); mflush(); }
267 BOOLEAN err;
268 // search for 2nd block of vars
269 int i=0;
270 int block=-1;
271 loop
272 {
273 if ((currRing->order[i]!=ringorder_c)
274 && (currRing->order[i]!=ringorder_C)
275 && (currRing->order[i]!=ringorder_s))
276 {
277 if (currRing->order[i]==0) { err=TRUE;break;}
278 block++;
279 if (block==1) { block=i; break;}
280 }
281 i++;
282 }
283 if (block>0)
284 {
285 if (TEST_OPT_PROT)
286 {
287 Print("sat(%d..%d)\n",currRing->block0[block],currRing->block1[block]);
288 mflush();
289 }
290 ideal v=idInit(currRing->block1[block]-currRing->block0[block]+1,1);
291 for(i=currRing->block0[block];i<=currRing->block1[block];i++)
292 {
293 v->m[i-currRing->block0[block]]=pOne();
294 pSetExp(v->m[i-currRing->block0[block]],i,1);
295 pSetm(v->m[i-currRing->block0[block]]);
296 }
297 void *args[]={temp,v,NULL};
298 int arg_t[]={MODUL_CMD,IDEAL_CMD,0};
299 leftv temp0=ii_CallLibProcM("satstd",args,arg_t,currRing,err);
300 temp1=(ideal)temp0->data;
302 }
303 if (err)
304 {
305 Werror("error %d in >>satstd<<",err);
306 temp1=idInit(1,1);
307 }
308 }
309 if (w!=NULL) delete w;
310 return temp1;
311}
312
313/*2
314* h3 := h1 intersect h2
315*/
316ideal idSect (ideal h1,ideal h2, GbVariant alg)
317{
318 int i,j,k;
319 unsigned length;
320 int flength = id_RankFreeModule(h1,currRing);
321 int slength = id_RankFreeModule(h2,currRing);
322 int rank=si_max(h1->rank,h2->rank);
323 if ((idIs0(h1)) || (idIs0(h2))) return idInit(1,rank);
324
325 BITSET save_opt;
326 SI_SAVE_OPT1(save_opt);
328
329 ideal first,second,temp,temp1,result;
330 poly p,q;
331
332 if (IDELEMS(h1)<IDELEMS(h2))
333 {
334 first = h1;
335 second = h2;
336 }
337 else
338 {
339 first = h2;
340 second = h1;
341 int t=flength; flength=slength; slength=t;
342 }
343 length = si_max(flength,slength);
344 if (length==0)
345 {
346 if ((currRing->qideal==NULL)
347 && (currRing->OrdSgn==1)
350 return idSectWithElim(first,second,alg);
351 else length = 1;
352 }
353 if (TEST_OPT_PROT) PrintS("intersect by syzygy methods\n");
354 j = IDELEMS(first);
355
356 ring orig_ring=currRing;
357 ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
358 rSetSyzComp(length,syz_ring);
359 rChangeCurrRing(syz_ring);
360
361 while ((j>0) && (first->m[j-1]==NULL)) j--;
362 temp = idInit(j /*IDELEMS(first)*/+IDELEMS(second),length+j);
363 k = 0;
364 for (i=0;i<j;i++)
365 {
366 if (first->m[i]!=NULL)
367 {
368 if (syz_ring==orig_ring)
369 temp->m[k] = pCopy(first->m[i]);
370 else
371 temp->m[k] = prCopyR(first->m[i], orig_ring, syz_ring);
372 q = pOne();
373 pSetComp(q,i+1+length);
374 pSetmComp(q);
375 if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
376 p = temp->m[k];
377 while (pNext(p)!=NULL) pIter(p);
378 pNext(p) = q;
379 k++;
380 }
381 }
382 for (i=0;i<IDELEMS(second);i++)
383 {
384 if (second->m[i]!=NULL)
385 {
386 if (syz_ring==orig_ring)
387 temp->m[k] = pCopy(second->m[i]);
388 else
389 temp->m[k] = prCopyR(second->m[i], orig_ring,currRing);
390 if (slength==0) p_Shift(&(temp->m[k]),1,currRing);
391 k++;
392 }
393 }
394 intvec *w=NULL;
395
396 if ((alg!=GbDefault)
397 && (alg!=GbGroebner)
398 && (alg!=GbModstd)
399 && (alg!=GbSlimgb)
400 && (alg!=GbStd))
401 {
402 WarnS("wrong algorithm for GB");
403 alg=GbDefault;
404 }
405 temp1=idGroebner(temp,length,alg);
406
407 if(syz_ring!=orig_ring)
408 rChangeCurrRing(orig_ring);
409
410 result = idInit(IDELEMS(temp1),rank);
411 j = 0;
412 for (i=0;i<IDELEMS(temp1);i++)
413 {
414 if ((temp1->m[i]!=NULL)
415 && (__p_GetComp(temp1->m[i],syz_ring)>length))
416 {
417 if(syz_ring==orig_ring)
418 {
419 p = temp1->m[i];
420 }
421 else
422 {
423 p = prMoveR(temp1->m[i], syz_ring,orig_ring);
424 }
425 temp1->m[i]=NULL;
426 while (p!=NULL)
427 {
428 q = pNext(p);
429 pNext(p) = NULL;
430 k = pGetComp(p)-1-length;
431 pSetComp(p,0);
432 pSetmComp(p);
433 /* Warning! multiply only from the left! it's very important for Plural */
434 result->m[j] = pAdd(result->m[j],pMult(p,pCopy(first->m[k])));
435 p = q;
436 }
437 j++;
438 }
439 }
440 if(syz_ring!=orig_ring)
441 {
442 rChangeCurrRing(syz_ring);
443 idDelete(&temp1);
444 rChangeCurrRing(orig_ring);
445 rDelete(syz_ring);
446 }
447 else
448 {
449 idDelete(&temp1);
450 }
451
453 SI_RESTORE_OPT1(save_opt);
455 {
456 w=NULL;
457 temp1=kStd(result,currRing->qideal,testHomog,&w);
458 if (w!=NULL) delete w;
460 idSkipZeroes(temp1);
461 return temp1;
462 }
463 //else
464 // temp1=kInterRed(result,currRing->qideal);
465 return result;
466}
467
468/*2
469* ideal/module intersection for a list of objects
470* given as 'resolvente'
471*/
473{
474 int i,j=0,k=0,l,maxrk=-1,realrki;
475 unsigned syzComp;
476 ideal bigmat,tempstd,result;
477 poly p;
478 int isIdeal=0;
479
480 /* find 0-ideals and max rank -----------------------------------*/
481 for (i=0;i<length;i++)
482 {
483 if (!idIs0(arg[i]))
484 {
485 realrki=id_RankFreeModule(arg[i],currRing);
486 k++;
487 j += IDELEMS(arg[i]);
488 if (realrki>maxrk) maxrk = realrki;
489 }
490 else
491 {
492 if (arg[i]!=NULL)
493 {
494 return idInit(1,arg[i]->rank);
495 }
496 }
497 }
498 if (maxrk == 0)
499 {
500 isIdeal = 1;
501 maxrk = 1;
502 }
503 /* init -----------------------------------------------------------*/
504 j += maxrk;
505 syzComp = k*maxrk;
506
507 ring orig_ring=currRing;
508 ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
509 rSetSyzComp(syzComp,syz_ring);
510 rChangeCurrRing(syz_ring);
511
512 bigmat = idInit(j,(k+1)*maxrk);
513 /* create unit matrices ------------------------------------------*/
514 for (i=0;i<maxrk;i++)
515 {
516 for (j=0;j<=k;j++)
517 {
518 p = pOne();
519 pSetComp(p,i+1+j*maxrk);
520 pSetmComp(p);
521 bigmat->m[i] = pAdd(bigmat->m[i],p);
522 }
523 }
524 /* enter given ideals ------------------------------------------*/
525 i = maxrk;
526 k = 0;
527 for (j=0;j<length;j++)
528 {
529 if (arg[j]!=NULL)
530 {
531 for (l=0;l<IDELEMS(arg[j]);l++)
532 {
533 if (arg[j]->m[l]!=NULL)
534 {
535 if (syz_ring==orig_ring)
536 bigmat->m[i] = pCopy(arg[j]->m[l]);
537 else
538 bigmat->m[i] = prCopyR(arg[j]->m[l], orig_ring,currRing);
539 p_Shift(&(bigmat->m[i]),k*maxrk+isIdeal,currRing);
540 i++;
541 }
542 }
543 k++;
544 }
545 }
546 /* std computation --------------------------------------------*/
547 if ((alg!=GbDefault)
548 && (alg!=GbGroebner)
549 && (alg!=GbModstd)
550 && (alg!=GbSlimgb)
551 && (alg!=GbStd))
552 {
553 WarnS("wrong algorithm for GB");
554 alg=GbDefault;
555 }
556 tempstd=idGroebner(bigmat,syzComp,alg);
557
558 if(syz_ring!=orig_ring)
559 rChangeCurrRing(orig_ring);
560
561 /* interpret result ----------------------------------------*/
562 result = idInit(IDELEMS(tempstd),maxrk);
563 k = 0;
564 for (j=0;j<IDELEMS(tempstd);j++)
565 {
566 if ((tempstd->m[j]!=NULL) && (__p_GetComp(tempstd->m[j],syz_ring)>syzComp))
567 {
568 if (syz_ring==orig_ring)
569 p = pCopy(tempstd->m[j]);
570 else
571 p = prCopyR(tempstd->m[j], syz_ring,currRing);
572 p_Shift(&p,-syzComp-isIdeal,currRing);
573 result->m[k] = p;
574 k++;
575 }
576 }
577 /* clean up ----------------------------------------------------*/
578 if(syz_ring!=orig_ring)
579 rChangeCurrRing(syz_ring);
580 idDelete(&tempstd);
581 if(syz_ring!=orig_ring)
582 {
583 rChangeCurrRing(orig_ring);
584 rDelete(syz_ring);
585 }
587 return result;
588}
589
590/*2
591*computes syzygies of h1,
592*if quot != NULL it computes in the quotient ring modulo "quot"
593*works always in a ring with ringorder_s
594*/
595/* construct a "matrix" (h11 may be NULL)
596 * h1 h11
597 * E_n 0
598 * and compute a (column) GB of it, with a syzComp=rows(h1)=rows(h11)
599 * currRing must be a syz-ring with syzComp set
600 * result is a "matrix":
601 * G 0
602 * T S
603 * where G: GB of (h1+h11)
604 * T: G/h11=h1*T
605 * S: relative syzygies(h1) modulo h11
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 if (idIs0(h1)) return NULL;
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 ideal s_h3;
1165 if (isSB)
1166 {
1167 s_h3 = idCopy(s_mod);
1168 idPrepareStd(s_h3, k+comps_to_add);
1169 }
1170 else
1171 {
1172 s_h3 = idPrepare(s_mod,NULL,(tHomog)FALSE,k+comps_to_add,NULL,alg);
1173 }
1174 if (!goodShape)
1175 {
1176 for (j=0;j<IDELEMS(s_h3);j++)
1177 {
1178 if ((s_h3->m[j] != NULL) && (pMinComp(s_h3->m[j]) > k))
1179 p_Delete(&(s_h3->m[j]),currRing);
1180 }
1181 }
1182 idSkipZeroes(s_h3);
1183 if (lsmod==0)
1184 {
1185 id_Shift(s_temp,1,currRing);
1186 }
1187 if (unit!=NULL)
1188 {
1189 for(j = 0;j<comps_to_add;j++)
1190 {
1191 p = s_temp->m[j];
1192 if (p!=NULL)
1193 {
1194 while (pNext(p)!=NULL) pIter(p);
1195 pNext(p) = pOne();
1196 pIter(p);
1197 pSetComp(p,1+j+k);
1198 pSetmComp(p);
1199 p = pNeg(p);
1200 }
1201 }
1202 s_temp->rank += (k+comps_to_add);
1203 }
1204 ideal s_result = kNF(s_h3,currRing->qideal,s_temp,k);
1205 s_result->rank = s_h3->rank;
1206 ideal s_rest = idInit(IDELEMS(s_result),k);
1207 idDelete(&s_h3);
1208 idDelete(&s_temp);
1209
1210 for (j=0;j<IDELEMS(s_result);j++)
1211 {
1212 if (s_result->m[j]!=NULL)
1213 {
1214 if (pGetComp(s_result->m[j])<=k)
1215 {
1216 if (!divide)
1217 {
1218 if (rest==NULL)
1219 {
1220 if (isSB)
1221 {
1222 WarnS("first module not a standardbasis\n"
1223 "// ** or second not a proper submodule");
1224 }
1225 else
1226 WerrorS("2nd module does not lie in the first");
1227 }
1228 idDelete(&s_result);
1229 idDelete(&s_rest);
1230 if(syz_ring!=orig_ring)
1231 {
1232 idDelete(&s_mod);
1233 rChangeCurrRing(orig_ring);
1234 rDelete(syz_ring);
1235 }
1236 if (unit!=NULL)
1237 {
1238 idLift_setUnit(idelems_submod,unit);
1239 }
1240 if (rest!=NULL) *rest=idCopy(submod);
1241 s_result=idInit(idelems_submod,idelems_mod);
1242 return s_result;
1243 }
1244 else
1245 {
1246 p = s_rest->m[j] = s_result->m[j];
1247 while ((pNext(p)!=NULL) && (pGetComp(pNext(p))<=k)) pIter(p);
1248 s_result->m[j] = pNext(p);
1249 pNext(p) = NULL;
1250 }
1251 }
1252 p_Shift(&(s_result->m[j]),-k,currRing);
1253 pNeg(s_result->m[j]);
1254 }
1255 }
1256 if ((lsmod==0) && (s_rest!=NULL))
1257 {
1258 for (j=IDELEMS(s_rest);j>0;j--)
1259 {
1260 if (s_rest->m[j-1]!=NULL)
1261 {
1262 p_Shift(&(s_rest->m[j-1]),-1,currRing);
1263 }
1264 }
1265 }
1266 if(syz_ring!=orig_ring)
1267 {
1268 idDelete(&s_mod);
1269 rChangeCurrRing(orig_ring);
1270 s_result = idrMoveR_NoSort(s_result, syz_ring, orig_ring);
1271 s_rest = idrMoveR_NoSort(s_rest, syz_ring, orig_ring);
1272 rDelete(syz_ring);
1273 }
1274 if (rest!=NULL)
1275 {
1276 s_rest->rank=mod->rank;
1277 *rest = s_rest;
1278 }
1279 else
1280 idDelete(&s_rest);
1281 if (unit!=NULL)
1282 {
1283 *unit=mpNew(idelems_submod,idelems_submod);
1284 int i;
1285 for(i=0;i<IDELEMS(s_result);i++)
1286 {
1287 poly p=s_result->m[i];
1288 poly q=NULL;
1289 while(p!=NULL)
1290 {
1291 if(pGetComp(p)<=comps_to_add)
1292 {
1293 pSetComp(p,0);
1294 if (q!=NULL)
1295 {
1296 pNext(q)=pNext(p);
1297 }
1298 else
1299 {
1300 pIter(s_result->m[i]);
1301 }
1302 pNext(p)=NULL;
1303 MATELEM(*unit,i+1,i+1)=pAdd(MATELEM(*unit,i+1,i+1),p);
1304 if(q!=NULL) p=pNext(q);
1305 else p=s_result->m[i];
1306 }
1307 else
1308 {
1309 q=p;
1310 pIter(p);
1311 }
1312 }
1313 p_Shift(&s_result->m[i],-comps_to_add,currRing);
1314 }
1315 }
1316 s_result->rank=idelems_mod;
1317 return s_result;
1318}
1319
1320/*2
1321*computes division of P by Q with remainder up to (w-weighted) degree n
1322*P, Q, and w are not changed
1323*/
1324void idLiftW(ideal P,ideal Q,int n,matrix &T, ideal &R,int *w)
1325{
1326 long N=0;
1327 int i;
1328 for(i=IDELEMS(Q)-1;i>=0;i--)
1329 if(w==NULL)
1330 N=si_max(N,p_Deg(Q->m[i],currRing));
1331 else
1332 N=si_max(N,p_DegW(Q->m[i],w,currRing));
1333 N+=n;
1334
1335 T=mpNew(IDELEMS(Q),IDELEMS(P));
1336 R=idInit(IDELEMS(P),P->rank);
1337
1338 for(i=IDELEMS(P)-1;i>=0;i--)
1339 {
1340 poly p;
1341 if(w==NULL)
1342 p=ppJet(P->m[i],N);
1343 else
1344 p=ppJetW(P->m[i],N,w);
1345
1346 int j=IDELEMS(Q)-1;
1347 while(p!=NULL)
1348 {
1349 if(pDivisibleBy(Q->m[j],p))
1350 {
1351 poly p0=p_DivideM(pHead(p),pHead(Q->m[j]),currRing);
1352 if(w==NULL)
1353 p=pJet(pSub(p,ppMult_mm(Q->m[j],p0)),N);
1354 else
1355 p=pJetW(pSub(p,ppMult_mm(Q->m[j],p0)),N,w);
1356 pNormalize(p);
1357 if(((w==NULL)&&(p_Deg(p0,currRing)>n))||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
1358 p_Delete(&p0,currRing);
1359 else
1360 MATELEM(T,j+1,i+1)=pAdd(MATELEM(T,j+1,i+1),p0);
1361 j=IDELEMS(Q)-1;
1362 }
1363 else
1364 {
1365 if(j==0)
1366 {
1367 poly p0=p;
1368 pIter(p);
1369 pNext(p0)=NULL;
1370 if(((w==NULL)&&(p_Deg(p0,currRing)>n))
1371 ||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
1372 p_Delete(&p0,currRing);
1373 else
1374 R->m[i]=pAdd(R->m[i],p0);
1375 j=IDELEMS(Q)-1;
1376 }
1377 else
1378 j--;
1379 }
1380 }
1381 }
1382}
1383
1384/*2
1385*computes the quotient of h1,h2 : internal routine for idQuot
1386*BEWARE: the returned ideals may contain incorrectly ordered polys !
1387*
1388*/
1389static ideal idInitializeQuot (ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN *addOnlyOne, int *kkmax)
1390{
1391 idTest(h1);
1392 idTest(h2);
1393
1394 ideal temph1;
1395 poly p,q = NULL;
1396 int i,l,ll,k,kkk,kmax;
1397 int j = 0;
1398 int k1 = id_RankFreeModule(h1,currRing);
1399 int k2 = id_RankFreeModule(h2,currRing);
1400 tHomog hom=isNotHomog;
1401 k=si_max(k1,k2);
1402 if (k==0)
1403 k = 1;
1404 if ((k2==0) && (k>1)) *addOnlyOne = FALSE;
1405 intvec * weights;
1406 hom = (tHomog)idHomModule(h1,currRing->qideal,&weights);
1407 if /**addOnlyOne &&*/ (/*(*/ !h1IsStb /*)*/)
1408 temph1 = kStd(h1,currRing->qideal,hom,&weights,NULL);
1409 else
1410 temph1 = idCopy(h1);
1411 if (weights!=NULL) delete weights;
1412 idTest(temph1);
1413/*--- making a single vector from h2 ---------------------*/
1414 for (i=0; i<IDELEMS(h2); i++)
1415 {
1416 if (h2->m[i] != NULL)
1417 {
1418 p = pCopy(h2->m[i]);
1419 if (k2 == 0)
1420 p_Shift(&p,j*k+1,currRing);
1421 else
1422 p_Shift(&p,j*k,currRing);
1423 q = pAdd(q,p);
1424 j++;
1425 }
1426 }
1427 *kkmax = kmax = j*k+1;
1428/*--- adding a monomial for the result (syzygy) ----------*/
1429 p = q;
1430 while (pNext(p)!=NULL) pIter(p);
1431 pNext(p) = pOne();
1432 pIter(p);
1433 pSetComp(p,kmax);
1434 pSetmComp(p);
1435/*--- constructing the big matrix ------------------------*/
1436 ideal h4 = idInit(k,kmax+k-1);
1437 h4->m[0] = q;
1438 if (k2 == 0)
1439 {
1440 for (i=1; i<k; i++)
1441 {
1442 if (h4->m[i-1]!=NULL)
1443 {
1444 p = p_Copy_noCheck(h4->m[i-1], currRing); /*h4->m[i-1]!=NULL*/
1445 p_Shift(&p,1,currRing);
1446 h4->m[i] = p;
1447 }
1448 else break;
1449 }
1450 }
1451 idSkipZeroes(h4);
1452 kkk = IDELEMS(h4);
1453 i = IDELEMS(temph1);
1454 for (l=0; l<i; l++)
1455 {
1456 if(temph1->m[l]!=NULL)
1457 {
1458 for (ll=0; ll<j; ll++)
1459 {
1460 p = pCopy(temph1->m[l]);
1461 if (k1 == 0)
1462 p_Shift(&p,ll*k+1,currRing);
1463 else
1464 p_Shift(&p,ll*k,currRing);
1465 if (kkk >= IDELEMS(h4))
1466 {
1467 pEnlargeSet(&(h4->m),IDELEMS(h4),16);
1468 IDELEMS(h4) += 16;
1469 }
1470 h4->m[kkk] = p;
1471 kkk++;
1472 }
1473 }
1474 }
1475/*--- if h2 goes in as single vector - the h1-part is just SB ---*/
1476 if (*addOnlyOne)
1477 {
1478 idSkipZeroes(h4);
1479 p = h4->m[0];
1480 for (i=0;i<IDELEMS(h4)-1;i++)
1481 {
1482 h4->m[i] = h4->m[i+1];
1483 }
1484 h4->m[IDELEMS(h4)-1] = p;
1485 }
1486 idDelete(&temph1);
1487 //idTest(h4);//see remark at the beginning
1488 return h4;
1489}
1490
1491/*2
1492*computes the quotient of h1,h2
1493*/
1494ideal idQuot (ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN resultIsIdeal)
1495{
1496 // first check for special case h1:(0)
1497 if (idIs0(h2))
1498 {
1499 ideal res;
1500 if (resultIsIdeal)
1501 {
1502 res = idInit(1,1);
1503 res->m[0] = pOne();
1504 }
1505 else
1506 res = idFreeModule(h1->rank);
1507 return res;
1508 }
1509 int i, kmax;
1510 BOOLEAN addOnlyOne=TRUE;
1511 tHomog hom=isNotHomog;
1512 intvec * weights1;
1513
1514 ideal s_h4 = idInitializeQuot (h1,h2,h1IsStb,&addOnlyOne,&kmax);
1515
1516 hom = (tHomog)idHomModule(s_h4,currRing->qideal,&weights1);
1517
1518 ring orig_ring=currRing;
1519 ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
1520 rSetSyzComp(kmax-1,syz_ring);
1521 rChangeCurrRing(syz_ring);
1522 if (orig_ring!=syz_ring)
1523 // s_h4 = idrMoveR_NoSort(s_h4,orig_ring, syz_ring);
1524 s_h4 = idrMoveR(s_h4,orig_ring, syz_ring);
1525 idTest(s_h4);
1526
1527 #if 0
1528 matrix m=idModule2Matrix(idCopy(s_h4));
1529 PrintS("start:\n");
1530 ipPrint_MA0(m,"Q");
1531 idDelete((ideal *)&m);
1532 PrintS("last elem:");wrp(s_h4->m[IDELEMS(s_h4)-1]);PrintLn();
1533 #endif
1534
1535 ideal s_h3;
1536 BITSET old_test1;
1537 SI_SAVE_OPT1(old_test1);
1539 if (addOnlyOne)
1540 {
1542 s_h3 = kStd(s_h4,currRing->qideal,hom,&weights1,NULL,0/*kmax-1*/,IDELEMS(s_h4)-1);
1543 }
1544 else
1545 {
1546 s_h3 = kStd(s_h4,currRing->qideal,hom,&weights1,NULL,kmax-1);
1547 }
1548 SI_RESTORE_OPT1(old_test1);
1549
1550 #if 0
1551 // only together with the above debug stuff
1552 idSkipZeroes(s_h3);
1553 m=idModule2Matrix(idCopy(s_h3));
1554 Print("result, kmax=%d:\n",kmax);
1555 ipPrint_MA0(m,"S");
1556 idDelete((ideal *)&m);
1557 #endif
1558
1559 idTest(s_h3);
1560 if (weights1!=NULL) delete weights1;
1561 idDelete(&s_h4);
1562
1563 for (i=0;i<IDELEMS(s_h3);i++)
1564 {
1565 if ((s_h3->m[i]!=NULL) && (pGetComp(s_h3->m[i])>=kmax))
1566 {
1567 if (resultIsIdeal)
1568 p_Shift(&s_h3->m[i],-kmax,currRing);
1569 else
1570 p_Shift(&s_h3->m[i],-kmax+1,currRing);
1571 }
1572 else
1573 p_Delete(&s_h3->m[i],currRing);
1574 }
1575 if (resultIsIdeal)
1576 s_h3->rank = 1;
1577 else
1578 s_h3->rank = h1->rank;
1579 if(syz_ring!=orig_ring)
1580 {
1581 rChangeCurrRing(orig_ring);
1582 s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
1583 rDelete(syz_ring);
1584 }
1585 idSkipZeroes(s_h3);
1586 idTest(s_h3);
1587 return s_h3;
1588}
1589
1590/*2
1591* eliminate delVar (product of vars) in h1
1592*/
1593ideal idElimination (ideal h1,poly delVar,intvec *hilb, GbVariant alg)
1594{
1595 int i,j=0,k,l;
1596 ideal h,hh, h3;
1597 rRingOrder_t *ord;
1598 int *block0,*block1;
1599 int ordersize=2;
1600 int **wv;
1601 tHomog hom;
1602 intvec * w;
1603 ring tmpR;
1604 ring origR = currRing;
1605
1606 if (delVar==NULL)
1607 {
1608 return idCopy(h1);
1609 }
1610 if ((currRing->qideal!=NULL) && rIsPluralRing(origR))
1611 {
1612 WerrorS("cannot eliminate in a qring");
1613 return NULL;
1614 }
1615 if (idIs0(h1)) return idInit(1,h1->rank);
1616#ifdef HAVE_PLURAL
1617 if (rIsPluralRing(origR))
1618 /* in the NC case, we have to check the admissibility of */
1619 /* the subalgebra to be intersected with */
1620 {
1621 if ((ncRingType(origR) != nc_skew) && (ncRingType(origR) != nc_exterior)) /* in (quasi)-commutative algebras every subalgebra is admissible */
1622 {
1623 if (nc_CheckSubalgebra(delVar,origR))
1624 {
1625 WerrorS("no elimination is possible: subalgebra is not admissible");
1626 return NULL;
1627 }
1628 }
1629 }
1630#endif
1631 hom=(tHomog)idHomModule(h1,NULL,&w); //sets w to weight vector or NULL
1632 h3=idInit(16,h1->rank);
1633 ordersize=rBlocks(origR)+1;
1634#if 0
1635 if (rIsPluralRing(origR)) // we have too keep the odering: it may be needed
1636 // for G-algebra
1637 {
1638 for (k=0;k<ordersize-1; k++)
1639 {
1640 block0[k+1] = origR->block0[k];
1641 block1[k+1] = origR->block1[k];
1642 ord[k+1] = origR->order[k];
1643 if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1644 }
1645 }
1646 else
1647 {
1648 block0[1] = 1;
1649 block1[1] = (currRing->N);
1650 if (origR->OrdSgn==1) ord[1] = ringorder_wp;
1651 else ord[1] = ringorder_ws;
1652 wv[1]=(int*)omAlloc0((currRing->N)*sizeof(int));
1653 double wNsqr = (double)2.0 / (double)(currRing->N);
1655 int *x= (int * )omAlloc(2 * ((currRing->N) + 1) * sizeof(int));
1656 int sl=IDELEMS(h1) - 1;
1657 wCall(h1->m, sl, x, wNsqr);
1658 for (sl = (currRing->N); sl!=0; sl--)
1659 wv[1][sl-1] = x[sl + (currRing->N) + 1];
1660 omFreeSize((ADDRESS)x, 2 * ((currRing->N) + 1) * sizeof(int));
1661
1662 ord[2]=ringorder_C;
1663 ord[3]=0;
1664 }
1665#else
1666#endif
1667 if ((hom==TRUE) && (origR->OrdSgn==1) && (!rIsPluralRing(origR)))
1668 {
1669 #if 1
1670 // we change to an ordering:
1671 // aa(1,1,1,...,0,0,0),wp(...),C
1672 // this seems to be better than version 2 below,
1673 // according to Tst/../elimiate_[3568].tat (- 17 %)
1674 ord=(rRingOrder_t*)omAlloc0(4*sizeof(rRingOrder_t));
1675 block0=(int*)omAlloc0(4*sizeof(int));
1676 block1=(int*)omAlloc0(4*sizeof(int));
1677 wv=(int**) omAlloc0(4*sizeof(int**));
1678 block0[0] = block0[1] = 1;
1679 block1[0] = block1[1] = rVar(origR);
1680 wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1681 // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1682 // ignore it
1683 ord[0] = ringorder_aa;
1684 for (j=0;j<rVar(origR);j++)
1685 if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1686 BOOLEAN wp=FALSE;
1687 for (j=0;j<rVar(origR);j++)
1688 if (p_Weight(j+1,origR)!=1) { wp=TRUE;break; }
1689 if (wp)
1690 {
1691 wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1692 for (j=0;j<rVar(origR);j++)
1693 wv[1][j]=p_Weight(j+1,origR);
1694 ord[1] = ringorder_wp;
1695 }
1696 else
1697 ord[1] = ringorder_dp;
1698 #else
1699 // we change to an ordering:
1700 // a(w1,...wn),wp(1,...0.....),C
1701 ord=(int*)omAlloc0(4*sizeof(int));
1702 block0=(int*)omAlloc0(4*sizeof(int));
1703 block1=(int*)omAlloc0(4*sizeof(int));
1704 wv=(int**) omAlloc0(4*sizeof(int**));
1705 block0[0] = block0[1] = 1;
1706 block1[0] = block1[1] = rVar(origR);
1707 wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1708 wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1709 ord[0] = ringorder_a;
1710 for (j=0;j<rVar(origR);j++)
1711 wv[0][j]=pWeight(j+1,origR);
1712 ord[1] = ringorder_wp;
1713 for (j=0;j<rVar(origR);j++)
1714 if (pGetExp(delVar,j+1)!=0) wv[1][j]=1;
1715 #endif
1716 ord[2] = ringorder_C;
1717 ord[3] = (rRingOrder_t)0;
1718 }
1719 else
1720 {
1721 // we change to an ordering:
1722 // aa(....),orig_ordering
1723 ord=(rRingOrder_t*)omAlloc0(ordersize*sizeof(rRingOrder_t));
1724 block0=(int*)omAlloc0(ordersize*sizeof(int));
1725 block1=(int*)omAlloc0(ordersize*sizeof(int));
1726 wv=(int**) omAlloc0(ordersize*sizeof(int**));
1727 for (k=0;k<ordersize-1; k++)
1728 {
1729 block0[k+1] = origR->block0[k];
1730 block1[k+1] = origR->block1[k];
1731 ord[k+1] = origR->order[k];
1732 if (origR->wvhdl[k]!=NULL)
1733 #ifdef HAVE_OMALLOC
1734 wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1735 #else
1736 {
1737 int l=(origR->block1[k]-origR->block0[k]+1)*sizeof(int);
1738 if (origR->order[k]==ringorder_a64) l*=2;
1739 wv[k+1]=(int*)omalloc(l);
1740 memcpy(wv[k+1],origR->wvhdl[k],l);
1741 }
1742 #endif
1743 }
1744 block0[0] = 1;
1745 block1[0] = rVar(origR);
1746 wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1747 for (j=0;j<rVar(origR);j++)
1748 if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1749 // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1750 // ignore it
1751 ord[0] = ringorder_aa;
1752 }
1753 // fill in tmp ring to get back the data later on
1754 tmpR = rCopy0(origR,FALSE,FALSE); // qring==NULL
1755 //rUnComplete(tmpR);
1756 tmpR->p_Procs=NULL;
1757 tmpR->order = ord;
1758 tmpR->block0 = block0;
1759 tmpR->block1 = block1;
1760 tmpR->wvhdl = wv;
1761 rComplete(tmpR, 1);
1762
1763#ifdef HAVE_PLURAL
1764 /* update nc structure on tmpR */
1765 if (rIsPluralRing(origR))
1766 {
1767 if ( nc_rComplete(origR, tmpR, false) ) // no quotient ideal!
1768 {
1769 WerrorS("no elimination is possible: ordering condition is violated");
1770 // cleanup
1771 rDelete(tmpR);
1772 if (w!=NULL)
1773 delete w;
1774 return NULL;
1775 }
1776 }
1777#endif
1778 // change into the new ring
1779 //pChangeRing((currRing->N),currRing->OrdSgn,ord,block0,block1,wv);
1780 rChangeCurrRing(tmpR);
1781
1782 //h = idInit(IDELEMS(h1),h1->rank);
1783 // fetch data from the old ring
1784 //for (k=0;k<IDELEMS(h1);k++) h->m[k] = prCopyR( h1->m[k], origR);
1785 h=idrCopyR(h1,origR,currRing);
1786 if (origR->qideal!=NULL)
1787 {
1788 WarnS("eliminate in q-ring: experimental");
1789 ideal q=idrCopyR(origR->qideal,origR,currRing);
1790 ideal s=idSimpleAdd(h,q);
1791 idDelete(&h);
1792 idDelete(&q);
1793 h=s;
1794 }
1795 // compute GB
1796 if ((alg!=GbDefault)
1797 && (alg!=GbGroebner)
1798 && (alg!=GbModstd)
1799 && (alg!=GbSlimgb)
1800 && (alg!=GbSba)
1801 && (alg!=GbStd))
1802 {
1803 WarnS("wrong algorithm for GB");
1804 alg=GbDefault;
1805 }
1806 BITSET save2;
1807 SI_SAVE_OPT2(save2);
1809 hh=idGroebner(h,0,alg,hilb);
1810 SI_RESTORE_OPT2(save2);
1811 // go back to the original ring
1812 rChangeCurrRing(origR);
1813 i = IDELEMS(hh)-1;
1814 while ((i >= 0) && (hh->m[i] == NULL)) i--;
1815 j = -1;
1816 // fetch data from temp ring
1817 for (k=0; k<=i; k++)
1818 {
1819 l=(currRing->N);
1820 while ((l>0) && (p_GetExp( hh->m[k],l,tmpR)*pGetExp(delVar,l)==0)) l--;
1821 if (l==0)
1822 {
1823 j++;
1824 if (j >= IDELEMS(h3))
1825 {
1826 pEnlargeSet(&(h3->m),IDELEMS(h3),16);
1827 IDELEMS(h3) += 16;
1828 }
1829 h3->m[j] = prMoveR( hh->m[k], tmpR,origR);
1830 hh->m[k] = NULL;
1831 }
1832 }
1833 id_Delete(&hh, tmpR);
1834 idSkipZeroes(h3);
1835 rDelete(tmpR);
1836 if (w!=NULL)
1837 delete w;
1838 return h3;
1839}
1840
1841#ifdef WITH_OLD_MINOR
1842/*2
1843* compute the which-th ar-minor of the matrix a
1844*/
1845poly idMinor(matrix a, int ar, unsigned long which, ideal R)
1846{
1847 int i,j/*,k,size*/;
1848 unsigned long curr;
1849 int *rowchoise,*colchoise;
1850 BOOLEAN rowch,colch;
1851 // ideal result;
1852 matrix tmp;
1853 poly p,q;
1854
1855 rowchoise=(int *)omAlloc(ar*sizeof(int));
1856 colchoise=(int *)omAlloc(ar*sizeof(int));
1857 tmp=mpNew(ar,ar);
1858 curr = 0; /* index of current minor */
1859 idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1860 while (!rowch)
1861 {
1862 idInitChoise(ar,1,a->cols(),&colch,colchoise);
1863 while (!colch)
1864 {
1865 if (curr == which)
1866 {
1867 for (i=1; i<=ar; i++)
1868 {
1869 for (j=1; j<=ar; j++)
1870 {
1871 MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1872 }
1873 }
1874 p = mp_DetBareiss(tmp,currRing);
1875 if (p!=NULL)
1876 {
1877 if (R!=NULL)
1878 {
1879 q = p;
1880 p = kNF(R,currRing->qideal,q);
1881 p_Delete(&q,currRing);
1882 }
1883 }
1884 /*delete the matrix tmp*/
1885 for (i=1; i<=ar; i++)
1886 {
1887 for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1888 }
1889 idDelete((ideal*)&tmp);
1890 omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1891 omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1892 return (p);
1893 }
1894 curr++;
1895 idGetNextChoise(ar,a->cols(),&colch,colchoise);
1896 }
1897 idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1898 }
1899 return (poly) 1;
1900}
1901
1902/*2
1903* compute all ar-minors of the matrix a
1904*/
1905ideal idMinors(matrix a, int ar, ideal R)
1906{
1907 int i,j,/*k,*/size;
1908 int *rowchoise,*colchoise;
1909 BOOLEAN rowch,colch;
1910 ideal result;
1911 matrix tmp;
1912 poly p,q;
1913
1914 i = binom(a->rows(),ar);
1915 j = binom(a->cols(),ar);
1916 size=i*j;
1917
1918 rowchoise=(int *)omAlloc(ar*sizeof(int));
1919 colchoise=(int *)omAlloc(ar*sizeof(int));
1920 result=idInit(size,1);
1921 tmp=mpNew(ar,ar);
1922 // k = 0; /* the index in result*/
1923 idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1924 while (!rowch)
1925 {
1926 idInitChoise(ar,1,a->cols(),&colch,colchoise);
1927 while (!colch)
1928 {
1929 for (i=1; i<=ar; i++)
1930 {
1931 for (j=1; j<=ar; j++)
1932 {
1933 MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1934 }
1935 }
1936 p = mp_DetBareiss(tmp,currRing);
1937 if (p!=NULL)
1938 {
1939 if (R!=NULL)
1940 {
1941 q = p;
1942 p = kNF(R,currRing->qideal,q);
1943 p_Delete(&q,currRing);
1944 }
1945 }
1946 if (k>=size)
1947 {
1948 pEnlargeSet(&result->m,size,32);
1949 size += 32;
1950 }
1951 result->m[k] = p;
1952 k++;
1953 idGetNextChoise(ar,a->cols(),&colch,colchoise);
1954 }
1955 idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1956 }
1957 /*delete the matrix tmp*/
1958 for (i=1; i<=ar; i++)
1959 {
1960 for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1961 }
1962 idDelete((ideal*)&tmp);
1963 if (k==0)
1964 {
1965 k=1;
1966 result->m[0]=NULL;
1967 }
1968 omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1969 omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1971 IDELEMS(result) = k;
1972 return (result);
1973}
1974#else
1975
1976
1977/// compute all ar-minors of the matrix a
1978/// the caller of mpRecMin
1979/// the elements of the result are not in R (if R!=NULL)
1980ideal idMinors(matrix a, int ar, ideal R)
1981{
1982
1983 const ring origR=currRing;
1984 id_Test((ideal)a, origR);
1985
1986 const int r = a->nrows;
1987 const int c = a->ncols;
1988
1989 if((ar<=0) || (ar>r) || (ar>c))
1990 {
1991 Werror("%d-th minor, matrix is %dx%d",ar,r,c);
1992 return NULL;
1993 }
1994
1995 ideal h = id_Matrix2Module(mp_Copy(a,origR),origR);
1996 long bound = sm_ExpBound(h,c,r,ar,origR);
1997 id_Delete(&h, origR);
1998
1999 ring tmpR = sm_RingChange(origR,bound);
2000
2001 matrix b = mpNew(r,c);
2002
2003 for (int i=r*c-1;i>=0;i--)
2004 if (a->m[i] != NULL)
2005 b->m[i] = prCopyR(a->m[i],origR,tmpR);
2006
2007 id_Test( (ideal)b, tmpR);
2008
2009 if (R!=NULL)
2010 {
2011 R = idrCopyR(R,origR,tmpR); // TODO: overwrites R? memory leak?
2012 //if (ar>1) // otherwise done in mpMinorToResult
2013 //{
2014 // matrix bb=(matrix)kNF(R,currRing->qideal,(ideal)b);
2015 // bb->rank=b->rank; bb->nrows=b->nrows; bb->ncols=b->ncols;
2016 // idDelete((ideal*)&b); b=bb;
2017 //}
2018 id_Test( R, tmpR);
2019 }
2020
2021 int size=binom(r,ar)*binom(c,ar);
2022 ideal result = idInit(size,1);
2023
2024 int elems = 0;
2025
2026 if(ar>1)
2027 mp_RecMin(ar-1,result,elems,b,r,c,NULL,R,tmpR);
2028 else
2029 mp_MinorToResult(result,elems,b,r,c,R,tmpR);
2030
2031 id_Test( (ideal)b, tmpR);
2032
2033 id_Delete((ideal *)&b, tmpR);
2034
2035 if (R!=NULL) id_Delete(&R,tmpR);
2036
2037 rChangeCurrRing(origR);
2038 result = idrMoveR(result,tmpR,origR);
2039 sm_KillModifiedRing(tmpR);
2040 idTest(result);
2041 return result;
2042}
2043#endif
2044
2045/*2
2046*returns TRUE if id1 is a submodule of id2
2047*/
2048BOOLEAN idIsSubModule(ideal id1,ideal id2)
2049{
2050 int i;
2051 poly p;
2052
2053 if (idIs0(id1)) return TRUE;
2054 for (i=0;i<IDELEMS(id1);i++)
2055 {
2056 if (id1->m[i] != NULL)
2057 {
2058 p = kNF(id2,currRing->qideal,id1->m[i]);
2059 if (p != NULL)
2060 {
2062 return FALSE;
2063 }
2064 }
2065 }
2066 return TRUE;
2067}
2068
2070{
2071 if ((Q!=NULL) && (!idHomIdeal(Q,NULL))) { PrintS(" Q not hom\n"); return FALSE;}
2072 if (idIs0(m)) return TRUE;
2073
2074 int cmax=-1;
2075 int i;
2076 poly p=NULL;
2077 int length=IDELEMS(m);
2078 polyset P=m->m;
2079 for (i=length-1;i>=0;i--)
2080 {
2081 p=P[i];
2082 if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
2083 }
2084 if (w != NULL)
2085 if (w->length()+1 < cmax)
2086 {
2087 // Print("length: %d - %d \n", w->length(),cmax);
2088 return FALSE;
2089 }
2090
2091 if(w!=NULL)
2093
2094 for (i=length-1;i>=0;i--)
2095 {
2096 p=P[i];
2097 if (p!=NULL)
2098 {
2099 int d=currRing->pFDeg(p,currRing);
2100 loop
2101 {
2102 pIter(p);
2103 if (p==NULL) break;
2104 if (d!=currRing->pFDeg(p,currRing))
2105 {
2106 //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
2107 if(w!=NULL)
2109 return FALSE;
2110 }
2111 }
2112 }
2113 }
2114
2115 if(w!=NULL)
2117
2118 return TRUE;
2119}
2120
2121ideal idSeries(int n,ideal M,matrix U,intvec *w)
2122{
2123 for(int i=IDELEMS(M)-1;i>=0;i--)
2124 {
2125 if(U==NULL)
2126 M->m[i]=pSeries(n,M->m[i],NULL,w);
2127 else
2128 {
2129 M->m[i]=pSeries(n,M->m[i],MATELEM(U,i+1,i+1),w);
2130 MATELEM(U,i+1,i+1)=NULL;
2131 }
2132 }
2133 if(U!=NULL)
2134 idDelete((ideal*)&U);
2135 return M;
2136}
2137
2139{
2140 int e=MATCOLS(i)*MATROWS(i);
2142 r->rank=i->rank;
2143 int j;
2144 for(j=0; j<e; j++)
2145 {
2146 r->m[j]=pDiff(i->m[j],k);
2147 }
2148 return r;
2149}
2150
2151matrix idDiffOp(ideal I, ideal J,BOOLEAN multiply)
2152{
2153 matrix r=mpNew(IDELEMS(I),IDELEMS(J));
2154 int i,j;
2155 for(i=0; i<IDELEMS(I); i++)
2156 {
2157 for(j=0; j<IDELEMS(J); j++)
2158 {
2159 MATELEM(r,i+1,j+1)=pDiffOp(I->m[i],J->m[j],multiply);
2160 }
2161 }
2162 return r;
2163}
2164
2165/*3
2166*handles for some ideal operations the ring/syzcomp management
2167*returns all syzygies (componentwise-)shifted by -syzcomp
2168*or -syzcomp-1 (in case of ideals as input)
2169static ideal idHandleIdealOp(ideal arg,int syzcomp,int isIdeal=FALSE)
2170{
2171 ring orig_ring=currRing;
2172 ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE); rChangeCurrRing(syz_ring);
2173 rSetSyzComp(length, syz_ring);
2174
2175 ideal s_temp;
2176 if (orig_ring!=syz_ring)
2177 s_temp=idrMoveR_NoSort(arg,orig_ring, syz_ring);
2178 else
2179 s_temp=arg;
2180
2181 ideal s_temp1 = kStd(s_temp,currRing->qideal,testHomog,&w,NULL,length);
2182 if (w!=NULL) delete w;
2183
2184 if (syz_ring!=orig_ring)
2185 {
2186 idDelete(&s_temp);
2187 rChangeCurrRing(orig_ring);
2188 }
2189
2190 idDelete(&temp);
2191 ideal temp1=idRingCopy(s_temp1,syz_ring);
2192
2193 if (syz_ring!=orig_ring)
2194 {
2195 rChangeCurrRing(syz_ring);
2196 idDelete(&s_temp1);
2197 rChangeCurrRing(orig_ring);
2198 rDelete(syz_ring);
2199 }
2200
2201 for (i=0;i<IDELEMS(temp1);i++)
2202 {
2203 if ((temp1->m[i]!=NULL)
2204 && (pGetComp(temp1->m[i])<=length))
2205 {
2206 pDelete(&(temp1->m[i]));
2207 }
2208 else
2209 {
2210 p_Shift(&(temp1->m[i]),-length,currRing);
2211 }
2212 }
2213 temp1->rank = rk;
2214 idSkipZeroes(temp1);
2215
2216 return temp1;
2217}
2218*/
2219
2220#ifdef HAVE_SHIFTBBA
2221ideal idModuloLP (ideal h2,ideal h1, tHomog, intvec ** w, matrix *T, GbVariant alg)
2222{
2223 intvec *wtmp=NULL;
2224 if (T!=NULL) idDelete((ideal*)T);
2225
2226 int i,k,rk,flength=0,slength,length;
2227 poly p,q;
2228
2229 if (idIs0(h2))
2230 return idFreeModule(si_max(1,h2->ncols));
2231 if (!idIs0(h1))
2232 flength = id_RankFreeModule(h1,currRing);
2233 slength = id_RankFreeModule(h2,currRing);
2234 length = si_max(flength,slength);
2235 if (length==0)
2236 {
2237 length = 1;
2238 }
2239 ideal temp = idInit(IDELEMS(h2),length+IDELEMS(h2));
2240 if ((w!=NULL)&&((*w)!=NULL))
2241 {
2242 //Print("input weights:");(*w)->show(1);PrintLn();
2243 int d;
2244 int k;
2245 wtmp=new intvec(length+IDELEMS(h2));
2246 for (i=0;i<length;i++)
2247 ((*wtmp)[i])=(**w)[i];
2248 for (i=0;i<IDELEMS(h2);i++)
2249 {
2250 poly p=h2->m[i];
2251 if (p!=NULL)
2252 {
2253 d = p_Deg(p,currRing);
2254 k= pGetComp(p);
2255 if (slength>0) k--;
2256 d +=((**w)[k]);
2257 ((*wtmp)[i+length]) = d;
2258 }
2259 }
2260 //Print("weights:");wtmp->show(1);PrintLn();
2261 }
2262 for (i=0;i<IDELEMS(h2);i++)
2263 {
2264 temp->m[i] = pCopy(h2->m[i]);
2265 q = pOne();
2266 // non multiplicative variable
2267 pSetExp(q, currRing->isLPring - currRing->LPncGenCount + i + 1, 1);
2268 p_Setm(q, currRing);
2269 pSetComp(q,i+1+length);
2270 pSetmComp(q);
2271 if(temp->m[i]!=NULL)
2272 {
2273 if (slength==0) p_Shift(&(temp->m[i]),1,currRing);
2274 p = temp->m[i];
2275 temp->m[i] = pAdd(p, q);
2276 }
2277 else
2278 temp->m[i]=q;
2279 }
2280 rk = k = IDELEMS(h2);
2281 if (!idIs0(h1))
2282 {
2283 pEnlargeSet(&(temp->m),IDELEMS(temp),IDELEMS(h1));
2284 IDELEMS(temp) += IDELEMS(h1);
2285 for (i=0;i<IDELEMS(h1);i++)
2286 {
2287 if (h1->m[i]!=NULL)
2288 {
2289 temp->m[k] = pCopy(h1->m[i]);
2290 if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
2291 k++;
2292 }
2293 }
2294 }
2295
2296 ring orig_ring=currRing;
2297 ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE);
2298 rSetSyzComp(length,syz_ring);
2299 rChangeCurrRing(syz_ring);
2300 // we can use OPT_RETURN_SB only, if syz_ring==orig_ring,
2301 // therefore we disable OPT_RETURN_SB for modulo:
2302 // (see tr. #701)
2303 //if (TEST_OPT_RETURN_SB)
2304 // rSetSyzComp(IDELEMS(h2)+length, syz_ring);
2305 //else
2306 // rSetSyzComp(length, syz_ring);
2307 ideal s_temp;
2308
2309 if (syz_ring != orig_ring)
2310 {
2311 s_temp = idrMoveR_NoSort(temp, orig_ring, syz_ring);
2312 }
2313 else
2314 {
2315 s_temp = temp;
2316 }
2317
2318 idTest(s_temp);
2319 unsigned save_opt,save_opt2;
2320 SI_SAVE_OPT1(save_opt);
2321 SI_SAVE_OPT2(save_opt2);
2324 ideal s_temp1 = idGroebner(s_temp,length,alg);
2325 SI_RESTORE_OPT1(save_opt);
2326 SI_RESTORE_OPT2(save_opt2);
2327
2328 //if (wtmp!=NULL) Print("output weights:");wtmp->show(1);PrintLn();
2329 if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
2330 {
2331 delete *w;
2332 *w=new intvec(IDELEMS(h2));
2333 for (i=0;i<IDELEMS(h2);i++)
2334 ((**w)[i])=(*wtmp)[i+length];
2335 }
2336 if (wtmp!=NULL) delete wtmp;
2337
2338 if (T==NULL)
2339 {
2340 for (i=0;i<IDELEMS(s_temp1);i++)
2341 {
2342 if (s_temp1->m[i]!=NULL)
2343 {
2344 if (((int)pGetComp(s_temp1->m[i]))<=length)
2345 {
2346 p_Delete(&(s_temp1->m[i]),currRing);
2347 }
2348 else
2349 {
2350 p_Shift(&(s_temp1->m[i]),-length,currRing);
2351 }
2352 }
2353 }
2354 }
2355 else
2356 {
2357 *T=mpNew(IDELEMS(s_temp1),IDELEMS(h2));
2358 for (i=0;i<IDELEMS(s_temp1);i++)
2359 {
2360 if (s_temp1->m[i]!=NULL)
2361 {
2362 if (((int)pGetComp(s_temp1->m[i]))<=length)
2363 {
2364 do
2365 {
2366 p_LmDelete(&(s_temp1->m[i]),currRing);
2367 } while((int)pGetComp(s_temp1->m[i])<=length);
2368 poly q = prMoveR( s_temp1->m[i], syz_ring,orig_ring);
2369 s_temp1->m[i] = NULL;
2370 if (q!=NULL)
2371 {
2372 q=pReverse(q);
2373 do
2374 {
2375 poly p = q;
2376 long t=pGetComp(p);
2377 pIter(q);
2378 pNext(p) = NULL;
2379 pSetComp(p,0);
2380 pSetmComp(p);
2381 pTest(p);
2382 MATELEM(*T,(int)t-length,i) = pAdd(MATELEM(*T,(int)t-length,i),p);
2383 } while (q != NULL);
2384 }
2385 }
2386 else
2387 {
2388 p_Shift(&(s_temp1->m[i]),-length,currRing);
2389 }
2390 }
2391 }
2392 }
2393 s_temp1->rank = rk;
2394 idSkipZeroes(s_temp1);
2395
2396 if (syz_ring!=orig_ring)
2397 {
2398 rChangeCurrRing(orig_ring);
2399 s_temp1 = idrMoveR_NoSort(s_temp1, syz_ring, orig_ring);
2400 rDelete(syz_ring);
2401 // Hmm ... here seems to be a memory leak
2402 // However, simply deleting it causes memory trouble
2403 // idDelete(&s_temp);
2404 }
2405 idTest(s_temp1);
2406 return s_temp1;
2407}
2408#endif
2409
2410/*2
2411* represents (h1+h2)/h2=h1/(h1 intersect h2)
2412*/
2413//ideal idModulo (ideal h2,ideal h1)
2414ideal idModulo (ideal h2,ideal h1, tHomog hom, intvec ** w, matrix *T, GbVariant alg)
2415{
2416#ifdef HAVE_SHIFTBBA
2417 if (rIsLPRing(currRing))
2418 return idModuloLP(h2,h1,hom,w,T,alg);
2419#endif
2420 intvec *wtmp=NULL;
2421 if (T!=NULL) idDelete((ideal*)T);
2422
2423 int i,flength=0,slength,length;
2424
2425 if (idIs0(h2))
2426 return idFreeModule(si_max(1,h2->ncols));
2427 if (!idIs0(h1))
2428 flength = id_RankFreeModule(h1,currRing);
2429 slength = id_RankFreeModule(h2,currRing);
2430 length = si_max(flength,slength);
2431 BOOLEAN inputIsIdeal=FALSE;
2432 if (length==0)
2433 {
2434 length = 1;
2435 inputIsIdeal=TRUE;
2436 }
2437 if ((w!=NULL)&&((*w)!=NULL))
2438 {
2439 //Print("input weights:");(*w)->show(1);PrintLn();
2440 int d;
2441 int k;
2442 wtmp=new intvec(length+IDELEMS(h2));
2443 for (i=0;i<length;i++)
2444 ((*wtmp)[i])=(**w)[i];
2445 for (i=0;i<IDELEMS(h2);i++)
2446 {
2447 poly p=h2->m[i];
2448 if (p!=NULL)
2449 {
2450 d = p_Deg(p,currRing);
2451 k= pGetComp(p);
2452 if (slength>0) k--;
2453 d +=((**w)[k]);
2454 ((*wtmp)[i+length]) = d;
2455 }
2456 }
2457 //Print("weights:");wtmp->show(1);PrintLn();
2458 }
2459 ideal s_temp1;
2460 ring orig_ring=currRing;
2461 ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE);
2462 rSetSyzComp(length,syz_ring);
2463 {
2464 rChangeCurrRing(syz_ring);
2465 ideal s1,s2;
2466
2467 if (syz_ring != orig_ring)
2468 {
2469 s1 = idrCopyR_NoSort(h1, orig_ring, syz_ring);
2470 s2 = idrCopyR_NoSort(h2, orig_ring, syz_ring);
2471 }
2472 else
2473 {
2474 s1=idCopy(h1);
2475 s2=idCopy(h2);
2476 }
2477
2478 unsigned save_opt,save_opt2;
2479 SI_SAVE_OPT1(save_opt);
2480 SI_SAVE_OPT2(save_opt2);
2481 if (T==NULL) si_opt_1 |= Sy_bit(OPT_REDTAIL);
2483 s_temp1 = idPrepare(s2,s1,testHomog,length,w,alg);
2484 SI_RESTORE_OPT1(save_opt);
2485 SI_RESTORE_OPT2(save_opt2);
2486 }
2487
2488 //if (wtmp!=NULL) Print("output weights:");wtmp->show(1);PrintLn();
2489 if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
2490 {
2491 delete *w;
2492 *w=new intvec(IDELEMS(h2));
2493 for (i=0;i<IDELEMS(h2);i++)
2494 ((**w)[i])=(*wtmp)[i+length];
2495 }
2496 if (wtmp!=NULL) delete wtmp;
2497
2498 ideal result=idInit(IDELEMS(s_temp1),IDELEMS(h2));
2499 s_temp1=idExtractG_T_S(s_temp1,T,&result,length,IDELEMS(h2),inputIsIdeal,orig_ring,syz_ring);
2500
2501 idDelete(&s_temp1);
2502 if (syz_ring!=orig_ring)
2503 {
2504 rDelete(syz_ring);
2505 }
2506 idTest(h2);
2507 idTest(h1);
2508 idTest(result);
2509 if (T!=NULL) idTest((ideal)*T);
2510 return result;
2511}
2512
2513/*
2514*computes module-weights for liftings of homogeneous modules
2515*/
2516#if 0
2517static intvec * idMWLift(ideal mod,intvec * weights)
2518{
2519 if (idIs0(mod)) return new intvec(2);
2520 int i=IDELEMS(mod);
2521 while ((i>0) && (mod->m[i-1]==NULL)) i--;
2522 intvec *result = new intvec(i+1);
2523 while (i>0)
2524 {
2525 (*result)[i]=currRing->pFDeg(mod->m[i],currRing)+(*weights)[pGetComp(mod->m[i])];
2526 }
2527 return result;
2528}
2529#endif
2530
2531/*2
2532*sorts the kbase for idCoef* in a special way (lexicographically
2533*with x_max,...,x_1)
2534*/
2535ideal idCreateSpecialKbase(ideal kBase,intvec ** convert)
2536{
2537 int i;
2538 ideal result;
2539
2540 if (idIs0(kBase)) return NULL;
2541 result = idInit(IDELEMS(kBase),kBase->rank);
2542 *convert = idSort(kBase,FALSE);
2543 for (i=0;i<(*convert)->length();i++)
2544 {
2545 result->m[i] = pCopy(kBase->m[(**convert)[i]-1]);
2546 }
2547 return result;
2548}
2549
2550/*2
2551*returns the index of a given monom in the list of the special kbase
2552*/
2553int idIndexOfKBase(poly monom, ideal kbase)
2554{
2555 int j=IDELEMS(kbase);
2556
2557 while ((j>0) && (kbase->m[j-1]==NULL)) j--;
2558 if (j==0) return -1;
2559 int i=(currRing->N);
2560 while (i>0)
2561 {
2562 loop
2563 {
2564 if (pGetExp(monom,i)>pGetExp(kbase->m[j-1],i)) return -1;
2565 if (pGetExp(monom,i)==pGetExp(kbase->m[j-1],i)) break;
2566 j--;
2567 if (j==0) return -1;
2568 }
2569 if (i==1)
2570 {
2571 while(j>0)
2572 {
2573 if (pGetComp(monom)==pGetComp(kbase->m[j-1])) return j-1;
2574 if (pGetComp(monom)>pGetComp(kbase->m[j-1])) return -1;
2575 j--;
2576 }
2577 }
2578 i--;
2579 }
2580 return -1;
2581}
2582
2583/*2
2584*decomposes the monom in a part of coefficients described by the
2585*complement of how and a monom in variables occurring in how, the
2586*index of which in kbase is returned as integer pos (-1 if it don't
2587*exists)
2588*/
2589poly idDecompose(poly monom, poly how, ideal kbase, int * pos)
2590{
2591 int i;
2592 poly coeff=pOne(), base=pOne();
2593
2594 for (i=1;i<=(currRing->N);i++)
2595 {
2596 if (pGetExp(how,i)>0)
2597 {
2598 pSetExp(base,i,pGetExp(monom,i));
2599 }
2600 else
2601 {
2602 pSetExp(coeff,i,pGetExp(monom,i));
2603 }
2604 }
2605 pSetComp(base,pGetComp(monom));
2606 pSetm(base);
2607 pSetCoeff(coeff,nCopy(pGetCoeff(monom)));
2608 pSetm(coeff);
2609 *pos = idIndexOfKBase(base,kbase);
2610 if (*pos<0)
2611 p_Delete(&coeff,currRing);
2612 p_Delete(&base,currRing);
2613 return coeff;
2614}
2615
2616/*2
2617*returns a matrix A of coefficients with kbase*A=arg
2618*if all monomials in variables of how occur in kbase
2619*the other are deleted
2620*/
2621matrix idCoeffOfKBase(ideal arg, ideal kbase, poly how)
2622{
2623 matrix result;
2624 ideal tempKbase;
2625 poly p,q;
2626 intvec * convert;
2627 int i=IDELEMS(kbase),j=IDELEMS(arg),k,pos;
2628#if 0
2629 while ((i>0) && (kbase->m[i-1]==NULL)) i--;
2630 if (idIs0(arg))
2631 return mpNew(i,1);
2632 while ((j>0) && (arg->m[j-1]==NULL)) j--;
2633 result = mpNew(i,j);
2634#else
2635 result = mpNew(i, j);
2636 while ((j>0) && (arg->m[j-1]==NULL)) j--;
2637#endif
2638
2639 tempKbase = idCreateSpecialKbase(kbase,&convert);
2640 for (k=0;k<j;k++)
2641 {
2642 p = arg->m[k];
2643 while (p!=NULL)
2644 {
2645 q = idDecompose(p,how,tempKbase,&pos);
2646 if (pos>=0)
2647 {
2648 MATELEM(result,(*convert)[pos],k+1) =
2649 pAdd(MATELEM(result,(*convert)[pos],k+1),q);
2650 }
2651 else
2652 p_Delete(&q,currRing);
2653 pIter(p);
2654 }
2655 }
2656 idDelete(&tempKbase);
2657 return result;
2658}
2659
2660static void idDeleteComps(ideal arg,int* red_comp,int del)
2661// red_comp is an array [0..args->rank]
2662{
2663 int i,j;
2664 poly p;
2665
2666 for (i=IDELEMS(arg)-1;i>=0;i--)
2667 {
2668 p = arg->m[i];
2669 while (p!=NULL)
2670 {
2671 j = pGetComp(p);
2672 if (red_comp[j]!=j)
2673 {
2674 pSetComp(p,red_comp[j]);
2675 pSetmComp(p);
2676 }
2677 pIter(p);
2678 }
2679 }
2680 (arg->rank) -= del;
2681}
2682
2683/*2
2684* returns the presentation of an isomorphic, minimally
2685* embedded module (arg represents the quotient!)
2686*/
2687ideal idMinEmbedding(ideal arg,BOOLEAN inPlace, intvec **w)
2688{
2689 if (idIs0(arg)) return idInit(1,arg->rank);
2690 int i,next_gen,next_comp;
2691 ideal res=arg;
2692 if (!inPlace) res = idCopy(arg);
2694 int *red_comp=(int*)omAlloc((res->rank+1)*sizeof(int));
2695 for (i=res->rank;i>=0;i--) red_comp[i]=i;
2696
2697 int del=0;
2698 loop
2699 {
2700 next_gen = id_ReadOutPivot(res, &next_comp, currRing);
2701 if (next_gen<0) break;
2702 del++;
2703 syGaussForOne(res,next_gen,next_comp,0,IDELEMS(res));
2704 for(i=next_comp+1;i<=arg->rank;i++) red_comp[i]--;
2705 if ((w !=NULL)&&(*w!=NULL))
2706 {
2707 for(i=next_comp;i<(*w)->length();i++) (**w)[i-1]=(**w)[i];
2708 }
2709 }
2710
2711 idDeleteComps(res,red_comp,del);
2713 omFree(red_comp);
2714
2715 if ((w !=NULL)&&(*w!=NULL) &&(del>0))
2716 {
2717 int nl=si_max((*w)->length()-del,1);
2718 intvec *wtmp=new intvec(nl);
2719 for(i=0;i<res->rank;i++) (*wtmp)[i]=(**w)[i];
2720 delete *w;
2721 *w=wtmp;
2722 }
2723 return res;
2724}
2725
2726#include "polys/clapsing.h"
2727
2728#if 0
2729poly id_GCD(poly f, poly g, const ring r)
2730{
2731 ring save_r=currRing;
2732 rChangeCurrRing(r);
2733 ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2734 intvec *w = NULL;
2735 ideal S=idSyzygies(I,testHomog,&w);
2736 if (w!=NULL) delete w;
2737 poly gg=pTakeOutComp(&(S->m[0]),2);
2738 idDelete(&S);
2739 poly gcd_p=singclap_pdivide(f,gg,r);
2740 p_Delete(&gg,r);
2741 rChangeCurrRing(save_r);
2742 return gcd_p;
2743}
2744#else
2745poly id_GCD(poly f, poly g, const ring r)
2746{
2747 ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2748 intvec *w = NULL;
2749
2750 ring save_r = currRing;
2751 rChangeCurrRing(r);
2752 ideal S=idSyzygies(I,testHomog,&w);
2753 rChangeCurrRing(save_r);
2754
2755 if (w!=NULL) delete w;
2756 poly gg=p_TakeOutComp(&(S->m[0]), 2, r);
2757 id_Delete(&S, r);
2758 poly gcd_p=singclap_pdivide(f,gg, r);
2759 p_Delete(&gg, r);
2760
2761 return gcd_p;
2762}
2763#endif
2764
2765#if 0
2766/*2
2767* xx,q: arrays of length 0..rl-1
2768* xx[i]: SB mod q[i]
2769* assume: char=0
2770* assume: q[i]!=0
2771* destroys xx
2772*/
2773ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring R)
2774{
2775 int cnt=IDELEMS(xx[0])*xx[0]->nrows;
2776 ideal result=idInit(cnt,xx[0]->rank);
2777 result->nrows=xx[0]->nrows; // for lifting matrices
2778 result->ncols=xx[0]->ncols; // for lifting matrices
2779 int i,j;
2780 poly r,h,hh,res_p;
2781 number *x=(number *)omAlloc(rl*sizeof(number));
2782 for(i=cnt-1;i>=0;i--)
2783 {
2784 res_p=NULL;
2785 loop
2786 {
2787 r=NULL;
2788 for(j=rl-1;j>=0;j--)
2789 {
2790 h=xx[j]->m[i];
2791 if ((h!=NULL)
2792 &&((r==NULL)||(p_LmCmp(r,h,R)==-1)))
2793 r=h;
2794 }
2795 if (r==NULL) break;
2796 h=p_Head(r, R);
2797 for(j=rl-1;j>=0;j--)
2798 {
2799 hh=xx[j]->m[i];
2800 if ((hh!=NULL) && (p_LmCmp(r,hh, R)==0))
2801 {
2802 x[j]=p_GetCoeff(hh, R);
2803 hh=p_LmFreeAndNext(hh, R);
2804 xx[j]->m[i]=hh;
2805 }
2806 else
2807 x[j]=n_Init(0, R->cf); // is R->cf really n_Q???, yes!
2808 }
2809
2810 number n=n_ChineseRemainder(x,q,rl, R->cf);
2811
2812 for(j=rl-1;j>=0;j--)
2813 {
2814 x[j]=NULL; // nlInit(0...) takes no memory
2815 }
2816 if (n_IsZero(n, R->cf)) p_Delete(&h, R);
2817 else
2818 {
2819 p_SetCoeff(h,n, R);
2820 //Print("new mon:");pWrite(h);
2821 res_p=p_Add_q(res_p, h, R);
2822 }
2823 }
2824 result->m[i]=res_p;
2825 }
2826 omFree(x);
2827 for(i=rl-1;i>=0;i--) id_Delete(&(xx[i]), R);
2828 omFree(xx);
2829 return result;
2830}
2831#endif
2832/* currently unused:
2833ideal idChineseRemainder(ideal *xx, intvec *iv)
2834{
2835 int rl=iv->length();
2836 number *q=(number *)omAlloc(rl*sizeof(number));
2837 int i;
2838 for(i=0; i<rl; i++)
2839 {
2840 q[i]=nInit((*iv)[i]);
2841 }
2842 return idChineseRemainder(xx,q,rl);
2843}
2844*/
2845/*
2846 * lift ideal with coeffs over Z (mod N) to Q via Farey
2847 */
2848ideal id_Farey(ideal x, number N, const ring r)
2849{
2850 int cnt=IDELEMS(x)*x->nrows;
2851 ideal result=idInit(cnt,x->rank);
2852 result->nrows=x->nrows; // for lifting matrices
2853 result->ncols=x->ncols; // for lifting matrices
2854
2855 int i;
2856 for(i=cnt-1;i>=0;i--)
2857 {
2858 result->m[i]=p_Farey(x->m[i],N,r);
2859 }
2860 return result;
2861}
2862
2863
2864
2865
2866// uses glabl vars via pSetModDeg
2867/*
2868BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
2869{
2870 if ((Q!=NULL) && (!idHomIdeal(Q,NULL))) { PrintS(" Q not hom\n"); return FALSE;}
2871 if (idIs0(m)) return TRUE;
2872
2873 int cmax=-1;
2874 int i;
2875 poly p=NULL;
2876 int length=IDELEMS(m);
2877 poly* P=m->m;
2878 for (i=length-1;i>=0;i--)
2879 {
2880 p=P[i];
2881 if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
2882 }
2883 if (w != NULL)
2884 if (w->length()+1 < cmax)
2885 {
2886 // Print("length: %d - %d \n", w->length(),cmax);
2887 return FALSE;
2888 }
2889
2890 if(w!=NULL)
2891 p_SetModDeg(w, currRing);
2892
2893 for (i=length-1;i>=0;i--)
2894 {
2895 p=P[i];
2896 poly q=p;
2897 if (p!=NULL)
2898 {
2899 int d=p_FDeg(p,currRing);
2900 loop
2901 {
2902 pIter(p);
2903 if (p==NULL) break;
2904 if (d!=p_FDeg(p,currRing))
2905 {
2906 //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
2907 if(w!=NULL)
2908 p_SetModDeg(NULL, currRing);
2909 return FALSE;
2910 }
2911 }
2912 }
2913 }
2914
2915 if(w!=NULL)
2916 p_SetModDeg(NULL, currRing);
2917
2918 return TRUE;
2919}
2920*/
2921
2922/// keeps the first k (>= 1) entries of the given ideal
2923/// (Note that the kept polynomials may be zero.)
2924void idKeepFirstK(ideal id, const int k)
2925{
2926 for (int i = IDELEMS(id)-1; i >= k; i--)
2927 {
2928 if (id->m[i] != NULL) pDelete(&id->m[i]);
2929 }
2930 int kk=k;
2931 if (k==0) kk=1; /* ideals must have at least one element(0)*/
2932 pEnlargeSet(&(id->m), IDELEMS(id), kk-IDELEMS(id));
2933 IDELEMS(id) = kk;
2934}
2935
2936typedef struct
2937{
2938 poly p;
2940} poly_sort;
2941
2942int pCompare_qsort(const void *a, const void *b)
2943{
2944 return (p_Compare(((poly_sort *)a)->p, ((poly_sort *)b)->p,currRing));
2945}
2946
2947void idSort_qsort(poly_sort *id_sort, int idsize)
2948{
2949 qsort(id_sort, idsize, sizeof(poly_sort), pCompare_qsort);
2950}
2951
2952/*2
2953* ideal id = (id[i])
2954* if id[i] = id[j] then id[j] is deleted for j > i
2955*/
2956void idDelEquals(ideal id)
2957{
2958 int idsize = IDELEMS(id);
2959 poly_sort *id_sort = (poly_sort *)omAlloc0(idsize*sizeof(poly_sort));
2960 for (int i = 0; i < idsize; i++)
2961 {
2962 id_sort[i].p = id->m[i];
2963 id_sort[i].index = i;
2964 }
2965 idSort_qsort(id_sort, idsize);
2966 int index, index_i, index_j;
2967 int i = 0;
2968 for (int j = 1; j < idsize; j++)
2969 {
2970 if (id_sort[i].p != NULL && pEqualPolys(id_sort[i].p, id_sort[j].p))
2971 {
2972 index_i = id_sort[i].index;
2973 index_j = id_sort[j].index;
2974 if (index_j > index_i)
2975 {
2976 index = index_j;
2977 }
2978 else
2979 {
2980 index = index_i;
2981 i = j;
2982 }
2983 pDelete(&id->m[index]);
2984 }
2985 else
2986 {
2987 i = j;
2988 }
2989 }
2990 omFreeSize((ADDRESS)(id_sort), idsize*sizeof(poly_sort));
2991}
2992
2994
2996{
2997 BOOLEAN b = FALSE; // set b to TRUE, if spoly was changed,
2998 // let it remain FALSE otherwise
2999 if (strat->P.t_p==NULL)
3000 {
3001 poly p=strat->P.p;
3002
3003 // iterate over all terms of p and
3004 // compute the minimum mm of all exponent vectors
3005 int *mm=(int*)omAlloc((1+rVar(currRing))*sizeof(int));
3006 int *m0=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
3007 p_GetExpV(p,mm,currRing);
3008 bool nonTrivialSaturationToBeDone=true;
3009 for (p=pNext(p); p!=NULL; pIter(p))
3010 {
3011 nonTrivialSaturationToBeDone=false;
3012 p_GetExpV(p,m0,currRing);
3013 for (int i=rVar(currRing); i>0; i--)
3014 {
3016 {
3017 mm[i]=si_min(mm[i],m0[i]);
3018 if (mm[i]>0) nonTrivialSaturationToBeDone=true;
3019 }
3020 else mm[i]=0;
3021 }
3022 // abort if the minimum is zero in each component
3023 if (!nonTrivialSaturationToBeDone) break;
3024 }
3025 if (nonTrivialSaturationToBeDone)
3026 {
3027 // std::cout << "simplifying!" << std::endl;
3028 if (TEST_OPT_PROT) { PrintS("S"); mflush(); }
3029 p=p_Copy(strat->P.p,currRing);
3030 //pWrite(p);
3031 // for (int i=rVar(currRing); i>0; i--)
3032 // if (mm[i]!=0) Print("x_%d:%d ",i,mm[i]);
3033 //PrintLn();
3034 strat->P.Init(currRing);
3035 //memset(&strat->P,0,sizeof(strat->P));
3036 strat->P.tailRing = strat->tailRing;
3037 strat->P.p=p;
3038 while(p!=NULL)
3039 {
3040 for (int i=rVar(currRing); i>0; i--)
3041 {
3042 p_SubExp(p,i,mm[i],currRing);
3043 }
3044 p_Setm(p,currRing);
3045 pIter(p);
3046 }
3047 b = TRUE;
3048 }
3049 omFree(mm);
3050 omFree(m0);
3051 }
3052 else
3053 {
3054 poly p=strat->P.t_p;
3055
3056 // iterate over all terms of p and
3057 // compute the minimum mm of all exponent vectors
3058 int *mm=(int*)omAlloc((1+rVar(currRing))*sizeof(int));
3059 int *m0=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
3060 p_GetExpV(p,mm,strat->tailRing);
3061 bool nonTrivialSaturationToBeDone=true;
3062 for (p = pNext(p); p!=NULL; pIter(p))
3063 {
3064 nonTrivialSaturationToBeDone=false;
3065 p_GetExpV(p,m0,strat->tailRing);
3066 for(int i=rVar(currRing); i>0; i--)
3067 {
3069 {
3070 mm[i]=si_min(mm[i],m0[i]);
3071 if (mm[i]>0) nonTrivialSaturationToBeDone = true;
3072 }
3073 else mm[i]=0;
3074 }
3075 // abort if the minimum is zero in each component
3076 if (!nonTrivialSaturationToBeDone) break;
3077 }
3078 if (nonTrivialSaturationToBeDone)
3079 {
3080 if (TEST_OPT_PROT) { PrintS("S"); mflush(); }
3081 p=p_Copy(strat->P.t_p,strat->tailRing);
3082 //p_Write(p,strat->tailRing);
3083 // for (int i=rVar(currRing); i>0; i--)
3084 // if (mm[i]!=0) Print("x_%d:%d ",i,mm[i]);
3085 //PrintLn();
3086 strat->P.Init(currRing);
3087 //memset(&strat->P,0,sizeof(strat->P));
3088 strat->P.tailRing = strat->tailRing;
3089 strat->P.t_p=p;
3090 while(p!=NULL)
3091 {
3092 for(int i=rVar(currRing); i>0; i--)
3093 {
3094 p_SubExp(p,i,mm[i],strat->tailRing);
3095 }
3096 p_Setm(p,strat->tailRing);
3097 pIter(p);
3098 }
3099 strat->P.GetP();
3100 b = TRUE;
3101 }
3102 omFree(mm);
3103 omFree(m0);
3104 }
3105 return b; // return TRUE if sp was changed, FALSE if not
3106}
3107
3108ideal id_Satstd(const ideal I, ideal J, const ring r)
3109{
3110 ring save=currRing;
3111 if (currRing!=r) rChangeCurrRing(r);
3112 idSkipZeroes(J);
3113 id_satstdSaturatingVariables=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
3114 int k=IDELEMS(J);
3115 if (k>1)
3116 {
3117 for (int i=0; i<k; i++)
3118 {
3119 poly x = J->m[i];
3120 int li = p_Var(x,r);
3121 if (li>0)
3123 else
3124 {
3125 if (currRing!=save) rChangeCurrRing(save);
3126 WerrorS("ideal generators must be variables");
3127 return NULL;
3128 }
3129 }
3130 }
3131 else
3132 {
3133 poly x = J->m[0];
3134 for (int i=1; i<=r->N; i++)
3135 {
3136 int li = p_GetExp(x,i,r);
3137 if (li==1)
3139 else if (li>1)
3140 {
3141 if (currRing!=save) rChangeCurrRing(save);
3142 Werror("exponent(x(%d)^%d) must be 0 or 1",i,li);
3143 return NULL;
3144 }
3145 }
3146 }
3147 ideal res=kStd(I,r->qideal,testHomog,NULL,NULL,0,0,NULL,id_sat_vars_sp);
3150 if (currRing!=save) rChangeCurrRing(save);
3151 return res;
3152}
3153
3154GbVariant syGetAlgorithm(char *n, const ring r, const ideal /*M*/)
3155{
3156 GbVariant alg=GbDefault;
3157 if (strcmp(n,"default")==0) alg=GbDefault;
3158 else if (strcmp(n,"slimgb")==0) alg=GbSlimgb;
3159 else if (strcmp(n,"std")==0) alg=GbStd;
3160 else if (strcmp(n,"sba")==0) alg=GbSba;
3161 else if (strcmp(n,"singmatic")==0) alg=GbSingmatic;
3162 else if (strcmp(n,"groebner")==0) alg=GbGroebner;
3163 else if (strcmp(n,"modstd")==0) alg=GbModstd;
3164 else if (strcmp(n,"ffmod")==0) alg=GbFfmod;
3165 else if (strcmp(n,"nfmod")==0) alg=GbNfmod;
3166 else if (strcmp(n,"std:sat")==0) alg=GbStdSat;
3167 else Warn(">>%s<< is an unknown algorithm",n);
3168
3169 if (alg==GbSlimgb) // test conditions for slimgb
3170 {
3171 if(rHasGlobalOrdering(r)
3172 &&(!rIsNCRing(r))
3173 &&(r->qideal==NULL)
3174 &&(!rField_is_Ring(r)))
3175 {
3176 return GbSlimgb;
3177 }
3178 if (TEST_OPT_PROT)
3179 WarnS("requires: coef:field, commutative, global ordering, not qring");
3180 }
3181 else if (alg==GbSba) // cond. for sba
3182 {
3183 if(rField_is_Domain(r)
3184 &&(!rIsNCRing(r))
3185 &&(rHasGlobalOrdering(r)))
3186 {
3187 return GbSba;
3188 }
3189 if (TEST_OPT_PROT)
3190 WarnS("requires: coef:domain, commutative, global ordering");
3191 }
3192 else if (alg==GbGroebner) // cond. for groebner
3193 {
3194 return GbGroebner;
3195 }
3196 else if(alg==GbModstd) // cond for modstd: Q or Q(a)
3197 {
3198 if(ggetid("modStd")==NULL)
3199 {
3200 WarnS(">>modStd<< not found");
3201 }
3202 else if(rField_is_Q(r)
3203 &&(!rIsNCRing(r))
3204 &&(rHasGlobalOrdering(r)))
3205 {
3206 return GbModstd;
3207 }
3208 if (TEST_OPT_PROT)
3209 WarnS("requires: coef:QQ, commutative, global ordering");
3210 }
3211 else if(alg==GbStdSat) // cond for std:sat: 2 blocks of variables
3212 {
3213 if(ggetid("satstd")==NULL)
3214 {
3215 WarnS(">>satstd<< not found");
3216 }
3217 else
3218 {
3219 return GbStdSat;
3220 }
3221 }
3222
3223 return GbStd; // no conditions for std
3224}
3225//----------------------------------------------------------------------------
3226// GB-algorithms and their pre-conditions
3227// std slimgb sba singmatic modstd ffmod nfmod groebner
3228// + + + - + - - + coeffs: QQ
3229// + + + + - - - + coeffs: ZZ/p
3230// + + + - ? - + + coeffs: K[a]/f
3231// + + + - ? + - + coeffs: K(a)
3232// + - + - - - - + coeffs: domain, not field
3233// + - - - - - - + coeffs: zero-divisors
3234// + + + + - ? ? + also for modules: C
3235// + + - + - ? ? + also for modules: all orderings
3236// + + - - - - - + exterior algebra
3237// + + - - - - - + G-algebra
3238// + + + + + + + + degree ordering
3239// + - + + + + + + non-degree ordering
3240// - - - + + + + + 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:4082
int p
Definition: cfModGcd.cc:4078
g
Definition: cfModGcd.cc:4090
CanonicalForm b
Definition: cfModGcd.cc:4103
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
Definition: intvec.h:23
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
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
void * data
Definition: subexpr.h:88
Coefficient rings, fields and other domains suitable for Singular polynomials.
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:461
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:535
#define Print
Definition: emacs.cc:80
#define Warn
Definition: emacs.cc:77
#define WarnS
Definition: emacs.cc:78
return result
Definition: facAbsBiFact.cc:75
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
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define STATIC_VAR
Definition: globaldefs.h:7
@ IDEAL_CMD
Definition: grammar.cc:284
@ MODUL_CMD
Definition: grammar.cc:287
GbVariant syGetAlgorithm(char *n, const ring r, const ideal)
Definition: ideals.cc:3154
int index
Definition: ideals.cc:2939
static void idPrepareStd(ideal s_temp, int k)
Definition: ideals.cc:1041
matrix idCoeffOfKBase(ideal arg, ideal kbase, poly how)
Definition: ideals.cc:2621
void idLiftW(ideal P, ideal Q, int n, matrix &T, ideal &R, int *w)
Definition: ideals.cc:1324
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
poly p
Definition: ideals.cc:2938
matrix idDiff(matrix i, int k)
Definition: ideals.cc:2138
BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
Definition: ideals.cc:2069
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:2956
int pCompare_qsort(const void *a, const void *b)
Definition: ideals.cc:2942
ideal idQuot(ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN resultIsIdeal)
Definition: ideals.cc:1494
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:1980
BOOLEAN idIsSubModule(ideal id1, ideal id2)
Definition: ideals.cc:2048
ideal idSeries(int n, ideal M, matrix U, intvec *w)
Definition: ideals.cc:2121
static ideal idGroebner(ideal temp, int syzComp, GbVariant alg, intvec *hilb=NULL, intvec *w=NULL, tHomog hom=testHomog)
Definition: ideals.cc:201
ideal idCreateSpecialKbase(ideal kBase, intvec **convert)
Definition: ideals.cc:2535
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:2745
int idIndexOfKBase(poly monom, ideal kbase)
Definition: ideals.cc:2553
poly idDecompose(poly monom, poly how, ideal kbase, int *pos)
Definition: ideals.cc:2589
matrix idDiffOp(ideal I, ideal J, BOOLEAN multiply)
Definition: ideals.cc:2151
void idSort_qsort(poly_sort *id_sort, int idsize)
Definition: ideals.cc:2947
static ideal idInitializeQuot(ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN *addOnlyOne, int *kkmax)
Definition: ideals.cc:1389
ideal idElimination(ideal h1, poly delVar, intvec *hilb, GbVariant alg)
Definition: ideals.cc:1593
static ideal idSectWithElim(ideal h1, ideal h2, GbVariant alg)
Definition: ideals.cc:133
ideal idMinBase(ideal h1)
Definition: ideals.cc:51
ideal idSect(ideal h1, ideal h2, GbVariant alg)
Definition: ideals.cc:316
ideal idMultSect(resolvente arg, int length, GbVariant alg)
Definition: ideals.cc:472
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:2924
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:2993
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:2660
ideal idModulo(ideal h2, ideal h1, tHomog hom, intvec **w, matrix *T, GbVariant alg)
Definition: ideals.cc:2414
ideal id_Farey(ideal x, number N, const ring r)
Definition: ideals.cc:2848
ideal id_Satstd(const ideal I, ideal J, const ring r)
Definition: ideals.cc:3108
ideal idModuloLP(ideal h2, ideal h1, tHomog, intvec **w, matrix *T, GbVariant alg)
Definition: ideals.cc:2221
static BOOLEAN id_sat_vars_sp(kStrategy strat)
Definition: ideals.cc:2995
ideal idMinEmbedding(ideal arg, BOOLEAN inPlace, intvec **w)
Definition: ideals.cc:2687
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)
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:184
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:581
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:701
void * iiCallLibProc1(const char *n, void *arg, int arg_type, BOOLEAN &err)
Definition: iplib.cc:627
void ipPrint_MA0(matrix m, const char *name)
Definition: ipprint.cc:57
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:3496
ideal kMin_std(ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb, int syzComp, int reduced)
Definition: kstd1.cc:3034
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3182
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:2632
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:2447
@ 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)
Definition: old.gring.cc:2576
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
#define MATROWS(i)
Definition: matpol.h:26
#define MATCOLS(i)
Definition: matpol.h:27
#define assume(x)
Definition: mod2.h:389
#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 nCopy(n)
Definition: numbers.h:15
#define omStrDup(s)
Definition: omAllocDecl.h:263
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omalloc(size)
Definition: omAllocDecl.h:228
#define omFree(addr)
Definition: omAllocDecl.h:261
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
#define omMemDup(s)
Definition: omAllocDecl.h:264
#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 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:113
#define TEST_V_INTERSECT_ELIM
Definition: options.h:145
#define TEST_V_INTERSECT_SYZ
Definition: options.h:146
#define TEST_OPT_NOTREGULARITY
Definition: options.h:121
#define TEST_OPT_PROT
Definition: options.h:104
#define V_IDLIFT
Definition: options.h:63
#define V_IDELIM
Definition: options.h:71
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
poly p_DivideM(poly a, poly b, const ring r)
Definition: p_polys.cc:1578
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:705
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition: p_polys.cc:4706
int p_Compare(const poly a, const poly b, const ring R)
Definition: p_polys.cc:4849
long p_DegW(poly p, const int *w, const ring R)
Definition: p_polys.cc:690
void p_SetModDeg(intvec *w, ring r)
Definition: p_polys.cc:3673
int p_Var(poly m, const ring r)
Definition: p_polys.cc:4656
poly p_One(const ring r)
Definition: p_polys.cc:1313
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3696
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:587
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1105
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:934
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:721
static long p_SubExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:611
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:486
static long p_MinComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:311
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:231
static poly p_Copy_noCheck(poly p, const ring r)
returns a copy of p (without any additional testing)
Definition: p_polys.h:834
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:410
static poly pReverse(poly p)
Definition: p_polys.h:333
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition: p_polys.h:858
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1578
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:467
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:899
static void p_GetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1518
static poly p_LmFreeAndNext(poly p, ring)
Definition: p_polys.h:709
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:844
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 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:3450
ring rAssure_SyzComp(const ring r, BOOLEAN complete)
Definition: ring.cc:4435
BOOLEAN nc_rComplete(const ring src, ring dest, bool bSetupQuotient)
Definition: ring.cc:5685
ring rAssure_SyzOrder(const ring r, BOOLEAN complete)
Definition: ring.cc:4430
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition: ring.cc:1421
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:450
void rSetSyzComp(int k, const ring r)
Definition: ring.cc:5086
ring rAssure_dp_C(const ring r)
Definition: ring.cc:4980
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:400
static int rBlocks(const ring r)
Definition: ring.h:568
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:487
static BOOLEAN rIsLPRing(const ring r)
Definition: ring.h:411
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:91
@ ringorder_ws
Definition: ring.h:86
@ ringorder_s
s?
Definition: ring.h:76
@ ringorder_wp
Definition: ring.h:81
static BOOLEAN rField_is_Q(const ring r)
Definition: ring.h:506
static BOOLEAN rIsNCRing(const ring r)
Definition: ring.h:421
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:592
BOOLEAN rHasGlobalOrdering(const ring r)
Definition: ring.h:759
#define rField_is_Ring(R)
Definition: ring.h:485
#define block
Definition: scanner.cc:646
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
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
int id_ReadOutPivot(ideal arg, int *comp, const ring r)
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)
Definition: simpleideals.h:23
#define id_Test(A, lR)
Definition: simpleideals.h:87
#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
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
#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:770
resolvente sySchreyerResolvente(ideal arg, int maxlength, int *length, BOOLEAN isMonomial=FALSE, BOOLEAN notReplace=FALSE)
Definition: syz0.cc:855
ideal t_rep_gb(const ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode)
Definition: tgb.cc:3571
@ 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