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