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