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