source: git/kernel/ideals.cc @ 01c97b

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