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
20 #include "polys/monomials/ring.h"
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
32 #include "kernel/GBEngine/kstd1.h"
33 #include "kernel/GBEngine/kutil.h"
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 */
idMinBase(ideal h1)51 ideal 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;
58 if(rField_is_Ring(currRing))
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);
65 if (rHasGlobalOrdering(currRing))
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
idSectWithElim(ideal h1,ideal h2,GbVariant alg)133 static 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));
140 assume(id_RankFreeModule(h1,currRing)==0);
141 assume(id_RankFreeModule(h2,currRing)==0);
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
164 rChangeCurrRing(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
idGroebner(ideal temp,int syzComp,GbVariant alg,intvec * hilb=NULL,intvec * w=NULL,tHomog hom=testHomog)201 static 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;
251 omFreeBin((ADDRESS)temp0,sleftv_bin);
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;
301 omFreeBin((ADDRESS)temp0, sleftv_bin);
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 */
idSect(ideal h1,ideal h2,GbVariant alg)316 ideal 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);
327 si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
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)
348 && (!rIsPluralRing(currRing))
349 && ((TEST_V_INTERSECT_ELIM) || (!TEST_V_INTERSECT_SYZ)))
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
452 idSkipZeroes(result);
453 SI_RESTORE_OPT1(save_opt);
454 if (TEST_OPT_RETURN_SB)
455 {
456 w=NULL;
457 temp1=kStd(result,currRing->qideal,testHomog,&w);
458 if (w!=NULL) delete w;
459 idDelete(&result);
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 */
idMultSect(resolvente arg,int length,GbVariant alg)472 ideal idMultSect(resolvente arg, int length, GbVariant alg)
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 /* interprete 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 }
586 idSkipZeroes(result);
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 */
idPrepare(ideal h1,ideal h11,tHomog hom,int syzcomp,intvec ** w,GbVariant alg)607 static 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;
614 k = id_RankFreeModule(h1,currRing);
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;
633 rSetSyzComp(k,currRing);
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
686 matrix TT=id_Module2Matrix(idCopy(h2),currRing);
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
idExtractG_T_S(ideal s_h3,matrix * T,ideal * S,long syzComp,int h1_size,BOOLEAN inputIsIdeal,const ring oring,const ring sring)709 ideal 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
719 matrix TT=id_Module2Matrix(idCopy(s_h3),currRing);
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
766 TT=id_Module2Matrix(idCopy(s_h2),currRing);
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 */
idSyzygies(ideal h1,tHomog h,intvec ** w,BOOLEAN setSyzComp,BOOLEAN setRegularity,int * deg,GbVariant alg)830 ideal 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);
871 si_opt_1|=Sy_bit(OPT_REDTAIL_SYZ);
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)
927 && (!TEST_OPT_NOTREGULARITY)
928 && (setRegularity)
929 && (h==isHomog)
930 && (!rIsPluralRing(currRing))
931 && (!rField_is_Ring(currRing))
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 }
941 resolvente res = sySchreyerResolvente(e,-1,&length,TRUE, TRUE);
942 intvec * dummy = syBetti(res,length,®, *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 */
idLiftStd(ideal h1,matrix * T,tHomog hi,ideal * S,GbVariant alg,ideal h11)976 ideal 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,0);
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
idPrepareStd(ideal s_temp,int k)1041 static 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
idLift_setUnit(int e_mod,matrix * unit)1082 static 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
idLift(ideal mod,ideal submod,ideal * rest,BOOLEAN goodShape,BOOLEAN isSB,BOOLEAN divide,matrix * unit,GbVariant alg)1099 ideal idLift(ideal mod, ideal submod,ideal *rest, BOOLEAN goodShape,
1100 BOOLEAN isSB, BOOLEAN divide, matrix *unit, GbVariant alg)
1101 {
1102 int lsmod =id_RankFreeModule(submod,currRing), j, k;
1103 int comps_to_add=0;
1104 int idelems_mod=IDELEMS(mod);
1105 int idelems_submod=IDELEMS(submod);
1106 poly p;
1107
1108 if (idIs0(submod))
1109 {
1110 if (rest!=NULL)
1111 {
1112 *rest=idInit(1,mod->rank);
1113 }
1114 idLift_setUnit(idelems_submod,unit);
1115 return idInit(1,idelems_mod);
1116 }
1117 if (idIs0(mod)) /* and not idIs0(submod) */
1118 {
1119 if (rest!=NULL)
1120 {
1121 *rest=idCopy(submod);
1122 idLift_setUnit(idelems_submod,unit);
1123 return idInit(1,idelems_mod);
1124 }
1125 else
1126 {
1127 WerrorS("2nd module does not lie in the first");
1128 return NULL;
1129 }
1130 }
1131 if (unit!=NULL)
1132 {
1133 comps_to_add = idelems_submod;
1134 while ((comps_to_add>0) && (submod->m[comps_to_add-1]==NULL))
1135 comps_to_add--;
1136 }
1137 k=si_max(id_RankFreeModule(mod,currRing),id_RankFreeModule(submod,currRing));
1138 if ((k!=0) && (lsmod==0)) lsmod=1;
1139 k=si_max(k,(int)mod->rank);
1140 if (k<submod->rank) { WarnS("rk(submod) > rk(mod) ?");k=submod->rank; }
1141
1142 ring orig_ring=currRing;
1143 ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
1144 rSetSyzComp(k,syz_ring);
1145 rChangeCurrRing(syz_ring);
1146
1147 ideal s_mod, s_temp;
1148 if (orig_ring != syz_ring)
1149 {
1150 s_mod = idrCopyR_NoSort(mod,orig_ring,syz_ring);
1151 s_temp = idrCopyR_NoSort(submod,orig_ring,syz_ring);
1152 }
1153 else
1154 {
1155 s_mod = mod;
1156 s_temp = idCopy(submod);
1157 }
1158 ideal s_h3;
1159 if (isSB)
1160 {
1161 s_h3 = idCopy(s_mod);
1162 idPrepareStd(s_h3, k+comps_to_add);
1163 }
1164 else
1165 {
1166 s_h3 = idPrepare(s_mod,NULL,(tHomog)FALSE,k+comps_to_add,NULL,alg);
1167 }
1168 if (!goodShape)
1169 {
1170 for (j=0;j<IDELEMS(s_h3);j++)
1171 {
1172 if ((s_h3->m[j] != NULL) && (pMinComp(s_h3->m[j]) > k))
1173 p_Delete(&(s_h3->m[j]),currRing);
1174 }
1175 }
1176 idSkipZeroes(s_h3);
1177 if (lsmod==0)
1178 {
1179 id_Shift(s_temp,1,currRing);
1180 }
1181 if (unit!=NULL)
1182 {
1183 for(j = 0;j<comps_to_add;j++)
1184 {
1185 p = s_temp->m[j];
1186 if (p!=NULL)
1187 {
1188 while (pNext(p)!=NULL) pIter(p);
1189 pNext(p) = pOne();
1190 pIter(p);
1191 pSetComp(p,1+j+k);
1192 pSetmComp(p);
1193 p = pNeg(p);
1194 }
1195 }
1196 s_temp->rank += (k+comps_to_add);
1197 }
1198 ideal s_result = kNF(s_h3,currRing->qideal,s_temp,k);
1199 s_result->rank = s_h3->rank;
1200 ideal s_rest = idInit(IDELEMS(s_result),k);
1201 idDelete(&s_h3);
1202 idDelete(&s_temp);
1203
1204 for (j=0;j<IDELEMS(s_result);j++)
1205 {
1206 if (s_result->m[j]!=NULL)
1207 {
1208 if (pGetComp(s_result->m[j])<=k)
1209 {
1210 if (!divide)
1211 {
1212 if (rest==NULL)
1213 {
1214 if (isSB)
1215 {
1216 WarnS("first module not a standardbasis\n"
1217 "// ** or second not a proper submodule");
1218 }
1219 else
1220 WerrorS("2nd module does not lie in the first");
1221 }
1222 idDelete(&s_result);
1223 idDelete(&s_rest);
1224 if(syz_ring!=orig_ring)
1225 {
1226 idDelete(&s_mod);
1227 rChangeCurrRing(orig_ring);
1228 rDelete(syz_ring);
1229 }
1230 if (unit!=NULL)
1231 {
1232 idLift_setUnit(idelems_submod,unit);
1233 }
1234 if (rest!=NULL) *rest=idCopy(submod);
1235 s_result=idInit(idelems_submod,idelems_mod);
1236 return s_result;
1237 }
1238 else
1239 {
1240 p = s_rest->m[j] = s_result->m[j];
1241 while ((pNext(p)!=NULL) && (pGetComp(pNext(p))<=k)) pIter(p);
1242 s_result->m[j] = pNext(p);
1243 pNext(p) = NULL;
1244 }
1245 }
1246 p_Shift(&(s_result->m[j]),-k,currRing);
1247 pNeg(s_result->m[j]);
1248 }
1249 }
1250 if ((lsmod==0) && (s_rest!=NULL))
1251 {
1252 for (j=IDELEMS(s_rest);j>0;j--)
1253 {
1254 if (s_rest->m[j-1]!=NULL)
1255 {
1256 p_Shift(&(s_rest->m[j-1]),-1,currRing);
1257 }
1258 }
1259 }
1260 if(syz_ring!=orig_ring)
1261 {
1262 idDelete(&s_mod);
1263 rChangeCurrRing(orig_ring);
1264 s_result = idrMoveR_NoSort(s_result, syz_ring, orig_ring);
1265 s_rest = idrMoveR_NoSort(s_rest, syz_ring, orig_ring);
1266 rDelete(syz_ring);
1267 }
1268 if (rest!=NULL)
1269 {
1270 s_rest->rank=mod->rank;
1271 *rest = s_rest;
1272 }
1273 else
1274 idDelete(&s_rest);
1275 if (unit!=NULL)
1276 {
1277 *unit=mpNew(idelems_submod,idelems_submod);
1278 int i;
1279 for(i=0;i<IDELEMS(s_result);i++)
1280 {
1281 poly p=s_result->m[i];
1282 poly q=NULL;
1283 while(p!=NULL)
1284 {
1285 if(pGetComp(p)<=comps_to_add)
1286 {
1287 pSetComp(p,0);
1288 if (q!=NULL)
1289 {
1290 pNext(q)=pNext(p);
1291 }
1292 else
1293 {
1294 pIter(s_result->m[i]);
1295 }
1296 pNext(p)=NULL;
1297 MATELEM(*unit,i+1,i+1)=pAdd(MATELEM(*unit,i+1,i+1),p);
1298 if(q!=NULL) p=pNext(q);
1299 else p=s_result->m[i];
1300 }
1301 else
1302 {
1303 q=p;
1304 pIter(p);
1305 }
1306 }
1307 p_Shift(&s_result->m[i],-comps_to_add,currRing);
1308 }
1309 }
1310 s_result->rank=idelems_mod;
1311 return s_result;
1312 }
1313
1314 /*2
1315 *computes division of P by Q with remainder up to (w-weighted) degree n
1316 *P, Q, and w are not changed
1317 */
idLiftW(ideal P,ideal Q,int n,matrix & T,ideal & R,int * w)1318 void idLiftW(ideal P,ideal Q,int n,matrix &T, ideal &R,int *w)
1319 {
1320 long N=0;
1321 int i;
1322 for(i=IDELEMS(Q)-1;i>=0;i--)
1323 if(w==NULL)
1324 N=si_max(N,p_Deg(Q->m[i],currRing));
1325 else
1326 N=si_max(N,p_DegW(Q->m[i],w,currRing));
1327 N+=n;
1328
1329 T=mpNew(IDELEMS(Q),IDELEMS(P));
1330 R=idInit(IDELEMS(P),P->rank);
1331
1332 for(i=IDELEMS(P)-1;i>=0;i--)
1333 {
1334 poly p;
1335 if(w==NULL)
1336 p=ppJet(P->m[i],N);
1337 else
1338 p=ppJetW(P->m[i],N,w);
1339
1340 int j=IDELEMS(Q)-1;
1341 while(p!=NULL)
1342 {
1343 if(pDivisibleBy(Q->m[j],p))
1344 {
1345 poly p0=p_DivideM(pHead(p),pHead(Q->m[j]),currRing);
1346 if(w==NULL)
1347 p=pJet(pSub(p,ppMult_mm(Q->m[j],p0)),N);
1348 else
1349 p=pJetW(pSub(p,ppMult_mm(Q->m[j],p0)),N,w);
1350 pNormalize(p);
1351 if(((w==NULL)&&(p_Deg(p0,currRing)>n))||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
1352 p_Delete(&p0,currRing);
1353 else
1354 MATELEM(T,j+1,i+1)=pAdd(MATELEM(T,j+1,i+1),p0);
1355 j=IDELEMS(Q)-1;
1356 }
1357 else
1358 {
1359 if(j==0)
1360 {
1361 poly p0=p;
1362 pIter(p);
1363 pNext(p0)=NULL;
1364 if(((w==NULL)&&(p_Deg(p0,currRing)>n))
1365 ||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
1366 p_Delete(&p0,currRing);
1367 else
1368 R->m[i]=pAdd(R->m[i],p0);
1369 j=IDELEMS(Q)-1;
1370 }
1371 else
1372 j--;
1373 }
1374 }
1375 }
1376 }
1377
1378 /*2
1379 *computes the quotient of h1,h2 : internal routine for idQuot
1380 *BEWARE: the returned ideals may contain incorrectly ordered polys !
1381 *
1382 */
idInitializeQuot(ideal h1,ideal h2,BOOLEAN h1IsStb,BOOLEAN * addOnlyOne,int * kkmax)1383 static ideal idInitializeQuot (ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN *addOnlyOne, int *kkmax)
1384 {
1385 idTest(h1);
1386 idTest(h2);
1387
1388 ideal temph1;
1389 poly p,q = NULL;
1390 int i,l,ll,k,kkk,kmax;
1391 int j = 0;
1392 int k1 = id_RankFreeModule(h1,currRing);
1393 int k2 = id_RankFreeModule(h2,currRing);
1394 tHomog hom=isNotHomog;
1395 k=si_max(k1,k2);
1396 if (k==0)
1397 k = 1;
1398 if ((k2==0) && (k>1)) *addOnlyOne = FALSE;
1399 intvec * weights;
1400 hom = (tHomog)idHomModule(h1,currRing->qideal,&weights);
1401 if /**addOnlyOne &&*/ (/*(*/ !h1IsStb /*)*/)
1402 temph1 = kStd(h1,currRing->qideal,hom,&weights,NULL);
1403 else
1404 temph1 = idCopy(h1);
1405 if (weights!=NULL) delete weights;
1406 idTest(temph1);
1407 /*--- making a single vector from h2 ---------------------*/
1408 for (i=0; i<IDELEMS(h2); i++)
1409 {
1410 if (h2->m[i] != NULL)
1411 {
1412 p = pCopy(h2->m[i]);
1413 if (k2 == 0)
1414 p_Shift(&p,j*k+1,currRing);
1415 else
1416 p_Shift(&p,j*k,currRing);
1417 q = pAdd(q,p);
1418 j++;
1419 }
1420 }
1421 *kkmax = kmax = j*k+1;
1422 /*--- adding a monomial for the result (syzygy) ----------*/
1423 p = q;
1424 while (pNext(p)!=NULL) pIter(p);
1425 pNext(p) = pOne();
1426 pIter(p);
1427 pSetComp(p,kmax);
1428 pSetmComp(p);
1429 /*--- constructing the big matrix ------------------------*/
1430 ideal h4 = idInit(k,kmax+k-1);
1431 h4->m[0] = q;
1432 if (k2 == 0)
1433 {
1434 for (i=1; i<k; i++)
1435 {
1436 if (h4->m[i-1]!=NULL)
1437 {
1438 p = p_Copy_noCheck(h4->m[i-1], currRing); /*h4->m[i-1]!=NULL*/
1439 p_Shift(&p,1,currRing);
1440 h4->m[i] = p;
1441 }
1442 else break;
1443 }
1444 }
1445 idSkipZeroes(h4);
1446 kkk = IDELEMS(h4);
1447 i = IDELEMS(temph1);
1448 for (l=0; l<i; l++)
1449 {
1450 if(temph1->m[l]!=NULL)
1451 {
1452 for (ll=0; ll<j; ll++)
1453 {
1454 p = pCopy(temph1->m[l]);
1455 if (k1 == 0)
1456 p_Shift(&p,ll*k+1,currRing);
1457 else
1458 p_Shift(&p,ll*k,currRing);
1459 if (kkk >= IDELEMS(h4))
1460 {
1461 pEnlargeSet(&(h4->m),IDELEMS(h4),16);
1462 IDELEMS(h4) += 16;
1463 }
1464 h4->m[kkk] = p;
1465 kkk++;
1466 }
1467 }
1468 }
1469 /*--- if h2 goes in as single vector - the h1-part is just SB ---*/
1470 if (*addOnlyOne)
1471 {
1472 idSkipZeroes(h4);
1473 p = h4->m[0];
1474 for (i=0;i<IDELEMS(h4)-1;i++)
1475 {
1476 h4->m[i] = h4->m[i+1];
1477 }
1478 h4->m[IDELEMS(h4)-1] = p;
1479 }
1480 idDelete(&temph1);
1481 //idTest(h4);//see remark at the beginning
1482 return h4;
1483 }
1484
1485 /*2
1486 *computes the quotient of h1,h2
1487 */
idQuot(ideal h1,ideal h2,BOOLEAN h1IsStb,BOOLEAN resultIsIdeal)1488 ideal idQuot (ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN resultIsIdeal)
1489 {
1490 // first check for special case h1:(0)
1491 if (idIs0(h2))
1492 {
1493 ideal res;
1494 if (resultIsIdeal)
1495 {
1496 res = idInit(1,1);
1497 res->m[0] = pOne();
1498 }
1499 else
1500 res = idFreeModule(h1->rank);
1501 return res;
1502 }
1503 int i, kmax;
1504 BOOLEAN addOnlyOne=TRUE;
1505 tHomog hom=isNotHomog;
1506 intvec * weights1;
1507
1508 ideal s_h4 = idInitializeQuot (h1,h2,h1IsStb,&addOnlyOne,&kmax);
1509
1510 hom = (tHomog)idHomModule(s_h4,currRing->qideal,&weights1);
1511
1512 ring orig_ring=currRing;
1513 ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
1514 rSetSyzComp(kmax-1,syz_ring);
1515 rChangeCurrRing(syz_ring);
1516 if (orig_ring!=syz_ring)
1517 // s_h4 = idrMoveR_NoSort(s_h4,orig_ring, syz_ring);
1518 s_h4 = idrMoveR(s_h4,orig_ring, syz_ring);
1519 idTest(s_h4);
1520
1521 #if 0
1522 matrix m=idModule2Matrix(idCopy(s_h4));
1523 PrintS("start:\n");
1524 ipPrint_MA0(m,"Q");
1525 idDelete((ideal *)&m);
1526 PrintS("last elem:");wrp(s_h4->m[IDELEMS(s_h4)-1]);PrintLn();
1527 #endif
1528
1529 ideal s_h3;
1530 BITSET old_test1;
1531 SI_SAVE_OPT1(old_test1);
1532 if (TEST_OPT_RETURN_SB) si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
1533 if (addOnlyOne)
1534 {
1535 if(!rField_is_Ring(currRing)) si_opt_1 |= Sy_bit(OPT_SB_1);
1536 s_h3 = kStd(s_h4,currRing->qideal,hom,&weights1,NULL,0/*kmax-1*/,IDELEMS(s_h4)-1);
1537 }
1538 else
1539 {
1540 s_h3 = kStd(s_h4,currRing->qideal,hom,&weights1,NULL,kmax-1);
1541 }
1542 SI_RESTORE_OPT1(old_test1);
1543
1544 #if 0
1545 // only together with the above debug stuff
1546 idSkipZeroes(s_h3);
1547 m=idModule2Matrix(idCopy(s_h3));
1548 Print("result, kmax=%d:\n",kmax);
1549 ipPrint_MA0(m,"S");
1550 idDelete((ideal *)&m);
1551 #endif
1552
1553 idTest(s_h3);
1554 if (weights1!=NULL) delete weights1;
1555 idDelete(&s_h4);
1556
1557 for (i=0;i<IDELEMS(s_h3);i++)
1558 {
1559 if ((s_h3->m[i]!=NULL) && (pGetComp(s_h3->m[i])>=kmax))
1560 {
1561 if (resultIsIdeal)
1562 p_Shift(&s_h3->m[i],-kmax,currRing);
1563 else
1564 p_Shift(&s_h3->m[i],-kmax+1,currRing);
1565 }
1566 else
1567 p_Delete(&s_h3->m[i],currRing);
1568 }
1569 if (resultIsIdeal)
1570 s_h3->rank = 1;
1571 else
1572 s_h3->rank = h1->rank;
1573 if(syz_ring!=orig_ring)
1574 {
1575 rChangeCurrRing(orig_ring);
1576 s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
1577 rDelete(syz_ring);
1578 }
1579 idSkipZeroes(s_h3);
1580 idTest(s_h3);
1581 return s_h3;
1582 }
1583
1584 /*2
1585 * eliminate delVar (product of vars) in h1
1586 */
idElimination(ideal h1,poly delVar,intvec * hilb,GbVariant alg)1587 ideal idElimination (ideal h1,poly delVar,intvec *hilb, GbVariant alg)
1588 {
1589 int i,j=0,k,l;
1590 ideal h,hh, h3;
1591 rRingOrder_t *ord;
1592 int *block0,*block1;
1593 int ordersize=2;
1594 int **wv;
1595 tHomog hom;
1596 intvec * w;
1597 ring tmpR;
1598 ring origR = currRing;
1599
1600 if (delVar==NULL)
1601 {
1602 return idCopy(h1);
1603 }
1604 if ((currRing->qideal!=NULL) && rIsPluralRing(origR))
1605 {
1606 WerrorS("cannot eliminate in a qring");
1607 return NULL;
1608 }
1609 if (idIs0(h1)) return idInit(1,h1->rank);
1610 #ifdef HAVE_PLURAL
1611 if (rIsPluralRing(origR))
1612 /* in the NC case, we have to check the admissibility of */
1613 /* the subalgebra to be intersected with */
1614 {
1615 if ((ncRingType(origR) != nc_skew) && (ncRingType(origR) != nc_exterior)) /* in (quasi)-commutative algebras every subalgebra is admissible */
1616 {
1617 if (nc_CheckSubalgebra(delVar,origR))
1618 {
1619 WerrorS("no elimination is possible: subalgebra is not admissible");
1620 return NULL;
1621 }
1622 }
1623 }
1624 #endif
1625 hom=(tHomog)idHomModule(h1,NULL,&w); //sets w to weight vector or NULL
1626 h3=idInit(16,h1->rank);
1627 for (k=0;; k++)
1628 {
1629 if (origR->order[k]!=0) ordersize++;
1630 else break;
1631 }
1632 #if 0
1633 if (rIsPluralRing(origR)) // we have too keep the odering: it may be needed
1634 // for G-algebra
1635 {
1636 for (k=0;k<ordersize-1; k++)
1637 {
1638 block0[k+1] = origR->block0[k];
1639 block1[k+1] = origR->block1[k];
1640 ord[k+1] = origR->order[k];
1641 if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1642 }
1643 }
1644 else
1645 {
1646 block0[1] = 1;
1647 block1[1] = (currRing->N);
1648 if (origR->OrdSgn==1) ord[1] = ringorder_wp;
1649 else ord[1] = ringorder_ws;
1650 wv[1]=(int*)omAlloc0((currRing->N)*sizeof(int));
1651 double wNsqr = (double)2.0 / (double)(currRing->N);
1652 wFunctional = wFunctionalBuch;
1653 int *x= (int * )omAlloc(2 * ((currRing->N) + 1) * sizeof(int));
1654 int sl=IDELEMS(h1) - 1;
1655 wCall(h1->m, sl, x, wNsqr);
1656 for (sl = (currRing->N); sl!=0; sl--)
1657 wv[1][sl-1] = x[sl + (currRing->N) + 1];
1658 omFreeSize((ADDRESS)x, 2 * ((currRing->N) + 1) * sizeof(int));
1659
1660 ord[2]=ringorder_C;
1661 ord[3]=0;
1662 }
1663 #else
1664 #endif
1665 if ((hom==TRUE) && (origR->OrdSgn==1) && (!rIsPluralRing(origR)))
1666 {
1667 #if 1
1668 // we change to an ordering:
1669 // aa(1,1,1,...,0,0,0),wp(...),C
1670 // this seems to be better than version 2 below,
1671 // according to Tst/../elimiate_[3568].tat (- 17 %)
1672 ord=(rRingOrder_t*)omAlloc0(4*sizeof(rRingOrder_t));
1673 block0=(int*)omAlloc0(4*sizeof(int));
1674 block1=(int*)omAlloc0(4*sizeof(int));
1675 wv=(int**) omAlloc0(4*sizeof(int**));
1676 block0[0] = block0[1] = 1;
1677 block1[0] = block1[1] = rVar(origR);
1678 wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1679 // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1680 // ignore it
1681 ord[0] = ringorder_aa;
1682 for (j=0;j<rVar(origR);j++)
1683 if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1684 BOOLEAN wp=FALSE;
1685 for (j=0;j<rVar(origR);j++)
1686 if (p_Weight(j+1,origR)!=1) { wp=TRUE;break; }
1687 if (wp)
1688 {
1689 wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1690 for (j=0;j<rVar(origR);j++)
1691 wv[1][j]=p_Weight(j+1,origR);
1692 ord[1] = ringorder_wp;
1693 }
1694 else
1695 ord[1] = ringorder_dp;
1696 #else
1697 // we change to an ordering:
1698 // a(w1,...wn),wp(1,...0.....),C
1699 ord=(int*)omAlloc0(4*sizeof(int));
1700 block0=(int*)omAlloc0(4*sizeof(int));
1701 block1=(int*)omAlloc0(4*sizeof(int));
1702 wv=(int**) omAlloc0(4*sizeof(int**));
1703 block0[0] = block0[1] = 1;
1704 block1[0] = block1[1] = rVar(origR);
1705 wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1706 wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1707 ord[0] = ringorder_a;
1708 for (j=0;j<rVar(origR);j++)
1709 wv[0][j]=pWeight(j+1,origR);
1710 ord[1] = ringorder_wp;
1711 for (j=0;j<rVar(origR);j++)
1712 if (pGetExp(delVar,j+1)!=0) wv[1][j]=1;
1713 #endif
1714 ord[2] = ringorder_C;
1715 ord[3] = (rRingOrder_t)0;
1716 }
1717 else
1718 {
1719 // we change to an ordering:
1720 // aa(....),orig_ordering
1721 ord=(rRingOrder_t*)omAlloc0(ordersize*sizeof(rRingOrder_t));
1722 block0=(int*)omAlloc0(ordersize*sizeof(int));
1723 block1=(int*)omAlloc0(ordersize*sizeof(int));
1724 wv=(int**) omAlloc0(ordersize*sizeof(int**));
1725 for (k=0;k<ordersize-1; k++)
1726 {
1727 block0[k+1] = origR->block0[k];
1728 block1[k+1] = origR->block1[k];
1729 ord[k+1] = origR->order[k];
1730 if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1731 }
1732 block0[0] = 1;
1733 block1[0] = rVar(origR);
1734 wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1735 for (j=0;j<rVar(origR);j++)
1736 if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1737 // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1738 // ignore it
1739 ord[0] = ringorder_aa;
1740 }
1741 // fill in tmp ring to get back the data later on
1742 tmpR = rCopy0(origR,FALSE,FALSE); // qring==NULL
1743 //rUnComplete(tmpR);
1744 tmpR->p_Procs=NULL;
1745 tmpR->order = ord;
1746 tmpR->block0 = block0;
1747 tmpR->block1 = block1;
1748 tmpR->wvhdl = wv;
1749 rComplete(tmpR, 1);
1750
1751 #ifdef HAVE_PLURAL
1752 /* update nc structure on tmpR */
1753 if (rIsPluralRing(origR))
1754 {
1755 if ( nc_rComplete(origR, tmpR, false) ) // no quotient ideal!
1756 {
1757 WerrorS("no elimination is possible: ordering condition is violated");
1758 // cleanup
1759 rDelete(tmpR);
1760 if (w!=NULL)
1761 delete w;
1762 return NULL;
1763 }
1764 }
1765 #endif
1766 // change into the new ring
1767 //pChangeRing((currRing->N),currRing->OrdSgn,ord,block0,block1,wv);
1768 rChangeCurrRing(tmpR);
1769
1770 //h = idInit(IDELEMS(h1),h1->rank);
1771 // fetch data from the old ring
1772 //for (k=0;k<IDELEMS(h1);k++) h->m[k] = prCopyR( h1->m[k], origR);
1773 h=idrCopyR(h1,origR,currRing);
1774 if (origR->qideal!=NULL)
1775 {
1776 WarnS("eliminate in q-ring: experimental");
1777 ideal q=idrCopyR(origR->qideal,origR,currRing);
1778 ideal s=idSimpleAdd(h,q);
1779 idDelete(&h);
1780 idDelete(&q);
1781 h=s;
1782 }
1783 // compute GB
1784 if ((alg!=GbDefault)
1785 && (alg!=GbGroebner)
1786 && (alg!=GbModstd)
1787 && (alg!=GbSlimgb)
1788 && (alg!=GbSba)
1789 && (alg!=GbStd))
1790 {
1791 WarnS("wrong algorithm for GB");
1792 alg=GbDefault;
1793 }
1794 BITSET save2;
1795 SI_SAVE_OPT2(save2);
1796 if (!TEST_OPT_RETURN_SB) si_opt_2|=V_IDELIM;
1797 hh=idGroebner(h,0,alg,hilb);
1798 SI_RESTORE_OPT2(save2);
1799 // go back to the original ring
1800 rChangeCurrRing(origR);
1801 i = IDELEMS(hh)-1;
1802 while ((i >= 0) && (hh->m[i] == NULL)) i--;
1803 j = -1;
1804 // fetch data from temp ring
1805 for (k=0; k<=i; k++)
1806 {
1807 l=(currRing->N);
1808 while ((l>0) && (p_GetExp( hh->m[k],l,tmpR)*pGetExp(delVar,l)==0)) l--;
1809 if (l==0)
1810 {
1811 j++;
1812 if (j >= IDELEMS(h3))
1813 {
1814 pEnlargeSet(&(h3->m),IDELEMS(h3),16);
1815 IDELEMS(h3) += 16;
1816 }
1817 h3->m[j] = prMoveR( hh->m[k], tmpR,origR);
1818 hh->m[k] = NULL;
1819 }
1820 }
1821 id_Delete(&hh, tmpR);
1822 idSkipZeroes(h3);
1823 rDelete(tmpR);
1824 if (w!=NULL)
1825 delete w;
1826 return h3;
1827 }
1828
1829 #ifdef WITH_OLD_MINOR
1830 /*2
1831 * compute the which-th ar-minor of the matrix a
1832 */
idMinor(matrix a,int ar,unsigned long which,ideal R)1833 poly idMinor(matrix a, int ar, unsigned long which, ideal R)
1834 {
1835 int i,j/*,k,size*/;
1836 unsigned long curr;
1837 int *rowchoise,*colchoise;
1838 BOOLEAN rowch,colch;
1839 // ideal result;
1840 matrix tmp;
1841 poly p,q;
1842
1843 rowchoise=(int *)omAlloc(ar*sizeof(int));
1844 colchoise=(int *)omAlloc(ar*sizeof(int));
1845 tmp=mpNew(ar,ar);
1846 curr = 0; /* index of current minor */
1847 idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1848 while (!rowch)
1849 {
1850 idInitChoise(ar,1,a->cols(),&colch,colchoise);
1851 while (!colch)
1852 {
1853 if (curr == which)
1854 {
1855 for (i=1; i<=ar; i++)
1856 {
1857 for (j=1; j<=ar; j++)
1858 {
1859 MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1860 }
1861 }
1862 p = mp_DetBareiss(tmp,currRing);
1863 if (p!=NULL)
1864 {
1865 if (R!=NULL)
1866 {
1867 q = p;
1868 p = kNF(R,currRing->qideal,q);
1869 p_Delete(&q,currRing);
1870 }
1871 }
1872 /*delete the matrix tmp*/
1873 for (i=1; i<=ar; i++)
1874 {
1875 for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1876 }
1877 idDelete((ideal*)&tmp);
1878 omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1879 omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1880 return (p);
1881 }
1882 curr++;
1883 idGetNextChoise(ar,a->cols(),&colch,colchoise);
1884 }
1885 idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1886 }
1887 return (poly) 1;
1888 }
1889
1890 /*2
1891 * compute all ar-minors of the matrix a
1892 */
idMinors(matrix a,int ar,ideal R)1893 ideal idMinors(matrix a, int ar, ideal R)
1894 {
1895 int i,j,/*k,*/size;
1896 int *rowchoise,*colchoise;
1897 BOOLEAN rowch,colch;
1898 ideal result;
1899 matrix tmp;
1900 poly p,q;
1901
1902 i = binom(a->rows(),ar);
1903 j = binom(a->cols(),ar);
1904 size=i*j;
1905
1906 rowchoise=(int *)omAlloc(ar*sizeof(int));
1907 colchoise=(int *)omAlloc(ar*sizeof(int));
1908 result=idInit(size,1);
1909 tmp=mpNew(ar,ar);
1910 // k = 0; /* the index in result*/
1911 idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1912 while (!rowch)
1913 {
1914 idInitChoise(ar,1,a->cols(),&colch,colchoise);
1915 while (!colch)
1916 {
1917 for (i=1; i<=ar; i++)
1918 {
1919 for (j=1; j<=ar; j++)
1920 {
1921 MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1922 }
1923 }
1924 p = mp_DetBareiss(tmp,currRing);
1925 if (p!=NULL)
1926 {
1927 if (R!=NULL)
1928 {
1929 q = p;
1930 p = kNF(R,currRing->qideal,q);
1931 p_Delete(&q,currRing);
1932 }
1933 }
1934 if (k>=size)
1935 {
1936 pEnlargeSet(&result->m,size,32);
1937 size += 32;
1938 }
1939 result->m[k] = p;
1940 k++;
1941 idGetNextChoise(ar,a->cols(),&colch,colchoise);
1942 }
1943 idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1944 }
1945 /*delete the matrix tmp*/
1946 for (i=1; i<=ar; i++)
1947 {
1948 for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1949 }
1950 idDelete((ideal*)&tmp);
1951 if (k==0)
1952 {
1953 k=1;
1954 result->m[0]=NULL;
1955 }
1956 omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1957 omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1958 pEnlargeSet(&result->m,size,k-size);
1959 IDELEMS(result) = k;
1960 return (result);
1961 }
1962 #else
1963
1964
1965 /// compute all ar-minors of the matrix a
1966 /// the caller of mpRecMin
1967 /// the elements of the result are not in R (if R!=NULL)
idMinors(matrix a,int ar,ideal R)1968 ideal idMinors(matrix a, int ar, ideal R)
1969 {
1970
1971 const ring origR=currRing;
1972 id_Test((ideal)a, origR);
1973
1974 const int r = a->nrows;
1975 const int c = a->ncols;
1976
1977 if((ar<=0) || (ar>r) || (ar>c))
1978 {
1979 Werror("%d-th minor, matrix is %dx%d",ar,r,c);
1980 return NULL;
1981 }
1982
1983 ideal h = id_Matrix2Module(mp_Copy(a,origR),origR);
1984 long bound = sm_ExpBound(h,c,r,ar,origR);
1985 id_Delete(&h, origR);
1986
1987 ring tmpR = sm_RingChange(origR,bound);
1988
1989 matrix b = mpNew(r,c);
1990
1991 for (int i=r*c-1;i>=0;i--)
1992 if (a->m[i] != NULL)
1993 b->m[i] = prCopyR(a->m[i],origR,tmpR);
1994
1995 id_Test( (ideal)b, tmpR);
1996
1997 if (R!=NULL)
1998 {
1999 R = idrCopyR(R,origR,tmpR); // TODO: overwrites R? memory leak?
2000 //if (ar>1) // otherwise done in mpMinorToResult
2001 //{
2002 // matrix bb=(matrix)kNF(R,currRing->qideal,(ideal)b);
2003 // bb->rank=b->rank; bb->nrows=b->nrows; bb->ncols=b->ncols;
2004 // idDelete((ideal*)&b); b=bb;
2005 //}
2006 id_Test( R, tmpR);
2007 }
2008
2009 int size=binom(r,ar)*binom(c,ar);
2010 ideal result = idInit(size,1);
2011
2012 int elems = 0;
2013
2014 if(ar>1)
2015 mp_RecMin(ar-1,result,elems,b,r,c,NULL,R,tmpR);
2016 else
2017 mp_MinorToResult(result,elems,b,r,c,R,tmpR);
2018
2019 id_Test( (ideal)b, tmpR);
2020
2021 id_Delete((ideal *)&b, tmpR);
2022
2023 if (R!=NULL) id_Delete(&R,tmpR);
2024
2025 rChangeCurrRing(origR);
2026 result = idrMoveR(result,tmpR,origR);
2027 sm_KillModifiedRing(tmpR);
2028 idTest(result);
2029 return result;
2030 }
2031 #endif
2032
2033 /*2
2034 *returns TRUE if id1 is a submodule of id2
2035 */
idIsSubModule(ideal id1,ideal id2)2036 BOOLEAN idIsSubModule(ideal id1,ideal id2)
2037 {
2038 int i;
2039 poly p;
2040
2041 if (idIs0(id1)) return TRUE;
2042 for (i=0;i<IDELEMS(id1);i++)
2043 {
2044 if (id1->m[i] != NULL)
2045 {
2046 p = kNF(id2,currRing->qideal,id1->m[i]);
2047 if (p != NULL)
2048 {
2049 p_Delete(&p,currRing);
2050 return FALSE;
2051 }
2052 }
2053 }
2054 return TRUE;
2055 }
2056
idTestHomModule(ideal m,ideal Q,intvec * w)2057 BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
2058 {
2059 if ((Q!=NULL) && (!idHomIdeal(Q,NULL))) { PrintS(" Q not hom\n"); return FALSE;}
2060 if (idIs0(m)) return TRUE;
2061
2062 int cmax=-1;
2063 int i;
2064 poly p=NULL;
2065 int length=IDELEMS(m);
2066 polyset P=m->m;
2067 for (i=length-1;i>=0;i--)
2068 {
2069 p=P[i];
2070 if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
2071 }
2072 if (w != NULL)
2073 if (w->length()+1 < cmax)
2074 {
2075 // Print("length: %d - %d \n", w->length(),cmax);
2076 return FALSE;
2077 }
2078
2079 if(w!=NULL)
2080 p_SetModDeg(w, currRing);
2081
2082 for (i=length-1;i>=0;i--)
2083 {
2084 p=P[i];
2085 if (p!=NULL)
2086 {
2087 int d=currRing->pFDeg(p,currRing);
2088 loop
2089 {
2090 pIter(p);
2091 if (p==NULL) break;
2092 if (d!=currRing->pFDeg(p,currRing))
2093 {
2094 //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
2095 if(w!=NULL)
2096 p_SetModDeg(NULL, currRing);
2097 return FALSE;
2098 }
2099 }
2100 }
2101 }
2102
2103 if(w!=NULL)
2104 p_SetModDeg(NULL, currRing);
2105
2106 return TRUE;
2107 }
2108
idSeries(int n,ideal M,matrix U,intvec * w)2109 ideal idSeries(int n,ideal M,matrix U,intvec *w)
2110 {
2111 for(int i=IDELEMS(M)-1;i>=0;i--)
2112 {
2113 if(U==NULL)
2114 M->m[i]=pSeries(n,M->m[i],NULL,w);
2115 else
2116 {
2117 M->m[i]=pSeries(n,M->m[i],MATELEM(U,i+1,i+1),w);
2118 MATELEM(U,i+1,i+1)=NULL;
2119 }
2120 }
2121 if(U!=NULL)
2122 idDelete((ideal*)&U);
2123 return M;
2124 }
2125
idDiff(matrix i,int k)2126 matrix idDiff(matrix i, int k)
2127 {
2128 int e=MATCOLS(i)*MATROWS(i);
2129 matrix r=mpNew(MATROWS(i),MATCOLS(i));
2130 r->rank=i->rank;
2131 int j;
2132 for(j=0; j<e; j++)
2133 {
2134 r->m[j]=pDiff(i->m[j],k);
2135 }
2136 return r;
2137 }
2138
idDiffOp(ideal I,ideal J,BOOLEAN multiply)2139 matrix idDiffOp(ideal I, ideal J,BOOLEAN multiply)
2140 {
2141 matrix r=mpNew(IDELEMS(I),IDELEMS(J));
2142 int i,j;
2143 for(i=0; i<IDELEMS(I); i++)
2144 {
2145 for(j=0; j<IDELEMS(J); j++)
2146 {
2147 MATELEM(r,i+1,j+1)=pDiffOp(I->m[i],J->m[j],multiply);
2148 }
2149 }
2150 return r;
2151 }
2152
2153 /*3
2154 *handles for some ideal operations the ring/syzcomp managment
2155 *returns all syzygies (componentwise-)shifted by -syzcomp
2156 *or -syzcomp-1 (in case of ideals as input)
2157 static ideal idHandleIdealOp(ideal arg,int syzcomp,int isIdeal=FALSE)
2158 {
2159 ring orig_ring=currRing;
2160 ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE); rChangeCurrRing(syz_ring);
2161 rSetSyzComp(length, syz_ring);
2162
2163 ideal s_temp;
2164 if (orig_ring!=syz_ring)
2165 s_temp=idrMoveR_NoSort(arg,orig_ring, syz_ring);
2166 else
2167 s_temp=arg;
2168
2169 ideal s_temp1 = kStd(s_temp,currRing->qideal,testHomog,&w,NULL,length);
2170 if (w!=NULL) delete w;
2171
2172 if (syz_ring!=orig_ring)
2173 {
2174 idDelete(&s_temp);
2175 rChangeCurrRing(orig_ring);
2176 }
2177
2178 idDelete(&temp);
2179 ideal temp1=idRingCopy(s_temp1,syz_ring);
2180
2181 if (syz_ring!=orig_ring)
2182 {
2183 rChangeCurrRing(syz_ring);
2184 idDelete(&s_temp1);
2185 rChangeCurrRing(orig_ring);
2186 rDelete(syz_ring);
2187 }
2188
2189 for (i=0;i<IDELEMS(temp1);i++)
2190 {
2191 if ((temp1->m[i]!=NULL)
2192 && (pGetComp(temp1->m[i])<=length))
2193 {
2194 pDelete(&(temp1->m[i]));
2195 }
2196 else
2197 {
2198 p_Shift(&(temp1->m[i]),-length,currRing);
2199 }
2200 }
2201 temp1->rank = rk;
2202 idSkipZeroes(temp1);
2203
2204 return temp1;
2205 }
2206 */
2207
2208 #ifdef HAVE_SHIFTBBA
idModuloLP(ideal h2,ideal h1,tHomog,intvec ** w,matrix * T,GbVariant alg)2209 ideal idModuloLP (ideal h2,ideal h1, tHomog, intvec ** w, matrix *T, GbVariant alg)
2210 {
2211 intvec *wtmp=NULL;
2212 if (T!=NULL) idDelete((ideal*)T);
2213
2214 int i,k,rk,flength=0,slength,length;
2215 poly p,q;
2216
2217 if (idIs0(h2))
2218 return idFreeModule(si_max(1,h2->ncols));
2219 if (!idIs0(h1))
2220 flength = id_RankFreeModule(h1,currRing);
2221 slength = id_RankFreeModule(h2,currRing);
2222 length = si_max(flength,slength);
2223 if (length==0)
2224 {
2225 length = 1;
2226 }
2227 ideal temp = idInit(IDELEMS(h2),length+IDELEMS(h2));
2228 if ((w!=NULL)&&((*w)!=NULL))
2229 {
2230 //Print("input weights:");(*w)->show(1);PrintLn();
2231 int d;
2232 int k;
2233 wtmp=new intvec(length+IDELEMS(h2));
2234 for (i=0;i<length;i++)
2235 ((*wtmp)[i])=(**w)[i];
2236 for (i=0;i<IDELEMS(h2);i++)
2237 {
2238 poly p=h2->m[i];
2239 if (p!=NULL)
2240 {
2241 d = p_Deg(p,currRing);
2242 k= pGetComp(p);
2243 if (slength>0) k--;
2244 d +=((**w)[k]);
2245 ((*wtmp)[i+length]) = d;
2246 }
2247 }
2248 //Print("weights:");wtmp->show(1);PrintLn();
2249 }
2250 for (i=0;i<IDELEMS(h2);i++)
2251 {
2252 temp->m[i] = pCopy(h2->m[i]);
2253 q = pOne();
2254 // non multiplicative variable
2255 pSetExp(q, currRing->isLPring - currRing->LPncGenCount + i + 1, 1);
2256 p_Setm(q, currRing);
2257 pSetComp(q,i+1+length);
2258 pSetmComp(q);
2259 if(temp->m[i]!=NULL)
2260 {
2261 if (slength==0) p_Shift(&(temp->m[i]),1,currRing);
2262 p = temp->m[i];
2263 temp->m[i] = pAdd(p, q);
2264 }
2265 else
2266 temp->m[i]=q;
2267 }
2268 rk = k = IDELEMS(h2);
2269 if (!idIs0(h1))
2270 {
2271 pEnlargeSet(&(temp->m),IDELEMS(temp),IDELEMS(h1));
2272 IDELEMS(temp) += IDELEMS(h1);
2273 for (i=0;i<IDELEMS(h1);i++)
2274 {
2275 if (h1->m[i]!=NULL)
2276 {
2277 temp->m[k] = pCopy(h1->m[i]);
2278 if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
2279 k++;
2280 }
2281 }
2282 }
2283
2284 ring orig_ring=currRing;
2285 ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE);
2286 rSetSyzComp(length,syz_ring);
2287 rChangeCurrRing(syz_ring);
2288 // we can use OPT_RETURN_SB only, if syz_ring==orig_ring,
2289 // therefore we disable OPT_RETURN_SB for modulo:
2290 // (see tr. #701)
2291 //if (TEST_OPT_RETURN_SB)
2292 // rSetSyzComp(IDELEMS(h2)+length, syz_ring);
2293 //else
2294 // rSetSyzComp(length, syz_ring);
2295 ideal s_temp;
2296
2297 if (syz_ring != orig_ring)
2298 {
2299 s_temp = idrMoveR_NoSort(temp, orig_ring, syz_ring);
2300 }
2301 else
2302 {
2303 s_temp = temp;
2304 }
2305
2306 idTest(s_temp);
2307 unsigned save_opt,save_opt2;
2308 SI_SAVE_OPT1(save_opt);
2309 SI_SAVE_OPT2(save_opt2);
2310 if (T==NULL) si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
2311 si_opt_1 |= Sy_bit(OPT_REDTAIL);
2312 ideal s_temp1 = idGroebner(s_temp,length,alg);
2313 SI_RESTORE_OPT1(save_opt);
2314 SI_RESTORE_OPT2(save_opt2);
2315
2316 //if (wtmp!=NULL) Print("output weights:");wtmp->show(1);PrintLn();
2317 if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
2318 {
2319 delete *w;
2320 *w=new intvec(IDELEMS(h2));
2321 for (i=0;i<IDELEMS(h2);i++)
2322 ((**w)[i])=(*wtmp)[i+length];
2323 }
2324 if (wtmp!=NULL) delete wtmp;
2325
2326 if (T==NULL)
2327 {
2328 for (i=0;i<IDELEMS(s_temp1);i++)
2329 {
2330 if (s_temp1->m[i]!=NULL)
2331 {
2332 if (((int)pGetComp(s_temp1->m[i]))<=length)
2333 {
2334 p_Delete(&(s_temp1->m[i]),currRing);
2335 }
2336 else
2337 {
2338 p_Shift(&(s_temp1->m[i]),-length,currRing);
2339 }
2340 }
2341 }
2342 }
2343 else
2344 {
2345 *T=mpNew(IDELEMS(s_temp1),IDELEMS(h2));
2346 for (i=0;i<IDELEMS(s_temp1);i++)
2347 {
2348 if (s_temp1->m[i]!=NULL)
2349 {
2350 if (((int)pGetComp(s_temp1->m[i]))<=length)
2351 {
2352 do
2353 {
2354 p_LmDelete(&(s_temp1->m[i]),currRing);
2355 } while((int)pGetComp(s_temp1->m[i])<=length);
2356 poly q = prMoveR( s_temp1->m[i], syz_ring,orig_ring);
2357 s_temp1->m[i] = NULL;
2358 if (q!=NULL)
2359 {
2360 q=pReverse(q);
2361 do
2362 {
2363 poly p = q;
2364 long t=pGetComp(p);
2365 pIter(q);
2366 pNext(p) = NULL;
2367 pSetComp(p,0);
2368 pSetmComp(p);
2369 pTest(p);
2370 MATELEM(*T,(int)t-length,i) = pAdd(MATELEM(*T,(int)t-length,i),p);
2371 } while (q != NULL);
2372 }
2373 }
2374 else
2375 {
2376 p_Shift(&(s_temp1->m[i]),-length,currRing);
2377 }
2378 }
2379 }
2380 }
2381 s_temp1->rank = rk;
2382 idSkipZeroes(s_temp1);
2383
2384 if (syz_ring!=orig_ring)
2385 {
2386 rChangeCurrRing(orig_ring);
2387 s_temp1 = idrMoveR_NoSort(s_temp1, syz_ring, orig_ring);
2388 rDelete(syz_ring);
2389 // Hmm ... here seems to be a memory leak
2390 // However, simply deleting it causes memory trouble
2391 // idDelete(&s_temp);
2392 }
2393 idTest(s_temp1);
2394 return s_temp1;
2395 }
2396 #endif
2397
2398 /*2
2399 * represents (h1+h2)/h2=h1/(h1 intersect h2)
2400 */
2401 //ideal idModulo (ideal h2,ideal h1)
idModulo(ideal h2,ideal h1,tHomog hom,intvec ** w,matrix * T,GbVariant alg)2402 ideal idModulo (ideal h2,ideal h1, tHomog hom, intvec ** w, matrix *T, GbVariant alg)
2403 {
2404 #ifdef HAVE_SHIFTBBA
2405 if (rIsLPRing(currRing))
2406 return idModuloLP(h2,h1,hom,w,T,alg);
2407 #endif
2408 intvec *wtmp=NULL;
2409 if (T!=NULL) idDelete((ideal*)T);
2410
2411 int i,flength=0,slength,length;
2412
2413 if (idIs0(h2))
2414 return idFreeModule(si_max(1,h2->ncols));
2415 if (!idIs0(h1))
2416 flength = id_RankFreeModule(h1,currRing);
2417 slength = id_RankFreeModule(h2,currRing);
2418 length = si_max(flength,slength);
2419 BOOLEAN inputIsIdeal=FALSE;
2420 if (length==0)
2421 {
2422 length = 1;
2423 inputIsIdeal=TRUE;
2424 }
2425 if ((w!=NULL)&&((*w)!=NULL))
2426 {
2427 //Print("input weights:");(*w)->show(1);PrintLn();
2428 int d;
2429 int k;
2430 wtmp=new intvec(length+IDELEMS(h2));
2431 for (i=0;i<length;i++)
2432 ((*wtmp)[i])=(**w)[i];
2433 for (i=0;i<IDELEMS(h2);i++)
2434 {
2435 poly p=h2->m[i];
2436 if (p!=NULL)
2437 {
2438 d = p_Deg(p,currRing);
2439 k= pGetComp(p);
2440 if (slength>0) k--;
2441 d +=((**w)[k]);
2442 ((*wtmp)[i+length]) = d;
2443 }
2444 }
2445 //Print("weights:");wtmp->show(1);PrintLn();
2446 }
2447 ideal s_temp1;
2448 ring orig_ring=currRing;
2449 ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE);
2450 rSetSyzComp(length,syz_ring);
2451 {
2452 rChangeCurrRing(syz_ring);
2453 ideal s1,s2;
2454
2455 if (syz_ring != orig_ring)
2456 {
2457 s1 = idrCopyR_NoSort(h1, orig_ring, syz_ring);
2458 s2 = idrCopyR_NoSort(h2, orig_ring, syz_ring);
2459 }
2460 else
2461 {
2462 s1=idCopy(h1);
2463 s2=idCopy(h2);
2464 }
2465
2466 unsigned save_opt,save_opt2;
2467 SI_SAVE_OPT1(save_opt);
2468 SI_SAVE_OPT2(save_opt2);
2469 if (T==NULL) si_opt_1 |= Sy_bit(OPT_REDTAIL);
2470 si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
2471 s_temp1 = idPrepare(s2,s1,testHomog,length,w,alg);
2472 SI_RESTORE_OPT1(save_opt);
2473 SI_RESTORE_OPT2(save_opt2);
2474 }
2475
2476 //if (wtmp!=NULL) Print("output weights:");wtmp->show(1);PrintLn();
2477 if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
2478 {
2479 delete *w;
2480 *w=new intvec(IDELEMS(h2));
2481 for (i=0;i<IDELEMS(h2);i++)
2482 ((**w)[i])=(*wtmp)[i+length];
2483 }
2484 if (wtmp!=NULL) delete wtmp;
2485
2486 ideal result=idInit(IDELEMS(s_temp1),IDELEMS(h2));
2487 s_temp1=idExtractG_T_S(s_temp1,T,&result,length,IDELEMS(h2),inputIsIdeal,orig_ring,syz_ring);
2488
2489 idDelete(&s_temp1);
2490 if (syz_ring!=orig_ring)
2491 {
2492 rDelete(syz_ring);
2493 }
2494 idTest(h2);
2495 idTest(h1);
2496 idTest(result);
2497 if (T!=NULL) idTest((ideal)*T);
2498 return result;
2499 }
2500
2501 /*
2502 *computes module-weights for liftings of homogeneous modules
2503 */
2504 #if 0
2505 static intvec * idMWLift(ideal mod,intvec * weights)
2506 {
2507 if (idIs0(mod)) return new intvec(2);
2508 int i=IDELEMS(mod);
2509 while ((i>0) && (mod->m[i-1]==NULL)) i--;
2510 intvec *result = new intvec(i+1);
2511 while (i>0)
2512 {
2513 (*result)[i]=currRing->pFDeg(mod->m[i],currRing)+(*weights)[pGetComp(mod->m[i])];
2514 }
2515 return result;
2516 }
2517 #endif
2518
2519 /*2
2520 *sorts the kbase for idCoef* in a special way (lexicographically
2521 *with x_max,...,x_1)
2522 */
idCreateSpecialKbase(ideal kBase,intvec ** convert)2523 ideal idCreateSpecialKbase(ideal kBase,intvec ** convert)
2524 {
2525 int i;
2526 ideal result;
2527
2528 if (idIs0(kBase)) return NULL;
2529 result = idInit(IDELEMS(kBase),kBase->rank);
2530 *convert = idSort(kBase,FALSE);
2531 for (i=0;i<(*convert)->length();i++)
2532 {
2533 result->m[i] = pCopy(kBase->m[(**convert)[i]-1]);
2534 }
2535 return result;
2536 }
2537
2538 /*2
2539 *returns the index of a given monom in the list of the special kbase
2540 */
idIndexOfKBase(poly monom,ideal kbase)2541 int idIndexOfKBase(poly monom, ideal kbase)
2542 {
2543 int j=IDELEMS(kbase);
2544
2545 while ((j>0) && (kbase->m[j-1]==NULL)) j--;
2546 if (j==0) return -1;
2547 int i=(currRing->N);
2548 while (i>0)
2549 {
2550 loop
2551 {
2552 if (pGetExp(monom,i)>pGetExp(kbase->m[j-1],i)) return -1;
2553 if (pGetExp(monom,i)==pGetExp(kbase->m[j-1],i)) break;
2554 j--;
2555 if (j==0) return -1;
2556 }
2557 if (i==1)
2558 {
2559 while(j>0)
2560 {
2561 if (pGetComp(monom)==pGetComp(kbase->m[j-1])) return j-1;
2562 if (pGetComp(monom)>pGetComp(kbase->m[j-1])) return -1;
2563 j--;
2564 }
2565 }
2566 i--;
2567 }
2568 return -1;
2569 }
2570
2571 /*2
2572 *decomposes the monom in a part of coefficients described by the
2573 *complement of how and a monom in variables occuring in how, the
2574 *index of which in kbase is returned as integer pos (-1 if it don't
2575 *exists)
2576 */
idDecompose(poly monom,poly how,ideal kbase,int * pos)2577 poly idDecompose(poly monom, poly how, ideal kbase, int * pos)
2578 {
2579 int i;
2580 poly coeff=pOne(), base=pOne();
2581
2582 for (i=1;i<=(currRing->N);i++)
2583 {
2584 if (pGetExp(how,i)>0)
2585 {
2586 pSetExp(base,i,pGetExp(monom,i));
2587 }
2588 else
2589 {
2590 pSetExp(coeff,i,pGetExp(monom,i));
2591 }
2592 }
2593 pSetComp(base,pGetComp(monom));
2594 pSetm(base);
2595 pSetCoeff(coeff,nCopy(pGetCoeff(monom)));
2596 pSetm(coeff);
2597 *pos = idIndexOfKBase(base,kbase);
2598 if (*pos<0)
2599 p_Delete(&coeff,currRing);
2600 p_Delete(&base,currRing);
2601 return coeff;
2602 }
2603
2604 /*2
2605 *returns a matrix A of coefficients with kbase*A=arg
2606 *if all monomials in variables of how occur in kbase
2607 *the other are deleted
2608 */
idCoeffOfKBase(ideal arg,ideal kbase,poly how)2609 matrix idCoeffOfKBase(ideal arg, ideal kbase, poly how)
2610 {
2611 matrix result;
2612 ideal tempKbase;
2613 poly p,q;
2614 intvec * convert;
2615 int i=IDELEMS(kbase),j=IDELEMS(arg),k,pos;
2616 #if 0
2617 while ((i>0) && (kbase->m[i-1]==NULL)) i--;
2618 if (idIs0(arg))
2619 return mpNew(i,1);
2620 while ((j>0) && (arg->m[j-1]==NULL)) j--;
2621 result = mpNew(i,j);
2622 #else
2623 result = mpNew(i, j);
2624 while ((j>0) && (arg->m[j-1]==NULL)) j--;
2625 #endif
2626
2627 tempKbase = idCreateSpecialKbase(kbase,&convert);
2628 for (k=0;k<j;k++)
2629 {
2630 p = arg->m[k];
2631 while (p!=NULL)
2632 {
2633 q = idDecompose(p,how,tempKbase,&pos);
2634 if (pos>=0)
2635 {
2636 MATELEM(result,(*convert)[pos],k+1) =
2637 pAdd(MATELEM(result,(*convert)[pos],k+1),q);
2638 }
2639 else
2640 p_Delete(&q,currRing);
2641 pIter(p);
2642 }
2643 }
2644 idDelete(&tempKbase);
2645 return result;
2646 }
2647
idDeleteComps(ideal arg,int * red_comp,int del)2648 static void idDeleteComps(ideal arg,int* red_comp,int del)
2649 // red_comp is an array [0..args->rank]
2650 {
2651 int i,j;
2652 poly p;
2653
2654 for (i=IDELEMS(arg)-1;i>=0;i--)
2655 {
2656 p = arg->m[i];
2657 while (p!=NULL)
2658 {
2659 j = pGetComp(p);
2660 if (red_comp[j]!=j)
2661 {
2662 pSetComp(p,red_comp[j]);
2663 pSetmComp(p);
2664 }
2665 pIter(p);
2666 }
2667 }
2668 (arg->rank) -= del;
2669 }
2670
2671 /*2
2672 * returns the presentation of an isomorphic, minimally
2673 * embedded module (arg represents the quotient!)
2674 */
idMinEmbedding(ideal arg,BOOLEAN inPlace,intvec ** w)2675 ideal idMinEmbedding(ideal arg,BOOLEAN inPlace, intvec **w)
2676 {
2677 if (idIs0(arg)) return idInit(1,arg->rank);
2678 int i,next_gen,next_comp;
2679 ideal res=arg;
2680 if (!inPlace) res = idCopy(arg);
2681 res->rank=si_max(res->rank,id_RankFreeModule(res,currRing));
2682 int *red_comp=(int*)omAlloc((res->rank+1)*sizeof(int));
2683 for (i=res->rank;i>=0;i--) red_comp[i]=i;
2684
2685 int del=0;
2686 loop
2687 {
2688 next_gen = id_ReadOutPivot(res, &next_comp, currRing);
2689 if (next_gen<0) break;
2690 del++;
2691 syGaussForOne(res,next_gen,next_comp,0,IDELEMS(res));
2692 for(i=next_comp+1;i<=arg->rank;i++) red_comp[i]--;
2693 if ((w !=NULL)&&(*w!=NULL))
2694 {
2695 for(i=next_comp;i<(*w)->length();i++) (**w)[i-1]=(**w)[i];
2696 }
2697 }
2698
2699 idDeleteComps(res,red_comp,del);
2700 idSkipZeroes(res);
2701 omFree(red_comp);
2702
2703 if ((w !=NULL)&&(*w!=NULL) &&(del>0))
2704 {
2705 int nl=si_max((*w)->length()-del,1);
2706 intvec *wtmp=new intvec(nl);
2707 for(i=0;i<res->rank;i++) (*wtmp)[i]=(**w)[i];
2708 delete *w;
2709 *w=wtmp;
2710 }
2711 return res;
2712 }
2713
2714 #include "polys/clapsing.h"
2715
2716 #if 0
2717 poly id_GCD(poly f, poly g, const ring r)
2718 {
2719 ring save_r=currRing;
2720 rChangeCurrRing(r);
2721 ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2722 intvec *w = NULL;
2723 ideal S=idSyzygies(I,testHomog,&w);
2724 if (w!=NULL) delete w;
2725 poly gg=pTakeOutComp(&(S->m[0]),2);
2726 idDelete(&S);
2727 poly gcd_p=singclap_pdivide(f,gg,r);
2728 p_Delete(&gg,r);
2729 rChangeCurrRing(save_r);
2730 return gcd_p;
2731 }
2732 #else
id_GCD(poly f,poly g,const ring r)2733 poly id_GCD(poly f, poly g, const ring r)
2734 {
2735 ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2736 intvec *w = NULL;
2737
2738 ring save_r = currRing;
2739 rChangeCurrRing(r);
2740 ideal S=idSyzygies(I,testHomog,&w);
2741 rChangeCurrRing(save_r);
2742
2743 if (w!=NULL) delete w;
2744 poly gg=p_TakeOutComp(&(S->m[0]), 2, r);
2745 id_Delete(&S, r);
2746 poly gcd_p=singclap_pdivide(f,gg, r);
2747 p_Delete(&gg, r);
2748
2749 return gcd_p;
2750 }
2751 #endif
2752
2753 #if 0
2754 /*2
2755 * xx,q: arrays of length 0..rl-1
2756 * xx[i]: SB mod q[i]
2757 * assume: char=0
2758 * assume: q[i]!=0
2759 * destroys xx
2760 */
2761 ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring R)
2762 {
2763 int cnt=IDELEMS(xx[0])*xx[0]->nrows;
2764 ideal result=idInit(cnt,xx[0]->rank);
2765 result->nrows=xx[0]->nrows; // for lifting matrices
2766 result->ncols=xx[0]->ncols; // for lifting matrices
2767 int i,j;
2768 poly r,h,hh,res_p;
2769 number *x=(number *)omAlloc(rl*sizeof(number));
2770 for(i=cnt-1;i>=0;i--)
2771 {
2772 res_p=NULL;
2773 loop
2774 {
2775 r=NULL;
2776 for(j=rl-1;j>=0;j--)
2777 {
2778 h=xx[j]->m[i];
2779 if ((h!=NULL)
2780 &&((r==NULL)||(p_LmCmp(r,h,R)==-1)))
2781 r=h;
2782 }
2783 if (r==NULL) break;
2784 h=p_Head(r, R);
2785 for(j=rl-1;j>=0;j--)
2786 {
2787 hh=xx[j]->m[i];
2788 if ((hh!=NULL) && (p_LmCmp(r,hh, R)==0))
2789 {
2790 x[j]=p_GetCoeff(hh, R);
2791 hh=p_LmFreeAndNext(hh, R);
2792 xx[j]->m[i]=hh;
2793 }
2794 else
2795 x[j]=n_Init(0, R->cf); // is R->cf really n_Q???, yes!
2796 }
2797
2798 number n=n_ChineseRemainder(x,q,rl, R->cf);
2799
2800 for(j=rl-1;j>=0;j--)
2801 {
2802 x[j]=NULL; // nlInit(0...) takes no memory
2803 }
2804 if (n_IsZero(n, R->cf)) p_Delete(&h, R);
2805 else
2806 {
2807 p_SetCoeff(h,n, R);
2808 //Print("new mon:");pWrite(h);
2809 res_p=p_Add_q(res_p, h, R);
2810 }
2811 }
2812 result->m[i]=res_p;
2813 }
2814 omFree(x);
2815 for(i=rl-1;i>=0;i--) id_Delete(&(xx[i]), R);
2816 omFree(xx);
2817 return result;
2818 }
2819 #endif
2820 /* currently unused:
2821 ideal idChineseRemainder(ideal *xx, intvec *iv)
2822 {
2823 int rl=iv->length();
2824 number *q=(number *)omAlloc(rl*sizeof(number));
2825 int i;
2826 for(i=0; i<rl; i++)
2827 {
2828 q[i]=nInit((*iv)[i]);
2829 }
2830 return idChineseRemainder(xx,q,rl);
2831 }
2832 */
2833 /*
2834 * lift ideal with coeffs over Z (mod N) to Q via Farey
2835 */
id_Farey(ideal x,number N,const ring r)2836 ideal id_Farey(ideal x, number N, const ring r)
2837 {
2838 int cnt=IDELEMS(x)*x->nrows;
2839 ideal result=idInit(cnt,x->rank);
2840 result->nrows=x->nrows; // for lifting matrices
2841 result->ncols=x->ncols; // for lifting matrices
2842
2843 int i;
2844 for(i=cnt-1;i>=0;i--)
2845 {
2846 result->m[i]=p_Farey(x->m[i],N,r);
2847 }
2848 return result;
2849 }
2850
2851
2852
2853
2854 // uses glabl vars via pSetModDeg
2855 /*
2856 BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
2857 {
2858 if ((Q!=NULL) && (!idHomIdeal(Q,NULL))) { PrintS(" Q not hom\n"); return FALSE;}
2859 if (idIs0(m)) return TRUE;
2860
2861 int cmax=-1;
2862 int i;
2863 poly p=NULL;
2864 int length=IDELEMS(m);
2865 poly* P=m->m;
2866 for (i=length-1;i>=0;i--)
2867 {
2868 p=P[i];
2869 if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
2870 }
2871 if (w != NULL)
2872 if (w->length()+1 < cmax)
2873 {
2874 // Print("length: %d - %d \n", w->length(),cmax);
2875 return FALSE;
2876 }
2877
2878 if(w!=NULL)
2879 p_SetModDeg(w, currRing);
2880
2881 for (i=length-1;i>=0;i--)
2882 {
2883 p=P[i];
2884 poly q=p;
2885 if (p!=NULL)
2886 {
2887 int d=p_FDeg(p,currRing);
2888 loop
2889 {
2890 pIter(p);
2891 if (p==NULL) break;
2892 if (d!=p_FDeg(p,currRing))
2893 {
2894 //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
2895 if(w!=NULL)
2896 p_SetModDeg(NULL, currRing);
2897 return FALSE;
2898 }
2899 }
2900 }
2901 }
2902
2903 if(w!=NULL)
2904 p_SetModDeg(NULL, currRing);
2905
2906 return TRUE;
2907 }
2908 */
2909
2910 /// keeps the first k (>= 1) entries of the given ideal
2911 /// (Note that the kept polynomials may be zero.)
idKeepFirstK(ideal id,const int k)2912 void idKeepFirstK(ideal id, const int k)
2913 {
2914 for (int i = IDELEMS(id)-1; i >= k; i--)
2915 {
2916 if (id->m[i] != NULL) pDelete(&id->m[i]);
2917 }
2918 int kk=k;
2919 if (k==0) kk=1; /* ideals must have at least one element(0)*/
2920 pEnlargeSet(&(id->m), IDELEMS(id), kk-IDELEMS(id));
2921 IDELEMS(id) = kk;
2922 }
2923
2924 typedef struct
2925 {
2926 poly p;
2927 int index;
2928 } poly_sort;
2929
pCompare_qsort(const void * a,const void * b)2930 int pCompare_qsort(const void *a, const void *b)
2931 {
2932 return (p_Compare(((poly_sort *)a)->p, ((poly_sort *)b)->p,currRing));
2933 }
2934
idSort_qsort(poly_sort * id_sort,int idsize)2935 void idSort_qsort(poly_sort *id_sort, int idsize)
2936 {
2937 qsort(id_sort, idsize, sizeof(poly_sort), pCompare_qsort);
2938 }
2939
2940 /*2
2941 * ideal id = (id[i])
2942 * if id[i] = id[j] then id[j] is deleted for j > i
2943 */
idDelEquals(ideal id)2944 void idDelEquals(ideal id)
2945 {
2946 int idsize = IDELEMS(id);
2947 poly_sort *id_sort = (poly_sort *)omAlloc0(idsize*sizeof(poly_sort));
2948 for (int i = 0; i < idsize; i++)
2949 {
2950 id_sort[i].p = id->m[i];
2951 id_sort[i].index = i;
2952 }
2953 idSort_qsort(id_sort, idsize);
2954 int index, index_i, index_j;
2955 int i = 0;
2956 for (int j = 1; j < idsize; j++)
2957 {
2958 if (id_sort[i].p != NULL && pEqualPolys(id_sort[i].p, id_sort[j].p))
2959 {
2960 index_i = id_sort[i].index;
2961 index_j = id_sort[j].index;
2962 if (index_j > index_i)
2963 {
2964 index = index_j;
2965 }
2966 else
2967 {
2968 index = index_i;
2969 i = j;
2970 }
2971 pDelete(&id->m[index]);
2972 }
2973 else
2974 {
2975 i = j;
2976 }
2977 }
2978 omFreeSize((ADDRESS)(id_sort), idsize*sizeof(poly_sort));
2979 }
2980
2981 STATIC_VAR int * id_satstdSaturatingVariables=NULL;
2982
id_sat_vars_sp(kStrategy strat)2983 static BOOLEAN id_sat_vars_sp(kStrategy strat)
2984 {
2985 BOOLEAN b = FALSE; // set b to TRUE, if spoly was changed,
2986 // let it remain FALSE otherwise
2987 if (strat->P.t_p==NULL)
2988 {
2989 poly p=strat->P.p;
2990
2991 // iterate over all terms of p and
2992 // compute the minimum mm of all exponent vectors
2993 int *mm=(int*)omAlloc((1+rVar(currRing))*sizeof(int));
2994 int *m0=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
2995 p_GetExpV(p,mm,currRing);
2996 bool nonTrivialSaturationToBeDone=true;
2997 for (p=pNext(p); p!=NULL; pIter(p))
2998 {
2999 nonTrivialSaturationToBeDone=false;
3000 p_GetExpV(p,m0,currRing);
3001 for (int i=rVar(currRing); i>0; i--)
3002 {
3003 if (id_satstdSaturatingVariables[i]!=0)
3004 {
3005 mm[i]=si_min(mm[i],m0[i]);
3006 if (mm[i]>0) nonTrivialSaturationToBeDone=true;
3007 }
3008 else mm[i]=0;
3009 }
3010 // abort if the minimum is zero in each component
3011 if (!nonTrivialSaturationToBeDone) break;
3012 }
3013 if (nonTrivialSaturationToBeDone)
3014 {
3015 // std::cout << "simplifying!" << std::endl;
3016 if (TEST_OPT_PROT) { PrintS("S"); mflush(); }
3017 p=p_Copy(strat->P.p,currRing);
3018 //pWrite(p);
3019 // for (int i=rVar(currRing); i>0; i--)
3020 // if (mm[i]!=0) Print("x_%d:%d ",i,mm[i]);
3021 //PrintLn();
3022 strat->P.Init(currRing);
3023 //memset(&strat->P,0,sizeof(strat->P));
3024 strat->P.tailRing = strat->tailRing;
3025 strat->P.p=p;
3026 while(p!=NULL)
3027 {
3028 for (int i=rVar(currRing); i>0; i--)
3029 {
3030 p_SubExp(p,i,mm[i],currRing);
3031 }
3032 p_Setm(p,currRing);
3033 pIter(p);
3034 }
3035 b = TRUE;
3036 }
3037 omFree(mm);
3038 omFree(m0);
3039 }
3040 else
3041 {
3042 poly p=strat->P.t_p;
3043
3044 // iterate over all terms of p and
3045 // compute the minimum mm of all exponent vectors
3046 int *mm=(int*)omAlloc((1+rVar(currRing))*sizeof(int));
3047 int *m0=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
3048 p_GetExpV(p,mm,strat->tailRing);
3049 bool nonTrivialSaturationToBeDone=true;
3050 for (p = pNext(p); p!=NULL; pIter(p))
3051 {
3052 nonTrivialSaturationToBeDone=false;
3053 p_GetExpV(p,m0,strat->tailRing);
3054 for(int i=rVar(currRing); i>0; i--)
3055 {
3056 if(id_satstdSaturatingVariables[i]!=0)
3057 {
3058 mm[i]=si_min(mm[i],m0[i]);
3059 if (mm[i]>0) nonTrivialSaturationToBeDone = true;
3060 }
3061 else mm[i]=0;
3062 }
3063 // abort if the minimum is zero in each component
3064 if (!nonTrivialSaturationToBeDone) break;
3065 }
3066 if (nonTrivialSaturationToBeDone)
3067 {
3068 if (TEST_OPT_PROT) { PrintS("S"); mflush(); }
3069 p=p_Copy(strat->P.t_p,strat->tailRing);
3070 //p_Write(p,strat->tailRing);
3071 // for (int i=rVar(currRing); i>0; i--)
3072 // if (mm[i]!=0) Print("x_%d:%d ",i,mm[i]);
3073 //PrintLn();
3074 strat->P.Init(currRing);
3075 //memset(&strat->P,0,sizeof(strat->P));
3076 strat->P.tailRing = strat->tailRing;
3077 strat->P.t_p=p;
3078 while(p!=NULL)
3079 {
3080 for(int i=rVar(currRing); i>0; i--)
3081 {
3082 p_SubExp(p,i,mm[i],strat->tailRing);
3083 }
3084 p_Setm(p,strat->tailRing);
3085 pIter(p);
3086 }
3087 strat->P.GetP();
3088 b = TRUE;
3089 }
3090 omFree(mm);
3091 omFree(m0);
3092 }
3093 return b; // return TRUE if sp was changed, FALSE if not
3094 }
3095
id_Satstd(const ideal I,ideal J,const ring r)3096 ideal id_Satstd(const ideal I, ideal J, const ring r)
3097 {
3098 ring save=currRing;
3099 if (currRing!=r) rChangeCurrRing(r);
3100 idSkipZeroes(J);
3101 id_satstdSaturatingVariables=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
3102 int k=IDELEMS(J);
3103 if (k>1)
3104 {
3105 for (int i=0; i<k; i++)
3106 {
3107 poly x = J->m[i];
3108 int li = p_Var(x,r);
3109 if (li>0)
3110 id_satstdSaturatingVariables[li]=1;
3111 else
3112 {
3113 if (currRing!=save) rChangeCurrRing(save);
3114 WerrorS("ideal generators must be variables");
3115 return NULL;
3116 }
3117 }
3118 }
3119 else
3120 {
3121 poly x = J->m[0];
3122 for (int i=1; i<=r->N; i++)
3123 {
3124 int li = p_GetExp(x,i,r);
3125 if (li==1)
3126 id_satstdSaturatingVariables[i]=1;
3127 else if (li>1)
3128 {
3129 if (currRing!=save) rChangeCurrRing(save);
3130 Werror("exponent(x(%d)^%d) must be 0 or 1",i,li);
3131 return NULL;
3132 }
3133 }
3134 }
3135 ideal res=kStd(I,r->qideal,testHomog,NULL,NULL,0,0,NULL,id_sat_vars_sp);
3136 omFreeSize(id_satstdSaturatingVariables,(1+rVar(currRing))*sizeof(int));
3137 id_satstdSaturatingVariables=NULL;
3138 if (currRing!=save) rChangeCurrRing(save);
3139 return res;
3140 }
3141
syGetAlgorithm(char * n,const ring r,const ideal)3142 GbVariant syGetAlgorithm(char *n, const ring r, const ideal /*M*/)
3143 {
3144 GbVariant alg=GbDefault;
3145 if (strcmp(n,"default")==0) alg=GbDefault;
3146 else if (strcmp(n,"slimgb")==0) alg=GbSlimgb;
3147 else if (strcmp(n,"std")==0) alg=GbStd;
3148 else if (strcmp(n,"sba")==0) alg=GbSba;
3149 else if (strcmp(n,"singmatic")==0) alg=GbSingmatic;
3150 else if (strcmp(n,"groebner")==0) alg=GbGroebner;
3151 else if (strcmp(n,"modstd")==0) alg=GbModstd;
3152 else if (strcmp(n,"ffmod")==0) alg=GbFfmod;
3153 else if (strcmp(n,"nfmod")==0) alg=GbNfmod;
3154 else if (strcmp(n,"std:sat")==0) alg=GbStdSat;
3155 else Warn(">>%s<< is an unknown algorithm",n);
3156
3157 if (alg==GbSlimgb) // test conditions for slimgb
3158 {
3159 if(rHasGlobalOrdering(r)
3160 &&(!rIsNCRing(r))
3161 &&(r->qideal==NULL)
3162 &&(!rField_is_Ring(r)))
3163 {
3164 return GbSlimgb;
3165 }
3166 if (TEST_OPT_PROT)
3167 WarnS("requires: coef:field, commutative, global ordering, not qring");
3168 }
3169 else if (alg==GbSba) // cond. for sba
3170 {
3171 if(rField_is_Domain(r)
3172 &&(!rIsNCRing(r))
3173 &&(rHasGlobalOrdering(r)))
3174 {
3175 return GbSba;
3176 }
3177 if (TEST_OPT_PROT)
3178 WarnS("requires: coef:domain, commutative, global ordering");
3179 }
3180 else if (alg==GbGroebner) // cond. for groebner
3181 {
3182 return GbGroebner;
3183 }
3184 else if(alg==GbModstd) // cond for modstd: Q or Q(a)
3185 {
3186 if(ggetid("modStd")==NULL)
3187 {
3188 WarnS(">>modStd<< not found");
3189 }
3190 else if(rField_is_Q(r)
3191 &&(!rIsNCRing(r))
3192 &&(rHasGlobalOrdering(r)))
3193 {
3194 return GbModstd;
3195 }
3196 if (TEST_OPT_PROT)
3197 WarnS("requires: coef:QQ, commutative, global ordering");
3198 }
3199 else if(alg==GbStdSat) // cond for std:sat: 2 blocks of variables
3200 {
3201 if(ggetid("satstd")==NULL)
3202 {
3203 WarnS(">>satstd<< not found");
3204 }
3205 else
3206 {
3207 return GbStdSat;
3208 }
3209 }
3210
3211 return GbStd; // no conditions for std
3212 }
3213 //----------------------------------------------------------------------------
3214 // GB-algorithms and their pre-conditions
3215 // std slimgb sba singmatic modstd ffmod nfmod groebner
3216 // + + + - + - - + coeffs: QQ
3217 // + + + + - - - + coeffs: ZZ/p
3218 // + + + - ? - + + coeffs: K[a]/f
3219 // + + + - ? + - + coeffs: K(a)
3220 // + - + - - - - + coeffs: domain, not field
3221 // + - - - - - - + coeffs: zero-divisors
3222 // + + + + - ? ? + also for modules: C
3223 // + + - + - ? ? + also for modules: all orderings
3224 // + + - - - - - + exterior algebra
3225 // + + - - - - - + G-algebra
3226 // + + + + + + + + degree ordering
3227 // + - + + + + + + non-degree ordering
3228 // - - - + + + + + parallel
3229