Changeset 37a4c3 in git for kernel/kutil.cc


Ignore:
Timestamp:
Feb 15, 2008, 6:14:23 PM (16 years ago)
Author:
Viktor Levandovskyy <levandov@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
7d0cbb00ebc403b3845a38cbf3185e95e99cc015
Parents:
8cf4f3f04ec8ee4482f27f11b0444a3edf84fd3c
Message:
*levandov: major changes in shift free gb


git-svn-id: file:///usr/local/Singular/svn/trunk@10580 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/kutil.cc

    r8cf4f3f r37a4c3  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: kutil.cc,v 1.83 2008-02-08 10:11:29 wienand Exp $ */
     4/* $Id: kutil.cc,v 1.84 2008-02-15 17:14:22 levandov Exp $ */
    55/*
    66* ABSTRACT: kernel: utils for kStd
    … …  
    13501350* put the pair (s[i],p)  into the set B, ecart=ecart(p)
    13511351*/
     1352
    13521353
    13531354void enterOnePair (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR = -1)
    … …  
    60116012/* including the self pairs? */
    60126013
     6014void updateSShift(kStrategy strat,int uptodeg,int lV)
     6015{
     6016  /* to use after updateS(toT=FALSE,strat) */
     6017  /* fills T with shifted elt's of S */
     6018  int i;
     6019  LObject h;
     6020  int atT = -1; // or figure out smth better
     6021  strat->tl = -1; // init
     6022  for (i=0; i<=strat->sl; i++)
     6023  {
     6024    h.p =  strat->S[i];
     6025    strat->initEcart(&h);
     6026    h.sev = strat->sevS[i];
     6027    /*puts the elements of S with their shifts to T*/
     6028    //    int atT, int uptodeg, int lV)
     6029    enterTShift(h,strat,atT,uptodeg,lV);
     6030  }
     6031  /* what about setting strat->tl? */
     6032}
     6033
     6034void initBuchMoraShift (ideal F,ideal Q,kStrategy strat)
     6035{
     6036  strat->interpt = BTEST1(OPT_INTERRUPT);
     6037  strat->kHEdge=NULL;
     6038  if (pOrdSgn==1) strat->kHEdgeFound=FALSE;
     6039  /*- creating temp data structures------------------- -*/
     6040  strat->cp = 0;
     6041  strat->c3 = 0;
     6042  strat->tail = pInit();
     6043  /*- set s -*/
     6044  strat->sl = -1;
     6045  /*- set L -*/
     6046  strat->Lmax = setmaxL;
     6047  strat->Ll = -1;
     6048  strat->L = initL();
     6049  /*- set B -*/
     6050  strat->Bmax = setmaxL;
     6051  strat->Bl = -1;
     6052  strat->B = initL();
     6053  /*- set T -*/
     6054  strat->tl = -1;
     6055  strat->tmax = setmaxT;
     6056  strat->T = initT();
     6057  strat->R = initR();
     6058  strat->sevT = initsevT();
     6059  /*- init local data struct.---------------------------------------- -*/
     6060  strat->P.ecart=0;
     6061  strat->P.length=0;
     6062  if (pOrdSgn==-1)
     6063  {
     6064    if (strat->kHEdge!=NULL) pSetComp(strat->kHEdge, strat->ak);
     6065    if (strat->kNoether!=NULL) pSetComp(strat->kNoetherTail(), strat->ak);
     6066  }
     6067  if(TEST_OPT_SB_1)
     6068  {
     6069    int i;
     6070    ideal P=idInit(IDELEMS(F)-strat->newIdeal,F->rank);
     6071    for (i=strat->newIdeal;i<IDELEMS(F);i++)
     6072    {
     6073      P->m[i-strat->newIdeal] = F->m[i];
     6074      F->m[i] = NULL;
     6075    }
     6076    initSSpecial(F,Q,P,strat);
     6077    for (i=strat->newIdeal;i<IDELEMS(F);i++)
     6078    {
     6079      F->m[i] = P->m[i-strat->newIdeal];
     6080      P->m[i-strat->newIdeal] = NULL;
     6081    }
     6082    idDelete(&P);
     6083  }
     6084  else
     6085  {
     6086    /*Shdl=*/initSL(F, Q,strat); /*sets also S, ecartS, fromQ */
     6087    // /*Shdl=*/initS(F, Q,strat); /*sets also S, ecartS, fromQ */
     6088  }
     6089  strat->kIdeal = NULL;
     6090  strat->fromT = FALSE;
     6091  strat->noTailReduction = !TEST_OPT_REDTAIL;
     6092  if (!TEST_OPT_SB_1)
     6093  {
     6094    /* the only change: do not fill the set T*/
     6095    updateS(FALSE,strat);
     6096  }
     6097  if (strat->fromQ!=NULL) omFreeSize(strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
     6098  strat->fromQ=NULL;
     6099  /* more changes: fill the set T with all the shifts of elts of S*/
     6100  /* is done by other procedure */
     6101}
     6102
     6103// void initBuchMoraShift(ideal F,ideal Q,kStrategy strat)
     6104// {
     6105//   initBuchMora(F,Q,strat);
     6106//   strat->fromT = TRUE;
     6107// }
     6108
    60136109/*1
    6014 * put the pairs (s[i],sh \dot p)  into the set B, ecart=ecart(p)
     6110* put the pairs (sh \dot s[i],p)  into the set B, ecart=ecart(p)
    60156111*/
    60166112void enterOnePairManyShifts (int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int uptodeg, int lV)
    60176113{
     6114
     6115  /* should cycle through all shifts of s[i] until uptodeg - lastVblock(s[i]) */
     6116  /* that is create the pairs (f, s \dot g)  */
     6117
     6118  poly q;
     6119  q = pCopy(strat->S[i]); // zero shift
     6120
     6121 /* determine how many elements we have to insert for a given s[i] */
     6122  /* x(0)y(1)z(2) : lastVblock-1=2, to add until lastVblock=uptodeg-1 */
     6123  /* hence, a total number of elt's to add is: */
     6124  /*  int toInsert = 1 + (uptodeg-1) - (pLastVblock(p.p, lV) -1);  */
     6125  int toInsert = uptodeg  - pLastVblock(q, lV) +1;
     6126
     6127  assume(i<=strat->sl); // from OnePair
     6128  if (strat->interred_flag) return; // ?
     6129
     6130  /* these vars hold for all shifts of s[i] */
     6131  int ecartq = 0; //Hans says it's ok; we're in the homog case, no ecart
     6132  int qfromQ = strat->fromQ[i];
     6133
     6134  int j;
     6135
     6136  for (j=1; j<= toInsert -1; j++)
     6137  {
     6138    //    q = pLPshift(strat->S[i],j,uptodeg,lV);
     6139    /* we increase shifts by one; must delete q there*/
     6140    q = pLPshift(q,1,uptodeg,lV);
     6141    /* here we need to call enterOnePair with two polys ... */
     6142    enterOnePairShift(q, p, ecart, isFromQ, strat, -1, ecartq, qfromQ, uptodeg, lV);
     6143  }
     6144  /* delete q? */
     6145  pDelete(&q);
     6146}
     6147
     6148/*1
     6149* put the pairs (sh \dot qq,p)  into the set B, ecart=ecart(p)
     6150*/
     6151void enterOnePairSelfShifts (poly qq, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int uptodeg, int lV)
     6152{
     6153
     6154  /* should cycle through all shifts of q until uptodeg - lastVblock(q) */
     6155  /* that is create the pairs (f, s \dot g)  */
     6156
     6157 /* determine how many elements we have to insert for a given s[i] */
     6158  /* x(0)y(1)z(2) : lastVblock-1=2, to add until lastVblock=uptodeg-1 */
     6159  /* hence, a total number of elt's to add is: */
     6160  /*  int toInsert = 1 + (uptodeg-1) - (pLastVblock(p.p, lV) -1);  */
     6161  int toInsert = uptodeg  - pLastVblock(qq, lV) +1;
     6162
     6163  //  assume(i<=strat->sl); // from OnePair
     6164  if (strat->interred_flag) return; // ?
     6165
     6166  /* these vars hold for all shifts of s[i] */
     6167  int ecartq = 0; //Hans says it's ok; we're in the homog case, no ecart
     6168  int qfromQ = 0; // strat->fromQ[i];
     6169
     6170  int j;
     6171  poly q = pCopy(qq);   // q has zero shift
     6172  for (j=1; j<= toInsert -1; j++)
     6173  {
     6174    //    q = pLPshift(strat->S[i],j,uptodeg,lV);
     6175    /* we increase shifts by one; must delete q there*/
     6176    q = pLPshift(q,1,uptodeg,lV);
     6177    /* here we need to call enterOnePair with two polys ... */
     6178    enterOnePairShift(q, p, ecart, isFromQ, strat, -1, ecartq, qfromQ, uptodeg, lV);
     6179  }
     6180  /* delete q? */
     6181  pDelete(&q);
     6182}
     6183
     6184/*2
     6185* put the pair (q,p)  into the set B, ecart=ecart(p), q is the shift of some s[i]
     6186*/
     6187void enterOnePairShift (poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int uptodeg, int lV)
     6188{
     6189
     6190  /* poly q stays for s[i], ecartq = ecart(q), qisFromQ = applies to q */
     6191
     6192  int qfromQ = qisFromQ;
     6193
     6194  /* need additionally: int up_to_degree, poly V0 with the variables in (0)  or just the number lV = the length of the first block */
     6195
    60186196  atR = -1;
    6019   int j;
    6020   int lb = pLastVblock(p,lV);
    6021   poly q;
    6022   for (j=0; j<= uptodeg - lb; j++)
    6023   {
    6024     q = pLPshift(p,j,uptodeg,lV);
    6025     enterOnePairShift(i, q, ecart, isFromQ, strat, -1, uptodeg, lV);
    6026   }
    6027 }
    6028 #endif
    6029 
    6030 #ifdef HAVE_PLURAL
    6031 /*2
    6032 * put the pair (s[i],p)  into the set B, ecart=ecart(p)
    6033 */
    6034 void enterOnePairShift (int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int uptodeg, int lV)
    6035 {
    6036 
    6037   /* need additionally: int up_to_degree, poly V0 with the variables in (0)  or just the number lV = the length of the first block */
    6038   /* should cycle through all shifts of s[i] until up_to_degree - lastVblock(s[i]) */
    6039   /* that is create the pairs (f, s \dot g) for deg(s\dot g)= */
    6040   atR = -1;
    6041   assume(i<=strat->sl);
     6197  //  assume(i<=strat->sl); // satisfied automatically
    60426198  if (strat->interred_flag) return;
    60436199
    … …  
    60526208  Lp.lcm = pInit();
    60536209
    6054   pLcm(p,strat->S[i],Lp.lcm);
     6210  pLcm(p,q,Lp.lcm);
    60556211  pSetm(Lp.lcm);
    60566212
    60576213  /* apply the V criterion */
     6214  /* or do it in ManyShifts? */
    60586215  if (!isInV(Lp.lcm, lV))
    60596216  {
     6217#ifdef KDEBUG
     6218    if (TEST_OPT_DEBUG)
     6219    {
     6220      PrintS("V crit applied to q = ");
     6221      wrp(pHead(q));
     6222      PrintS(", p = ");
     6223      wrp(pHead(p));
     6224      PrintLn();
     6225    }
     6226#endif
    60606227    pLmFree(Lp.lcm);
    60616228    Lp.lcm=NULL;
    60626229    return;
    60636230    /* + add the counter for applying the V criterion */
    6064   }
    6065 
     6231    /* like strat->cv */
     6232  }
    60666233
    60676234  const BOOLEAN bIsPluralRing = rIsPluralRing(currRing);
    … …  
    60716238  if (strat->sugarCrit && bNCProdCrit)
    60726239  {
    6073     if((!((strat->ecartS[i]>0)&&(ecart>0)))
    6074     && pHasNotCF(p,strat->S[i]))
     6240    if((!((ecartq>0)&&(ecart>0)))
     6241    && pHasNotCF(p,q))
    60756242    {
    60766243    /*
    … …  
    60946261    }
    60956262    else
    6096       Lp.ecart = si_max(ecart,strat->ecartS[i]);
    6097     if (strat->fromT && (strat->ecartS[i]>ecart))
     6263      Lp.ecart = si_max(ecart,ecartq);
     6264    if (strat->fromT && (ecartq>ecart))
    60986265    {
    60996266      pLmFree(Lp.lcm);
    … …  
    61186285        {
    61196286          strat->c3++;
    6120           if ((strat->fromQ==NULL) || (isFromQ==0) || (strat->fromQ[i]==0))
     6287          if ((strat->fromQ==NULL) || (isFromQ==0) || (qfromQ==0))
    61216288          {
    61226289            pLmFree(Lp.lcm);
    … …  
    61436310      // TODO: enable productCrit for super commutative algebras...
    61446311      if(/*(strat->ak==0) && productCrit(p,strat->S[i])*/
    6145       pHasNotCF(p,strat->S[i]))
     6312      pHasNotCF(p,q))
    61466313      {
    61476314      /*
    … …  
    61626329          return;
    61636330      }
    6164       if (strat->fromT && (strat->ecartS[i]>ecart))
     6331      if (strat->fromT && (ecartq>ecart))
    61656332      {
    61666333        pLmFree(Lp.lcm);
    … …  
    61816348        {
    61826349          strat->c3++;
    6183           if ((strat->fromQ==NULL) || (isFromQ==0) || (strat->fromQ[i]==0))
     6350          if ((strat->fromQ==NULL) || (isFromQ==0) || (qfromQ==0))
    61846351          {
    61856352            pLmFree(Lp.lcm);
    … …  
    62036370  if (strat->fromT && !TEST_OPT_INTSTRATEGY)
    62046371    pNorm(p);
    6205   if ((strat->S[i]==NULL) || (p==NULL))
     6372  if ((q==NULL) || (p==NULL))
    62066373    return;
    6207   if ((strat->fromQ!=NULL) && (isFromQ!=0) && (strat->fromQ[i]!=0))
     6374  if ((strat->fromQ!=NULL) && (isFromQ!=0) && (qfromQ!=0))
    62086375    Lp.p=NULL;
    62096376  else
    62106377  {
    6211     if ( bIsPluralRing )
    6212     {
    6213       if(pHasNotCF(p, strat->S[i]))
    6214       {
    6215         if(ncRingType(currRing) == nc_lie)
    6216         {
    6217             // generalized prod-crit for lie-type
    6218             strat->cp++;
    6219             Lp.p = nc_p_Bracket_qq(pCopy(p),strat->S[i]);
    6220         }
    6221         else
    6222         if( bIsSCA )
    6223         {
    6224             // product criterion for homogeneous case in SCA
    6225             strat->cp++;
    6226             Lp.p = NULL;
    6227         }
    6228         else
    6229           Lp.p = nc_CreateSpoly(strat->S[i],p,currRing); // ?
    6230       }
    6231       else  Lp.p = nc_CreateSpoly(strat->S[i],p,currRing);
    6232     }
    6233     else
    6234     {
    6235       Lp.p = ksCreateShortSpoly(strat->S[i],p, strat->tailRing);
    6236     }
     6378//     if ( bIsPluralRing )
     6379//     {
     6380//       if(pHasNotCF(p, q))
     6381//       {
     6382//         if(ncRingType(currRing) == nc_lie)
     6383//         {
     6384//             // generalized prod-crit for lie-type
     6385//             strat->cp++;
     6386//             Lp.p = nc_p_Bracket_qq(pCopy(p),q);
     6387//         }
     6388//         else
     6389//         if( bIsSCA )
     6390//         {
     6391//             // product criterion for homogeneous case in SCA
     6392//             strat->cp++;
     6393//             Lp.p = NULL;
     6394//         }
     6395//         else
     6396//           Lp.p = nc_CreateSpoly(q,p,currRing); // ?
     6397//       }
     6398//       else  Lp.p = nc_CreateSpoly(q,p,currRing);
     6399//     }
     6400//     else
     6401//     {
     6402    Lp.p = ksCreateShortSpoly(q,p, strat->tailRing);
     6403      //  }
    62376404  }
    62386405  if (Lp.p == NULL)
    62396406  {
    62406407    /*- the case that the s-poly is 0 -*/
    6241     if (strat->pairtest==NULL) initPairtest(strat);
    6242     strat->pairtest[i] = TRUE;/*- hint for spoly(S^[i],p)=0 -*/
    6243     strat->pairtest[strat->sl+1] = TRUE;
     6408    /* TEMPORARILY DISABLED FOR SHIFTS */
     6409//     if (strat->pairtest==NULL) initPairtest(strat);
     6410//     strat->pairtest[i] = TRUE;/*- hint for spoly(S^[i],p)=0 -*/
     6411//     strat->pairtest[strat->sl+1] = TRUE;
     6412    /* END _ TEMPORARILY DISABLED FOR SHIFTS */
    62446413    /*hint for spoly(S[i],p) == 0 for some i,0 <= i <= sl*/
    62456414    /*
    … …  
    62576426  {
    62586427    /*- the pair (S[i],p) enters B -*/
    6259     Lp.p1 = strat->S[i];
     6428    Lp.p1 = q;
    62606429    Lp.p2 = p;
    62616430
    … …  
    62636432      pNext(Lp.p) = strat->tail;
    62646433
    6265     if (atR >= 0)
    6266     {
    6267       Lp.i_r1 = strat->S_2_R[i];
    6268       Lp.i_r2 = atR;
    6269     }
    6270     else
    6271     {
     6434    /* TEMPORARILY DISABLED FOR SHIFTS */
     6435    /* at the beginning we set atR = -1 */
     6436//     if (atR >= 0)
     6437//     {
     6438      /*      Lp.i_r1 = strat->S_2_R[i]; */
     6439//       Lp.i_r2 = atR;
     6440//     }
     6441//     else
     6442//     {
     6443    /* END _ TEMPORARILY DISABLED FOR SHIFTS */
    62726444      Lp.i_r1 = -1;
    62736445      Lp.i_r2 = -1;
    6274     }
    6275     strat->initEcartPair(&Lp,strat->S[i],p,strat->ecartS[i],ecart);
     6446      //    }
     6447    strat->initEcartPair(&Lp,q,p,ecartq,ecart);
    62766448
    62776449    if (TEST_OPT_INTSTRATEGY)
    … …  
    62856457  }
    62866458}
    6287 #endif
    6288 
    6289 #ifdef HAVE_PLURAL
     6459
     6460
     6461/*2
     6462*(s[0],h),...,(s[k],h) will be put to the pairset L(via initenterpairs)
     6463*superfluous elements in S will be deleted
     6464*/
     6465void enterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR,int uptodeg, int lV)
     6466{
     6467  /* Q: what is exactly the strat->fromT ? */
     6468  int j=pos;
     6469
     6470#ifdef HAVE_RINGS
     6471  assume (!rField_is_Ring(currRing));
     6472#endif
     6473  initenterpairsShift(h,k,ecart,0,strat, atR,uptodeg,lV);
     6474  if ( (!strat->fromT)
     6475  && ((strat->syzComp==0)
     6476    ||(pGetComp(h)<=strat->syzComp)))
     6477  {
     6478    //Print("start clearS k=%d, pos=%d, sl=%d\n",k,pos,strat->sl);
     6479    unsigned long h_sev = pGetShortExpVector(h);
     6480    loop
     6481    {
     6482      if (j > k) break;
     6483      clearS(h,h_sev, &j,&k,strat);
     6484      j++;
     6485    }
     6486    //Print("end clearS sl=%d\n",strat->sl);
     6487  }
     6488 // PrintS("end enterpairs\n");
     6489}
     6490
    62906491/*3
    62916492*(s[0],h),...,(s[k],h) will be put to the pairset L
    62926493* additionally we put the pairs (h, s \sdot h) for s>=1 to L
    62936494*/
    6294 void initenterpairsShift (poly h,int k,int ecart,int isFromQ, kStrategy strat, int atR)
     6495void initenterpairsShift (poly h,int k,int ecart,int isFromQ, kStrategy strat, int atR, int uptodeg, int lV)
    62956496{
    62966497  atR = -1;
    … …  
    63116512          {
    63126513            new_pair=TRUE;
    6313             enterOnePair(j,h,ecart,isFromQ,strat, atR);
     6514            enterOnePairManyShifts(j,h,ecart,isFromQ,strat, atR,uptodeg,lV);
    63146515          //Print("j:%d, Ll:%d\n",j,strat->Ll);
    63156516          }
    … …  
    63216522        for (j=0; j<=k; j++)
    63226523        {
    6323           enterOnePair(j,h,ecart,isFromQ,strat, atR);
     6524          enterOnePairManyShifts(j,h,ecart,isFromQ,strat, atR,uptodeg,lV);
    63246525        }
    63256526        /* HERE we put (h, s*h) pairs */
     6527       /* enterOnePairSelfShifts (poly qq, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int uptodeg, int lV); */
     6528       enterOnePairSelfShifts (h, h, ecart, isFromQ, strat, atR, uptodeg, lV);
    63266529      }
    63276530    }
    … …  
    63346537        {
    63356538          new_pair=TRUE;
    6336           enterOnePair(j,h,ecart,isFromQ,strat, atR);
     6539          enterOnePairManyShifts(j,h,ecart,isFromQ,strat, atR, uptodeg, lV);
    63376540        //Print("j:%d, Ll:%d\n",j,strat->Ll);
    63386541        }
    63396542      }
    63406543      /* HERE we put (h, s*h) pairs TOO */
     6544      enterOnePairSelfShifts (h, h, ecart, isFromQ, strat, atR, uptodeg, lV);
    63416545    }
    63426546
    … …  
    63476551#endif
    63486552
    6349 #ifdef HAVE_PLURAL
     6553
     6554
     6555
    63506556/*2
    6351 *reduces h with elements from T choosing  the first possible
    6352 * element in t with respect to the given pDivisibleBy
    6353 */
    6354 int redFirstShift (LObject* h,kStrategy strat)
    6355 {
    6356   int at,reddeg,d,i;
    6357   int pass = 0;
    6358   int j = 0;
    6359 
    6360   d = pFDeg((*h).p,currRing)+(*h).ecart;
    6361   reddeg = strat->LazyDegree+d;
    6362   loop
    6363   {
    6364     if (j > strat->sl)
    6365     {
    6366       #ifdef KDEBUG
    6367       if (TEST_OPT_DEBUG) PrintLn();
    6368       #endif
    6369       return 0;
    6370     }
    6371     #ifdef KDEBUG
    6372     if (TEST_OPT_DEBUG) Print("%d",j);
    6373     #endif
    6374     if (pDivisibleBy(strat->S[j],(*h).p))
    6375     {
    6376       #ifdef KDEBUG
    6377       if (TEST_OPT_DEBUG) PrintS("+\n");
    6378       #endif
    6379       /*
    6380       * the polynomial to reduce with is;
    6381       * T[j].p
    6382       */
    6383       if (!TEST_OPT_INTSTRATEGY)
    6384         pNorm(strat->S[j]);
    6385       #ifdef KDEBUG
    6386       if (TEST_OPT_DEBUG)
    6387       {
    6388         wrp(h->p);
    6389         PrintS(" with ");
    6390         wrp(strat->S[j]);
    6391       }
    6392       #endif
    6393       (*h).p = nc_ReduceSpoly(strat->S[j],(*h).p, currRing);
    6394       //spSpolyRed(strat->T[j].p,(*h).p,strat->kNoether);
    6395 
    6396       #ifdef KDEBUG
    6397       if (TEST_OPT_DEBUG)
    6398       {
    6399         PrintS(" to ");
    6400         wrp(h->p);
    6401       }
    6402       #endif
    6403       if ((*h).p == NULL)
    6404       {
    6405         if (h->lcm!=NULL) p_LmFree((*h).lcm, currRing);
    6406         return 0;
    6407       }
    6408       if (TEST_OPT_INTSTRATEGY)
    6409       {
    6410         if (rField_is_Zp_a()) pContent(h->p);
    6411         else pCleardenom(h->p);// also does a pContent
    6412       }
    6413       /*computes the ecart*/
    6414       d = pLDeg((*h).p,&((*h).length),currRing);
    6415       (*h).FDeg=pFDeg((*h).p,currRing);
    6416       (*h).ecart = d-(*h).FDeg; /*pFDeg((*h).p);*/
    6417       if ((strat->syzComp!=0) && !strat->honey)
    6418       {
    6419         if ((strat->syzComp>0) && (pMinComp((*h).p) > strat->syzComp))
    6420         {
    6421           #ifdef KDEBUG
    6422           if (TEST_OPT_DEBUG) PrintS(" > sysComp\n");
    6423           #endif
    6424           return 0;
    6425         }
    6426       }
    6427       /*- try to reduce the s-polynomial -*/
    6428       pass++;
    6429       /*
    6430       *test whether the polynomial should go to the lazyset L
    6431       *-if the degree jumps
    6432       *-if the number of pre-defined reductions jumps
    6433       */
    6434       if ((strat->Ll >= 0)
    6435       && ((d >= reddeg) || (pass > strat->LazyPass))
    6436       && !strat->homog)
    6437       {
    6438         at = strat->posInL(strat->L,strat->Ll,h,strat);
    6439         if (at <= strat->Ll)
    6440         {
    6441           i=strat->sl+1;
    6442           do
    6443           {
    6444             i--;
    6445             if (i<0) return 0;
    6446           } while (!pDivisibleBy(strat->S[i],(*h).p));
    6447           enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
    6448           #ifdef KDEBUG
    6449           if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
    6450           #endif
    6451           (*h).p = NULL;
    6452           return 0;
    6453         }
    6454       }
    6455       if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
    6456       {
    6457         reddeg = d+1;
    6458         Print(".%d",d);mflush();
    6459       }
    6460       j = 0;
    6461       #ifdef KDEBUG
    6462       if (TEST_OPT_DEBUG) PrintLn();
    6463       #endif
    6464     }
    6465     else
    6466     {
    6467       #ifdef KDEBUG
    6468       if (TEST_OPT_DEBUG) PrintS("-");
    6469       #endif
    6470       j++;
    6471     }
    6472   }
    6473 }
    6474 
    6475 
    6476 /*2
    6477 *  reduction procedure for the homogeneous case
    6478 *  and the case of a degree-ordering
    6479 */
    6480 int redHomogShift (LObject* h,kStrategy strat)
    6481 {
    6482   if (strat->tl<0) return 1;
    6483   //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
    6484   assume(h->FDeg == h->pFDeg());
    6485 
    6486   poly h_p;
    6487   int i,j,at,pass, ii;
    6488   unsigned long not_sev;
    6489   long reddeg,d;
    6490 
    6491   pass = j = 0;
    6492   d = reddeg = h->GetpFDeg();
    6493   h->SetShortExpVector();
    6494   int li;
    6495   h_p = h->GetLmTailRing();
    6496   not_sev = ~ h->sev;
    6497   loop
    6498   {
    6499     j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, h);
    6500     if (j < 0) return 1;
    6501 
    6502     li = strat->T[j].pLength;
    6503     ii = j;
    6504     /*
    6505      * the polynomial to reduce with (up to the moment) is;
    6506      * pi with length li
    6507      */
    6508     i = j;
    6509 #if 1
    6510     if (TEST_OPT_LENGTH)
     6557* puts p to the set T, starting with the at position atT
     6558* and inserts all admissible shifts of p
     6559*/
     6560void enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV)
     6561{
     6562  /* determine how many elements we have to insert */
     6563  /* x(0)y(1)z(2) : lastVblock-1=2, to add until lastVblock=uptodeg-1 */
     6564  /* hence, a total number of elt's to add is: */
     6565  /*  int toInsert = 1 + (uptodeg-1) - (pLastVblock(p.p, lV) -1);  */
     6566
     6567  pp_Test(p.p, currRing, p.tailRing);
     6568
     6569  int toInsert = uptodeg  - pLastVblock(pCopy(p.p), lV) +1;
     6570
     6571  int i;
     6572
     6573  if (atT < 0)
     6574    atT = strat->posInT(strat->T, strat->tl, p);
     6575 
     6576  LObject q;
     6577  poly s;
     6578  /* can call enterT in a sequence, e.g. */
     6579  for (i=0; i<=toInsert-1; i++)
     6580  {
     6581    q = p;
     6582    /* shift p, that is create another LObject and shift its poly */
     6583    /* change: p.p, p.t_p, */
     6584    /* change: i_r (must be -1 because we're not yet in T ? */
     6585    q.Copy(); // following
     6586    /*   pLPshift(poly p, int sh, int uptodeg, int lV); */
     6587    s = pLPshift(pCopy(q.p), i, uptodeg, lV); // deletes 1st arg, hence pCopy
     6588    q.p = pCopy(s); pDelete(&s);
     6589    if (q.t_p != NULL) pNext(q.t_p) = pNext(q.p); // from enterT
     6590    /* enter it into T */
     6591    enterT(q,strat,atT+i);
     6592  }
     6593
     6594/* Q: what to do with this one in the orig enterT ? */
     6595/*  strat->R[strat->tl] = &(strat->T[atT]); */
     6596/* Solution: it is done by enterT each time separately */
     6597}
     6598
     6599
     6600
     6601poly redtailBbaShift (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
     6602{
     6603  /* for the shift case need to run it with withT = TRUE */
     6604  strat->redTailChange=FALSE;
     6605  if (strat->noTailReduction) return L->GetLmCurrRing();
     6606  poly h, p;
     6607  p = h = L->GetLmTailRing();
     6608  if ((h==NULL) || (pNext(h)==NULL))
     6609    return L->GetLmCurrRing();
     6610
     6611  TObject* With;
     6612  // placeholder in case strat->tl < 0
     6613  TObject  With_s(strat->tailRing);
     6614
     6615  LObject Ln(pNext(h), strat->tailRing);
     6616  Ln.pLength = L->GetpLength() - 1;
     6617
     6618  pNext(h) = NULL;
     6619  if (L->p != NULL) pNext(L->p) = NULL;
     6620  L->pLength = 1;
     6621
     6622  Ln.PrepareRed(strat->use_buckets);
     6623
     6624  while(!Ln.IsNull())
     6625  {
    65116626    loop
    65126627    {
    6513       /*- search the shortest possible with respect to length -*/
    6514       i++;
    6515       if (i > strat->tl)
    6516         break;
    6517       if (li<=1)
    6518         break;
    6519       if ((strat->T[i].pLength < li)
    6520          &&
    6521           p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
    6522                                h_p, not_sev, strat->tailRing))
    6523       {
    6524         /*
    6525          * the polynomial to reduce with is now;
    6526          */
    6527         li = strat->T[i].pLength;
    6528         ii = i;
    6529       }
    6530     }
    6531 #endif
    6532 
    6533     /*
    6534      * end of search: have to reduce with pi
    6535      */
    6536 #ifdef KDEBUG
    6537     if (TEST_OPT_DEBUG)
    6538     {
    6539       PrintS("red:");
    6540       h->wrp();
    6541       PrintS(" with ");
    6542       strat->T[ii].wrp();
    6543     }
    6544 #endif
    6545     assume(strat->fromT == FALSE);
    6546 
    6547     ksReducePoly(h, &(strat->T[ii]), NULL, NULL, strat);
    6548 
    6549 #ifdef KDEBUG
    6550     if (TEST_OPT_DEBUG)
    6551     {
    6552       PrintS("\nto ");
    6553       h->wrp();
    6554       PrintLn();
    6555     }
    6556 #endif
    6557 
    6558     h_p = h->GetLmTailRing();
    6559     if (h_p == NULL)
    6560     {
    6561       if (h->lcm!=NULL) pLmFree(h->lcm);
    6562 #ifdef KDEBUG
    6563       h->lcm=NULL;
    6564 #endif
    6565       return 0;
    6566     }
    6567     h->SetShortExpVector();
    6568     not_sev = ~ h->sev;
    6569     /*
    6570      * try to reduce the s-polynomial h
    6571      *test first whether h should go to the lazyset L
    6572      *-if the degree jumps
    6573      *-if the number of pre-defined reductions jumps
    6574      */
    6575     pass++;
    6576     if (!K_TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
    6577     {
    6578       h->SetLmCurrRing();
    6579       at = strat->posInL(strat->L,strat->Ll,h,strat);
    6580       if (at <= strat->Ll)
    6581       {
    6582         int dummy=strat->sl;
    6583         if (kFindDivisibleByInS(strat, &dummy, h) < 0)
    6584           return 1;
    6585         enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
    6586 #ifdef KDEBUG
    6587         if (TEST_OPT_DEBUG)
    6588           Print(" lazy: -> L%d\n",at);
    6589 #endif
    6590         h->Clear();
    6591         return -1;
    6592       }
    6593     }
    6594   }
    6595 }
    6596 #endif // HAVE_PLURAL
     6628      Ln.SetShortExpVector();
     6629      if (withT)
     6630      {
     6631        int j;
     6632        j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, &Ln);
     6633        if (j < 0) break;
     6634        With = &(strat->T[j]);
     6635      }
     6636      else
     6637      {
     6638        With = kFindDivisibleByInS(strat, pos, &Ln, &With_s);
     6639        if (With == NULL) break;
     6640      }
     6641      if (normalize && (!TEST_OPT_INTSTRATEGY) && (!nIsOne(pGetCoeff(With->p))))
     6642      {
     6643        With->pNorm();
     6644        //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
     6645      }
     6646      strat->redTailChange=TRUE;
     6647      if (ksReducePolyTail(L, With, &Ln))
     6648      {
     6649        // reducing the tail would violate the exp bound
     6650        //  set a flag and hope for a retry (in bba)
     6651        strat->completeReduce_retry=TRUE;
     6652        do
     6653        {
     6654          pNext(h) = Ln.LmExtractAndIter();
     6655          pIter(h);
     6656          L->pLength++;
     6657        } while (!Ln.IsNull());
     6658        goto all_done;
     6659      }
     6660      if (Ln.IsNull()) goto all_done;
     6661      if (! withT) With_s.Init(currRing);
     6662    }
     6663    pNext(h) = Ln.LmExtractAndIter();
     6664    pIter(h);
     6665    L->pLength++;
     6666  }
     6667
     6668  all_done:
     6669  Ln.Delete();
     6670  if (L->p != NULL) pNext(L->p) = pNext(p);
     6671
     6672  if (strat->redTailChange)
     6673  {
     6674    L->last = NULL;
     6675    L->length = 0;
     6676  }
     6677  L->Normalize(); // HANNES: should have a test
     6678  kTest_L(L);
     6679  return L->GetLmCurrRing();
     6680}
    65976681
    65986682#endif // KUTIL_CC
Note: See TracChangeset for help on using the changeset viewer.