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