My Project
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 
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 */
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;
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 
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));
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 
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 */
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);
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))
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);
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 */
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  }
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  */
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;
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 
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
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 */
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);
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)
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  }
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 */
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,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 
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 
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 /// 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
1105 ideal 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 */
1324 void 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 */
1389 static 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 */
1494 ideal 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 */
1593 ideal 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  for (k=0;; k++)
1634  {
1635  if (origR->order[k]!=0) ordersize++;
1636  else break;
1637  }
1638 #if 0
1639  if (rIsPluralRing(origR)) // we have too keep the odering: it may be needed
1640  // for G-algebra
1641  {
1642  for (k=0;k<ordersize-1; k++)
1643  {
1644  block0[k+1] = origR->block0[k];
1645  block1[k+1] = origR->block1[k];
1646  ord[k+1] = origR->order[k];
1647  if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1648  }
1649  }
1650  else
1651  {
1652  block0[1] = 1;
1653  block1[1] = (currRing->N);
1654  if (origR->OrdSgn==1) ord[1] = ringorder_wp;
1655  else ord[1] = ringorder_ws;
1656  wv[1]=(int*)omAlloc0((currRing->N)*sizeof(int));
1657  double wNsqr = (double)2.0 / (double)(currRing->N);
1659  int *x= (int * )omAlloc(2 * ((currRing->N) + 1) * sizeof(int));
1660  int sl=IDELEMS(h1) - 1;
1661  wCall(h1->m, sl, x, wNsqr);
1662  for (sl = (currRing->N); sl!=0; sl--)
1663  wv[1][sl-1] = x[sl + (currRing->N) + 1];
1664  omFreeSize((ADDRESS)x, 2 * ((currRing->N) + 1) * sizeof(int));
1665 
1666  ord[2]=ringorder_C;
1667  ord[3]=0;
1668  }
1669 #else
1670 #endif
1671  if ((hom==TRUE) && (origR->OrdSgn==1) && (!rIsPluralRing(origR)))
1672  {
1673  #if 1
1674  // we change to an ordering:
1675  // aa(1,1,1,...,0,0,0),wp(...),C
1676  // this seems to be better than version 2 below,
1677  // according to Tst/../elimiate_[3568].tat (- 17 %)
1678  ord=(rRingOrder_t*)omAlloc0(4*sizeof(rRingOrder_t));
1679  block0=(int*)omAlloc0(4*sizeof(int));
1680  block1=(int*)omAlloc0(4*sizeof(int));
1681  wv=(int**) omAlloc0(4*sizeof(int**));
1682  block0[0] = block0[1] = 1;
1683  block1[0] = block1[1] = rVar(origR);
1684  wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1685  // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1686  // ignore it
1687  ord[0] = ringorder_aa;
1688  for (j=0;j<rVar(origR);j++)
1689  if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1690  BOOLEAN wp=FALSE;
1691  for (j=0;j<rVar(origR);j++)
1692  if (p_Weight(j+1,origR)!=1) { wp=TRUE;break; }
1693  if (wp)
1694  {
1695  wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1696  for (j=0;j<rVar(origR);j++)
1697  wv[1][j]=p_Weight(j+1,origR);
1698  ord[1] = ringorder_wp;
1699  }
1700  else
1701  ord[1] = ringorder_dp;
1702  #else
1703  // we change to an ordering:
1704  // a(w1,...wn),wp(1,...0.....),C
1705  ord=(int*)omAlloc0(4*sizeof(int));
1706  block0=(int*)omAlloc0(4*sizeof(int));
1707  block1=(int*)omAlloc0(4*sizeof(int));
1708  wv=(int**) omAlloc0(4*sizeof(int**));
1709  block0[0] = block0[1] = 1;
1710  block1[0] = block1[1] = rVar(origR);
1711  wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1712  wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1713  ord[0] = ringorder_a;
1714  for (j=0;j<rVar(origR);j++)
1715  wv[0][j]=pWeight(j+1,origR);
1716  ord[1] = ringorder_wp;
1717  for (j=0;j<rVar(origR);j++)
1718  if (pGetExp(delVar,j+1)!=0) wv[1][j]=1;
1719  #endif
1720  ord[2] = ringorder_C;
1721  ord[3] = (rRingOrder_t)0;
1722  }
1723  else
1724  {
1725  // we change to an ordering:
1726  // aa(....),orig_ordering
1727  ord=(rRingOrder_t*)omAlloc0(ordersize*sizeof(rRingOrder_t));
1728  block0=(int*)omAlloc0(ordersize*sizeof(int));
1729  block1=(int*)omAlloc0(ordersize*sizeof(int));
1730  wv=(int**) omAlloc0(ordersize*sizeof(int**));
1731  for (k=0;k<ordersize-1; k++)
1732  {
1733  block0[k+1] = origR->block0[k];
1734  block1[k+1] = origR->block1[k];
1735  ord[k+1] = origR->order[k];
1736  if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1737  }
1738  block0[0] = 1;
1739  block1[0] = rVar(origR);
1740  wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1741  for (j=0;j<rVar(origR);j++)
1742  if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1743  // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1744  // ignore it
1745  ord[0] = ringorder_aa;
1746  }
1747  // fill in tmp ring to get back the data later on
1748  tmpR = rCopy0(origR,FALSE,FALSE); // qring==NULL
1749  //rUnComplete(tmpR);
1750  tmpR->p_Procs=NULL;
1751  tmpR->order = ord;
1752  tmpR->block0 = block0;
1753  tmpR->block1 = block1;
1754  tmpR->wvhdl = wv;
1755  rComplete(tmpR, 1);
1756 
1757 #ifdef HAVE_PLURAL
1758  /* update nc structure on tmpR */
1759  if (rIsPluralRing(origR))
1760  {
1761  if ( nc_rComplete(origR, tmpR, false) ) // no quotient ideal!
1762  {
1763  WerrorS("no elimination is possible: ordering condition is violated");
1764  // cleanup
1765  rDelete(tmpR);
1766  if (w!=NULL)
1767  delete w;
1768  return NULL;
1769  }
1770  }
1771 #endif
1772  // change into the new ring
1773  //pChangeRing((currRing->N),currRing->OrdSgn,ord,block0,block1,wv);
1774  rChangeCurrRing(tmpR);
1775 
1776  //h = idInit(IDELEMS(h1),h1->rank);
1777  // fetch data from the old ring
1778  //for (k=0;k<IDELEMS(h1);k++) h->m[k] = prCopyR( h1->m[k], origR);
1779  h=idrCopyR(h1,origR,currRing);
1780  if (origR->qideal!=NULL)
1781  {
1782  WarnS("eliminate in q-ring: experimental");
1783  ideal q=idrCopyR(origR->qideal,origR,currRing);
1784  ideal s=idSimpleAdd(h,q);
1785  idDelete(&h);
1786  idDelete(&q);
1787  h=s;
1788  }
1789  // compute GB
1790  if ((alg!=GbDefault)
1791  && (alg!=GbGroebner)
1792  && (alg!=GbModstd)
1793  && (alg!=GbSlimgb)
1794  && (alg!=GbSba)
1795  && (alg!=GbStd))
1796  {
1797  WarnS("wrong algorithm for GB");
1798  alg=GbDefault;
1799  }
1800  BITSET save2;
1801  SI_SAVE_OPT2(save2);
1803  hh=idGroebner(h,0,alg,hilb);
1804  SI_RESTORE_OPT2(save2);
1805  // go back to the original ring
1806  rChangeCurrRing(origR);
1807  i = IDELEMS(hh)-1;
1808  while ((i >= 0) && (hh->m[i] == NULL)) i--;
1809  j = -1;
1810  // fetch data from temp ring
1811  for (k=0; k<=i; k++)
1812  {
1813  l=(currRing->N);
1814  while ((l>0) && (p_GetExp( hh->m[k],l,tmpR)*pGetExp(delVar,l)==0)) l--;
1815  if (l==0)
1816  {
1817  j++;
1818  if (j >= IDELEMS(h3))
1819  {
1820  pEnlargeSet(&(h3->m),IDELEMS(h3),16);
1821  IDELEMS(h3) += 16;
1822  }
1823  h3->m[j] = prMoveR( hh->m[k], tmpR,origR);
1824  hh->m[k] = NULL;
1825  }
1826  }
1827  id_Delete(&hh, tmpR);
1828  idSkipZeroes(h3);
1829  rDelete(tmpR);
1830  if (w!=NULL)
1831  delete w;
1832  return h3;
1833 }
1834 
1835 #ifdef WITH_OLD_MINOR
1836 /*2
1837 * compute the which-th ar-minor of the matrix a
1838 */
1839 poly idMinor(matrix a, int ar, unsigned long which, ideal R)
1840 {
1841  int i,j/*,k,size*/;
1842  unsigned long curr;
1843  int *rowchoise,*colchoise;
1844  BOOLEAN rowch,colch;
1845  // ideal result;
1846  matrix tmp;
1847  poly p,q;
1848 
1849  rowchoise=(int *)omAlloc(ar*sizeof(int));
1850  colchoise=(int *)omAlloc(ar*sizeof(int));
1851  tmp=mpNew(ar,ar);
1852  curr = 0; /* index of current minor */
1853  idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1854  while (!rowch)
1855  {
1856  idInitChoise(ar,1,a->cols(),&colch,colchoise);
1857  while (!colch)
1858  {
1859  if (curr == which)
1860  {
1861  for (i=1; i<=ar; i++)
1862  {
1863  for (j=1; j<=ar; j++)
1864  {
1865  MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1866  }
1867  }
1868  p = mp_DetBareiss(tmp,currRing);
1869  if (p!=NULL)
1870  {
1871  if (R!=NULL)
1872  {
1873  q = p;
1874  p = kNF(R,currRing->qideal,q);
1875  p_Delete(&q,currRing);
1876  }
1877  }
1878  /*delete the matrix tmp*/
1879  for (i=1; i<=ar; i++)
1880  {
1881  for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1882  }
1883  idDelete((ideal*)&tmp);
1884  omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1885  omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1886  return (p);
1887  }
1888  curr++;
1889  idGetNextChoise(ar,a->cols(),&colch,colchoise);
1890  }
1891  idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1892  }
1893  return (poly) 1;
1894 }
1895 
1896 /*2
1897 * compute all ar-minors of the matrix a
1898 */
1899 ideal idMinors(matrix a, int ar, ideal R)
1900 {
1901  int i,j,/*k,*/size;
1902  int *rowchoise,*colchoise;
1903  BOOLEAN rowch,colch;
1904  ideal result;
1905  matrix tmp;
1906  poly p,q;
1907 
1908  i = binom(a->rows(),ar);
1909  j = binom(a->cols(),ar);
1910  size=i*j;
1911 
1912  rowchoise=(int *)omAlloc(ar*sizeof(int));
1913  colchoise=(int *)omAlloc(ar*sizeof(int));
1914  result=idInit(size,1);
1915  tmp=mpNew(ar,ar);
1916  // k = 0; /* the index in result*/
1917  idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1918  while (!rowch)
1919  {
1920  idInitChoise(ar,1,a->cols(),&colch,colchoise);
1921  while (!colch)
1922  {
1923  for (i=1; i<=ar; i++)
1924  {
1925  for (j=1; j<=ar; j++)
1926  {
1927  MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1928  }
1929  }
1930  p = mp_DetBareiss(tmp,currRing);
1931  if (p!=NULL)
1932  {
1933  if (R!=NULL)
1934  {
1935  q = p;
1936  p = kNF(R,currRing->qideal,q);
1937  p_Delete(&q,currRing);
1938  }
1939  }
1940  if (k>=size)
1941  {
1942  pEnlargeSet(&result->m,size,32);
1943  size += 32;
1944  }
1945  result->m[k] = p;
1946  k++;
1947  idGetNextChoise(ar,a->cols(),&colch,colchoise);
1948  }
1949  idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1950  }
1951  /*delete the matrix tmp*/
1952  for (i=1; i<=ar; i++)
1953  {
1954  for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1955  }
1956  idDelete((ideal*)&tmp);
1957  if (k==0)
1958  {
1959  k=1;
1960  result->m[0]=NULL;
1961  }
1962  omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1963  omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1964  pEnlargeSet(&result->m,size,k-size);
1965  IDELEMS(result) = k;
1966  return (result);
1967 }
1968 #else
1969 
1970 
1971 /// compute all ar-minors of the matrix a
1972 /// the caller of mpRecMin
1973 /// the elements of the result are not in R (if R!=NULL)
1974 ideal idMinors(matrix a, int ar, ideal R)
1975 {
1976 
1977  const ring origR=currRing;
1978  id_Test((ideal)a, origR);
1979 
1980  const int r = a->nrows;
1981  const int c = a->ncols;
1982 
1983  if((ar<=0) || (ar>r) || (ar>c))
1984  {
1985  Werror("%d-th minor, matrix is %dx%d",ar,r,c);
1986  return NULL;
1987  }
1988 
1989  ideal h = id_Matrix2Module(mp_Copy(a,origR),origR);
1990  long bound = sm_ExpBound(h,c,r,ar,origR);
1991  id_Delete(&h, origR);
1992 
1993  ring tmpR = sm_RingChange(origR,bound);
1994 
1995  matrix b = mpNew(r,c);
1996 
1997  for (int i=r*c-1;i>=0;i--)
1998  if (a->m[i] != NULL)
1999  b->m[i] = prCopyR(a->m[i],origR,tmpR);
2000 
2001  id_Test( (ideal)b, tmpR);
2002 
2003  if (R!=NULL)
2004  {
2005  R = idrCopyR(R,origR,tmpR); // TODO: overwrites R? memory leak?
2006  //if (ar>1) // otherwise done in mpMinorToResult
2007  //{
2008  // matrix bb=(matrix)kNF(R,currRing->qideal,(ideal)b);
2009  // bb->rank=b->rank; bb->nrows=b->nrows; bb->ncols=b->ncols;
2010  // idDelete((ideal*)&b); b=bb;
2011  //}
2012  id_Test( R, tmpR);
2013  }
2014 
2015  int size=binom(r,ar)*binom(c,ar);
2016  ideal result = idInit(size,1);
2017 
2018  int elems = 0;
2019 
2020  if(ar>1)
2021  mp_RecMin(ar-1,result,elems,b,r,c,NULL,R,tmpR);
2022  else
2023  mp_MinorToResult(result,elems,b,r,c,R,tmpR);
2024 
2025  id_Test( (ideal)b, tmpR);
2026 
2027  id_Delete((ideal *)&b, tmpR);
2028 
2029  if (R!=NULL) id_Delete(&R,tmpR);
2030 
2031  rChangeCurrRing(origR);
2032  result = idrMoveR(result,tmpR,origR);
2033  sm_KillModifiedRing(tmpR);
2034  idTest(result);
2035  return result;
2036 }
2037 #endif
2038 
2039 /*2
2040 *returns TRUE if id1 is a submodule of id2
2041 */
2042 BOOLEAN idIsSubModule(ideal id1,ideal id2)
2043 {
2044  int i;
2045  poly p;
2046 
2047  if (idIs0(id1)) return TRUE;
2048  for (i=0;i<IDELEMS(id1);i++)
2049  {
2050  if (id1->m[i] != NULL)
2051  {
2052  p = kNF(id2,currRing->qideal,id1->m[i]);
2053  if (p != NULL)
2054  {
2055  p_Delete(&p,currRing);
2056  return FALSE;
2057  }
2058  }
2059  }
2060  return TRUE;
2061 }
2062 
2064 {
2065  if ((Q!=NULL) && (!idHomIdeal(Q,NULL))) { PrintS(" Q not hom\n"); return FALSE;}
2066  if (idIs0(m)) return TRUE;
2067 
2068  int cmax=-1;
2069  int i;
2070  poly p=NULL;
2071  int length=IDELEMS(m);
2072  polyset P=m->m;
2073  for (i=length-1;i>=0;i--)
2074  {
2075  p=P[i];
2076  if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
2077  }
2078  if (w != NULL)
2079  if (w->length()+1 < cmax)
2080  {
2081  // Print("length: %d - %d \n", w->length(),cmax);
2082  return FALSE;
2083  }
2084 
2085  if(w!=NULL)
2087 
2088  for (i=length-1;i>=0;i--)
2089  {
2090  p=P[i];
2091  if (p!=NULL)
2092  {
2093  int d=currRing->pFDeg(p,currRing);
2094  loop
2095  {
2096  pIter(p);
2097  if (p==NULL) break;
2098  if (d!=currRing->pFDeg(p,currRing))
2099  {
2100  //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
2101  if(w!=NULL)
2103  return FALSE;
2104  }
2105  }
2106  }
2107  }
2108 
2109  if(w!=NULL)
2111 
2112  return TRUE;
2113 }
2114 
2115 ideal idSeries(int n,ideal M,matrix U,intvec *w)
2116 {
2117  for(int i=IDELEMS(M)-1;i>=0;i--)
2118  {
2119  if(U==NULL)
2120  M->m[i]=pSeries(n,M->m[i],NULL,w);
2121  else
2122  {
2123  M->m[i]=pSeries(n,M->m[i],MATELEM(U,i+1,i+1),w);
2124  MATELEM(U,i+1,i+1)=NULL;
2125  }
2126  }
2127  if(U!=NULL)
2128  idDelete((ideal*)&U);
2129  return M;
2130 }
2131 
2133 {
2134  int e=MATCOLS(i)*MATROWS(i);
2135  matrix r=mpNew(MATROWS(i),MATCOLS(i));
2136  r->rank=i->rank;
2137  int j;
2138  for(j=0; j<e; j++)
2139  {
2140  r->m[j]=pDiff(i->m[j],k);
2141  }
2142  return r;
2143 }
2144 
2145 matrix idDiffOp(ideal I, ideal J,BOOLEAN multiply)
2146 {
2147  matrix r=mpNew(IDELEMS(I),IDELEMS(J));
2148  int i,j;
2149  for(i=0; i<IDELEMS(I); i++)
2150  {
2151  for(j=0; j<IDELEMS(J); j++)
2152  {
2153  MATELEM(r,i+1,j+1)=pDiffOp(I->m[i],J->m[j],multiply);
2154  }
2155  }
2156  return r;
2157 }
2158 
2159 /*3
2160 *handles for some ideal operations the ring/syzcomp managment
2161 *returns all syzygies (componentwise-)shifted by -syzcomp
2162 *or -syzcomp-1 (in case of ideals as input)
2163 static ideal idHandleIdealOp(ideal arg,int syzcomp,int isIdeal=FALSE)
2164 {
2165  ring orig_ring=currRing;
2166  ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE); rChangeCurrRing(syz_ring);
2167  rSetSyzComp(length, syz_ring);
2168 
2169  ideal s_temp;
2170  if (orig_ring!=syz_ring)
2171  s_temp=idrMoveR_NoSort(arg,orig_ring, syz_ring);
2172  else
2173  s_temp=arg;
2174 
2175  ideal s_temp1 = kStd(s_temp,currRing->qideal,testHomog,&w,NULL,length);
2176  if (w!=NULL) delete w;
2177 
2178  if (syz_ring!=orig_ring)
2179  {
2180  idDelete(&s_temp);
2181  rChangeCurrRing(orig_ring);
2182  }
2183 
2184  idDelete(&temp);
2185  ideal temp1=idRingCopy(s_temp1,syz_ring);
2186 
2187  if (syz_ring!=orig_ring)
2188  {
2189  rChangeCurrRing(syz_ring);
2190  idDelete(&s_temp1);
2191  rChangeCurrRing(orig_ring);
2192  rDelete(syz_ring);
2193  }
2194 
2195  for (i=0;i<IDELEMS(temp1);i++)
2196  {
2197  if ((temp1->m[i]!=NULL)
2198  && (pGetComp(temp1->m[i])<=length))
2199  {
2200  pDelete(&(temp1->m[i]));
2201  }
2202  else
2203  {
2204  p_Shift(&(temp1->m[i]),-length,currRing);
2205  }
2206  }
2207  temp1->rank = rk;
2208  idSkipZeroes(temp1);
2209 
2210  return temp1;
2211 }
2212 */
2213 
2214 #ifdef HAVE_SHIFTBBA
2215 ideal idModuloLP (ideal h2,ideal h1, tHomog, intvec ** w, matrix *T, GbVariant alg)
2216 {
2217  intvec *wtmp=NULL;
2218  if (T!=NULL) idDelete((ideal*)T);
2219 
2220  int i,k,rk,flength=0,slength,length;
2221  poly p,q;
2222 
2223  if (idIs0(h2))
2224  return idFreeModule(si_max(1,h2->ncols));
2225  if (!idIs0(h1))
2226  flength = id_RankFreeModule(h1,currRing);
2227  slength = id_RankFreeModule(h2,currRing);
2228  length = si_max(flength,slength);
2229  if (length==0)
2230  {
2231  length = 1;
2232  }
2233  ideal temp = idInit(IDELEMS(h2),length+IDELEMS(h2));
2234  if ((w!=NULL)&&((*w)!=NULL))
2235  {
2236  //Print("input weights:");(*w)->show(1);PrintLn();
2237  int d;
2238  int k;
2239  wtmp=new intvec(length+IDELEMS(h2));
2240  for (i=0;i<length;i++)
2241  ((*wtmp)[i])=(**w)[i];
2242  for (i=0;i<IDELEMS(h2);i++)
2243  {
2244  poly p=h2->m[i];
2245  if (p!=NULL)
2246  {
2247  d = p_Deg(p,currRing);
2248  k= pGetComp(p);
2249  if (slength>0) k--;
2250  d +=((**w)[k]);
2251  ((*wtmp)[i+length]) = d;
2252  }
2253  }
2254  //Print("weights:");wtmp->show(1);PrintLn();
2255  }
2256  for (i=0;i<IDELEMS(h2);i++)
2257  {
2258  temp->m[i] = pCopy(h2->m[i]);
2259  q = pOne();
2260  // non multiplicative variable
2261  pSetExp(q, currRing->isLPring - currRing->LPncGenCount + i + 1, 1);
2262  p_Setm(q, currRing);
2263  pSetComp(q,i+1+length);
2264  pSetmComp(q);
2265  if(temp->m[i]!=NULL)
2266  {
2267  if (slength==0) p_Shift(&(temp->m[i]),1,currRing);
2268  p = temp->m[i];
2269  temp->m[i] = pAdd(p, q);
2270  }
2271  else
2272  temp->m[i]=q;
2273  }
2274  rk = k = IDELEMS(h2);
2275  if (!idIs0(h1))
2276  {
2277  pEnlargeSet(&(temp->m),IDELEMS(temp),IDELEMS(h1));
2278  IDELEMS(temp) += IDELEMS(h1);
2279  for (i=0;i<IDELEMS(h1);i++)
2280  {
2281  if (h1->m[i]!=NULL)
2282  {
2283  temp->m[k] = pCopy(h1->m[i]);
2284  if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
2285  k++;
2286  }
2287  }
2288  }
2289 
2290  ring orig_ring=currRing;
2291  ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE);
2292  rSetSyzComp(length,syz_ring);
2293  rChangeCurrRing(syz_ring);
2294  // we can use OPT_RETURN_SB only, if syz_ring==orig_ring,
2295  // therefore we disable OPT_RETURN_SB for modulo:
2296  // (see tr. #701)
2297  //if (TEST_OPT_RETURN_SB)
2298  // rSetSyzComp(IDELEMS(h2)+length, syz_ring);
2299  //else
2300  // rSetSyzComp(length, syz_ring);
2301  ideal s_temp;
2302 
2303  if (syz_ring != orig_ring)
2304  {
2305  s_temp = idrMoveR_NoSort(temp, orig_ring, syz_ring);
2306  }
2307  else
2308  {
2309  s_temp = temp;
2310  }
2311 
2312  idTest(s_temp);
2313  unsigned save_opt,save_opt2;
2314  SI_SAVE_OPT1(save_opt);
2315  SI_SAVE_OPT2(save_opt2);
2316  if (T==NULL) si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
2318  ideal s_temp1 = idGroebner(s_temp,length,alg);
2319  SI_RESTORE_OPT1(save_opt);
2320  SI_RESTORE_OPT2(save_opt2);
2321 
2322  //if (wtmp!=NULL) Print("output weights:");wtmp->show(1);PrintLn();
2323  if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
2324  {
2325  delete *w;
2326  *w=new intvec(IDELEMS(h2));
2327  for (i=0;i<IDELEMS(h2);i++)
2328  ((**w)[i])=(*wtmp)[i+length];
2329  }
2330  if (wtmp!=NULL) delete wtmp;
2331 
2332  if (T==NULL)
2333  {
2334  for (i=0;i<IDELEMS(s_temp1);i++)
2335  {
2336  if (s_temp1->m[i]!=NULL)
2337  {
2338  if (((int)pGetComp(s_temp1->m[i]))<=length)
2339  {
2340  p_Delete(&(s_temp1->m[i]),currRing);
2341  }
2342  else
2343  {
2344  p_Shift(&(s_temp1->m[i]),-length,currRing);
2345  }
2346  }
2347  }
2348  }
2349  else
2350  {
2351  *T=mpNew(IDELEMS(s_temp1),IDELEMS(h2));
2352  for (i=0;i<IDELEMS(s_temp1);i++)
2353  {
2354  if (s_temp1->m[i]!=NULL)
2355  {
2356  if (((int)pGetComp(s_temp1->m[i]))<=length)
2357  {
2358  do
2359  {
2360  p_LmDelete(&(s_temp1->m[i]),currRing);
2361  } while((int)pGetComp(s_temp1->m[i])<=length);
2362  poly q = prMoveR( s_temp1->m[i], syz_ring,orig_ring);
2363  s_temp1->m[i] = NULL;
2364  if (q!=NULL)
2365  {
2366  q=pReverse(q);
2367  do
2368  {
2369  poly p = q;
2370  long t=pGetComp(p);
2371  pIter(q);
2372  pNext(p) = NULL;
2373  pSetComp(p,0);
2374  pSetmComp(p);
2375  pTest(p);
2376  MATELEM(*T,(int)t-length,i) = pAdd(MATELEM(*T,(int)t-length,i),p);
2377  } while (q != NULL);
2378  }
2379  }
2380  else
2381  {
2382  p_Shift(&(s_temp1->m[i]),-length,currRing);
2383  }
2384  }
2385  }
2386  }
2387  s_temp1->rank = rk;
2388  idSkipZeroes(s_temp1);
2389 
2390  if (syz_ring!=orig_ring)
2391  {
2392  rChangeCurrRing(orig_ring);
2393  s_temp1 = idrMoveR_NoSort(s_temp1, syz_ring, orig_ring);
2394  rDelete(syz_ring);
2395  // Hmm ... here seems to be a memory leak
2396  // However, simply deleting it causes memory trouble
2397  // idDelete(&s_temp);
2398  }
2399  idTest(s_temp1);
2400  return s_temp1;
2401 }
2402 #endif
2403 
2404 /*2
2405 * represents (h1+h2)/h2=h1/(h1 intersect h2)
2406 */
2407 //ideal idModulo (ideal h2,ideal h1)
2408 ideal idModulo (ideal h2,ideal h1, tHomog hom, intvec ** w, matrix *T, GbVariant alg)
2409 {
2410 #ifdef HAVE_SHIFTBBA
2411  if (rIsLPRing(currRing))
2412  return idModuloLP(h2,h1,hom,w,T,alg);
2413 #endif
2414  intvec *wtmp=NULL;
2415  if (T!=NULL) idDelete((ideal*)T);
2416 
2417  int i,flength=0,slength,length;
2418 
2419  if (idIs0(h2))
2420  return idFreeModule(si_max(1,h2->ncols));
2421  if (!idIs0(h1))
2422  flength = id_RankFreeModule(h1,currRing);
2423  slength = id_RankFreeModule(h2,currRing);
2424  length = si_max(flength,slength);
2425  BOOLEAN inputIsIdeal=FALSE;
2426  if (length==0)
2427  {
2428  length = 1;
2429  inputIsIdeal=TRUE;
2430  }
2431  if ((w!=NULL)&&((*w)!=NULL))
2432  {
2433  //Print("input weights:");(*w)->show(1);PrintLn();
2434  int d;
2435  int k;
2436  wtmp=new intvec(length+IDELEMS(h2));
2437  for (i=0;i<length;i++)
2438  ((*wtmp)[i])=(**w)[i];
2439  for (i=0;i<IDELEMS(h2);i++)
2440  {
2441  poly p=h2->m[i];
2442  if (p!=NULL)
2443  {
2444  d = p_Deg(p,currRing);
2445  k= pGetComp(p);
2446  if (slength>0) k--;
2447  d +=((**w)[k]);
2448  ((*wtmp)[i+length]) = d;
2449  }
2450  }
2451  //Print("weights:");wtmp->show(1);PrintLn();
2452  }
2453  ideal s_temp1;
2454  ring orig_ring=currRing;
2455  ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE);
2456  rSetSyzComp(length,syz_ring);
2457  {
2458  rChangeCurrRing(syz_ring);
2459  ideal s1,s2;
2460 
2461  if (syz_ring != orig_ring)
2462  {
2463  s1 = idrCopyR_NoSort(h1, orig_ring, syz_ring);
2464  s2 = idrCopyR_NoSort(h2, orig_ring, syz_ring);
2465  }
2466  else
2467  {
2468  s1=idCopy(h1);
2469  s2=idCopy(h2);
2470  }
2471 
2472  unsigned save_opt,save_opt2;
2473  SI_SAVE_OPT1(save_opt);
2474  SI_SAVE_OPT2(save_opt2);
2475  if (T==NULL) si_opt_1 |= Sy_bit(OPT_REDTAIL);
2477  s_temp1 = idPrepare(s2,s1,testHomog,length,w,alg);
2478  SI_RESTORE_OPT1(save_opt);
2479  SI_RESTORE_OPT2(save_opt2);
2480  }
2481 
2482  //if (wtmp!=NULL) Print("output weights:");wtmp->show(1);PrintLn();
2483  if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
2484  {
2485  delete *w;
2486  *w=new intvec(IDELEMS(h2));
2487  for (i=0;i<IDELEMS(h2);i++)
2488  ((**w)[i])=(*wtmp)[i+length];
2489  }
2490  if (wtmp!=NULL) delete wtmp;
2491 
2492  ideal result=idInit(IDELEMS(s_temp1),IDELEMS(h2));
2493  s_temp1=idExtractG_T_S(s_temp1,T,&result,length,IDELEMS(h2),inputIsIdeal,orig_ring,syz_ring);
2494 
2495  idDelete(&s_temp1);
2496  if (syz_ring!=orig_ring)
2497  {
2498  rDelete(syz_ring);
2499  }
2500  idTest(h2);
2501  idTest(h1);
2502  idTest(result);
2503  if (T!=NULL) idTest((ideal)*T);
2504  return result;
2505 }
2506 
2507 /*
2508 *computes module-weights for liftings of homogeneous modules
2509 */
2510 #if 0
2511 static intvec * idMWLift(ideal mod,intvec * weights)
2512 {
2513  if (idIs0(mod)) return new intvec(2);
2514  int i=IDELEMS(mod);
2515  while ((i>0) && (mod->m[i-1]==NULL)) i--;
2516  intvec *result = new intvec(i+1);
2517  while (i>0)
2518  {
2519  (*result)[i]=currRing->pFDeg(mod->m[i],currRing)+(*weights)[pGetComp(mod->m[i])];
2520  }
2521  return result;
2522 }
2523 #endif
2524 
2525 /*2
2526 *sorts the kbase for idCoef* in a special way (lexicographically
2527 *with x_max,...,x_1)
2528 */
2529 ideal idCreateSpecialKbase(ideal kBase,intvec ** convert)
2530 {
2531  int i;
2532  ideal result;
2533 
2534  if (idIs0(kBase)) return NULL;
2535  result = idInit(IDELEMS(kBase),kBase->rank);
2536  *convert = idSort(kBase,FALSE);
2537  for (i=0;i<(*convert)->length();i++)
2538  {
2539  result->m[i] = pCopy(kBase->m[(**convert)[i]-1]);
2540  }
2541  return result;
2542 }
2543 
2544 /*2
2545 *returns the index of a given monom in the list of the special kbase
2546 */
2547 int idIndexOfKBase(poly monom, ideal kbase)
2548 {
2549  int j=IDELEMS(kbase);
2550 
2551  while ((j>0) && (kbase->m[j-1]==NULL)) j--;
2552  if (j==0) return -1;
2553  int i=(currRing->N);
2554  while (i>0)
2555  {
2556  loop
2557  {
2558  if (pGetExp(monom,i)>pGetExp(kbase->m[j-1],i)) return -1;
2559  if (pGetExp(monom,i)==pGetExp(kbase->m[j-1],i)) break;
2560  j--;
2561  if (j==0) return -1;
2562  }
2563  if (i==1)
2564  {
2565  while(j>0)
2566  {
2567  if (pGetComp(monom)==pGetComp(kbase->m[j-1])) return j-1;
2568  if (pGetComp(monom)>pGetComp(kbase->m[j-1])) return -1;
2569  j--;
2570  }
2571  }
2572  i--;
2573  }
2574  return -1;
2575 }
2576 
2577 /*2
2578 *decomposes the monom in a part of coefficients described by the
2579 *complement of how and a monom in variables occuring in how, the
2580 *index of which in kbase is returned as integer pos (-1 if it don't
2581 *exists)
2582 */
2583 poly idDecompose(poly monom, poly how, ideal kbase, int * pos)
2584 {
2585  int i;
2586  poly coeff=pOne(), base=pOne();
2587 
2588  for (i=1;i<=(currRing->N);i++)
2589  {
2590  if (pGetExp(how,i)>0)
2591  {
2592  pSetExp(base,i,pGetExp(monom,i));
2593  }
2594  else
2595  {
2596  pSetExp(coeff,i,pGetExp(monom,i));
2597  }
2598  }
2599  pSetComp(base,pGetComp(monom));
2600  pSetm(base);
2601  pSetCoeff(coeff,nCopy(pGetCoeff(monom)));
2602  pSetm(coeff);
2603  *pos = idIndexOfKBase(base,kbase);
2604  if (*pos<0)
2605  p_Delete(&coeff,currRing);
2607  return coeff;
2608 }
2609 
2610 /*2
2611 *returns a matrix A of coefficients with kbase*A=arg
2612 *if all monomials in variables of how occur in kbase
2613 *the other are deleted
2614 */
2615 matrix idCoeffOfKBase(ideal arg, ideal kbase, poly how)
2616 {
2617  matrix result;
2618  ideal tempKbase;
2619  poly p,q;
2620  intvec * convert;
2621  int i=IDELEMS(kbase),j=IDELEMS(arg),k,pos;
2622 #if 0
2623  while ((i>0) && (kbase->m[i-1]==NULL)) i--;
2624  if (idIs0(arg))
2625  return mpNew(i,1);
2626  while ((j>0) && (arg->m[j-1]==NULL)) j--;
2627  result = mpNew(i,j);
2628 #else
2629  result = mpNew(i, j);
2630  while ((j>0) && (arg->m[j-1]==NULL)) j--;
2631 #endif
2632 
2633  tempKbase = idCreateSpecialKbase(kbase,&convert);
2634  for (k=0;k<j;k++)
2635  {
2636  p = arg->m[k];
2637  while (p!=NULL)
2638  {
2639  q = idDecompose(p,how,tempKbase,&pos);
2640  if (pos>=0)
2641  {
2642  MATELEM(result,(*convert)[pos],k+1) =
2643  pAdd(MATELEM(result,(*convert)[pos],k+1),q);
2644  }
2645  else
2646  p_Delete(&q,currRing);
2647  pIter(p);
2648  }
2649  }
2650  idDelete(&tempKbase);
2651  return result;
2652 }
2653 
2654 static void idDeleteComps(ideal arg,int* red_comp,int del)
2655 // red_comp is an array [0..args->rank]
2656 {
2657  int i,j;
2658  poly p;
2659 
2660  for (i=IDELEMS(arg)-1;i>=0;i--)
2661  {
2662  p = arg->m[i];
2663  while (p!=NULL)
2664  {
2665  j = pGetComp(p);
2666  if (red_comp[j]!=j)
2667  {
2668  pSetComp(p,red_comp[j]);
2669  pSetmComp(p);
2670  }
2671  pIter(p);
2672  }
2673  }
2674  (arg->rank) -= del;
2675 }
2676 
2677 /*2
2678 * returns the presentation of an isomorphic, minimally
2679 * embedded module (arg represents the quotient!)
2680 */
2681 ideal idMinEmbedding(ideal arg,BOOLEAN inPlace, intvec **w)
2682 {
2683  if (idIs0(arg)) return idInit(1,arg->rank);
2684  int i,next_gen,next_comp;
2685  ideal res=arg;
2686  if (!inPlace) res = idCopy(arg);
2687  res->rank=si_max(res->rank,id_RankFreeModule(res,currRing));
2688  int *red_comp=(int*)omAlloc((res->rank+1)*sizeof(int));
2689  for (i=res->rank;i>=0;i--) red_comp[i]=i;
2690 
2691  int del=0;
2692  loop
2693  {
2694  next_gen = id_ReadOutPivot(res, &next_comp, currRing);
2695  if (next_gen<0) break;
2696  del++;
2697  syGaussForOne(res,next_gen,next_comp,0,IDELEMS(res));
2698  for(i=next_comp+1;i<=arg->rank;i++) red_comp[i]--;
2699  if ((w !=NULL)&&(*w!=NULL))
2700  {
2701  for(i=next_comp;i<(*w)->length();i++) (**w)[i-1]=(**w)[i];
2702  }
2703  }
2704 
2705  idDeleteComps(res,red_comp,del);
2706  idSkipZeroes(res);
2707  omFree(red_comp);
2708 
2709  if ((w !=NULL)&&(*w!=NULL) &&(del>0))
2710  {
2711  int nl=si_max((*w)->length()-del,1);
2712  intvec *wtmp=new intvec(nl);
2713  for(i=0;i<res->rank;i++) (*wtmp)[i]=(**w)[i];
2714  delete *w;
2715  *w=wtmp;
2716  }
2717  return res;
2718 }
2719 
2720 #include "polys/clapsing.h"
2721 
2722 #if 0
2723 poly id_GCD(poly f, poly g, const ring r)
2724 {
2725  ring save_r=currRing;
2726  rChangeCurrRing(r);
2727  ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2728  intvec *w = NULL;
2729  ideal S=idSyzygies(I,testHomog,&w);
2730  if (w!=NULL) delete w;
2731  poly gg=pTakeOutComp(&(S->m[0]),2);
2732  idDelete(&S);
2733  poly gcd_p=singclap_pdivide(f,gg,r);
2734  p_Delete(&gg,r);
2735  rChangeCurrRing(save_r);
2736  return gcd_p;
2737 }
2738 #else
2739 poly id_GCD(poly f, poly g, const ring r)
2740 {
2741  ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2742  intvec *w = NULL;
2743 
2744  ring save_r = currRing;
2745  rChangeCurrRing(r);
2746  ideal S=idSyzygies(I,testHomog,&w);
2747  rChangeCurrRing(save_r);
2748 
2749  if (w!=NULL) delete w;
2750  poly gg=p_TakeOutComp(&(S->m[0]), 2, r);
2751  id_Delete(&S, r);
2752  poly gcd_p=singclap_pdivide(f,gg, r);
2753  p_Delete(&gg, r);
2754 
2755  return gcd_p;
2756 }
2757 #endif
2758 
2759 #if 0
2760 /*2
2761 * xx,q: arrays of length 0..rl-1
2762 * xx[i]: SB mod q[i]
2763 * assume: char=0
2764 * assume: q[i]!=0
2765 * destroys xx
2766 */
2767 ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring R)
2768 {
2769  int cnt=IDELEMS(xx[0])*xx[0]->nrows;
2770  ideal result=idInit(cnt,xx[0]->rank);
2771  result->nrows=xx[0]->nrows; // for lifting matrices
2772  result->ncols=xx[0]->ncols; // for lifting matrices
2773  int i,j;
2774  poly r,h,hh,res_p;
2775  number *x=(number *)omAlloc(rl*sizeof(number));
2776  for(i=cnt-1;i>=0;i--)
2777  {
2778  res_p=NULL;
2779  loop
2780  {
2781  r=NULL;
2782  for(j=rl-1;j>=0;j--)
2783  {
2784  h=xx[j]->m[i];
2785  if ((h!=NULL)
2786  &&((r==NULL)||(p_LmCmp(r,h,R)==-1)))
2787  r=h;
2788  }
2789  if (r==NULL) break;
2790  h=p_Head(r, R);
2791  for(j=rl-1;j>=0;j--)
2792  {
2793  hh=xx[j]->m[i];
2794  if ((hh!=NULL) && (p_LmCmp(r,hh, R)==0))
2795  {
2796  x[j]=p_GetCoeff(hh, R);
2797  hh=p_LmFreeAndNext(hh, R);
2798  xx[j]->m[i]=hh;
2799  }
2800  else
2801  x[j]=n_Init(0, R->cf); // is R->cf really n_Q???, yes!
2802  }
2803 
2804  number n=n_ChineseRemainder(x,q,rl, R->cf);
2805 
2806  for(j=rl-1;j>=0;j--)
2807  {
2808  x[j]=NULL; // nlInit(0...) takes no memory
2809  }
2810  if (n_IsZero(n, R->cf)) p_Delete(&h, R);
2811  else
2812  {
2813  p_SetCoeff(h,n, R);
2814  //Print("new mon:");pWrite(h);
2815  res_p=p_Add_q(res_p, h, R);
2816  }
2817  }
2818  result->m[i]=res_p;
2819  }
2820  omFree(x);
2821  for(i=rl-1;i>=0;i--) id_Delete(&(xx[i]), R);
2822  omFree(xx);
2823  return result;
2824 }
2825 #endif
2826 /* currently unused:
2827 ideal idChineseRemainder(ideal *xx, intvec *iv)
2828 {
2829  int rl=iv->length();
2830  number *q=(number *)omAlloc(rl*sizeof(number));
2831  int i;
2832  for(i=0; i<rl; i++)
2833  {
2834  q[i]=nInit((*iv)[i]);
2835  }
2836  return idChineseRemainder(xx,q,rl);
2837 }
2838 */
2839 /*
2840  * lift ideal with coeffs over Z (mod N) to Q via Farey
2841  */
2842 ideal id_Farey(ideal x, number N, const ring r)
2843 {
2844  int cnt=IDELEMS(x)*x->nrows;
2845  ideal result=idInit(cnt,x->rank);
2846  result->nrows=x->nrows; // for lifting matrices
2847  result->ncols=x->ncols; // for lifting matrices
2848 
2849  int i;
2850  for(i=cnt-1;i>=0;i--)
2851  {
2852  result->m[i]=p_Farey(x->m[i],N,r);
2853  }
2854  return result;
2855 }
2856 
2857 
2858 
2859 
2860 // uses glabl vars via pSetModDeg
2861 /*
2862 BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
2863 {
2864  if ((Q!=NULL) && (!idHomIdeal(Q,NULL))) { PrintS(" Q not hom\n"); return FALSE;}
2865  if (idIs0(m)) return TRUE;
2866 
2867  int cmax=-1;
2868  int i;
2869  poly p=NULL;
2870  int length=IDELEMS(m);
2871  poly* P=m->m;
2872  for (i=length-1;i>=0;i--)
2873  {
2874  p=P[i];
2875  if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
2876  }
2877  if (w != NULL)
2878  if (w->length()+1 < cmax)
2879  {
2880  // Print("length: %d - %d \n", w->length(),cmax);
2881  return FALSE;
2882  }
2883 
2884  if(w!=NULL)
2885  p_SetModDeg(w, currRing);
2886 
2887  for (i=length-1;i>=0;i--)
2888  {
2889  p=P[i];
2890  poly q=p;
2891  if (p!=NULL)
2892  {
2893  int d=p_FDeg(p,currRing);
2894  loop
2895  {
2896  pIter(p);
2897  if (p==NULL) break;
2898  if (d!=p_FDeg(p,currRing))
2899  {
2900  //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
2901  if(w!=NULL)
2902  p_SetModDeg(NULL, currRing);
2903  return FALSE;
2904  }
2905  }
2906  }
2907  }
2908 
2909  if(w!=NULL)
2910  p_SetModDeg(NULL, currRing);
2911 
2912  return TRUE;
2913 }
2914 */
2915 
2916 /// keeps the first k (>= 1) entries of the given ideal
2917 /// (Note that the kept polynomials may be zero.)
2918 void idKeepFirstK(ideal id, const int k)
2919 {
2920  for (int i = IDELEMS(id)-1; i >= k; i--)
2921  {
2922  if (id->m[i] != NULL) pDelete(&id->m[i]);
2923  }
2924  int kk=k;
2925  if (k==0) kk=1; /* ideals must have at least one element(0)*/
2926  pEnlargeSet(&(id->m), IDELEMS(id), kk-IDELEMS(id));
2927  IDELEMS(id) = kk;
2928 }
2929 
2930 typedef struct
2931 {
2932  poly p;
2933  int index;
2934 } poly_sort;
2935 
2936 int pCompare_qsort(const void *a, const void *b)
2937 {
2938  return (p_Compare(((poly_sort *)a)->p, ((poly_sort *)b)->p,currRing));
2939 }
2940 
2941 void idSort_qsort(poly_sort *id_sort, int idsize)
2942 {
2943  qsort(id_sort, idsize, sizeof(poly_sort), pCompare_qsort);
2944 }
2945 
2946 /*2
2947 * ideal id = (id[i])
2948 * if id[i] = id[j] then id[j] is deleted for j > i
2949 */
2950 void idDelEquals(ideal id)
2951 {
2952  int idsize = IDELEMS(id);
2953  poly_sort *id_sort = (poly_sort *)omAlloc0(idsize*sizeof(poly_sort));
2954  for (int i = 0; i < idsize; i++)
2955  {
2956  id_sort[i].p = id->m[i];
2957  id_sort[i].index = i;
2958  }
2959  idSort_qsort(id_sort, idsize);
2960  int index, index_i, index_j;
2961  int i = 0;
2962  for (int j = 1; j < idsize; j++)
2963  {
2964  if (id_sort[i].p != NULL && pEqualPolys(id_sort[i].p, id_sort[j].p))
2965  {
2966  index_i = id_sort[i].index;
2967  index_j = id_sort[j].index;
2968  if (index_j > index_i)
2969  {
2970  index = index_j;
2971  }
2972  else
2973  {
2974  index = index_i;
2975  i = j;
2976  }
2977  pDelete(&id->m[index]);
2978  }
2979  else
2980  {
2981  i = j;
2982  }
2983  }
2984  omFreeSize((ADDRESS)(id_sort), idsize*sizeof(poly_sort));
2985 }
2986 
2988 
2990 {
2991  BOOLEAN b = FALSE; // set b to TRUE, if spoly was changed,
2992  // let it remain FALSE otherwise
2993  if (strat->P.t_p==NULL)
2994  {
2995  poly p=strat->P.p;
2996 
2997  // iterate over all terms of p and
2998  // compute the minimum mm of all exponent vectors
2999  int *mm=(int*)omAlloc((1+rVar(currRing))*sizeof(int));
3000  int *m0=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
3001  p_GetExpV(p,mm,currRing);
3002  bool nonTrivialSaturationToBeDone=true;
3003  for (p=pNext(p); p!=NULL; pIter(p))
3004  {
3005  nonTrivialSaturationToBeDone=false;
3006  p_GetExpV(p,m0,currRing);
3007  for (int i=rVar(currRing); i>0; i--)
3008  {
3010  {
3011  mm[i]=si_min(mm[i],m0[i]);
3012  if (mm[i]>0) nonTrivialSaturationToBeDone=true;
3013  }
3014  else mm[i]=0;
3015  }
3016  // abort if the minimum is zero in each component
3017  if (!nonTrivialSaturationToBeDone) break;
3018  }
3019  if (nonTrivialSaturationToBeDone)
3020  {
3021  // std::cout << "simplifying!" << std::endl;
3022  if (TEST_OPT_PROT) { PrintS("S"); mflush(); }
3023  p=p_Copy(strat->P.p,currRing);
3024  //pWrite(p);
3025  // for (int i=rVar(currRing); i>0; i--)
3026  // if (mm[i]!=0) Print("x_%d:%d ",i,mm[i]);
3027  //PrintLn();
3028  strat->P.Init(currRing);
3029  //memset(&strat->P,0,sizeof(strat->P));
3030  strat->P.tailRing = strat->tailRing;
3031  strat->P.p=p;
3032  while(p!=NULL)
3033  {
3034  for (int i=rVar(currRing); i>0; i--)
3035  {
3036  p_SubExp(p,i,mm[i],currRing);
3037  }
3038  p_Setm(p,currRing);
3039  pIter(p);
3040  }
3041  b = TRUE;
3042  }
3043  omFree(mm);
3044  omFree(m0);
3045  }
3046  else
3047  {
3048  poly p=strat->P.t_p;
3049 
3050  // iterate over all terms of p and
3051  // compute the minimum mm of all exponent vectors
3052  int *mm=(int*)omAlloc((1+rVar(currRing))*sizeof(int));
3053  int *m0=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
3054  p_GetExpV(p,mm,strat->tailRing);
3055  bool nonTrivialSaturationToBeDone=true;
3056  for (p = pNext(p); p!=NULL; pIter(p))
3057  {
3058  nonTrivialSaturationToBeDone=false;
3059  p_GetExpV(p,m0,strat->tailRing);
3060  for(int i=rVar(currRing); i>0; i--)
3061  {
3063  {
3064  mm[i]=si_min(mm[i],m0[i]);
3065  if (mm[i]>0) nonTrivialSaturationToBeDone = true;
3066  }
3067  else mm[i]=0;
3068  }
3069  // abort if the minimum is zero in each component
3070  if (!nonTrivialSaturationToBeDone) break;
3071  }
3072  if (nonTrivialSaturationToBeDone)
3073  {
3074  if (TEST_OPT_PROT) { PrintS("S"); mflush(); }
3075  p=p_Copy(strat->P.t_p,strat->tailRing);
3076  //p_Write(p,strat->tailRing);
3077  // for (int i=rVar(currRing); i>0; i--)
3078  // if (mm[i]!=0) Print("x_%d:%d ",i,mm[i]);
3079  //PrintLn();
3080  strat->P.Init(currRing);
3081  //memset(&strat->P,0,sizeof(strat->P));
3082  strat->P.tailRing = strat->tailRing;
3083  strat->P.t_p=p;
3084  while(p!=NULL)
3085  {
3086  for(int i=rVar(currRing); i>0; i--)
3087  {
3088  p_SubExp(p,i,mm[i],strat->tailRing);
3089  }
3090  p_Setm(p,strat->tailRing);
3091  pIter(p);
3092  }
3093  strat->P.GetP();
3094  b = TRUE;
3095  }
3096  omFree(mm);
3097  omFree(m0);
3098  }
3099  return b; // return TRUE if sp was changed, FALSE if not
3100 }
3101 
3102 ideal id_Satstd(const ideal I, ideal J, const ring r)
3103 {
3104  ring save=currRing;
3105  if (currRing!=r) rChangeCurrRing(r);
3106  idSkipZeroes(J);
3107  id_satstdSaturatingVariables=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
3108  int k=IDELEMS(J);
3109  if (k>1)
3110  {
3111  for (int i=0; i<k; i++)
3112  {
3113  poly x = J->m[i];
3114  int li = p_Var(x,r);
3115  if (li>0)
3117  else
3118  {
3119  if (currRing!=save) rChangeCurrRing(save);
3120  WerrorS("ideal generators must be variables");
3121  return NULL;
3122  }
3123  }
3124  }
3125  else
3126  {
3127  poly x = J->m[0];
3128  for (int i=1; i<=r->N; i++)
3129  {
3130  int li = p_GetExp(x,i,r);
3131  if (li==1)
3133  else if (li>1)
3134  {
3135  if (currRing!=save) rChangeCurrRing(save);
3136  Werror("exponent(x(%d)^%d) must be 0 or 1",i,li);
3137  return NULL;
3138  }
3139  }
3140  }
3141  ideal res=kStd(I,r->qideal,testHomog,NULL,NULL,0,0,NULL,id_sat_vars_sp);
3144  if (currRing!=save) rChangeCurrRing(save);
3145  return res;
3146 }
3147 
3148 GbVariant syGetAlgorithm(char *n, const ring r, const ideal /*M*/)
3149 {
3150  GbVariant alg=GbDefault;
3151  if (strcmp(n,"default")==0) alg=GbDefault;
3152  else if (strcmp(n,"slimgb")==0) alg=GbSlimgb;
3153  else if (strcmp(n,"std")==0) alg=GbStd;
3154  else if (strcmp(n,"sba")==0) alg=GbSba;
3155  else if (strcmp(n,"singmatic")==0) alg=GbSingmatic;
3156  else if (strcmp(n,"groebner")==0) alg=GbGroebner;
3157  else if (strcmp(n,"modstd")==0) alg=GbModstd;
3158  else if (strcmp(n,"ffmod")==0) alg=GbFfmod;
3159  else if (strcmp(n,"nfmod")==0) alg=GbNfmod;
3160  else if (strcmp(n,"std:sat")==0) alg=GbStdSat;
3161  else Warn(">>%s<< is an unknown algorithm",n);
3162 
3163  if (alg==GbSlimgb) // test conditions for slimgb
3164  {
3165  if(rHasGlobalOrdering(r)
3166  &&(!rIsNCRing(r))
3167  &&(r->qideal==NULL)
3168  &&(!rField_is_Ring(r)))
3169  {
3170  return GbSlimgb;
3171  }
3172  if (TEST_OPT_PROT)
3173  WarnS("requires: coef:field, commutative, global ordering, not qring");
3174  }
3175  else if (alg==GbSba) // cond. for sba
3176  {
3177  if(rField_is_Domain(r)
3178  &&(!rIsNCRing(r))
3179  &&(rHasGlobalOrdering(r)))
3180  {
3181  return GbSba;
3182  }
3183  if (TEST_OPT_PROT)
3184  WarnS("requires: coef:domain, commutative, global ordering");
3185  }
3186  else if (alg==GbGroebner) // cond. for groebner
3187  {
3188  return GbGroebner;
3189  }
3190  else if(alg==GbModstd) // cond for modstd: Q or Q(a)
3191  {
3192  if(ggetid("modStd")==NULL)
3193  {
3194  WarnS(">>modStd<< not found");
3195  }
3196  else if(rField_is_Q(r)
3197  &&(!rIsNCRing(r))
3198  &&(rHasGlobalOrdering(r)))
3199  {
3200  return GbModstd;
3201  }
3202  if (TEST_OPT_PROT)
3203  WarnS("requires: coef:QQ, commutative, global ordering");
3204  }
3205  else if(alg==GbStdSat) // cond for std:sat: 2 blocks of variables
3206  {
3207  if(ggetid("satstd")==NULL)
3208  {
3209  WarnS(">>satstd<< not found");
3210  }
3211  else
3212  {
3213  return GbStdSat;
3214  }
3215  }
3216 
3217  return GbStd; // no conditions for std
3218 }
3219 //----------------------------------------------------------------------------
3220 // GB-algorithms and their pre-conditions
3221 // std slimgb sba singmatic modstd ffmod nfmod groebner
3222 // + + + - + - - + coeffs: QQ
3223 // + + + + - - - + coeffs: ZZ/p
3224 // + + + - ? - + + coeffs: K[a]/f
3225 // + + + - ? + - + coeffs: K(a)
3226 // + - + - - - - + coeffs: domain, not field
3227 // + - - - - - - + coeffs: zero-divisors
3228 // + + + + - ? ? + also for modules: C
3229 // + + - + - ? ? + also for modules: all orderings
3230 // + + - - - - - + exterior algebra
3231 // + + - - - - - + G-algebra
3232 // + + + + + + + + degree ordering
3233 // + - + + + + + + non-degree ordering
3234 // - - - + + + + + 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:601
Definition: intvec.h:23
int nrows
Definition: matpol.h:20
long rank
Definition: matpol.h:19
int & rows()
Definition: matpol.h:23
int ncols
Definition: matpol.h:21
int & cols()
Definition: matpol.h:24
poly * m
Definition: matpol.h:18
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:464
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:538
#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:3148
int index
Definition: ideals.cc:2933
static void idPrepareStd(ideal s_temp, int k)
Definition: ideals.cc:1041
matrix idCoeffOfKBase(ideal arg, ideal kbase, poly how)
Definition: ideals.cc:2615
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:2932
matrix idDiff(matrix i, int k)
Definition: ideals.cc:2132
BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
Definition: ideals.cc:2063
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:2950
int pCompare_qsort(const void *a, const void *b)
Definition: ideals.cc:2936
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:1974
BOOLEAN idIsSubModule(ideal id1, ideal id2)
Definition: ideals.cc:2042
ideal idSeries(int n, ideal M, matrix U, intvec *w)
Definition: ideals.cc:2115
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:2529
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:2739
int idIndexOfKBase(poly monom, ideal kbase)
Definition: ideals.cc:2547
poly idDecompose(poly monom, poly how, ideal kbase, int *pos)
Definition: ideals.cc:2583
matrix idDiffOp(ideal I, ideal J, BOOLEAN multiply)
Definition: ideals.cc:2145
void idSort_qsort(poly_sort *id_sort, int idsize)
Definition: ideals.cc:2941
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:2918
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:2987
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:2654
ideal idModulo(ideal h2, ideal h1, tHomog hom, intvec **w, matrix *T, GbVariant alg)
Definition: ideals.cc:2408
ideal id_Farey(ideal x, number N, const ring r)
Definition: ideals.cc:2842
ideal id_Satstd(const ideal I, ideal J, const ring r)
Definition: ideals.cc:3102
ideal idModuloLP(ideal h2, ideal h1, tHomog, intvec **w, matrix *T, GbVariant alg)
Definition: ideals.cc:2215
static BOOLEAN id_sat_vars_sp(kStrategy strat)
Definition: ideals.cc:2989
ideal idMinEmbedding(ideal arg, BOOLEAN inPlace, intvec **w)
Definition: ideals.cc:2681
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
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition: ideals.h:184
#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)
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:135
idhdl ggetid(const char *n)
Definition: ipid.cc:571
EXTERN_VAR omBin sleftv_bin
Definition: ipid.h:145
void * iiCallLibProc1(const char *n, void *arg, int arg_type, BOOLEAN &err)
Definition: iplib.cc:627
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 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
STATIC_VAR jList * Q
Definition: janet.cc:30
void p_TakeOutComp(poly *p, long comp, poly *q, int *lq, const ring r)
Definition: p_polys.cc:3570
ideal kMin_std(ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb, int syzComp, int reduced)
Definition: kstd1.cc:3019
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3167
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:2617
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:2433
@ nc_skew
Definition: nc.h:16
@ nc_exterior
Definition: nc.h:21
BOOLEAN nc_CheckSubalgebra(poly PolyVar, ring r)
Definition: old.gring.cc:2568
static nc_type & ncRingType(nc_struct *p)
Definition: nc.h:159
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:148
matrix mp_Copy(matrix a, const ring r)
copies matrix a (from ring r to r)
Definition: matpol.cc:64
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:1507
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:1603
poly mp_DetBareiss(matrix a, const ring r)
returns the determinant of the matrix m; uses Bareiss algorithm
Definition: matpol.cc:1676
#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:387
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:44
#define p_GetCoeff(p, r)
Definition: monomials.h:50
#define __p_GetComp(p, r)
Definition: monomials.h:63
char N base
Definition: ValueTraits.h:144
#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 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:87
#define OPT_REDTAIL
Definition: options.h:91
#define OPT_SB_1
Definition: options.h:95
#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:112
#define TEST_V_INTERSECT_ELIM
Definition: options.h:144
#define TEST_V_INTERSECT_SYZ
Definition: options.h:145
#define TEST_OPT_NOTREGULARITY
Definition: options.h:120
#define TEST_OPT_PROT
Definition: options.h:103
#define V_IDLIFT
Definition: options.h:62
#define V_IDELIM
Definition: options.h:70
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:1570
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:701
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition: p_polys.cc:4739
int p_Compare(const poly a, const poly b, const ring R)
Definition: p_polys.cc:4940
long p_DegW(poly p, const int *w, const ring R)
Definition: p_polys.cc:686
void p_SetModDeg(intvec *w, ring r)
Definition: p_polys.cc:3747
int p_Var(poly m, const ring r)
Definition: p_polys.cc:4689
poly p_One(const ring r)
Definition: p_polys.cc:1309
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3770
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:583
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1079
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:908
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:711
static long p_SubExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:613
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition: p_polys.h:488
static long p_MinComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:313
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:233
static poly p_Copy_noCheck(poly p, const ring r)
returns a copy of p (without any additional testing)
Definition: p_polys.h:808
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:412
static poly pReverse(poly p)
Definition: p_polys.h:335
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition: p_polys.h:832
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1552
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:469
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:873
static void p_GetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1492
static poly p_LmFreeAndNext(poly p, ring)
Definition: p_polys.h:703
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:818
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
Compatiblity layer for legacy polynomial operations (over currRing)
#define pAdd(p, q)
Definition: polys.h:203
#define pTest(p)
Definition: polys.h:415
#define pDelete(p_ptr)
Definition: polys.h:186
#define ppJet(p, m)
Definition: polys.h:367
#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:368
#define pSub(a, b)
Definition: polys.h:287
#define pWeight(i)
Definition: polys.h:280
#define ppJetW(p, m, iv)
Definition: polys.h:369
#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:370
#define pDiffOp(a, b, m)
Definition: polys.h:297
#define pSeries(n, p, u, w)
Definition: polys.h:372
#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:400
#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:339
#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:89
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:247
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:191
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:260
poly prMoveR_NoSort(poly &p, ring src_r, ring dest_r)
Definition: prCopy.cc:100
ideal idrCopyR_NoSort(ideal id, ring src_r, ring dest_r)
Definition: prCopy.cc:204
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:3395
ring rAssure_SyzComp(const ring r, BOOLEAN complete)
Definition: ring.cc:4418
BOOLEAN nc_rComplete(const ring src, ring dest, bool bSetupQuotient)
Definition: ring.cc:5647
ring rAssure_SyzOrder(const ring r, BOOLEAN complete)
Definition: ring.cc:4413
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition: ring.cc:1363
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:449
void rSetSyzComp(int k, const ring r)
Definition: ring.cc:5027
ring rAssure_dp_C(const ring r)
Definition: ring.cc:4921
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:400
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:488
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_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:507
static BOOLEAN rIsNCRing(const ring r)
Definition: ring.h:421
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:593
BOOLEAN rHasGlobalOrdering(const ring r)
Definition: ring.h:760
#define rField_is_Ring(R)
Definition: ring.h:486
#define block
Definition: scanner.cc:666
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:78
#define R
Definition: sirandom.c:27
#define M
Definition: sirandom.c:25
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:57
tHomog
Definition: structs.h:39
@ isHomog
Definition: structs.h:41
@ testHomog
Definition: structs.h:42
@ isNotHomog
Definition: structs.h:40
#define BITSET
Definition: structs.h:20
#define loop
Definition: structs.h:79
intvec * syBetti(resolvente res, int length, int *regularity, intvec *weights, BOOLEAN tomin, int *row_shift)
Definition: syz.cc:770
void syGaussForOne(ideal syz, int elnum, int ModComp, int from, int till)
Definition: syz.cc:218
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:3585
@ 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.c:78