"Fossies" - the Fresh Open Source Software Archive

Member "singular-4.2.1/kernel/ideals.cc" (9 Jun 2021, 75475 Bytes) of package /linux/misc/singular-4.2.1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "ideals.cc" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 4.2.0p3_vs_4.2.1.

    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 */
   51 ideal 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 
  133 static 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 
  201 static 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 */
  316 ideal 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 */
  472 ideal 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  */
  607 static 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 
  709 ideal 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 */
  830 ideal 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 */
  976 ideal 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,0);
  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 
 1041 static 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 
 1082 static 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 
 1099 ideal idLift(ideal mod, ideal submod,ideal *rest, BOOLEAN goodShape,
 1100              BOOLEAN isSB, BOOLEAN divide, matrix *unit, GbVariant alg)
 1101 {
 1102   int lsmod =id_RankFreeModule(submod,currRing), j, k;
 1103   int comps_to_add=0;
 1104   int idelems_mod=IDELEMS(mod);
 1105   int idelems_submod=IDELEMS(submod);
 1106   poly p;
 1107 
 1108   if (idIs0(submod))
 1109   {
 1110     if (rest!=NULL)
 1111     {
 1112       *rest=idInit(1,mod->rank);
 1113     }
 1114     idLift_setUnit(idelems_submod,unit);
 1115     return idInit(1,idelems_mod);
 1116   }
 1117   if (idIs0(mod)) /* and not idIs0(submod) */
 1118   {
 1119     if (rest!=NULL)
 1120     {
 1121       *rest=idCopy(submod);
 1122       idLift_setUnit(idelems_submod,unit);
 1123       return idInit(1,idelems_mod);
 1124     }
 1125     else
 1126     {
 1127       WerrorS("2nd module does not lie in the first");
 1128       return NULL;
 1129     }
 1130   }
 1131   if (unit!=NULL)
 1132   {
 1133     comps_to_add = idelems_submod;
 1134     while ((comps_to_add>0) && (submod->m[comps_to_add-1]==NULL))
 1135       comps_to_add--;
 1136   }
 1137   k=si_max(id_RankFreeModule(mod,currRing),id_RankFreeModule(submod,currRing));
 1138   if  ((k!=0) && (lsmod==0)) lsmod=1;
 1139   k=si_max(k,(int)mod->rank);
 1140   if (k<submod->rank) { WarnS("rk(submod) > rk(mod) ?");k=submod->rank; }
 1141 
 1142   ring orig_ring=currRing;
 1143   ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
 1144   rSetSyzComp(k,syz_ring);
 1145   rChangeCurrRing(syz_ring);
 1146 
 1147   ideal s_mod, s_temp;
 1148   if (orig_ring != syz_ring)
 1149   {
 1150     s_mod = idrCopyR_NoSort(mod,orig_ring,syz_ring);
 1151     s_temp = idrCopyR_NoSort(submod,orig_ring,syz_ring);
 1152   }
 1153   else
 1154   {
 1155     s_mod = mod;
 1156     s_temp = idCopy(submod);
 1157   }
 1158   ideal s_h3;
 1159   if (isSB)
 1160   {
 1161     s_h3 = idCopy(s_mod);
 1162     idPrepareStd(s_h3, k+comps_to_add);
 1163   }
 1164   else
 1165   {
 1166     s_h3 = idPrepare(s_mod,NULL,(tHomog)FALSE,k+comps_to_add,NULL,alg);
 1167   }
 1168   if (!goodShape)
 1169   {
 1170     for (j=0;j<IDELEMS(s_h3);j++)
 1171     {
 1172       if ((s_h3->m[j] != NULL) && (pMinComp(s_h3->m[j]) > k))
 1173         p_Delete(&(s_h3->m[j]),currRing);
 1174     }
 1175   }
 1176   idSkipZeroes(s_h3);
 1177   if (lsmod==0)
 1178   {
 1179     id_Shift(s_temp,1,currRing);
 1180   }
 1181   if (unit!=NULL)
 1182   {
 1183     for(j = 0;j<comps_to_add;j++)
 1184     {
 1185       p = s_temp->m[j];
 1186       if (p!=NULL)
 1187       {
 1188         while (pNext(p)!=NULL) pIter(p);
 1189         pNext(p) = pOne();
 1190         pIter(p);
 1191         pSetComp(p,1+j+k);
 1192         pSetmComp(p);
 1193         p = pNeg(p);
 1194       }
 1195     }
 1196     s_temp->rank += (k+comps_to_add);
 1197   }
 1198   ideal s_result = kNF(s_h3,currRing->qideal,s_temp,k);
 1199   s_result->rank = s_h3->rank;
 1200   ideal s_rest = idInit(IDELEMS(s_result),k);
 1201   idDelete(&s_h3);
 1202   idDelete(&s_temp);
 1203 
 1204   for (j=0;j<IDELEMS(s_result);j++)
 1205   {
 1206     if (s_result->m[j]!=NULL)
 1207     {
 1208       if (pGetComp(s_result->m[j])<=k)
 1209       {
 1210         if (!divide)
 1211         {
 1212           if (rest==NULL)
 1213           {
 1214             if (isSB)
 1215             {
 1216               WarnS("first module not a standardbasis\n"
 1217               "// ** or second not a proper submodule");
 1218             }
 1219             else
 1220               WerrorS("2nd module does not lie in the first");
 1221           }
 1222           idDelete(&s_result);
 1223           idDelete(&s_rest);
 1224           if(syz_ring!=orig_ring)
 1225           {
 1226             idDelete(&s_mod);
 1227             rChangeCurrRing(orig_ring);
 1228             rDelete(syz_ring);
 1229           }
 1230           if (unit!=NULL)
 1231           {
 1232             idLift_setUnit(idelems_submod,unit);
 1233           }
 1234           if (rest!=NULL) *rest=idCopy(submod);
 1235           s_result=idInit(idelems_submod,idelems_mod);
 1236           return s_result;
 1237         }
 1238         else
 1239         {
 1240           p = s_rest->m[j] = s_result->m[j];
 1241           while ((pNext(p)!=NULL) && (pGetComp(pNext(p))<=k)) pIter(p);
 1242           s_result->m[j] = pNext(p);
 1243           pNext(p) = NULL;
 1244         }
 1245       }
 1246       p_Shift(&(s_result->m[j]),-k,currRing);
 1247       pNeg(s_result->m[j]);
 1248     }
 1249   }
 1250   if ((lsmod==0) && (s_rest!=NULL))
 1251   {
 1252     for (j=IDELEMS(s_rest);j>0;j--)
 1253     {
 1254       if (s_rest->m[j-1]!=NULL)
 1255       {
 1256         p_Shift(&(s_rest->m[j-1]),-1,currRing);
 1257       }
 1258     }
 1259   }
 1260   if(syz_ring!=orig_ring)
 1261   {
 1262     idDelete(&s_mod);
 1263     rChangeCurrRing(orig_ring);
 1264     s_result = idrMoveR_NoSort(s_result, syz_ring, orig_ring);
 1265     s_rest = idrMoveR_NoSort(s_rest, syz_ring, orig_ring);
 1266     rDelete(syz_ring);
 1267   }
 1268   if (rest!=NULL)
 1269   {
 1270     s_rest->rank=mod->rank;
 1271     *rest = s_rest;
 1272   }
 1273   else
 1274     idDelete(&s_rest);
 1275   if (unit!=NULL)
 1276   {
 1277     *unit=mpNew(idelems_submod,idelems_submod);
 1278     int i;
 1279     for(i=0;i<IDELEMS(s_result);i++)
 1280     {
 1281       poly p=s_result->m[i];
 1282       poly q=NULL;
 1283       while(p!=NULL)
 1284       {
 1285         if(pGetComp(p)<=comps_to_add)
 1286         {
 1287           pSetComp(p,0);
 1288           if (q!=NULL)
 1289           {
 1290             pNext(q)=pNext(p);
 1291           }
 1292           else
 1293           {
 1294             pIter(s_result->m[i]);
 1295           }
 1296           pNext(p)=NULL;
 1297           MATELEM(*unit,i+1,i+1)=pAdd(MATELEM(*unit,i+1,i+1),p);
 1298           if(q!=NULL)   p=pNext(q);
 1299           else          p=s_result->m[i];
 1300         }
 1301         else
 1302         {
 1303           q=p;
 1304           pIter(p);
 1305         }
 1306       }
 1307       p_Shift(&s_result->m[i],-comps_to_add,currRing);
 1308     }
 1309   }
 1310   s_result->rank=idelems_mod;
 1311   return s_result;
 1312 }
 1313 
 1314 /*2
 1315 *computes division of P by Q with remainder up to (w-weighted) degree n
 1316 *P, Q, and w are not changed
 1317 */
 1318 void idLiftW(ideal P,ideal Q,int n,matrix &T, ideal &R,int *w)
 1319 {
 1320   long N=0;
 1321   int i;
 1322   for(i=IDELEMS(Q)-1;i>=0;i--)
 1323     if(w==NULL)
 1324       N=si_max(N,p_Deg(Q->m[i],currRing));
 1325     else
 1326       N=si_max(N,p_DegW(Q->m[i],w,currRing));
 1327   N+=n;
 1328 
 1329   T=mpNew(IDELEMS(Q),IDELEMS(P));
 1330   R=idInit(IDELEMS(P),P->rank);
 1331 
 1332   for(i=IDELEMS(P)-1;i>=0;i--)
 1333   {
 1334     poly p;
 1335     if(w==NULL)
 1336       p=ppJet(P->m[i],N);
 1337     else
 1338       p=ppJetW(P->m[i],N,w);
 1339 
 1340     int j=IDELEMS(Q)-1;
 1341     while(p!=NULL)
 1342     {
 1343       if(pDivisibleBy(Q->m[j],p))
 1344       {
 1345         poly p0=p_DivideM(pHead(p),pHead(Q->m[j]),currRing);
 1346         if(w==NULL)
 1347           p=pJet(pSub(p,ppMult_mm(Q->m[j],p0)),N);
 1348         else
 1349           p=pJetW(pSub(p,ppMult_mm(Q->m[j],p0)),N,w);
 1350         pNormalize(p);
 1351         if(((w==NULL)&&(p_Deg(p0,currRing)>n))||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
 1352           p_Delete(&p0,currRing);
 1353         else
 1354           MATELEM(T,j+1,i+1)=pAdd(MATELEM(T,j+1,i+1),p0);
 1355         j=IDELEMS(Q)-1;
 1356       }
 1357       else
 1358       {
 1359         if(j==0)
 1360         {
 1361           poly p0=p;
 1362           pIter(p);
 1363           pNext(p0)=NULL;
 1364           if(((w==NULL)&&(p_Deg(p0,currRing)>n))
 1365           ||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
 1366             p_Delete(&p0,currRing);
 1367           else
 1368             R->m[i]=pAdd(R->m[i],p0);
 1369           j=IDELEMS(Q)-1;
 1370         }
 1371         else
 1372           j--;
 1373       }
 1374     }
 1375   }
 1376 }
 1377 
 1378 /*2
 1379 *computes the quotient of h1,h2 : internal routine for idQuot
 1380 *BEWARE: the returned ideals may contain incorrectly ordered polys !
 1381 *
 1382 */
 1383 static ideal idInitializeQuot (ideal  h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN *addOnlyOne, int *kkmax)
 1384 {
 1385   idTest(h1);
 1386   idTest(h2);
 1387 
 1388   ideal temph1;
 1389   poly     p,q = NULL;
 1390   int i,l,ll,k,kkk,kmax;
 1391   int j = 0;
 1392   int k1 = id_RankFreeModule(h1,currRing);
 1393   int k2 = id_RankFreeModule(h2,currRing);
 1394   tHomog   hom=isNotHomog;
 1395   k=si_max(k1,k2);
 1396   if (k==0)
 1397     k = 1;
 1398   if ((k2==0) && (k>1)) *addOnlyOne = FALSE;
 1399   intvec * weights;
 1400   hom = (tHomog)idHomModule(h1,currRing->qideal,&weights);
 1401   if /**addOnlyOne &&*/ (/*(*/ !h1IsStb /*)*/)
 1402     temph1 = kStd(h1,currRing->qideal,hom,&weights,NULL);
 1403   else
 1404     temph1 = idCopy(h1);
 1405   if (weights!=NULL) delete weights;
 1406   idTest(temph1);
 1407 /*--- making a single vector from h2 ---------------------*/
 1408   for (i=0; i<IDELEMS(h2); i++)
 1409   {
 1410     if (h2->m[i] != NULL)
 1411     {
 1412       p = pCopy(h2->m[i]);
 1413       if (k2 == 0)
 1414         p_Shift(&p,j*k+1,currRing);
 1415       else
 1416         p_Shift(&p,j*k,currRing);
 1417       q = pAdd(q,p);
 1418       j++;
 1419     }
 1420   }
 1421   *kkmax = kmax = j*k+1;
 1422 /*--- adding a monomial for the result (syzygy) ----------*/
 1423   p = q;
 1424   while (pNext(p)!=NULL) pIter(p);
 1425   pNext(p) = pOne();
 1426   pIter(p);
 1427   pSetComp(p,kmax);
 1428   pSetmComp(p);
 1429 /*--- constructing the big matrix ------------------------*/
 1430   ideal h4 = idInit(k,kmax+k-1);
 1431   h4->m[0] = q;
 1432   if (k2 == 0)
 1433   {
 1434     for (i=1; i<k; i++)
 1435     {
 1436       if (h4->m[i-1]!=NULL)
 1437       {
 1438         p = p_Copy_noCheck(h4->m[i-1], currRing); /*h4->m[i-1]!=NULL*/
 1439         p_Shift(&p,1,currRing);
 1440         h4->m[i] = p;
 1441       }
 1442       else break;
 1443     }
 1444   }
 1445   idSkipZeroes(h4);
 1446   kkk = IDELEMS(h4);
 1447   i = IDELEMS(temph1);
 1448   for (l=0; l<i; l++)
 1449   {
 1450     if(temph1->m[l]!=NULL)
 1451     {
 1452       for (ll=0; ll<j; ll++)
 1453       {
 1454         p = pCopy(temph1->m[l]);
 1455         if (k1 == 0)
 1456           p_Shift(&p,ll*k+1,currRing);
 1457         else
 1458           p_Shift(&p,ll*k,currRing);
 1459         if (kkk >= IDELEMS(h4))
 1460         {
 1461           pEnlargeSet(&(h4->m),IDELEMS(h4),16);
 1462           IDELEMS(h4) += 16;
 1463         }
 1464         h4->m[kkk] = p;
 1465         kkk++;
 1466       }
 1467     }
 1468   }
 1469 /*--- if h2 goes in as single vector - the h1-part is just SB ---*/
 1470   if (*addOnlyOne)
 1471   {
 1472     idSkipZeroes(h4);
 1473     p = h4->m[0];
 1474     for (i=0;i<IDELEMS(h4)-1;i++)
 1475     {
 1476       h4->m[i] = h4->m[i+1];
 1477     }
 1478     h4->m[IDELEMS(h4)-1] = p;
 1479   }
 1480   idDelete(&temph1);
 1481   //idTest(h4);//see remark at the beginning
 1482   return h4;
 1483 }
 1484 
 1485 /*2
 1486 *computes the quotient of h1,h2
 1487 */
 1488 ideal idQuot (ideal  h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN resultIsIdeal)
 1489 {
 1490   // first check for special case h1:(0)
 1491   if (idIs0(h2))
 1492   {
 1493     ideal res;
 1494     if (resultIsIdeal)
 1495     {
 1496       res = idInit(1,1);
 1497       res->m[0] = pOne();
 1498     }
 1499     else
 1500       res = idFreeModule(h1->rank);
 1501     return res;
 1502   }
 1503   int i, kmax;
 1504   BOOLEAN  addOnlyOne=TRUE;
 1505   tHomog   hom=isNotHomog;
 1506   intvec * weights1;
 1507 
 1508   ideal s_h4 = idInitializeQuot (h1,h2,h1IsStb,&addOnlyOne,&kmax);
 1509 
 1510   hom = (tHomog)idHomModule(s_h4,currRing->qideal,&weights1);
 1511 
 1512   ring orig_ring=currRing;
 1513   ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
 1514   rSetSyzComp(kmax-1,syz_ring);
 1515   rChangeCurrRing(syz_ring);
 1516   if (orig_ring!=syz_ring)
 1517   //  s_h4 = idrMoveR_NoSort(s_h4,orig_ring, syz_ring);
 1518     s_h4 = idrMoveR(s_h4,orig_ring, syz_ring);
 1519   idTest(s_h4);
 1520 
 1521   #if 0
 1522   matrix m=idModule2Matrix(idCopy(s_h4));
 1523   PrintS("start:\n");
 1524   ipPrint_MA0(m,"Q");
 1525   idDelete((ideal *)&m);
 1526   PrintS("last elem:");wrp(s_h4->m[IDELEMS(s_h4)-1]);PrintLn();
 1527   #endif
 1528 
 1529   ideal s_h3;
 1530   BITSET old_test1;
 1531   SI_SAVE_OPT1(old_test1);
 1532   if (TEST_OPT_RETURN_SB) si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
 1533   if (addOnlyOne)
 1534   {
 1535     if(!rField_is_Ring(currRing)) si_opt_1 |= Sy_bit(OPT_SB_1);
 1536     s_h3 = kStd(s_h4,currRing->qideal,hom,&weights1,NULL,0/*kmax-1*/,IDELEMS(s_h4)-1);
 1537   }
 1538   else
 1539   {
 1540     s_h3 = kStd(s_h4,currRing->qideal,hom,&weights1,NULL,kmax-1);
 1541   }
 1542   SI_RESTORE_OPT1(old_test1);
 1543 
 1544   #if 0
 1545   // only together with the above debug stuff
 1546   idSkipZeroes(s_h3);
 1547   m=idModule2Matrix(idCopy(s_h3));
 1548   Print("result, kmax=%d:\n",kmax);
 1549   ipPrint_MA0(m,"S");
 1550   idDelete((ideal *)&m);
 1551   #endif
 1552 
 1553   idTest(s_h3);
 1554   if (weights1!=NULL) delete weights1;
 1555   idDelete(&s_h4);
 1556 
 1557   for (i=0;i<IDELEMS(s_h3);i++)
 1558   {
 1559     if ((s_h3->m[i]!=NULL) && (pGetComp(s_h3->m[i])>=kmax))
 1560     {
 1561       if (resultIsIdeal)
 1562         p_Shift(&s_h3->m[i],-kmax,currRing);
 1563       else
 1564         p_Shift(&s_h3->m[i],-kmax+1,currRing);
 1565     }
 1566     else
 1567       p_Delete(&s_h3->m[i],currRing);
 1568   }
 1569   if (resultIsIdeal)
 1570     s_h3->rank = 1;
 1571   else
 1572     s_h3->rank = h1->rank;
 1573   if(syz_ring!=orig_ring)
 1574   {
 1575     rChangeCurrRing(orig_ring);
 1576     s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
 1577     rDelete(syz_ring);
 1578   }
 1579   idSkipZeroes(s_h3);
 1580   idTest(s_h3);
 1581   return s_h3;
 1582 }
 1583 
 1584 /*2
 1585 * eliminate delVar (product of vars) in h1
 1586 */
 1587 ideal idElimination (ideal h1,poly delVar,intvec *hilb, GbVariant alg)
 1588 {
 1589   int    i,j=0,k,l;
 1590   ideal  h,hh, h3;
 1591   rRingOrder_t    *ord;
 1592   int    *block0,*block1;
 1593   int    ordersize=2;
 1594   int    **wv;
 1595   tHomog hom;
 1596   intvec * w;
 1597   ring tmpR;
 1598   ring origR = currRing;
 1599 
 1600   if (delVar==NULL)
 1601   {
 1602     return idCopy(h1);
 1603   }
 1604   if ((currRing->qideal!=NULL) && rIsPluralRing(origR))
 1605   {
 1606     WerrorS("cannot eliminate in a qring");
 1607     return NULL;
 1608   }
 1609   if (idIs0(h1)) return idInit(1,h1->rank);
 1610 #ifdef HAVE_PLURAL
 1611   if (rIsPluralRing(origR))
 1612     /* in the NC case, we have to check the admissibility of */
 1613     /* the subalgebra to be intersected with */
 1614   {
 1615     if ((ncRingType(origR) != nc_skew) && (ncRingType(origR) != nc_exterior)) /* in (quasi)-commutative algebras every subalgebra is admissible */
 1616     {
 1617       if (nc_CheckSubalgebra(delVar,origR))
 1618       {
 1619         WerrorS("no elimination is possible: subalgebra is not admissible");
 1620         return NULL;
 1621       }
 1622     }
 1623   }
 1624 #endif
 1625   hom=(tHomog)idHomModule(h1,NULL,&w); //sets w to weight vector or NULL
 1626   h3=idInit(16,h1->rank);
 1627   for (k=0;; k++)
 1628   {
 1629     if (origR->order[k]!=0) ordersize++;
 1630     else break;
 1631   }
 1632 #if 0
 1633   if (rIsPluralRing(origR)) // we have too keep the odering: it may be needed
 1634                             // for G-algebra
 1635   {
 1636     for (k=0;k<ordersize-1; k++)
 1637     {
 1638       block0[k+1] = origR->block0[k];
 1639       block1[k+1] = origR->block1[k];
 1640       ord[k+1] = origR->order[k];
 1641       if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
 1642     }
 1643   }
 1644   else
 1645   {
 1646     block0[1] = 1;
 1647     block1[1] = (currRing->N);
 1648     if (origR->OrdSgn==1) ord[1] = ringorder_wp;
 1649     else                  ord[1] = ringorder_ws;
 1650     wv[1]=(int*)omAlloc0((currRing->N)*sizeof(int));
 1651     double wNsqr = (double)2.0 / (double)(currRing->N);
 1652     wFunctional = wFunctionalBuch;
 1653     int  *x= (int * )omAlloc(2 * ((currRing->N) + 1) * sizeof(int));
 1654     int sl=IDELEMS(h1) - 1;
 1655     wCall(h1->m, sl, x, wNsqr);
 1656     for (sl = (currRing->N); sl!=0; sl--)
 1657       wv[1][sl-1] = x[sl + (currRing->N) + 1];
 1658     omFreeSize((ADDRESS)x, 2 * ((currRing->N) + 1) * sizeof(int));
 1659 
 1660     ord[2]=ringorder_C;
 1661     ord[3]=0;
 1662   }
 1663 #else
 1664 #endif
 1665   if ((hom==TRUE) && (origR->OrdSgn==1) && (!rIsPluralRing(origR)))
 1666   {
 1667     #if 1
 1668     // we change to an ordering:
 1669     // aa(1,1,1,...,0,0,0),wp(...),C
 1670     // this seems to be better than version 2 below,
 1671     // according to Tst/../elimiate_[3568].tat (- 17 %)
 1672     ord=(rRingOrder_t*)omAlloc0(4*sizeof(rRingOrder_t));
 1673     block0=(int*)omAlloc0(4*sizeof(int));
 1674     block1=(int*)omAlloc0(4*sizeof(int));
 1675     wv=(int**) omAlloc0(4*sizeof(int**));
 1676     block0[0] = block0[1] = 1;
 1677     block1[0] = block1[1] = rVar(origR);
 1678     wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
 1679     // use this special ordering: like ringorder_a, except that pFDeg, pWeights
 1680     // ignore it
 1681     ord[0] = ringorder_aa;
 1682     for (j=0;j<rVar(origR);j++)
 1683       if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
 1684     BOOLEAN wp=FALSE;
 1685     for (j=0;j<rVar(origR);j++)
 1686       if (p_Weight(j+1,origR)!=1) { wp=TRUE;break; }
 1687     if (wp)
 1688     {
 1689       wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
 1690       for (j=0;j<rVar(origR);j++)
 1691         wv[1][j]=p_Weight(j+1,origR);
 1692       ord[1] = ringorder_wp;
 1693     }
 1694     else
 1695       ord[1] = ringorder_dp;
 1696     #else
 1697     // we change to an ordering:
 1698     // a(w1,...wn),wp(1,...0.....),C
 1699     ord=(int*)omAlloc0(4*sizeof(int));
 1700     block0=(int*)omAlloc0(4*sizeof(int));
 1701     block1=(int*)omAlloc0(4*sizeof(int));
 1702     wv=(int**) omAlloc0(4*sizeof(int**));
 1703     block0[0] = block0[1] = 1;
 1704     block1[0] = block1[1] = rVar(origR);
 1705     wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
 1706     wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
 1707     ord[0] = ringorder_a;
 1708     for (j=0;j<rVar(origR);j++)
 1709       wv[0][j]=pWeight(j+1,origR);
 1710     ord[1] = ringorder_wp;
 1711     for (j=0;j<rVar(origR);j++)
 1712       if (pGetExp(delVar,j+1)!=0) wv[1][j]=1;
 1713     #endif
 1714     ord[2] = ringorder_C;
 1715     ord[3] = (rRingOrder_t)0;
 1716   }
 1717   else
 1718   {
 1719     // we change to an ordering:
 1720     // aa(....),orig_ordering
 1721     ord=(rRingOrder_t*)omAlloc0(ordersize*sizeof(rRingOrder_t));
 1722     block0=(int*)omAlloc0(ordersize*sizeof(int));
 1723     block1=(int*)omAlloc0(ordersize*sizeof(int));
 1724     wv=(int**) omAlloc0(ordersize*sizeof(int**));
 1725     for (k=0;k<ordersize-1; k++)
 1726     {
 1727       block0[k+1] = origR->block0[k];
 1728       block1[k+1] = origR->block1[k];
 1729       ord[k+1] = origR->order[k];
 1730       if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
 1731     }
 1732     block0[0] = 1;
 1733     block1[0] = rVar(origR);
 1734     wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
 1735     for (j=0;j<rVar(origR);j++)
 1736       if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
 1737     // use this special ordering: like ringorder_a, except that pFDeg, pWeights
 1738     // ignore it
 1739     ord[0] = ringorder_aa;
 1740   }
 1741   // fill in tmp ring to get back the data later on
 1742   tmpR  = rCopy0(origR,FALSE,FALSE); // qring==NULL
 1743   //rUnComplete(tmpR);
 1744   tmpR->p_Procs=NULL;
 1745   tmpR->order = ord;
 1746   tmpR->block0 = block0;
 1747   tmpR->block1 = block1;
 1748   tmpR->wvhdl = wv;
 1749   rComplete(tmpR, 1);
 1750 
 1751 #ifdef HAVE_PLURAL
 1752   /* update nc structure on tmpR */
 1753   if (rIsPluralRing(origR))
 1754   {
 1755     if ( nc_rComplete(origR, tmpR, false) ) // no quotient ideal!
 1756     {
 1757       WerrorS("no elimination is possible: ordering condition is violated");
 1758       // cleanup
 1759       rDelete(tmpR);
 1760       if (w!=NULL)
 1761         delete w;
 1762       return NULL;
 1763     }
 1764   }
 1765 #endif
 1766   // change into the new ring
 1767   //pChangeRing((currRing->N),currRing->OrdSgn,ord,block0,block1,wv);
 1768   rChangeCurrRing(tmpR);
 1769 
 1770   //h = idInit(IDELEMS(h1),h1->rank);
 1771   // fetch data from the old ring
 1772   //for (k=0;k<IDELEMS(h1);k++) h->m[k] = prCopyR( h1->m[k], origR);
 1773   h=idrCopyR(h1,origR,currRing);
 1774   if (origR->qideal!=NULL)
 1775   {
 1776     WarnS("eliminate in q-ring: experimental");
 1777     ideal q=idrCopyR(origR->qideal,origR,currRing);
 1778     ideal s=idSimpleAdd(h,q);
 1779     idDelete(&h);
 1780     idDelete(&q);
 1781     h=s;
 1782   }
 1783   // compute GB
 1784   if ((alg!=GbDefault)
 1785   && (alg!=GbGroebner)
 1786   && (alg!=GbModstd)
 1787   && (alg!=GbSlimgb)
 1788   && (alg!=GbSba)
 1789   && (alg!=GbStd))
 1790   {
 1791     WarnS("wrong algorithm for GB");
 1792     alg=GbDefault;
 1793   }
 1794   BITSET save2;
 1795   SI_SAVE_OPT2(save2);
 1796   if (!TEST_OPT_RETURN_SB) si_opt_2|=V_IDELIM;
 1797   hh=idGroebner(h,0,alg,hilb);
 1798   SI_RESTORE_OPT2(save2);
 1799   // go back to the original ring
 1800   rChangeCurrRing(origR);
 1801   i = IDELEMS(hh)-1;
 1802   while ((i >= 0) && (hh->m[i] == NULL)) i--;
 1803   j = -1;
 1804   // fetch data from temp ring
 1805   for (k=0; k<=i; k++)
 1806   {
 1807     l=(currRing->N);
 1808     while ((l>0) && (p_GetExp( hh->m[k],l,tmpR)*pGetExp(delVar,l)==0)) l--;
 1809     if (l==0)
 1810     {
 1811       j++;
 1812       if (j >= IDELEMS(h3))
 1813       {
 1814         pEnlargeSet(&(h3->m),IDELEMS(h3),16);
 1815         IDELEMS(h3) += 16;
 1816       }
 1817       h3->m[j] = prMoveR( hh->m[k], tmpR,origR);
 1818       hh->m[k] = NULL;
 1819     }
 1820   }
 1821   id_Delete(&hh, tmpR);
 1822   idSkipZeroes(h3);
 1823   rDelete(tmpR);
 1824   if (w!=NULL)
 1825     delete w;
 1826   return h3;
 1827 }
 1828 
 1829 #ifdef WITH_OLD_MINOR
 1830 /*2
 1831 * compute the which-th ar-minor of the matrix a
 1832 */
 1833 poly idMinor(matrix a, int ar, unsigned long which, ideal R)
 1834 {
 1835   int     i,j/*,k,size*/;
 1836   unsigned long curr;
 1837   int *rowchoise,*colchoise;
 1838   BOOLEAN rowch,colch;
 1839   // ideal result;
 1840   matrix tmp;
 1841   poly p,q;
 1842 
 1843   rowchoise=(int *)omAlloc(ar*sizeof(int));
 1844   colchoise=(int *)omAlloc(ar*sizeof(int));
 1845   tmp=mpNew(ar,ar);
 1846   curr = 0; /* index of current minor */
 1847   idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
 1848   while (!rowch)
 1849   {
 1850     idInitChoise(ar,1,a->cols(),&colch,colchoise);
 1851     while (!colch)
 1852     {
 1853       if (curr == which)
 1854       {
 1855         for (i=1; i<=ar; i++)
 1856         {
 1857           for (j=1; j<=ar; j++)
 1858           {
 1859             MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
 1860           }
 1861         }
 1862         p = mp_DetBareiss(tmp,currRing);
 1863         if (p!=NULL)
 1864         {
 1865           if (R!=NULL)
 1866           {
 1867             q = p;
 1868             p = kNF(R,currRing->qideal,q);
 1869             p_Delete(&q,currRing);
 1870           }
 1871         }
 1872         /*delete the matrix tmp*/
 1873         for (i=1; i<=ar; i++)
 1874         {
 1875           for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
 1876         }
 1877         idDelete((ideal*)&tmp);
 1878         omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
 1879         omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
 1880         return (p);
 1881       }
 1882       curr++;
 1883       idGetNextChoise(ar,a->cols(),&colch,colchoise);
 1884     }
 1885     idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
 1886   }
 1887   return (poly) 1;
 1888 }
 1889 
 1890 /*2
 1891 * compute all ar-minors of the matrix a
 1892 */
 1893 ideal idMinors(matrix a, int ar, ideal R)
 1894 {
 1895   int     i,j,/*k,*/size;
 1896   int *rowchoise,*colchoise;
 1897   BOOLEAN rowch,colch;
 1898   ideal result;
 1899   matrix tmp;
 1900   poly p,q;
 1901 
 1902   i = binom(a->rows(),ar);
 1903   j = binom(a->cols(),ar);
 1904   size=i*j;
 1905 
 1906   rowchoise=(int *)omAlloc(ar*sizeof(int));
 1907   colchoise=(int *)omAlloc(ar*sizeof(int));
 1908   result=idInit(size,1);
 1909   tmp=mpNew(ar,ar);
 1910   // k = 0; /* the index in result*/
 1911   idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
 1912   while (!rowch)
 1913   {
 1914     idInitChoise(ar,1,a->cols(),&colch,colchoise);
 1915     while (!colch)
 1916     {
 1917       for (i=1; i<=ar; i++)
 1918       {
 1919         for (j=1; j<=ar; j++)
 1920         {
 1921           MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
 1922         }
 1923       }
 1924       p = mp_DetBareiss(tmp,currRing);
 1925       if (p!=NULL)
 1926       {
 1927         if (R!=NULL)
 1928         {
 1929           q = p;
 1930           p = kNF(R,currRing->qideal,q);
 1931           p_Delete(&q,currRing);
 1932         }
 1933       }
 1934       if (k>=size)
 1935       {
 1936         pEnlargeSet(&result->m,size,32);
 1937         size += 32;
 1938       }
 1939       result->m[k] = p;
 1940       k++;
 1941       idGetNextChoise(ar,a->cols(),&colch,colchoise);
 1942     }
 1943     idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
 1944   }
 1945   /*delete the matrix tmp*/
 1946   for (i=1; i<=ar; i++)
 1947   {
 1948     for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
 1949   }
 1950   idDelete((ideal*)&tmp);
 1951   if (k==0)
 1952   {
 1953     k=1;
 1954     result->m[0]=NULL;
 1955   }
 1956   omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
 1957   omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
 1958   pEnlargeSet(&result->m,size,k-size);
 1959   IDELEMS(result) = k;
 1960   return (result);
 1961 }
 1962 #else
 1963 
 1964 
 1965 /// compute all ar-minors of the matrix a
 1966 /// the caller of mpRecMin
 1967 /// the elements of the result are not in R (if R!=NULL)
 1968 ideal idMinors(matrix a, int ar, ideal R)
 1969 {
 1970 
 1971   const ring origR=currRing;
 1972   id_Test((ideal)a, origR);
 1973 
 1974   const int r = a->nrows;
 1975   const int c = a->ncols;
 1976 
 1977   if((ar<=0) || (ar>r) || (ar>c))
 1978   {
 1979     Werror("%d-th minor, matrix is %dx%d",ar,r,c);
 1980     return NULL;
 1981   }
 1982 
 1983   ideal h = id_Matrix2Module(mp_Copy(a,origR),origR);
 1984   long bound = sm_ExpBound(h,c,r,ar,origR);
 1985   id_Delete(&h, origR);
 1986 
 1987   ring tmpR = sm_RingChange(origR,bound);
 1988 
 1989   matrix b = mpNew(r,c);
 1990 
 1991   for (int i=r*c-1;i>=0;i--)
 1992     if (a->m[i] != NULL)
 1993       b->m[i] = prCopyR(a->m[i],origR,tmpR);
 1994 
 1995   id_Test( (ideal)b, tmpR);
 1996 
 1997   if (R!=NULL)
 1998   {
 1999     R = idrCopyR(R,origR,tmpR); // TODO: overwrites R? memory leak?
 2000     //if (ar>1) // otherwise done in mpMinorToResult
 2001     //{
 2002     //  matrix bb=(matrix)kNF(R,currRing->qideal,(ideal)b);
 2003     //  bb->rank=b->rank; bb->nrows=b->nrows; bb->ncols=b->ncols;
 2004     //  idDelete((ideal*)&b); b=bb;
 2005     //}
 2006     id_Test( R, tmpR);
 2007   }
 2008 
 2009   int size=binom(r,ar)*binom(c,ar);
 2010   ideal result = idInit(size,1);
 2011 
 2012   int elems = 0;
 2013 
 2014   if(ar>1)
 2015     mp_RecMin(ar-1,result,elems,b,r,c,NULL,R,tmpR);
 2016   else
 2017     mp_MinorToResult(result,elems,b,r,c,R,tmpR);
 2018 
 2019   id_Test( (ideal)b, tmpR);
 2020 
 2021   id_Delete((ideal *)&b, tmpR);
 2022 
 2023   if (R!=NULL) id_Delete(&R,tmpR);
 2024 
 2025   rChangeCurrRing(origR);
 2026   result = idrMoveR(result,tmpR,origR);
 2027   sm_KillModifiedRing(tmpR);
 2028   idTest(result);
 2029   return result;
 2030 }
 2031 #endif
 2032 
 2033 /*2
 2034 *returns TRUE if id1 is a submodule of id2
 2035 */
 2036 BOOLEAN idIsSubModule(ideal id1,ideal id2)
 2037 {
 2038   int i;
 2039   poly p;
 2040 
 2041   if (idIs0(id1)) return TRUE;
 2042   for (i=0;i<IDELEMS(id1);i++)
 2043   {
 2044     if (id1->m[i] != NULL)
 2045     {
 2046       p = kNF(id2,currRing->qideal,id1->m[i]);
 2047       if (p != NULL)
 2048       {
 2049         p_Delete(&p,currRing);
 2050         return FALSE;
 2051       }
 2052     }
 2053   }
 2054   return TRUE;
 2055 }
 2056 
 2057 BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
 2058 {
 2059   if ((Q!=NULL) && (!idHomIdeal(Q,NULL)))  { PrintS(" Q not hom\n"); return FALSE;}
 2060   if (idIs0(m)) return TRUE;
 2061 
 2062   int cmax=-1;
 2063   int i;
 2064   poly p=NULL;
 2065   int length=IDELEMS(m);
 2066   polyset P=m->m;
 2067   for (i=length-1;i>=0;i--)
 2068   {
 2069     p=P[i];
 2070     if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
 2071   }
 2072   if (w != NULL)
 2073   if (w->length()+1 < cmax)
 2074   {
 2075     // Print("length: %d - %d \n", w->length(),cmax);
 2076     return FALSE;
 2077   }
 2078 
 2079   if(w!=NULL)
 2080     p_SetModDeg(w, currRing);
 2081 
 2082   for (i=length-1;i>=0;i--)
 2083   {
 2084     p=P[i];
 2085     if (p!=NULL)
 2086     {
 2087       int d=currRing->pFDeg(p,currRing);
 2088       loop
 2089       {
 2090         pIter(p);
 2091         if (p==NULL) break;
 2092         if (d!=currRing->pFDeg(p,currRing))
 2093         {
 2094           //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
 2095           if(w!=NULL)
 2096             p_SetModDeg(NULL, currRing);
 2097           return FALSE;
 2098         }
 2099       }
 2100     }
 2101   }
 2102 
 2103   if(w!=NULL)
 2104     p_SetModDeg(NULL, currRing);
 2105 
 2106   return TRUE;
 2107 }
 2108 
 2109 ideal idSeries(int n,ideal M,matrix U,intvec *w)
 2110 {
 2111   for(int i=IDELEMS(M)-1;i>=0;i--)
 2112   {
 2113     if(U==NULL)
 2114       M->m[i]=pSeries(n,M->m[i],NULL,w);
 2115     else
 2116     {
 2117       M->m[i]=pSeries(n,M->m[i],MATELEM(U,i+1,i+1),w);
 2118       MATELEM(U,i+1,i+1)=NULL;
 2119     }
 2120   }
 2121   if(U!=NULL)
 2122     idDelete((ideal*)&U);
 2123   return M;
 2124 }
 2125 
 2126 matrix idDiff(matrix i, int k)
 2127 {
 2128   int e=MATCOLS(i)*MATROWS(i);
 2129   matrix r=mpNew(MATROWS(i),MATCOLS(i));
 2130   r->rank=i->rank;
 2131   int j;
 2132   for(j=0; j<e; j++)
 2133   {
 2134     r->m[j]=pDiff(i->m[j],k);
 2135   }
 2136   return r;
 2137 }
 2138 
 2139 matrix idDiffOp(ideal I, ideal J,BOOLEAN multiply)
 2140 {
 2141   matrix r=mpNew(IDELEMS(I),IDELEMS(J));
 2142   int i,j;
 2143   for(i=0; i<IDELEMS(I); i++)
 2144   {
 2145     for(j=0; j<IDELEMS(J); j++)
 2146     {
 2147       MATELEM(r,i+1,j+1)=pDiffOp(I->m[i],J->m[j],multiply);
 2148     }
 2149   }
 2150   return r;
 2151 }
 2152 
 2153 /*3
 2154 *handles for some ideal operations the ring/syzcomp managment
 2155 *returns all syzygies (componentwise-)shifted by -syzcomp
 2156 *or -syzcomp-1 (in case of ideals as input)
 2157 static ideal idHandleIdealOp(ideal arg,int syzcomp,int isIdeal=FALSE)
 2158 {
 2159   ring orig_ring=currRing;
 2160   ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE); rChangeCurrRing(syz_ring);
 2161   rSetSyzComp(length, syz_ring);
 2162 
 2163   ideal s_temp;
 2164   if (orig_ring!=syz_ring)
 2165     s_temp=idrMoveR_NoSort(arg,orig_ring, syz_ring);
 2166   else
 2167     s_temp=arg;
 2168 
 2169   ideal s_temp1 = kStd(s_temp,currRing->qideal,testHomog,&w,NULL,length);
 2170   if (w!=NULL) delete w;
 2171 
 2172   if (syz_ring!=orig_ring)
 2173   {
 2174     idDelete(&s_temp);
 2175     rChangeCurrRing(orig_ring);
 2176   }
 2177 
 2178   idDelete(&temp);
 2179   ideal temp1=idRingCopy(s_temp1,syz_ring);
 2180 
 2181   if (syz_ring!=orig_ring)
 2182   {
 2183     rChangeCurrRing(syz_ring);
 2184     idDelete(&s_temp1);
 2185     rChangeCurrRing(orig_ring);
 2186     rDelete(syz_ring);
 2187   }
 2188 
 2189   for (i=0;i<IDELEMS(temp1);i++)
 2190   {
 2191     if ((temp1->m[i]!=NULL)
 2192     && (pGetComp(temp1->m[i])<=length))
 2193     {
 2194       pDelete(&(temp1->m[i]));
 2195     }
 2196     else
 2197     {
 2198       p_Shift(&(temp1->m[i]),-length,currRing);
 2199     }
 2200   }
 2201   temp1->rank = rk;
 2202   idSkipZeroes(temp1);
 2203 
 2204   return temp1;
 2205 }
 2206 */
 2207 
 2208 #ifdef HAVE_SHIFTBBA
 2209 ideal idModuloLP (ideal h2,ideal h1, tHomog, intvec ** w, matrix *T, GbVariant alg)
 2210 {
 2211   intvec *wtmp=NULL;
 2212   if (T!=NULL) idDelete((ideal*)T);
 2213 
 2214   int i,k,rk,flength=0,slength,length;
 2215   poly p,q;
 2216 
 2217   if (idIs0(h2))
 2218     return idFreeModule(si_max(1,h2->ncols));
 2219   if (!idIs0(h1))
 2220     flength = id_RankFreeModule(h1,currRing);
 2221   slength = id_RankFreeModule(h2,currRing);
 2222   length  = si_max(flength,slength);
 2223   if (length==0)
 2224   {
 2225     length = 1;
 2226   }
 2227   ideal temp = idInit(IDELEMS(h2),length+IDELEMS(h2));
 2228   if ((w!=NULL)&&((*w)!=NULL))
 2229   {
 2230     //Print("input weights:");(*w)->show(1);PrintLn();
 2231     int d;
 2232     int k;
 2233     wtmp=new intvec(length+IDELEMS(h2));
 2234     for (i=0;i<length;i++)
 2235       ((*wtmp)[i])=(**w)[i];
 2236     for (i=0;i<IDELEMS(h2);i++)
 2237     {
 2238       poly p=h2->m[i];
 2239       if (p!=NULL)
 2240       {
 2241         d = p_Deg(p,currRing);
 2242         k= pGetComp(p);
 2243         if (slength>0) k--;
 2244         d +=((**w)[k]);
 2245         ((*wtmp)[i+length]) = d;
 2246       }
 2247     }
 2248     //Print("weights:");wtmp->show(1);PrintLn();
 2249   }
 2250   for (i=0;i<IDELEMS(h2);i++)
 2251   {
 2252     temp->m[i] = pCopy(h2->m[i]);
 2253     q = pOne();
 2254     // non multiplicative variable
 2255     pSetExp(q, currRing->isLPring - currRing->LPncGenCount + i + 1, 1);
 2256     p_Setm(q, currRing);
 2257     pSetComp(q,i+1+length);
 2258     pSetmComp(q);
 2259     if(temp->m[i]!=NULL)
 2260     {
 2261       if (slength==0) p_Shift(&(temp->m[i]),1,currRing);
 2262       p = temp->m[i];
 2263       temp->m[i] = pAdd(p, q);
 2264     }
 2265     else
 2266       temp->m[i]=q;
 2267   }
 2268   rk = k = IDELEMS(h2);
 2269   if (!idIs0(h1))
 2270   {
 2271     pEnlargeSet(&(temp->m),IDELEMS(temp),IDELEMS(h1));
 2272     IDELEMS(temp) += IDELEMS(h1);
 2273     for (i=0;i<IDELEMS(h1);i++)
 2274     {
 2275       if (h1->m[i]!=NULL)
 2276       {
 2277         temp->m[k] = pCopy(h1->m[i]);
 2278         if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
 2279         k++;
 2280       }
 2281     }
 2282   }
 2283 
 2284   ring orig_ring=currRing;
 2285   ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE);
 2286   rSetSyzComp(length,syz_ring);
 2287   rChangeCurrRing(syz_ring);
 2288   // we can use OPT_RETURN_SB only, if syz_ring==orig_ring,
 2289   // therefore we disable OPT_RETURN_SB for modulo:
 2290   // (see tr. #701)
 2291   //if (TEST_OPT_RETURN_SB)
 2292   //  rSetSyzComp(IDELEMS(h2)+length, syz_ring);
 2293   //else
 2294   //  rSetSyzComp(length, syz_ring);
 2295   ideal s_temp;
 2296 
 2297   if (syz_ring != orig_ring)
 2298   {
 2299     s_temp = idrMoveR_NoSort(temp, orig_ring, syz_ring);
 2300   }
 2301   else
 2302   {
 2303     s_temp = temp;
 2304   }
 2305 
 2306   idTest(s_temp);
 2307   unsigned save_opt,save_opt2;
 2308   SI_SAVE_OPT1(save_opt);
 2309   SI_SAVE_OPT2(save_opt2);
 2310   if (T==NULL) si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
 2311   si_opt_1 |= Sy_bit(OPT_REDTAIL);
 2312   ideal s_temp1 = idGroebner(s_temp,length,alg);
 2313   SI_RESTORE_OPT1(save_opt);
 2314   SI_RESTORE_OPT2(save_opt2);
 2315 
 2316   //if (wtmp!=NULL)  Print("output weights:");wtmp->show(1);PrintLn();
 2317   if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
 2318   {
 2319     delete *w;
 2320     *w=new intvec(IDELEMS(h2));
 2321     for (i=0;i<IDELEMS(h2);i++)
 2322       ((**w)[i])=(*wtmp)[i+length];
 2323   }
 2324   if (wtmp!=NULL) delete wtmp;
 2325 
 2326   if (T==NULL)
 2327   {
 2328     for (i=0;i<IDELEMS(s_temp1);i++)
 2329     {
 2330       if (s_temp1->m[i]!=NULL)
 2331       {
 2332         if (((int)pGetComp(s_temp1->m[i]))<=length)
 2333         {
 2334           p_Delete(&(s_temp1->m[i]),currRing);
 2335         }
 2336         else
 2337         {
 2338           p_Shift(&(s_temp1->m[i]),-length,currRing);
 2339         }
 2340       }
 2341     }
 2342   }
 2343   else
 2344   {
 2345     *T=mpNew(IDELEMS(s_temp1),IDELEMS(h2));
 2346     for (i=0;i<IDELEMS(s_temp1);i++)
 2347     {
 2348       if (s_temp1->m[i]!=NULL)
 2349       {
 2350         if (((int)pGetComp(s_temp1->m[i]))<=length)
 2351         {
 2352           do
 2353           {
 2354             p_LmDelete(&(s_temp1->m[i]),currRing);
 2355           } while((int)pGetComp(s_temp1->m[i])<=length);
 2356           poly q = prMoveR( s_temp1->m[i], syz_ring,orig_ring);
 2357           s_temp1->m[i] = NULL;
 2358           if (q!=NULL)
 2359           {
 2360             q=pReverse(q);
 2361             do
 2362             {
 2363               poly p = q;
 2364               long t=pGetComp(p);
 2365               pIter(q);
 2366               pNext(p) = NULL;
 2367               pSetComp(p,0);
 2368               pSetmComp(p);
 2369               pTest(p);
 2370               MATELEM(*T,(int)t-length,i) = pAdd(MATELEM(*T,(int)t-length,i),p);
 2371             } while (q != NULL);
 2372           }
 2373         }
 2374         else
 2375         {
 2376           p_Shift(&(s_temp1->m[i]),-length,currRing);
 2377         }
 2378       }
 2379     }
 2380   }
 2381   s_temp1->rank = rk;
 2382   idSkipZeroes(s_temp1);
 2383 
 2384   if (syz_ring!=orig_ring)
 2385   {
 2386     rChangeCurrRing(orig_ring);
 2387     s_temp1 = idrMoveR_NoSort(s_temp1, syz_ring, orig_ring);
 2388     rDelete(syz_ring);
 2389     // Hmm ... here seems to be a memory leak
 2390     // However, simply deleting it causes memory trouble
 2391     // idDelete(&s_temp);
 2392   }
 2393   idTest(s_temp1);
 2394   return s_temp1;
 2395 }
 2396 #endif
 2397 
 2398 /*2
 2399 * represents (h1+h2)/h2=h1/(h1 intersect h2)
 2400 */
 2401 //ideal idModulo (ideal h2,ideal h1)
 2402 ideal idModulo (ideal h2,ideal h1, tHomog hom, intvec ** w, matrix *T, GbVariant alg)
 2403 {
 2404 #ifdef HAVE_SHIFTBBA
 2405   if (rIsLPRing(currRing))
 2406     return idModuloLP(h2,h1,hom,w,T,alg);
 2407 #endif
 2408   intvec *wtmp=NULL;
 2409   if (T!=NULL) idDelete((ideal*)T);
 2410 
 2411   int i,flength=0,slength,length;
 2412 
 2413   if (idIs0(h2))
 2414     return idFreeModule(si_max(1,h2->ncols));
 2415   if (!idIs0(h1))
 2416     flength = id_RankFreeModule(h1,currRing);
 2417   slength = id_RankFreeModule(h2,currRing);
 2418   length  = si_max(flength,slength);
 2419   BOOLEAN inputIsIdeal=FALSE;
 2420   if (length==0)
 2421   {
 2422     length = 1;
 2423     inputIsIdeal=TRUE;
 2424   }
 2425   if ((w!=NULL)&&((*w)!=NULL))
 2426   {
 2427     //Print("input weights:");(*w)->show(1);PrintLn();
 2428     int d;
 2429     int k;
 2430     wtmp=new intvec(length+IDELEMS(h2));
 2431     for (i=0;i<length;i++)
 2432       ((*wtmp)[i])=(**w)[i];
 2433     for (i=0;i<IDELEMS(h2);i++)
 2434     {
 2435       poly p=h2->m[i];
 2436       if (p!=NULL)
 2437       {
 2438         d = p_Deg(p,currRing);
 2439         k= pGetComp(p);
 2440         if (slength>0) k--;
 2441         d +=((**w)[k]);
 2442         ((*wtmp)[i+length]) = d;
 2443       }
 2444     }
 2445     //Print("weights:");wtmp->show(1);PrintLn();
 2446   }
 2447   ideal s_temp1;
 2448   ring orig_ring=currRing;
 2449   ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE);
 2450   rSetSyzComp(length,syz_ring);
 2451   {
 2452     rChangeCurrRing(syz_ring);
 2453     ideal s1,s2;
 2454 
 2455     if (syz_ring != orig_ring)
 2456     {
 2457       s1 = idrCopyR_NoSort(h1, orig_ring, syz_ring);
 2458       s2 = idrCopyR_NoSort(h2, orig_ring, syz_ring);
 2459     }
 2460     else
 2461     {
 2462       s1=idCopy(h1);
 2463       s2=idCopy(h2);
 2464     }
 2465 
 2466     unsigned save_opt,save_opt2;
 2467     SI_SAVE_OPT1(save_opt);
 2468     SI_SAVE_OPT2(save_opt2);
 2469     if (T==NULL) si_opt_1 |= Sy_bit(OPT_REDTAIL);
 2470     si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
 2471     s_temp1 = idPrepare(s2,s1,testHomog,length,w,alg);
 2472     SI_RESTORE_OPT1(save_opt);
 2473     SI_RESTORE_OPT2(save_opt2);
 2474   }
 2475 
 2476   //if (wtmp!=NULL)  Print("output weights:");wtmp->show(1);PrintLn();
 2477   if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
 2478   {
 2479     delete *w;
 2480     *w=new intvec(IDELEMS(h2));
 2481     for (i=0;i<IDELEMS(h2);i++)
 2482       ((**w)[i])=(*wtmp)[i+length];
 2483   }
 2484   if (wtmp!=NULL) delete wtmp;
 2485 
 2486   ideal result=idInit(IDELEMS(s_temp1),IDELEMS(h2));
 2487   s_temp1=idExtractG_T_S(s_temp1,T,&result,length,IDELEMS(h2),inputIsIdeal,orig_ring,syz_ring);
 2488 
 2489   idDelete(&s_temp1);
 2490   if (syz_ring!=orig_ring)
 2491   {
 2492     rDelete(syz_ring);
 2493   }
 2494   idTest(h2);
 2495   idTest(h1);
 2496   idTest(result);
 2497   if (T!=NULL) idTest((ideal)*T);
 2498   return result;
 2499 }
 2500 
 2501 /*
 2502 *computes module-weights for liftings of homogeneous modules
 2503 */
 2504 #if 0
 2505 static intvec * idMWLift(ideal mod,intvec * weights)
 2506 {
 2507   if (idIs0(mod)) return new intvec(2);
 2508   int i=IDELEMS(mod);
 2509   while ((i>0) && (mod->m[i-1]==NULL)) i--;
 2510   intvec *result = new intvec(i+1);
 2511   while (i>0)
 2512   {
 2513     (*result)[i]=currRing->pFDeg(mod->m[i],currRing)+(*weights)[pGetComp(mod->m[i])];
 2514   }
 2515   return result;
 2516 }
 2517 #endif
 2518 
 2519 /*2
 2520 *sorts the kbase for idCoef* in a special way (lexicographically
 2521 *with x_max,...,x_1)
 2522 */
 2523 ideal idCreateSpecialKbase(ideal kBase,intvec ** convert)
 2524 {
 2525   int i;
 2526   ideal result;
 2527 
 2528   if (idIs0(kBase)) return NULL;
 2529   result = idInit(IDELEMS(kBase),kBase->rank);
 2530   *convert = idSort(kBase,FALSE);
 2531   for (i=0;i<(*convert)->length();i++)
 2532   {
 2533     result->m[i] = pCopy(kBase->m[(**convert)[i]-1]);
 2534   }
 2535   return result;
 2536 }
 2537 
 2538 /*2
 2539 *returns the index of a given monom in the list of the special kbase
 2540 */
 2541 int idIndexOfKBase(poly monom, ideal kbase)
 2542 {
 2543   int j=IDELEMS(kbase);
 2544 
 2545   while ((j>0) && (kbase->m[j-1]==NULL)) j--;
 2546   if (j==0) return -1;
 2547   int i=(currRing->N);
 2548   while (i>0)
 2549   {
 2550     loop
 2551     {
 2552       if (pGetExp(monom,i)>pGetExp(kbase->m[j-1],i)) return -1;
 2553       if (pGetExp(monom,i)==pGetExp(kbase->m[j-1],i)) break;
 2554       j--;
 2555       if (j==0) return -1;
 2556     }
 2557     if (i==1)
 2558     {
 2559       while(j>0)
 2560       {
 2561         if (pGetComp(monom)==pGetComp(kbase->m[j-1])) return j-1;
 2562         if (pGetComp(monom)>pGetComp(kbase->m[j-1])) return -1;
 2563         j--;
 2564       }
 2565     }
 2566     i--;
 2567   }
 2568   return -1;
 2569 }
 2570 
 2571 /*2
 2572 *decomposes the monom in a part of coefficients described by the
 2573 *complement of how and a monom in variables occuring in how, the
 2574 *index of which in kbase is returned as integer pos (-1 if it don't
 2575 *exists)
 2576 */
 2577 poly idDecompose(poly monom, poly how, ideal kbase, int * pos)
 2578 {
 2579   int i;
 2580   poly coeff=pOne(), base=pOne();
 2581 
 2582   for (i=1;i<=(currRing->N);i++)
 2583   {
 2584     if (pGetExp(how,i)>0)
 2585     {
 2586       pSetExp(base,i,pGetExp(monom,i));
 2587     }
 2588     else
 2589     {
 2590       pSetExp(coeff,i,pGetExp(monom,i));
 2591     }
 2592   }
 2593   pSetComp(base,pGetComp(monom));
 2594   pSetm(base);
 2595   pSetCoeff(coeff,nCopy(pGetCoeff(monom)));
 2596   pSetm(coeff);
 2597   *pos = idIndexOfKBase(base,kbase);
 2598   if (*pos<0)
 2599     p_Delete(&coeff,currRing);
 2600   p_Delete(&base,currRing);
 2601   return coeff;
 2602 }
 2603 
 2604 /*2
 2605 *returns a matrix A of coefficients with kbase*A=arg
 2606 *if all monomials in variables of how occur in kbase
 2607 *the other are deleted
 2608 */
 2609 matrix idCoeffOfKBase(ideal arg, ideal kbase, poly how)
 2610 {
 2611   matrix result;
 2612   ideal tempKbase;
 2613   poly p,q;
 2614   intvec * convert;
 2615   int i=IDELEMS(kbase),j=IDELEMS(arg),k,pos;
 2616 #if 0
 2617   while ((i>0) && (kbase->m[i-1]==NULL)) i--;
 2618   if (idIs0(arg))
 2619     return mpNew(i,1);
 2620   while ((j>0) && (arg->m[j-1]==NULL)) j--;
 2621   result = mpNew(i,j);
 2622 #else
 2623   result = mpNew(i, j);
 2624   while ((j>0) && (arg->m[j-1]==NULL)) j--;
 2625 #endif
 2626 
 2627   tempKbase = idCreateSpecialKbase(kbase,&convert);
 2628   for (k=0;k<j;k++)
 2629   {
 2630     p = arg->m[k];
 2631     while (p!=NULL)
 2632     {
 2633       q = idDecompose(p,how,tempKbase,&pos);
 2634       if (pos>=0)
 2635       {
 2636         MATELEM(result,(*convert)[pos],k+1) =
 2637             pAdd(MATELEM(result,(*convert)[pos],k+1),q);
 2638       }
 2639       else
 2640         p_Delete(&q,currRing);
 2641       pIter(p);
 2642     }
 2643   }
 2644   idDelete(&tempKbase);
 2645   return result;
 2646 }
 2647 
 2648 static void idDeleteComps(ideal arg,int* red_comp,int del)
 2649 // red_comp is an array [0..args->rank]
 2650 {
 2651   int i,j;
 2652   poly p;
 2653 
 2654   for (i=IDELEMS(arg)-1;i>=0;i--)
 2655   {
 2656     p = arg->m[i];
 2657     while (p!=NULL)
 2658     {
 2659       j = pGetComp(p);
 2660       if (red_comp[j]!=j)
 2661       {
 2662         pSetComp(p,red_comp[j]);
 2663         pSetmComp(p);
 2664       }
 2665       pIter(p);
 2666     }
 2667   }
 2668   (arg->rank) -= del;
 2669 }
 2670 
 2671 /*2
 2672 * returns the presentation of an isomorphic, minimally
 2673 * embedded  module (arg represents the quotient!)
 2674 */
 2675 ideal idMinEmbedding(ideal arg,BOOLEAN inPlace, intvec **w)
 2676 {
 2677   if (idIs0(arg)) return idInit(1,arg->rank);
 2678   int i,next_gen,next_comp;
 2679   ideal res=arg;
 2680   if (!inPlace) res = idCopy(arg);
 2681   res->rank=si_max(res->rank,id_RankFreeModule(res,currRing));
 2682   int *red_comp=(int*)omAlloc((res->rank+1)*sizeof(int));
 2683   for (i=res->rank;i>=0;i--) red_comp[i]=i;
 2684 
 2685   int del=0;
 2686   loop
 2687   {
 2688     next_gen = id_ReadOutPivot(res, &next_comp, currRing);
 2689     if (next_gen<0) break;
 2690     del++;
 2691     syGaussForOne(res,next_gen,next_comp,0,IDELEMS(res));
 2692     for(i=next_comp+1;i<=arg->rank;i++) red_comp[i]--;
 2693     if ((w !=NULL)&&(*w!=NULL))
 2694     {
 2695       for(i=next_comp;i<(*w)->length();i++) (**w)[i-1]=(**w)[i];
 2696     }
 2697   }
 2698 
 2699   idDeleteComps(res,red_comp,del);
 2700   idSkipZeroes(res);
 2701   omFree(red_comp);
 2702 
 2703   if ((w !=NULL)&&(*w!=NULL) &&(del>0))
 2704   {
 2705     int nl=si_max((*w)->length()-del,1);
 2706     intvec *wtmp=new intvec(nl);
 2707     for(i=0;i<res->rank;i++) (*wtmp)[i]=(**w)[i];
 2708     delete *w;
 2709     *w=wtmp;
 2710   }
 2711   return res;
 2712 }
 2713 
 2714 #include "polys/clapsing.h"
 2715 
 2716 #if 0
 2717 poly id_GCD(poly f, poly g, const ring r)
 2718 {
 2719   ring save_r=currRing;
 2720   rChangeCurrRing(r);
 2721   ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
 2722   intvec *w = NULL;
 2723   ideal S=idSyzygies(I,testHomog,&w);
 2724   if (w!=NULL) delete w;
 2725   poly gg=pTakeOutComp(&(S->m[0]),2);
 2726   idDelete(&S);
 2727   poly gcd_p=singclap_pdivide(f,gg,r);
 2728   p_Delete(&gg,r);
 2729   rChangeCurrRing(save_r);
 2730   return gcd_p;
 2731 }
 2732 #else
 2733 poly id_GCD(poly f, poly g, const ring r)
 2734 {
 2735   ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
 2736   intvec *w = NULL;
 2737 
 2738   ring save_r = currRing;
 2739   rChangeCurrRing(r);
 2740   ideal S=idSyzygies(I,testHomog,&w);
 2741   rChangeCurrRing(save_r);
 2742 
 2743   if (w!=NULL) delete w;
 2744   poly gg=p_TakeOutComp(&(S->m[0]), 2, r);
 2745   id_Delete(&S, r);
 2746   poly gcd_p=singclap_pdivide(f,gg, r);
 2747   p_Delete(&gg, r);
 2748 
 2749   return gcd_p;
 2750 }
 2751 #endif
 2752 
 2753 #if 0
 2754 /*2
 2755 * xx,q: arrays of length 0..rl-1
 2756 * xx[i]: SB mod q[i]
 2757 * assume: char=0
 2758 * assume: q[i]!=0
 2759 * destroys xx
 2760 */
 2761 ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring R)
 2762 {
 2763   int cnt=IDELEMS(xx[0])*xx[0]->nrows;
 2764   ideal result=idInit(cnt,xx[0]->rank);
 2765   result->nrows=xx[0]->nrows; // for lifting matrices
 2766   result->ncols=xx[0]->ncols; // for lifting matrices
 2767   int i,j;
 2768   poly r,h,hh,res_p;
 2769   number *x=(number *)omAlloc(rl*sizeof(number));
 2770   for(i=cnt-1;i>=0;i--)
 2771   {
 2772     res_p=NULL;
 2773     loop
 2774     {
 2775       r=NULL;
 2776       for(j=rl-1;j>=0;j--)
 2777       {
 2778         h=xx[j]->m[i];
 2779         if ((h!=NULL)
 2780         &&((r==NULL)||(p_LmCmp(r,h,R)==-1)))
 2781           r=h;
 2782       }
 2783       if (r==NULL) break;
 2784       h=p_Head(r, R);
 2785       for(j=rl-1;j>=0;j--)
 2786       {
 2787         hh=xx[j]->m[i];
 2788         if ((hh!=NULL) && (p_LmCmp(r,hh, R)==0))
 2789         {
 2790           x[j]=p_GetCoeff(hh, R);
 2791           hh=p_LmFreeAndNext(hh, R);
 2792           xx[j]->m[i]=hh;
 2793         }
 2794         else
 2795           x[j]=n_Init(0, R->cf); // is R->cf really n_Q???, yes!
 2796       }
 2797 
 2798       number n=n_ChineseRemainder(x,q,rl, R->cf);
 2799 
 2800       for(j=rl-1;j>=0;j--)
 2801       {
 2802         x[j]=NULL; // nlInit(0...) takes no memory
 2803       }
 2804       if (n_IsZero(n, R->cf)) p_Delete(&h, R);
 2805       else
 2806       {
 2807         p_SetCoeff(h,n, R);
 2808         //Print("new mon:");pWrite(h);
 2809         res_p=p_Add_q(res_p, h, R);
 2810       }
 2811     }
 2812     result->m[i]=res_p;
 2813   }
 2814   omFree(x);
 2815   for(i=rl-1;i>=0;i--) id_Delete(&(xx[i]), R);
 2816   omFree(xx);
 2817   return result;
 2818 }
 2819 #endif
 2820 /* currently unused:
 2821 ideal idChineseRemainder(ideal *xx, intvec *iv)
 2822 {
 2823   int rl=iv->length();
 2824   number *q=(number *)omAlloc(rl*sizeof(number));
 2825   int i;
 2826   for(i=0; i<rl; i++)
 2827   {
 2828     q[i]=nInit((*iv)[i]);
 2829   }
 2830   return idChineseRemainder(xx,q,rl);
 2831 }
 2832 */
 2833 /*
 2834  * lift ideal with coeffs over Z (mod N) to Q via Farey
 2835  */
 2836 ideal id_Farey(ideal x, number N, const ring r)
 2837 {
 2838   int cnt=IDELEMS(x)*x->nrows;
 2839   ideal result=idInit(cnt,x->rank);
 2840   result->nrows=x->nrows; // for lifting matrices
 2841   result->ncols=x->ncols; // for lifting matrices
 2842 
 2843   int i;
 2844   for(i=cnt-1;i>=0;i--)
 2845   {
 2846     result->m[i]=p_Farey(x->m[i],N,r);
 2847   }
 2848   return result;
 2849 }
 2850 
 2851 
 2852 
 2853 
 2854 // uses glabl vars via pSetModDeg
 2855 /*
 2856 BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
 2857 {
 2858   if ((Q!=NULL) && (!idHomIdeal(Q,NULL)))  { PrintS(" Q not hom\n"); return FALSE;}
 2859   if (idIs0(m)) return TRUE;
 2860 
 2861   int cmax=-1;
 2862   int i;
 2863   poly p=NULL;
 2864   int length=IDELEMS(m);
 2865   poly* P=m->m;
 2866   for (i=length-1;i>=0;i--)
 2867   {
 2868     p=P[i];
 2869     if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
 2870   }
 2871   if (w != NULL)
 2872   if (w->length()+1 < cmax)
 2873   {
 2874     // Print("length: %d - %d \n", w->length(),cmax);
 2875     return FALSE;
 2876   }
 2877 
 2878   if(w!=NULL)
 2879     p_SetModDeg(w, currRing);
 2880 
 2881   for (i=length-1;i>=0;i--)
 2882   {
 2883     p=P[i];
 2884     poly q=p;
 2885     if (p!=NULL)
 2886     {
 2887       int d=p_FDeg(p,currRing);
 2888       loop
 2889       {
 2890         pIter(p);
 2891         if (p==NULL) break;
 2892         if (d!=p_FDeg(p,currRing))
 2893         {
 2894           //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
 2895           if(w!=NULL)
 2896             p_SetModDeg(NULL, currRing);
 2897           return FALSE;
 2898         }
 2899       }
 2900     }
 2901   }
 2902 
 2903   if(w!=NULL)
 2904     p_SetModDeg(NULL, currRing);
 2905 
 2906   return TRUE;
 2907 }
 2908 */
 2909 
 2910 /// keeps the first k (>= 1) entries of the given ideal
 2911 /// (Note that the kept polynomials may be zero.)
 2912 void idKeepFirstK(ideal id, const int k)
 2913 {
 2914    for (int i = IDELEMS(id)-1; i >= k; i--)
 2915    {
 2916       if (id->m[i] != NULL) pDelete(&id->m[i]);
 2917    }
 2918    int kk=k;
 2919    if (k==0) kk=1; /* ideals must have at least one element(0)*/
 2920    pEnlargeSet(&(id->m), IDELEMS(id), kk-IDELEMS(id));
 2921    IDELEMS(id) = kk;
 2922 }
 2923 
 2924 typedef struct
 2925 {
 2926   poly p;
 2927   int index;
 2928 } poly_sort;
 2929 
 2930 int pCompare_qsort(const void *a, const void *b)
 2931 {
 2932   return (p_Compare(((poly_sort *)a)->p, ((poly_sort *)b)->p,currRing));
 2933 }
 2934 
 2935 void idSort_qsort(poly_sort *id_sort, int idsize)
 2936 {
 2937   qsort(id_sort, idsize, sizeof(poly_sort), pCompare_qsort);
 2938 }
 2939 
 2940 /*2
 2941 * ideal id = (id[i])
 2942 * if id[i] = id[j] then id[j] is deleted for j > i
 2943 */
 2944 void idDelEquals(ideal id)
 2945 {
 2946   int idsize = IDELEMS(id);
 2947   poly_sort *id_sort = (poly_sort *)omAlloc0(idsize*sizeof(poly_sort));
 2948   for (int i = 0; i < idsize; i++)
 2949   {
 2950     id_sort[i].p = id->m[i];
 2951     id_sort[i].index = i;
 2952   }
 2953   idSort_qsort(id_sort, idsize);
 2954   int index, index_i, index_j;
 2955   int i = 0;
 2956   for (int j = 1; j < idsize; j++)
 2957   {
 2958     if (id_sort[i].p != NULL && pEqualPolys(id_sort[i].p, id_sort[j].p))
 2959     {
 2960       index_i = id_sort[i].index;
 2961       index_j = id_sort[j].index;
 2962       if (index_j > index_i)
 2963       {
 2964         index = index_j;
 2965       }
 2966       else
 2967       {
 2968         index = index_i;
 2969         i = j;
 2970       }
 2971       pDelete(&id->m[index]);
 2972     }
 2973     else
 2974     {
 2975       i = j;
 2976     }
 2977   }
 2978   omFreeSize((ADDRESS)(id_sort), idsize*sizeof(poly_sort));
 2979 }
 2980 
 2981 STATIC_VAR int * id_satstdSaturatingVariables=NULL;
 2982 
 2983 static BOOLEAN id_sat_vars_sp(kStrategy strat)
 2984 {
 2985   BOOLEAN b = FALSE; // set b to TRUE, if spoly was changed,
 2986                      // let it remain FALSE otherwise
 2987   if (strat->P.t_p==NULL)
 2988   {
 2989     poly p=strat->P.p;
 2990 
 2991     // iterate over all terms of p and
 2992     // compute the minimum mm of all exponent vectors
 2993     int *mm=(int*)omAlloc((1+rVar(currRing))*sizeof(int));
 2994     int *m0=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
 2995     p_GetExpV(p,mm,currRing);
 2996     bool nonTrivialSaturationToBeDone=true;
 2997     for (p=pNext(p); p!=NULL; pIter(p))
 2998     {
 2999       nonTrivialSaturationToBeDone=false;
 3000       p_GetExpV(p,m0,currRing);
 3001       for (int i=rVar(currRing); i>0; i--)
 3002       {
 3003         if (id_satstdSaturatingVariables[i]!=0)
 3004         {
 3005           mm[i]=si_min(mm[i],m0[i]);
 3006           if (mm[i]>0) nonTrivialSaturationToBeDone=true;
 3007         }
 3008         else mm[i]=0;
 3009       }
 3010       // abort if the minimum is zero in each component
 3011       if (!nonTrivialSaturationToBeDone) break;
 3012     }
 3013     if (nonTrivialSaturationToBeDone)
 3014     {
 3015       // std::cout << "simplifying!" << std::endl;
 3016       if (TEST_OPT_PROT) { PrintS("S"); mflush(); }
 3017       p=p_Copy(strat->P.p,currRing);
 3018       //pWrite(p);
 3019       //  for (int i=rVar(currRing); i>0; i--)
 3020       //    if (mm[i]!=0) Print("x_%d:%d ",i,mm[i]);
 3021       //PrintLn();
 3022       strat->P.Init(currRing);
 3023       //memset(&strat->P,0,sizeof(strat->P));
 3024       strat->P.tailRing = strat->tailRing;
 3025       strat->P.p=p;
 3026       while(p!=NULL)
 3027       {
 3028         for (int i=rVar(currRing); i>0; i--)
 3029         {
 3030           p_SubExp(p,i,mm[i],currRing);
 3031         }
 3032         p_Setm(p,currRing);
 3033         pIter(p);
 3034       }
 3035       b = TRUE;
 3036     }
 3037     omFree(mm);
 3038     omFree(m0);
 3039   }
 3040   else
 3041   {
 3042     poly p=strat->P.t_p;
 3043 
 3044     // iterate over all terms of p and
 3045     // compute the minimum mm of all exponent vectors
 3046     int *mm=(int*)omAlloc((1+rVar(currRing))*sizeof(int));
 3047     int *m0=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
 3048     p_GetExpV(p,mm,strat->tailRing);
 3049     bool nonTrivialSaturationToBeDone=true;
 3050     for (p = pNext(p); p!=NULL; pIter(p))
 3051     {
 3052       nonTrivialSaturationToBeDone=false;
 3053       p_GetExpV(p,m0,strat->tailRing);
 3054       for(int i=rVar(currRing); i>0; i--)
 3055       {
 3056         if(id_satstdSaturatingVariables[i]!=0)
 3057         {
 3058           mm[i]=si_min(mm[i],m0[i]);
 3059           if (mm[i]>0) nonTrivialSaturationToBeDone = true;
 3060         }
 3061         else mm[i]=0;
 3062       }
 3063       // abort if the minimum is zero in each component
 3064       if (!nonTrivialSaturationToBeDone) break;
 3065     }
 3066     if (nonTrivialSaturationToBeDone)
 3067     {
 3068       if (TEST_OPT_PROT) { PrintS("S"); mflush(); }
 3069       p=p_Copy(strat->P.t_p,strat->tailRing);
 3070       //p_Write(p,strat->tailRing);
 3071       //  for (int i=rVar(currRing); i>0; i--)
 3072       //    if (mm[i]!=0) Print("x_%d:%d ",i,mm[i]);
 3073       //PrintLn();
 3074       strat->P.Init(currRing);
 3075       //memset(&strat->P,0,sizeof(strat->P));
 3076       strat->P.tailRing = strat->tailRing;
 3077       strat->P.t_p=p;
 3078       while(p!=NULL)
 3079       {
 3080         for(int i=rVar(currRing); i>0; i--)
 3081         {
 3082           p_SubExp(p,i,mm[i],strat->tailRing);
 3083         }
 3084         p_Setm(p,strat->tailRing);
 3085         pIter(p);
 3086       }
 3087       strat->P.GetP();
 3088       b = TRUE;
 3089     }
 3090     omFree(mm);
 3091     omFree(m0);
 3092   }
 3093   return b; // return TRUE if sp was changed, FALSE if not
 3094 }
 3095 
 3096 ideal id_Satstd(const ideal I, ideal J, const ring r)
 3097 {
 3098   ring save=currRing;
 3099   if (currRing!=r) rChangeCurrRing(r);
 3100   idSkipZeroes(J);
 3101   id_satstdSaturatingVariables=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
 3102   int k=IDELEMS(J);
 3103   if (k>1)
 3104   {
 3105     for (int i=0; i<k; i++)
 3106     {
 3107       poly x = J->m[i];
 3108       int li = p_Var(x,r);
 3109       if (li>0)
 3110         id_satstdSaturatingVariables[li]=1;
 3111       else
 3112       {
 3113         if (currRing!=save) rChangeCurrRing(save);
 3114         WerrorS("ideal generators must be variables");
 3115         return NULL;
 3116       }
 3117     }
 3118   }
 3119   else
 3120   {
 3121     poly x = J->m[0];
 3122     for (int i=1; i<=r->N; i++)
 3123     {
 3124       int li = p_GetExp(x,i,r);
 3125       if (li==1)
 3126         id_satstdSaturatingVariables[i]=1;
 3127       else if (li>1)
 3128       {
 3129         if (currRing!=save) rChangeCurrRing(save);
 3130         Werror("exponent(x(%d)^%d) must be 0 or 1",i,li);
 3131         return NULL;
 3132       }
 3133     }
 3134   }
 3135   ideal res=kStd(I,r->qideal,testHomog,NULL,NULL,0,0,NULL,id_sat_vars_sp);
 3136   omFreeSize(id_satstdSaturatingVariables,(1+rVar(currRing))*sizeof(int));
 3137   id_satstdSaturatingVariables=NULL;
 3138   if (currRing!=save) rChangeCurrRing(save);
 3139   return res;
 3140 }
 3141 
 3142 GbVariant syGetAlgorithm(char *n, const ring r, const ideal /*M*/)
 3143 {
 3144   GbVariant alg=GbDefault;
 3145   if (strcmp(n,"default")==0) alg=GbDefault;
 3146   else if (strcmp(n,"slimgb")==0) alg=GbSlimgb;
 3147   else if (strcmp(n,"std")==0) alg=GbStd;
 3148   else if (strcmp(n,"sba")==0) alg=GbSba;
 3149   else if (strcmp(n,"singmatic")==0) alg=GbSingmatic;
 3150   else if (strcmp(n,"groebner")==0) alg=GbGroebner;
 3151   else if (strcmp(n,"modstd")==0) alg=GbModstd;
 3152   else if (strcmp(n,"ffmod")==0) alg=GbFfmod;
 3153   else if (strcmp(n,"nfmod")==0) alg=GbNfmod;
 3154   else if (strcmp(n,"std:sat")==0) alg=GbStdSat;
 3155   else Warn(">>%s<< is an unknown algorithm",n);
 3156 
 3157   if (alg==GbSlimgb) // test conditions for slimgb
 3158   {
 3159     if(rHasGlobalOrdering(r)
 3160     &&(!rIsNCRing(r))
 3161     &&(r->qideal==NULL)
 3162     &&(!rField_is_Ring(r)))
 3163     {
 3164        return GbSlimgb;
 3165     }
 3166     if (TEST_OPT_PROT)
 3167       WarnS("requires: coef:field, commutative, global ordering, not qring");
 3168   }
 3169   else if (alg==GbSba) // cond. for sba
 3170   {
 3171     if(rField_is_Domain(r)
 3172     &&(!rIsNCRing(r))
 3173     &&(rHasGlobalOrdering(r)))
 3174     {
 3175       return GbSba;
 3176     }
 3177     if (TEST_OPT_PROT)
 3178       WarnS("requires: coef:domain, commutative, global ordering");
 3179   }
 3180   else if (alg==GbGroebner) // cond. for groebner
 3181   {
 3182     return GbGroebner;
 3183   }
 3184   else if(alg==GbModstd)  // cond for modstd: Q or Q(a)
 3185   {
 3186     if(ggetid("modStd")==NULL)
 3187     {
 3188       WarnS(">>modStd<< not found");
 3189     }
 3190     else if(rField_is_Q(r)
 3191     &&(!rIsNCRing(r))
 3192     &&(rHasGlobalOrdering(r)))
 3193     {
 3194       return GbModstd;
 3195     }
 3196     if (TEST_OPT_PROT)
 3197       WarnS("requires: coef:QQ, commutative, global ordering");
 3198   }
 3199   else if(alg==GbStdSat)  // cond for std:sat: 2 blocks of variables
 3200   {
 3201     if(ggetid("satstd")==NULL)
 3202     {
 3203       WarnS(">>satstd<< not found");
 3204     }
 3205     else
 3206     {
 3207       return GbStdSat;
 3208     }
 3209   }
 3210 
 3211   return GbStd; // no conditions for std
 3212 }
 3213 //----------------------------------------------------------------------------
 3214 // GB-algorithms and their pre-conditions
 3215 // std   slimgb  sba singmatic modstd ffmod nfmod groebner
 3216 // +     +       +   -         +      -     -     + coeffs: QQ
 3217 // +     +       +   +         -      -     -     + coeffs: ZZ/p
 3218 // +     +       +   -         ?      -     +     + coeffs: K[a]/f
 3219 // +     +       +   -         ?      +     -     + coeffs: K(a)
 3220 // +     -       +   -         -      -     -     + coeffs: domain, not field
 3221 // +     -       -   -         -      -     -     + coeffs: zero-divisors
 3222 // +     +       +   +         -      ?     ?     + also for modules: C
 3223 // +     +       -   +         -      ?     ?     + also for modules: all orderings
 3224 // +     +       -   -         -      -     -     + exterior algebra
 3225 // +     +       -   -         -      -     -     + G-algebra
 3226 // +     +       +   +         +      +     +     + degree ordering
 3227 // +     -       +   +         +      +     +     + non-degree ordering
 3228 // -     -       -   +         +      +     +     + parallel