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