source: git/kernel/ideals.cc @ 4a822ba

spielwiese
Last change on this file since 4a822ba was 4a822ba, checked in by Hans Schoenemann <hannes@…>, 8 years ago
adjust poly, matrix etc comparisons
  • Property mode set to 100644
File size: 57.2 KB
Line 
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*/
45ideal 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;
52  if(rField_is_Ring(currRing))
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);
59  if (rHasGlobalOrdering(currRing))
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*/
131ideal 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));
138  assume(id_RankFreeModule(h1,currRing)==0);
139  assume(id_RankFreeModule(h2,currRing)==0);
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=(int*)omAlloc0(3*sizeof(int*));
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*/
201ideal 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))
229    && ((TEST_V_INTERSECT_ELIM) || (!TEST_V_INTERSECT_SYZ)))
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*/
340ideal 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*/
455static 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;
474    rSetSyzComp(k,currRing);
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*/
515ideal 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)
612  && (!TEST_OPT_NOTREGULARITY)
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*/
657ideal 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*/
704ideal 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
727  k=si_max(1L,id_RankFreeModule(h1,currRing));
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
857static 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
891ideal 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  }
922  k=si_max(id_RankFreeModule(mod,currRing),id_RankFreeModule(submod,currRing));
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*/
1086void 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*/
1151static 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;
1251    if(!rField_is_Ring(currRing)) si_opt_1 |= Sy_bit(OPT_SB_1);
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*/
1260ideal 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*/
1353ideal idElimination (ideal h1,poly delVar,intvec *hilb)
1354{
1355  int    i,j=0,k,l;
1356  ideal  h,hh, h3;
1357  int    *ord,*block0,*block1;
1358  int    ordersize=2;
1359  int    **wv;
1360  tHomog hom;
1361  intvec * w;
1362  ring tmpR;
1363  ring origR = currRing;
1364
1365  if (delVar==NULL)
1366  {
1367    return idCopy(h1);
1368  }
1369  if ((currRing->qideal!=NULL) && rIsPluralRing(origR))
1370  {
1371    WerrorS("cannot eliminate in a qring");
1372    return NULL;
1373  }
1374  if (idIs0(h1)) return idInit(1,h1->rank);
1375#ifdef HAVE_PLURAL
1376  if (rIsPluralRing(origR))
1377    /* in the NC case, we have to check the admissibility of */
1378    /* the subalgebra to be intersected with */
1379  {
1380    if ((ncRingType(origR) != nc_skew) && (ncRingType(origR) != nc_exterior)) /* in (quasi)-commutative algebras every subalgebra is admissible */
1381    {
1382      if (nc_CheckSubalgebra(delVar,origR))
1383      {
1384        WerrorS("no elimination is possible: subalgebra is not admissible");
1385        return NULL;
1386      }
1387    }
1388  }
1389#endif
1390  hom=(tHomog)idHomModule(h1,NULL,&w); //sets w to weight vector or NULL
1391  h3=idInit(16,h1->rank);
1392  for (k=0;; k++)
1393  {
1394    if (origR->order[k]!=0) ordersize++;
1395    else break;
1396  }
1397#if 0
1398  if (rIsPluralRing(origR)) // we have too keep the odering: it may be needed
1399                            // for G-algebra
1400  {
1401    for (k=0;k<ordersize-1; k++)
1402    {
1403      block0[k+1] = origR->block0[k];
1404      block1[k+1] = origR->block1[k];
1405      ord[k+1] = origR->order[k];
1406      if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1407    }
1408  }
1409  else
1410  {
1411    block0[1] = 1;
1412    block1[1] = (currRing->N);
1413    if (origR->OrdSgn==1) ord[1] = ringorder_wp;
1414    else                  ord[1] = ringorder_ws;
1415    wv[1]=(int*)omAlloc0((currRing->N)*sizeof(int));
1416    double wNsqr = (double)2.0 / (double)(currRing->N);
1417    wFunctional = wFunctionalBuch;
1418    int  *x= (int * )omAlloc(2 * ((currRing->N) + 1) * sizeof(int));
1419    int sl=IDELEMS(h1) - 1;
1420    wCall(h1->m, sl, x, wNsqr);
1421    for (sl = (currRing->N); sl!=0; sl--)
1422      wv[1][sl-1] = x[sl + (currRing->N) + 1];
1423    omFreeSize((ADDRESS)x, 2 * ((currRing->N) + 1) * sizeof(int));
1424
1425    ord[2]=ringorder_C;
1426    ord[3]=0;
1427  }
1428#else
1429#endif
1430  if ((hom==TRUE) && (origR->OrdSgn==1) && (!rIsPluralRing(origR)))
1431  {
1432    #if 1
1433    // we change to an ordering:
1434    // aa(1,1,1,...,0,0,0),wp(...),C
1435    // this seems to be better than version 2 below,
1436    // according to Tst/../elimiate_[3568].tat (- 17 %)
1437    ord=(int*)omAlloc0(4*sizeof(int));
1438    block0=(int*)omAlloc0(4*sizeof(int));
1439    block1=(int*)omAlloc0(4*sizeof(int));
1440    wv=(int**) omAlloc0(4*sizeof(int**));
1441    block0[0] = block0[1] = 1;
1442    block1[0] = block1[1] = rVar(origR);
1443    wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1444    // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1445    // ignore it
1446    ord[0] = ringorder_aa;
1447    for (j=0;j<rVar(origR);j++)
1448      if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1449    BOOLEAN wp=FALSE;
1450    for (j=0;j<rVar(origR);j++)
1451      if (pWeight(j+1,origR)!=1) { wp=TRUE;break; }
1452    if (wp)
1453    {
1454      wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1455      for (j=0;j<rVar(origR);j++)
1456        wv[1][j]=pWeight(j+1,origR);
1457      ord[1] = ringorder_wp;
1458    }
1459    else
1460      ord[1] = ringorder_dp;
1461    #else
1462    // we change to an ordering:
1463    // a(w1,...wn),wp(1,...0.....),C
1464    ord=(int*)omAlloc0(4*sizeof(int));
1465    block0=(int*)omAlloc0(4*sizeof(int));
1466    block1=(int*)omAlloc0(4*sizeof(int));
1467    wv=(int**) omAlloc0(4*sizeof(int**));
1468    block0[0] = block0[1] = 1;
1469    block1[0] = block1[1] = rVar(origR);
1470    wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1471    wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1472    ord[0] = ringorder_a;
1473    for (j=0;j<rVar(origR);j++)
1474      wv[0][j]=pWeight(j+1,origR);
1475    ord[1] = ringorder_wp;
1476    for (j=0;j<rVar(origR);j++)
1477      if (pGetExp(delVar,j+1)!=0) wv[1][j]=1;
1478    #endif
1479    ord[2] = ringorder_C;
1480    ord[3] = 0;
1481  }
1482  else
1483  {
1484    // we change to an ordering:
1485    // aa(....),orig_ordering
1486    ord=(int*)omAlloc0(ordersize*sizeof(int));
1487    block0=(int*)omAlloc0(ordersize*sizeof(int));
1488    block1=(int*)omAlloc0(ordersize*sizeof(int));
1489    wv=(int**) omAlloc0(ordersize*sizeof(int**));
1490    for (k=0;k<ordersize-1; k++)
1491    {
1492      block0[k+1] = origR->block0[k];
1493      block1[k+1] = origR->block1[k];
1494      ord[k+1] = origR->order[k];
1495      if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1496    }
1497    block0[0] = 1;
1498    block1[0] = rVar(origR);
1499    wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1500    for (j=0;j<rVar(origR);j++)
1501      if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1502    // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1503    // ignore it
1504    ord[0] = ringorder_aa;
1505  }
1506  // fill in tmp ring to get back the data later on
1507  tmpR  = rCopy0(origR,FALSE,FALSE); // qring==NULL
1508  //rUnComplete(tmpR);
1509  tmpR->p_Procs=NULL;
1510  tmpR->order = ord;
1511  tmpR->block0 = block0;
1512  tmpR->block1 = block1;
1513  tmpR->wvhdl = wv;
1514  rComplete(tmpR, 1);
1515
1516#ifdef HAVE_PLURAL
1517  /* update nc structure on tmpR */
1518  if (rIsPluralRing(origR))
1519  {
1520    if ( nc_rComplete(origR, tmpR, false) ) // no quotient ideal!
1521    {
1522      WerrorS("no elimination is possible: ordering condition is violated");
1523      // cleanup
1524      rDelete(tmpR);
1525      if (w!=NULL)
1526        delete w;
1527      return NULL;
1528    }
1529  }
1530#endif
1531  // change into the new ring
1532  //pChangeRing((currRing->N),currRing->OrdSgn,ord,block0,block1,wv);
1533  rChangeCurrRing(tmpR);
1534
1535  //h = idInit(IDELEMS(h1),h1->rank);
1536  // fetch data from the old ring
1537  //for (k=0;k<IDELEMS(h1);k++) h->m[k] = prCopyR( h1->m[k], origR);
1538  h=idrCopyR(h1,origR,currRing);
1539  if (origR->qideal!=NULL)
1540  {
1541    WarnS("eliminate in q-ring: experimental");
1542    ideal q=idrCopyR(origR->qideal,origR,currRing);
1543    ideal s=idSimpleAdd(h,q);
1544    idDelete(&h);
1545    idDelete(&q);
1546    h=s;
1547  }
1548  // compute kStd
1549#if 1
1550  //rWrite(tmpR);PrintLn();
1551  //BITSET save1;
1552  //SI_SAVE_OPT1(save1);
1553  //si_opt_1 |=1;
1554  //Print("h: %d gen, rk=%d\n",IDELEMS(h),h->rank);
1555  //extern char * showOption();
1556  //Print("%s\n",showOption());
1557  hh = kStd(h,NULL,hom,&w,hilb);
1558  //SI_RESTORE_OPT1(save1);
1559  idDelete(&h);
1560#else
1561  extern ideal kGroebner(ideal F, ideal Q);
1562  hh=kGroebner(h,NULL);
1563#endif
1564  // go back to the original ring
1565  rChangeCurrRing(origR);
1566  i = IDELEMS(hh)-1;
1567  while ((i >= 0) && (hh->m[i] == NULL)) i--;
1568  j = -1;
1569  // fetch data from temp ring
1570  for (k=0; k<=i; k++)
1571  {
1572    l=(currRing->N);
1573    while ((l>0) && (p_GetExp( hh->m[k],l,tmpR)*pGetExp(delVar,l)==0)) l--;
1574    if (l==0)
1575    {
1576      j++;
1577      if (j >= IDELEMS(h3))
1578      {
1579        pEnlargeSet(&(h3->m),IDELEMS(h3),16);
1580        IDELEMS(h3) += 16;
1581      }
1582      h3->m[j] = prMoveR( hh->m[k], tmpR,origR);
1583      hh->m[k] = NULL;
1584    }
1585  }
1586  id_Delete(&hh, tmpR);
1587  idSkipZeroes(h3);
1588  rDelete(tmpR);
1589  if (w!=NULL)
1590    delete w;
1591  return h3;
1592}
1593
1594#ifdef WITH_OLD_MINOR
1595/*2
1596* compute the which-th ar-minor of the matrix a
1597*/
1598poly idMinor(matrix a, int ar, unsigned long which, ideal R)
1599{
1600  int     i,j/*,k,size*/;
1601  unsigned long curr;
1602  int *rowchoise,*colchoise;
1603  BOOLEAN rowch,colch;
1604  // ideal result;
1605  matrix tmp;
1606  poly p,q;
1607
1608  i = binom(a->rows(),ar);
1609  j = binom(a->cols(),ar);
1610
1611  rowchoise=(int *)omAlloc(ar*sizeof(int));
1612  colchoise=(int *)omAlloc(ar*sizeof(int));
1613  // if ((i>512) || (j>512) || (i*j >512)) size=512;
1614  // else size=i*j;
1615  // result=idInit(size,1);
1616  tmp=mpNew(ar,ar);
1617  // k = 0; /* the index in result*/
1618  curr = 0; /* index of current minor */
1619  idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1620  while (!rowch)
1621  {
1622    idInitChoise(ar,1,a->cols(),&colch,colchoise);
1623    while (!colch)
1624    {
1625      if (curr == which)
1626      {
1627        for (i=1; i<=ar; i++)
1628        {
1629          for (j=1; j<=ar; j++)
1630          {
1631            MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1632          }
1633        }
1634        p = mp_DetBareiss(tmp,currRing);
1635        if (p!=NULL)
1636        {
1637          if (R!=NULL)
1638          {
1639            q = p;
1640            p = kNF(R,currRing->qideal,q);
1641            p_Delete(&q,currRing);
1642          }
1643          /*delete the matrix tmp*/
1644          for (i=1; i<=ar; i++)
1645          {
1646            for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1647          }
1648          idDelete((ideal*)&tmp);
1649          omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1650          omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1651          return (p);
1652        }
1653      }
1654      curr++;
1655      idGetNextChoise(ar,a->cols(),&colch,colchoise);
1656    }
1657    idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1658  }
1659  return (poly) 1;
1660}
1661
1662/*2
1663* compute all ar-minors of the matrix a
1664*/
1665ideal idMinors(matrix a, int ar, ideal R)
1666{
1667  int     i,j,/*k,*/size;
1668  int *rowchoise,*colchoise;
1669  BOOLEAN rowch,colch;
1670  ideal result;
1671  matrix tmp;
1672  poly p,q;
1673
1674  i = binom(a->rows(),ar);
1675  j = binom(a->cols(),ar);
1676
1677  rowchoise=(int *)omAlloc(ar*sizeof(int));
1678  colchoise=(int *)omAlloc(ar*sizeof(int));
1679  if ((i>512) || (j>512) || (i*j >512)) size=512;
1680  else size=i*j;
1681  result=idInit(size,1);
1682  tmp=mpNew(ar,ar);
1683  // k = 0; /* the index in result*/
1684  idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1685  while (!rowch)
1686  {
1687    idInitChoise(ar,1,a->cols(),&colch,colchoise);
1688    while (!colch)
1689    {
1690      for (i=1; i<=ar; i++)
1691      {
1692        for (j=1; j<=ar; j++)
1693        {
1694          MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1695        }
1696      }
1697      p = mp_DetBareiss(tmp,currRing);
1698      if (p!=NULL)
1699      {
1700        if (R!=NULL)
1701        {
1702          q = p;
1703          p = kNF(R,currRing->qideal,q);
1704          p_Delete(&q,currRing);
1705        }
1706        if (p!=NULL)
1707        {
1708          if (k>=size)
1709          {
1710            pEnlargeSet(&result->m,size,32);
1711            size += 32;
1712          }
1713          result->m[k] = p;
1714          k++;
1715        }
1716      }
1717      idGetNextChoise(ar,a->cols(),&colch,colchoise);
1718    }
1719    idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1720  }
1721  /*delete the matrix tmp*/
1722  for (i=1; i<=ar; i++)
1723  {
1724    for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1725  }
1726  idDelete((ideal*)&tmp);
1727  if (k==0)
1728  {
1729    k=1;
1730    result->m[0]=NULL;
1731  }
1732  omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1733  omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1734  pEnlargeSet(&result->m,size,k-size);
1735  IDELEMS(result) = k;
1736  return (result);
1737}
1738#else
1739
1740
1741/// compute all ar-minors of the matrix a
1742/// the caller of mpRecMin
1743/// the elements of the result are not in R (if R!=NULL)
1744ideal idMinors(matrix a, int ar, ideal R)
1745{
1746
1747  const ring origR=currRing;
1748  id_Test((ideal)a, origR);
1749
1750  const int r = a->nrows;
1751  const int c = a->ncols;
1752
1753  if((ar<=0) || (ar>r) || (ar>c))
1754  {
1755    Werror("%d-th minor, matrix is %dx%d",ar,r,c);
1756    return NULL;
1757  }
1758
1759  ideal h = id_Matrix2Module(mp_Copy(a,origR),origR);
1760  long bound = sm_ExpBound(h,c,r,ar,origR);
1761  id_Delete(&h, origR);
1762
1763  ring tmpR = sm_RingChange(origR,bound);
1764
1765  matrix b = mpNew(r,c);
1766
1767  for (int i=r*c-1;i>=0;i--)
1768    if (a->m[i] != NULL)
1769      b->m[i] = prCopyR(a->m[i],origR,tmpR);
1770
1771  id_Test( (ideal)b, tmpR);
1772
1773  if (R!=NULL)
1774  {
1775    R = idrCopyR(R,origR,tmpR); // TODO: overwrites R? memory leak?
1776    //if (ar>1) // otherwise done in mpMinorToResult
1777    //{
1778    //  matrix bb=(matrix)kNF(R,currRing->qideal,(ideal)b);
1779    //  bb->rank=b->rank; bb->nrows=b->nrows; bb->ncols=b->ncols;
1780    //  idDelete((ideal*)&b); b=bb;
1781    //}
1782    id_Test( R, tmpR);
1783  }
1784
1785
1786  ideal result = idInit(32,1);
1787
1788  int elems = 0;
1789
1790  if(ar>1)
1791    mp_RecMin(ar-1,result,elems,b,r,c,NULL,R,tmpR);
1792  else
1793    mp_MinorToResult(result,elems,b,r,c,R,tmpR);
1794
1795  id_Test( (ideal)b, tmpR);
1796
1797  id_Delete((ideal *)&b, tmpR);
1798
1799  if (R!=NULL) id_Delete(&R,tmpR);
1800
1801  idSkipZeroes(result);
1802  rChangeCurrRing(origR);
1803  result = idrMoveR(result,tmpR,origR);
1804  sm_KillModifiedRing(tmpR);
1805  idTest(result);
1806  return result;
1807}
1808#endif
1809
1810/*2
1811*returns TRUE if id1 is a submodule of id2
1812*/
1813BOOLEAN idIsSubModule(ideal id1,ideal id2)
1814{
1815  int i;
1816  poly p;
1817
1818  if (idIs0(id1)) return TRUE;
1819  for (i=0;i<IDELEMS(id1);i++)
1820  {
1821    if (id1->m[i] != NULL)
1822    {
1823      p = kNF(id2,currRing->qideal,id1->m[i]);
1824      if (p != NULL)
1825      {
1826        p_Delete(&p,currRing);
1827        return FALSE;
1828      }
1829    }
1830  }
1831  return TRUE;
1832}
1833
1834BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
1835{
1836  if ((Q!=NULL) && (!idHomIdeal(Q,NULL)))  { PrintS(" Q not hom\n"); return FALSE;}
1837  if (idIs0(m)) return TRUE;
1838
1839  int cmax=-1;
1840  int i;
1841  poly p=NULL;
1842  int length=IDELEMS(m);
1843  polyset P=m->m;
1844  for (i=length-1;i>=0;i--)
1845  {
1846    p=P[i];
1847    if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
1848  }
1849  if (w != NULL)
1850  if (w->length()+1 < cmax)
1851  {
1852    // Print("length: %d - %d \n", w->length(),cmax);
1853    return FALSE;
1854  }
1855
1856  if(w!=NULL)
1857    p_SetModDeg(w, currRing);
1858
1859  for (i=length-1;i>=0;i--)
1860  {
1861    p=P[i];
1862    if (p!=NULL)
1863    {
1864      int d=currRing->pFDeg(p,currRing);
1865      loop
1866      {
1867        pIter(p);
1868        if (p==NULL) break;
1869        if (d!=currRing->pFDeg(p,currRing))
1870        {
1871          //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
1872          if(w!=NULL)
1873            p_SetModDeg(NULL, currRing);
1874          return FALSE;
1875        }
1876      }
1877    }
1878  }
1879
1880  if(w!=NULL)
1881    p_SetModDeg(NULL, currRing);
1882
1883  return TRUE;
1884}
1885
1886ideal idSeries(int n,ideal M,matrix U,intvec *w)
1887{
1888  for(int i=IDELEMS(M)-1;i>=0;i--)
1889  {
1890    if(U==NULL)
1891      M->m[i]=pSeries(n,M->m[i],NULL,w);
1892    else
1893    {
1894      M->m[i]=pSeries(n,M->m[i],MATELEM(U,i+1,i+1),w);
1895      MATELEM(U,i+1,i+1)=NULL;
1896    }
1897  }
1898  if(U!=NULL)
1899    idDelete((ideal*)&U);
1900  return M;
1901}
1902
1903matrix idDiff(matrix i, int k)
1904{
1905  int e=MATCOLS(i)*MATROWS(i);
1906  matrix r=mpNew(MATROWS(i),MATCOLS(i));
1907  r->rank=i->rank;
1908  int j;
1909  for(j=0; j<e; j++)
1910  {
1911    r->m[j]=pDiff(i->m[j],k);
1912  }
1913  return r;
1914}
1915
1916matrix idDiffOp(ideal I, ideal J,BOOLEAN multiply)
1917{
1918  matrix r=mpNew(IDELEMS(I),IDELEMS(J));
1919  int i,j;
1920  for(i=0; i<IDELEMS(I); i++)
1921  {
1922    for(j=0; j<IDELEMS(J); j++)
1923    {
1924      MATELEM(r,i+1,j+1)=pDiffOp(I->m[i],J->m[j],multiply);
1925    }
1926  }
1927  return r;
1928}
1929
1930/*3
1931*handles for some ideal operations the ring/syzcomp managment
1932*returns all syzygies (componentwise-)shifted by -syzcomp
1933*or -syzcomp-1 (in case of ideals as input)
1934static ideal idHandleIdealOp(ideal arg,int syzcomp,int isIdeal=FALSE)
1935{
1936  ring orig_ring=currRing;
1937  ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE); rChangeCurrRing(syz_ring);
1938  rSetSyzComp(length, syz_ring);
1939
1940  ideal s_temp;
1941  if (orig_ring!=syz_ring)
1942    s_temp=idrMoveR_NoSort(arg,orig_ring, syz_ring);
1943  else
1944    s_temp=arg;
1945
1946  ideal s_temp1 = kStd(s_temp,currRing->qideal,testHomog,&w,NULL,length);
1947  if (w!=NULL) delete w;
1948
1949  if (syz_ring!=orig_ring)
1950  {
1951    idDelete(&s_temp);
1952    rChangeCurrRing(orig_ring);
1953  }
1954
1955  idDelete(&temp);
1956  ideal temp1=idRingCopy(s_temp1,syz_ring);
1957
1958  if (syz_ring!=orig_ring)
1959  {
1960    rChangeCurrRing(syz_ring);
1961    idDelete(&s_temp1);
1962    rChangeCurrRing(orig_ring);
1963    rDelete(syz_ring);
1964  }
1965
1966  for (i=0;i<IDELEMS(temp1);i++)
1967  {
1968    if ((temp1->m[i]!=NULL)
1969    && (pGetComp(temp1->m[i])<=length))
1970    {
1971      pDelete(&(temp1->m[i]));
1972    }
1973    else
1974    {
1975      p_Shift(&(temp1->m[i]),-length,currRing);
1976    }
1977  }
1978  temp1->rank = rk;
1979  idSkipZeroes(temp1);
1980
1981  return temp1;
1982}
1983*/
1984/*2
1985* represents (h1+h2)/h2=h1/(h1 intersect h2)
1986*/
1987//ideal idModulo (ideal h2,ideal h1)
1988ideal idModulo (ideal h2,ideal h1, tHomog hom, intvec ** w)
1989{
1990  intvec *wtmp=NULL;
1991
1992  int i,k,rk,flength=0,slength,length;
1993  poly p,q;
1994
1995  if (idIs0(h2))
1996    return idFreeModule(si_max(1,h2->ncols));
1997  if (!idIs0(h1))
1998    flength = id_RankFreeModule(h1,currRing);
1999  slength = id_RankFreeModule(h2,currRing);
2000  length  = si_max(flength,slength);
2001  if (length==0)
2002  {
2003    length = 1;
2004  }
2005  ideal temp = idInit(IDELEMS(h2),length+IDELEMS(h2));
2006  if ((w!=NULL)&&((*w)!=NULL))
2007  {
2008    //Print("input weights:");(*w)->show(1);PrintLn();
2009    int d;
2010    int k;
2011    wtmp=new intvec(length+IDELEMS(h2));
2012    for (i=0;i<length;i++)
2013      ((*wtmp)[i])=(**w)[i];
2014    for (i=0;i<IDELEMS(h2);i++)
2015    {
2016      poly p=h2->m[i];
2017      if (p!=NULL)
2018      {
2019        d = p_Deg(p,currRing);
2020        k= pGetComp(p);
2021        if (slength>0) k--;
2022        d +=((**w)[k]);
2023        ((*wtmp)[i+length]) = d;
2024      }
2025    }
2026    //Print("weights:");wtmp->show(1);PrintLn();
2027  }
2028  for (i=0;i<IDELEMS(h2);i++)
2029  {
2030    temp->m[i] = pCopy(h2->m[i]);
2031    q = pOne();
2032    pSetComp(q,i+1+length);
2033    pSetmComp(q);
2034    if(temp->m[i]!=NULL)
2035    {
2036      if (slength==0) p_Shift(&(temp->m[i]),1,currRing);
2037      p = temp->m[i];
2038      while (pNext(p)!=NULL) pIter(p);
2039      pNext(p) = q; // will be sorted later correctly
2040    }
2041    else
2042      temp->m[i]=q;
2043  }
2044  rk = k = IDELEMS(h2);
2045  if (!idIs0(h1))
2046  {
2047    pEnlargeSet(&(temp->m),IDELEMS(temp),IDELEMS(h1));
2048    IDELEMS(temp) += IDELEMS(h1);
2049    for (i=0;i<IDELEMS(h1);i++)
2050    {
2051      if (h1->m[i]!=NULL)
2052      {
2053        temp->m[k] = pCopy(h1->m[i]);
2054        if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
2055        k++;
2056      }
2057    }
2058  }
2059
2060  ring orig_ring=currRing;
2061  ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE); rChangeCurrRing(syz_ring);
2062  // we can use OPT_RETURN_SB only, if syz_ring==orig_ring,
2063  // therefore we disable OPT_RETURN_SB for modulo:
2064  // (see tr. #701)
2065  //if (TEST_OPT_RETURN_SB)
2066  //  rSetSyzComp(IDELEMS(h2)+length, syz_ring);
2067  //else
2068    rSetSyzComp(length, syz_ring);
2069  ideal s_temp;
2070
2071  if (syz_ring != orig_ring)
2072  {
2073    s_temp = idrMoveR_NoSort(temp, orig_ring, syz_ring);
2074  }
2075  else
2076  {
2077    s_temp = temp;
2078  }
2079
2080  idTest(s_temp);
2081  ideal s_temp1 = kStd(s_temp,currRing->qideal,hom,&wtmp,NULL,length);
2082
2083  //if (wtmp!=NULL)  Print("output weights:");wtmp->show(1);PrintLn();
2084  if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
2085  {
2086    delete *w;
2087    *w=new intvec(IDELEMS(h2));
2088    for (i=0;i<IDELEMS(h2);i++)
2089      ((**w)[i])=(*wtmp)[i+length];
2090  }
2091  if (wtmp!=NULL) delete wtmp;
2092
2093  for (i=0;i<IDELEMS(s_temp1);i++)
2094  {
2095    if ((s_temp1->m[i]!=NULL)
2096    && (((int)pGetComp(s_temp1->m[i]))<=length))
2097    {
2098      p_Delete(&(s_temp1->m[i]),currRing);
2099    }
2100    else
2101    {
2102      p_Shift(&(s_temp1->m[i]),-length,currRing);
2103    }
2104  }
2105  s_temp1->rank = rk;
2106  idSkipZeroes(s_temp1);
2107
2108  if (syz_ring!=orig_ring)
2109  {
2110    rChangeCurrRing(orig_ring);
2111    s_temp1 = idrMoveR_NoSort(s_temp1, syz_ring, orig_ring);
2112    rDelete(syz_ring);
2113    // Hmm ... here seems to be a memory leak
2114    // However, simply deleting it causes memory trouble
2115    // idDelete(&s_temp);
2116  }
2117  else
2118  {
2119    idDelete(&temp);
2120  }
2121  idTest(s_temp1);
2122  return s_temp1;
2123}
2124
2125/*
2126*computes module-weights for liftings of homogeneous modules
2127*/
2128intvec * idMWLift(ideal mod,intvec * weights)
2129{
2130  if (idIs0(mod)) return new intvec(2);
2131  int i=IDELEMS(mod);
2132  while ((i>0) && (mod->m[i-1]==NULL)) i--;
2133  intvec *result = new intvec(i+1);
2134  while (i>0)
2135  {
2136    (*result)[i]=currRing->pFDeg(mod->m[i],currRing)+(*weights)[pGetComp(mod->m[i])];
2137  }
2138  return result;
2139}
2140
2141/*2
2142*sorts the kbase for idCoef* in a special way (lexicographically
2143*with x_max,...,x_1)
2144*/
2145ideal idCreateSpecialKbase(ideal kBase,intvec ** convert)
2146{
2147  int i;
2148  ideal result;
2149
2150  if (idIs0(kBase)) return NULL;
2151  result = idInit(IDELEMS(kBase),kBase->rank);
2152  *convert = idSort(kBase,FALSE);
2153  for (i=0;i<(*convert)->length();i++)
2154  {
2155    result->m[i] = pCopy(kBase->m[(**convert)[i]-1]);
2156  }
2157  return result;
2158}
2159
2160/*2
2161*returns the index of a given monom in the list of the special kbase
2162*/
2163int idIndexOfKBase(poly monom, ideal kbase)
2164{
2165  int j=IDELEMS(kbase);
2166
2167  while ((j>0) && (kbase->m[j-1]==NULL)) j--;
2168  if (j==0) return -1;
2169  int i=(currRing->N);
2170  while (i>0)
2171  {
2172    loop
2173    {
2174      if (pGetExp(monom,i)>pGetExp(kbase->m[j-1],i)) return -1;
2175      if (pGetExp(monom,i)==pGetExp(kbase->m[j-1],i)) break;
2176      j--;
2177      if (j==0) return -1;
2178    }
2179    if (i==1)
2180    {
2181      while(j>0)
2182      {
2183        if (pGetComp(monom)==pGetComp(kbase->m[j-1])) return j-1;
2184        if (pGetComp(monom)>pGetComp(kbase->m[j-1])) return -1;
2185        j--;
2186      }
2187    }
2188    i--;
2189  }
2190  return -1;
2191}
2192
2193/*2
2194*decomposes the monom in a part of coefficients described by the
2195*complement of how and a monom in variables occuring in how, the
2196*index of which in kbase is returned as integer pos (-1 if it don't
2197*exists)
2198*/
2199poly idDecompose(poly monom, poly how, ideal kbase, int * pos)
2200{
2201  int i;
2202  poly coeff=pOne(), base=pOne();
2203
2204  for (i=1;i<=(currRing->N);i++)
2205  {
2206    if (pGetExp(how,i)>0)
2207    {
2208      pSetExp(base,i,pGetExp(monom,i));
2209    }
2210    else
2211    {
2212      pSetExp(coeff,i,pGetExp(monom,i));
2213    }
2214  }
2215  pSetComp(base,pGetComp(monom));
2216  pSetm(base);
2217  pSetCoeff(coeff,nCopy(pGetCoeff(monom)));
2218  pSetm(coeff);
2219  *pos = idIndexOfKBase(base,kbase);
2220  if (*pos<0)
2221    p_Delete(&coeff,currRing);
2222  p_Delete(&base,currRing);
2223  return coeff;
2224}
2225
2226/*2
2227*returns a matrix A of coefficients with kbase*A=arg
2228*if all monomials in variables of how occur in kbase
2229*the other are deleted
2230*/
2231matrix idCoeffOfKBase(ideal arg, ideal kbase, poly how)
2232{
2233  matrix result;
2234  ideal tempKbase;
2235  poly p,q;
2236  intvec * convert;
2237  int i=IDELEMS(kbase),j=IDELEMS(arg),k,pos;
2238#if 0
2239  while ((i>0) && (kbase->m[i-1]==NULL)) i--;
2240  if (idIs0(arg))
2241    return mpNew(i,1);
2242  while ((j>0) && (arg->m[j-1]==NULL)) j--;
2243  result = mpNew(i,j);
2244#else
2245  result = mpNew(i, j);
2246  while ((j>0) && (arg->m[j-1]==NULL)) j--;
2247#endif
2248
2249  tempKbase = idCreateSpecialKbase(kbase,&convert);
2250  for (k=0;k<j;k++)
2251  {
2252    p = arg->m[k];
2253    while (p!=NULL)
2254    {
2255      q = idDecompose(p,how,tempKbase,&pos);
2256      if (pos>=0)
2257      {
2258        MATELEM(result,(*convert)[pos],k+1) =
2259            pAdd(MATELEM(result,(*convert)[pos],k+1),q);
2260      }
2261      else
2262        p_Delete(&q,currRing);
2263      pIter(p);
2264    }
2265  }
2266  idDelete(&tempKbase);
2267  return result;
2268}
2269
2270static void idDeleteComps(ideal arg,int* red_comp,int del)
2271// red_comp is an array [0..args->rank]
2272{
2273  int i,j;
2274  poly p;
2275
2276  for (i=IDELEMS(arg)-1;i>=0;i--)
2277  {
2278    p = arg->m[i];
2279    while (p!=NULL)
2280    {
2281      j = pGetComp(p);
2282      if (red_comp[j]!=j)
2283      {
2284        pSetComp(p,red_comp[j]);
2285        pSetmComp(p);
2286      }
2287      pIter(p);
2288    }
2289  }
2290  (arg->rank) -= del;
2291}
2292
2293/*2
2294* returns the presentation of an isomorphic, minimally
2295* embedded  module (arg represents the quotient!)
2296*/
2297ideal idMinEmbedding(ideal arg,BOOLEAN inPlace, intvec **w)
2298{
2299  if (idIs0(arg)) return idInit(1,arg->rank);
2300  int i,next_gen,next_comp;
2301  ideal res=arg;
2302  if (!inPlace) res = idCopy(arg);
2303  res->rank=si_max(res->rank,id_RankFreeModule(res,currRing));
2304  int *red_comp=(int*)omAlloc((res->rank+1)*sizeof(int));
2305  for (i=res->rank;i>=0;i--) red_comp[i]=i;
2306
2307  int del=0;
2308  loop
2309  {
2310    next_gen = id_ReadOutPivot(res, &next_comp, currRing);
2311    if (next_gen<0) break;
2312    del++;
2313    syGaussForOne(res,next_gen,next_comp,0,IDELEMS(res));
2314    for(i=next_comp+1;i<=arg->rank;i++) red_comp[i]--;
2315    if ((w !=NULL)&&(*w!=NULL))
2316    {
2317      for(i=next_comp;i<(*w)->length();i++) (**w)[i-1]=(**w)[i];
2318    }
2319  }
2320
2321  idDeleteComps(res,red_comp,del);
2322  idSkipZeroes(res);
2323  omFree(red_comp);
2324
2325  if ((w !=NULL)&&(*w!=NULL) &&(del>0))
2326  {
2327    int nl=si_max((*w)->length()-del,1);
2328    intvec *wtmp=new intvec(nl);
2329    for(i=0;i<res->rank;i++) (*wtmp)[i]=(**w)[i];
2330    delete *w;
2331    *w=wtmp;
2332  }
2333  return res;
2334}
2335
2336#include <polys/clapsing.h>
2337
2338#if 0
2339poly id_GCD(poly f, poly g, const ring r)
2340{
2341  ring save_r=currRing;
2342  rChangeCurrRing(r);
2343  ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2344  intvec *w = NULL;
2345  ideal S=idSyzygies(I,testHomog,&w);
2346  if (w!=NULL) delete w;
2347  poly gg=pTakeOutComp(&(S->m[0]),2);
2348  idDelete(&S);
2349  poly gcd_p=singclap_pdivide(f,gg,r);
2350  p_Delete(&gg,r);
2351  rChangeCurrRing(save_r);
2352  return gcd_p;
2353}
2354#else
2355poly id_GCD(poly f, poly g, const ring r)
2356{
2357  ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2358  intvec *w = NULL;
2359
2360  ring save_r = currRing; rChangeCurrRing(r); ideal S=idSyzygies(I,testHomog,&w); rChangeCurrRing(save_r);
2361
2362  if (w!=NULL) delete w;
2363  poly gg=p_TakeOutComp(&(S->m[0]), 2, r);
2364  id_Delete(&S, r);
2365  poly gcd_p=singclap_pdivide(f,gg, r);
2366  p_Delete(&gg, r);
2367
2368  return gcd_p;
2369}
2370#endif
2371
2372#if 0
2373/*2
2374* xx,q: arrays of length 0..rl-1
2375* xx[i]: SB mod q[i]
2376* assume: char=0
2377* assume: q[i]!=0
2378* destroys xx
2379*/
2380ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring R)
2381{
2382  int cnt=IDELEMS(xx[0])*xx[0]->nrows;
2383  ideal result=idInit(cnt,xx[0]->rank);
2384  result->nrows=xx[0]->nrows; // for lifting matrices
2385  result->ncols=xx[0]->ncols; // for lifting matrices
2386  int i,j;
2387  poly r,h,hh,res_p;
2388  number *x=(number *)omAlloc(rl*sizeof(number));
2389  for(i=cnt-1;i>=0;i--)
2390  {
2391    res_p=NULL;
2392    loop
2393    {
2394      r=NULL;
2395      for(j=rl-1;j>=0;j--)
2396      {
2397        h=xx[j]->m[i];
2398        if ((h!=NULL)
2399        &&((r==NULL)||(p_LmCmp(r,h,R)==-1)))
2400          r=h;
2401      }
2402      if (r==NULL) break;
2403      h=p_Head(r, R);
2404      for(j=rl-1;j>=0;j--)
2405      {
2406        hh=xx[j]->m[i];
2407        if ((hh!=NULL) && (p_LmCmp(r,hh, R)==0))
2408        {
2409          x[j]=p_GetCoeff(hh, R);
2410          hh=p_LmFreeAndNext(hh, R);
2411          xx[j]->m[i]=hh;
2412        }
2413        else
2414          x[j]=n_Init(0, R->cf); // is R->cf really n_Q???, yes!
2415      }
2416
2417      number n=n_ChineseRemainder(x,q,rl, R->cf);
2418
2419      for(j=rl-1;j>=0;j--)
2420      {
2421        x[j]=NULL; // nlInit(0...) takes no memory
2422      }
2423      if (n_IsZero(n, R->cf)) p_Delete(&h, R);
2424      else
2425      {
2426        p_SetCoeff(h,n, R);
2427        //Print("new mon:");pWrite(h);
2428        res_p=p_Add_q(res_p, h, R);
2429      }
2430    }
2431    result->m[i]=res_p;
2432  }
2433  omFree(x);
2434  for(i=rl-1;i>=0;i--) id_Delete(&(xx[i]), R);
2435  omFree(xx);
2436  return result;
2437}
2438#endif
2439/* currently unsed:
2440ideal idChineseRemainder(ideal *xx, intvec *iv)
2441{
2442  int rl=iv->length();
2443  number *q=(number *)omAlloc(rl*sizeof(number));
2444  int i;
2445  for(i=0; i<rl; i++)
2446  {
2447    q[i]=nInit((*iv)[i]);
2448  }
2449  return idChineseRemainder(xx,q,rl);
2450}
2451*/
2452/*
2453 * lift ideal with coeffs over Z (mod N) to Q via Farey
2454 */
2455ideal id_Farey(ideal x, number N, const ring r)
2456{
2457  int cnt=IDELEMS(x)*x->nrows;
2458  ideal result=idInit(cnt,x->rank);
2459  result->nrows=x->nrows; // for lifting matrices
2460  result->ncols=x->ncols; // for lifting matrices
2461
2462  int i;
2463  for(i=cnt-1;i>=0;i--)
2464  {
2465    result->m[i]=p_Farey(x->m[i],N,r);
2466  }
2467  return result;
2468}
2469
2470
2471
2472
2473// uses glabl vars via pSetModDeg
2474/*
2475BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
2476{
2477  if ((Q!=NULL) && (!idHomIdeal(Q,NULL)))  { PrintS(" Q not hom\n"); return FALSE;}
2478  if (idIs0(m)) return TRUE;
2479
2480  int cmax=-1;
2481  int i;
2482  poly p=NULL;
2483  int length=IDELEMS(m);
2484  poly* P=m->m;
2485  for (i=length-1;i>=0;i--)
2486  {
2487    p=P[i];
2488    if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
2489  }
2490  if (w != NULL)
2491  if (w->length()+1 < cmax)
2492  {
2493    // Print("length: %d - %d \n", w->length(),cmax);
2494    return FALSE;
2495  }
2496
2497  if(w!=NULL)
2498    p_SetModDeg(w, currRing);
2499
2500  for (i=length-1;i>=0;i--)
2501  {
2502    p=P[i];
2503    poly q=p;
2504    if (p!=NULL)
2505    {
2506      int d=p_FDeg(p,currRing);
2507      loop
2508      {
2509        pIter(p);
2510        if (p==NULL) break;
2511        if (d!=p_FDeg(p,currRing))
2512        {
2513          //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
2514          if(w!=NULL)
2515            p_SetModDeg(NULL, currRing);
2516          return FALSE;
2517        }
2518      }
2519    }
2520  }
2521
2522  if(w!=NULL)
2523    p_SetModDeg(NULL, currRing);
2524
2525  return TRUE;
2526}
2527*/
2528
2529/// keeps the first k (>= 1) entries of the given ideal
2530/// (Note that the kept polynomials may be zero.)
2531void idKeepFirstK(ideal id, const int k)
2532{
2533   for (int i = IDELEMS(id)-1; i >= k; i--)
2534   {
2535      if (id->m[i] != NULL) pDelete(&id->m[i]);
2536   }
2537   int kk=k;
2538   if (k==0) kk=1; /* ideals must have at least one element(0)*/
2539   pEnlargeSet(&(id->m), IDELEMS(id), kk-IDELEMS(id));
2540   IDELEMS(id) = kk;
2541}
2542
2543typedef struct
2544{
2545  poly p;
2546  int index;
2547} poly_sort;
2548
2549int pCompare_qsort(const void *a, const void *b)
2550{
2551  return (p_Compare(((poly_sort *)a)->p, ((poly_sort *)b)->p,currRing));
2552}
2553
2554void idSort_qsort(poly_sort *id_sort, int idsize)
2555{
2556  qsort(id_sort, idsize, sizeof(poly_sort), pCompare_qsort);
2557}
2558
2559/*2
2560* ideal id = (id[i])
2561* if id[i] = id[j] then id[j] is deleted for j > i
2562*/
2563void idDelEquals(ideal id)
2564{
2565  int idsize = IDELEMS(id);
2566  poly_sort *id_sort = (poly_sort *)omAlloc0(idsize*sizeof(poly_sort));
2567  for (int i = 0; i < idsize; i++)
2568  {
2569    id_sort[i].p = id->m[i];
2570    id_sort[i].index = i;
2571  }
2572  idSort_qsort(id_sort, idsize);
2573  int index, index_i, index_j;
2574  int i = 0;
2575  for (int j = 1; j < idsize; j++)
2576  {
2577    if (id_sort[i].p != NULL && pEqualPolys(id_sort[i].p, id_sort[j].p))
2578    {
2579      index_i = id_sort[i].index;
2580      index_j = id_sort[j].index;
2581      if (index_j > index_i)
2582      {
2583        index = index_j;
2584      }
2585      else
2586      {
2587        index = index_i;
2588        i = j;
2589      }
2590      pDelete(&id->m[index]);
2591    }
2592    else
2593    {
2594      i = j;
2595    }
2596  }
2597  omFreeSize((ADDRESS)(id_sort), idsize*sizeof(poly_sort));
2598}
Note: See TracBrowser for help on using the repository browser.