Changeset ad1c3b in git


Ignore:
Timestamp:
Mar 13, 2008, 8:25:49 PM (15 years ago)
Author:
Viktor Levandovskyy <levandov@…>
Branches:
(u'spielwiese', '91fdef05f09f54b8d58d92a472e9c4a43aa4656f')
Children:
ba49d9f52b36950f74de618b1a41a677fa14fa07
Parents:
411ea98eecab97fbeac7f8395433a159d6d03584
Message:
*levandov: shift GB nonhomog case


git-svn-id: file:///usr/local/Singular/svn/trunk@10616 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
kernel
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • kernel/kstd2.cc

    r411ea98 rad1c3b  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: kstd2.cc,v 1.64 2008-02-26 23:35:30 levandov Exp $ */
     4/* $Id: kstd2.cc,v 1.65 2008-03-13 19:25:48 levandov Exp $ */
    55/*
    66*  ABSTRACT -  Kernel: alg. of Buchberger
    … …  
    15291529    }
    15301530
     1531    poly qq;
     1532
     1533    /* here in the nonhomog case we shrink the new spoly */
     1534   
     1535    if ( ! strat->homog)
     1536    {
     1537      strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
     1538      /* assume strat->P.t_p != NULL */
     1539      /* in the nonhomog case we have to shrink the polynomial */
     1540      assume(strat->P.t_p!=NULL);
     1541      qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
     1542      if (qq != NULL)
     1543      {
     1544         /* we're here if Shrink is nonzero */
     1545        //         strat->P.p =  NULL;
     1546        //        strat->P.Delete(); /* deletes P.p and P.t_p */ //error
     1547        strat->P.p   =  NULL; // is not set by Delete
     1548        strat->P.t_p =  qq;
     1549        strat->P.GetP(strat->lmBin);
     1550        // update sev and length
     1551        strat->initEcart(&(strat->P));
     1552        strat->P.sev = pGetShortExpVector(strat->P.p);
     1553//         strat->P.FDeg = strat->P.pFDeg();
     1554//         strat->P.length = strat->P.pLDeg();
     1555//         strat->P.pLength =strat->P.GetpLength(); //pLength(strat->P.p);
     1556      }
     1557      else
     1558      {
     1559         /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
     1560#ifdef KDEBUG
     1561         if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
     1562#endif
     1563         //      strat->P.Delete();  // cause error
     1564         strat->P.p = NULL;
     1565         strat->P.t_p = NULL;
     1566           //         strat->P.p = NULL; // or delete strat->P.p ?
     1567       }
     1568    }
     1569      /* end shrinking poly in the nonhomog case */
     1570
    15311571    if (strat->P.p == NULL && strat->P.t_p == NULL)
    15321572    {
    … …  
    15701610          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
    15711611      }
     1612
     1613      // here we must shrink again! and optionally reduce again
     1614      // or build shrink into redtailBba!
    15721615
    15731616#ifdef KDEBUG
    … …  
    15961639      }
    15971640
     1641    /* here in the nonhomog case we shrink the reduced poly AGAIN */
     1642   
     1643    if ( ! strat->homog)
     1644    {
     1645      strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
     1646      /* assume strat->P.t_p != NULL */
     1647      /* in the nonhomog case we have to shrink the polynomial */
     1648      assume(strat->P.t_p!=NULL); // poly qq defined above
     1649      qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
     1650      if (qq != NULL)
     1651      {
     1652         /* we're here if Shrink is nonzero */
     1653        //         strat->P.p =  NULL;
     1654        //        strat->P.Delete(); /* deletes P.p and P.t_p */ //error
     1655        strat->P.p   =  NULL; // is not set by Delete
     1656        strat->P.t_p =  qq;
     1657        strat->P.GetP(strat->lmBin);
     1658        // update sev and length
     1659        strat->initEcart(&(strat->P));
     1660        strat->P.sev = pGetShortExpVector(strat->P.p);
     1661      }
     1662      else
     1663      {
     1664         /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
     1665#ifdef PDEBUG
     1666         if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
     1667#endif
     1668         //      strat->P.Delete();  // cause error
     1669         strat->P.p = NULL;
     1670         strat->P.t_p = NULL;
     1671           //         strat->P.p = NULL; // or delete strat->P.p ?
     1672         goto     red_shrink2zero;
     1673       }
     1674    }
     1675      /* end shrinking poly AGAIN in the nonhomog case */
     1676
     1677
    15981678      // enter into S, L, and T
    15991679      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
    … …  
    16011681      //enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV); // syntax
    16021682      // the default value for atT = -1 as in bba
    1603       strat->P.GetP(); // because shifts are counted with .p structure
     1683      /*   strat->P.GetP(); */
     1684      // because shifts are counted with .p structure // done before, but ?
    16041685      enterTShift(strat->P,strat,-1,uptodeg, lV);
    1605 //       poly vw;
    1606 //       if (strat->P.t_p!=NULL)
    1607 //       {
    1608 //          vw = pCopyL2p(strat->P,strat);     
    1609 //       }
    1610 //       else
    1611 //       {
    1612 //          vw = pCopy(strat->P.p);
    1613 //       }
    16141686      enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
    16151687      //      enterpairsShift(vw,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
    1616       // delete vw ?
    16171688      // posInS only depends on the leading term
    16181689      if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
    … …  
    16241695      //  strat->P.Delete(); // syzComp test: it is in T
    16251696      }
     1697
    16261698      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
    16271699//      Print("[%d]",hilbeledeg);
    … …  
    16291701      if (strat->sl>srmax) srmax = strat->sl;
    16301702    }
    1631     else if (strat->P.p1 == NULL && strat->minim > 0)
    1632     {
    1633       p_Delete(&strat->P.p2, currRing, strat->tailRing);
     1703    else
     1704    {
     1705    red_shrink2zero:
     1706      if (strat->P.p1 == NULL && strat->minim > 0)
     1707      {
     1708        p_Delete(&strat->P.p2, currRing, strat->tailRing);
     1709      }
    16341710    }
    16351711#ifdef KDEBUG

  • kernel/kutil.cc

    r411ea98 rad1c3b  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: kutil.cc,v 1.87 2008-02-26 23:35:30 levandov Exp $ */
     4/* $Id: kutil.cc,v 1.88 2008-03-13 19:25:48 levandov Exp $ */
    55/*
    66* ABSTRACT: kernel: utils for kStd
    … …  
    62616261    if (TEST_OPT_DEBUG)
    62626262    {
    6263       Print("entered ManyShifts: with toInsert=%d",toInsert); PrintLn();
     6263      //      Print("entered ManyShifts: with toInsert=%d",toInsert); PrintLn();
    62646264    }
    62656265#endif
    … …  
    63006300    if (TEST_OPT_DEBUG)
    63016301    {
    6302       PrintS("ManyShifts: calling enterOnePairShift(q,p)");
    6303 //       wrp(q); //     wrp(pHead(q));
    6304 //       PrintS(", p = ");
    6305 //       wrp(p); //wrp(pHead(p));
    6306       PrintLn();
     6302      //      PrintS("ManyShifts: calling enterOnePairShift(q,p)");      PrintLn();
    63076303    }
    63086304#endif
    … …  
    63426338    if (TEST_OPT_DEBUG)
    63436339    {
    6344       Print("entered SelfShifts: with toInsert=%d",toInsert); PrintLn();
     6340      //      Print("entered SelfShifts: with toInsert=%d",toInsert); PrintLn();
    63456341    }
    63466342#endif
    … …  
    63686364    if (TEST_OPT_DEBUG)
    63696365    {
    6370       PrintS("SelfShifts: calling enterOnePairShift(q,p)");
    6371 //       wrp(q); //     wrp(pHead(q));
    6372 //       PrintS(", p = ");
    6373 //       wrp(p); //wrp(pHead(p));
    6374       PrintLn();
     6366      //      PrintS("SelfShifts: calling enterOnePairShift(q,p)");      PrintLn();
    63756367    }
    63766368#endif
    … …  
    63966388    if (TEST_OPT_DEBUG)
    63976389    {
    6398       PrintS("enterOnePairShift(q,p) invoked with q = ");
    6399       wrp(q); //      wrp(pHead(q));
    6400       PrintS(", p = ");
    6401       wrp(p); //wrp(pHead(p));
    6402       PrintLn();
     6390//       PrintS("enterOnePairShift(q,p) invoked with q = ");
     6391//       wrp(q); //      wrp(pHead(q));
     6392//       PrintS(", p = ");
     6393//       wrp(p); //wrp(pHead(p));
     6394//       PrintLn();
    64036395    }
    64046396#endif
    … …  
    67956787
    67966788#ifdef PDEBUG
    6797   Print("enterTShift uses toInsert: %d", toInsert);  PrintLn();
     6789  //  Print("enterTShift uses toInsert: %d", toInsert);  PrintLn();
    67986790#endif
    67996791  int i;

  • kernel/shiftgb.cc

    r411ea98 rad1c3b  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: shiftgb.cc,v 1.6 2008-02-24 17:41:32 levandov Exp $ */
     4/* $Id: shiftgb.cc,v 1.7 2008-03-13 19:25:49 levandov Exp $ */
    55/*
    66* ABSTRACT: kernel: utils for shift GB and free GB
    … …  
    4141
    4242/* TODO: write p* stuff as instances of p_* for all the functions */
     43/* p_* functions are new, p* are old */
    4344
    4445poly p_LPshiftT(poly p, int sh, int uptodeg, int lV, kStrategy strat, const ring r)
    … …  
    5253  assume(p_CheckIsFromRing(pNext(p),strat->tailRing));
    5354
    54   /* assume sh and uptodeg agree */
     55  /* assume sh and uptodeg agree  TODO check */
    5556
    5657  if (sh == 0) return(p); /* the zero shift */
    … …  
    7475{
    7576  /* assume shift takes place */
    76   /* shifts the poly p by sh */
    77   /* deletes p */
    78 
    79   /* assume sh and uptodeg agree */
     77  /* shifts the poly p from the ring r by sh */
     78
     79  /* assume sh and uptodeg agree TODO check */
    8080
    8181  if (p==NULL) return(p);
    … …  
    8383
    8484  poly q  = NULL;
    85   poly pp = p; // pCopy(p);
     85  poly pp = p; // do not take copies
    8686  while (pp!=NULL)
    8787  {
    … …  
    8989    pIter(pp);
    9090  }
    91   /* delete pp? */
    92   /* int version: returns TRUE if it was successful */
    9391  return(q);
    9492}
    … …  
    9694poly p_mLPshift(poly p, int sh, int uptodeg, int lV, const ring r)
    9795{
    98   /* pm is a monomial */
     96  /* p is a monomial from the ring r */
    9997
    10098  if (sh == 0) return(p); /* the zero shift */
    … …  
    119117  int *s=(int *)omAlloc0((r->N+1)*sizeof(int));
    120118  p_GetExpV(p,e,r);
    121   number c = pGetCoeff(p);
     119
    122120  int j;
    123121  //  for (j=1; j<=r->N; j++)
    … …  
    128126    {
    129127      s[j + (sh*lV)] = e[j]; /* actually 1 */
     128#ifdef PDEBUG
    130129      omCheckAddr(s);
     130#endif
    131131    }
     132#ifdef PDEBUG
    132133    else
    133134    {
    134135      if (e[j]!=0)
    135136      {
    136 #ifdef PDEBUG
    137          Print("p_mLPshift: ex[%d]=%d\n",j,e[j]);
    138 #endif
     137        //         Print("p_mLPshift: ex[%d]=%d\n",j,e[j]);
    139138      }
    140139    }
     140#endif
    141141  }
    142142  poly m = p_ISet(1,r);
    143143  p_SetExpV(m,s,r);
    144   /*  pSetm(m); */ /* done in the pSetExpV */
    145   /* think on the component */
    146   pSetCoeff0(m,c);
    147144  freeT(e, r->N);
    148145  freeT(s, r->N);
     146  /*  pSetm(m); */ /* done in the pSetExpV */
     147  /* think on the component and coefficient */
     148  //  number c = pGetCoeff(p);
     149  //  p_SetCoeff0(m,p_GetCoeff(p,r),r);
     150  p_SetComp(m,p_GetComp(p,r),r); // component is preserved
     151  p_SetCoeff0(m,p_GetCoeff(p,r),r);  // coeff is preserved
    149152  return(m);
    150153}
    … …  
    202205  for (j=1; j<=currRing->N; j++)
    203206  {
    204     if (e[j])
     207    if (e[j]==1)
    205208    {
    206209      s[j + (sh*lV)] = e[j]; /* actually 1 */
    … …  
    371374
    372375  /* there should be two routines: */
    373   /* 1. tests squarefreeness: in homog this suffices */
     376  /* 1. test place-squarefreeness: in homog this suffices: isInV */
    374377  /* 2. test the presence of a hole -> in the tail??? */
    375378
    376379int isInV(poly p, int lV)
    377380{
    378 
     381  /* investigate only the leading monomial of p in currRing */
    379382  if (lV <= 0) return(0);
    380383  /* returns 1 iff p is in V */
    … …  
    382385  /* lV = the length of V = the number of orig vars */
    383386  int *e = (int *)omAlloc0((currRing->N+1)*sizeof(int));
    384   int  b = (int)(currRing->N)/lV; /* the number of blocks */
     387  int  b = (int)((currRing->N +lV-1)/lV); /* the number of blocks */
     388  //int b  = (int)(currRing->N)/lV;
    385389  int *B = (int *)omAlloc0((b+1)*sizeof(int)); /* the num of elements in a block */
    386390  pGetExpV(p,e);
    … …  
    395399    }
    396400  }
    397   j = b;
     401  //  j = b;
    398402  //  while ( (!B[j]) && (j>=1)) j--;
    399403  for (j=b; j>=1; j--)
    … …  
    401405    if (B[j]!=0) break;
    402406  }
    403 
    404   if (j==0)
    405   {
    406     /* it is a zero exp vector, which is in V */
    407     return(1);
    408   }
    409   /* now B[j] != 0 */
     407  /* do not need e anymore */
     408  freeT(e, currRing->N);
     409
     410  if (j==0) goto ret_true;
     411//   {
     412//     /* it is a zero exp vector, which is in V */
     413//     freeT(B, b);
     414//     return(1);
     415//   }
     416  /* now B[j] != 0 and we test place-squarefreeness */
    410417  for (j; j>=1; j--)
    411418  {
    412419    if (B[j]!=1)
    413420    {
     421      freeT(B, b);
    414422      return(0);
    415423    }
    416424  }
     425 ret_true:
     426  freeT(B, b);
    417427  return(1);
    418428}
    … …  
    421431{
    422432  /* for poly in lmCR/tailTR presentation */
    423   /* the below situation might happen! */
     433  /* the below situation (commented out) might happen! */
    424434//   if (r == currRing)
    425435//   {
    … …  
    439449}
    440450
     451poly p_ShrinkT(poly p, int lV, kStrategy strat, const ring r)
     452//poly p_Shrink(poly p, int uptodeg, int lV, kStrategy strat, const ring r)
     453{
     454  /* p is like TObject: lm in currRing = r, tail in tailRing  */
     455  /* proc shrinks the poly p in ring r */
     456  /* lV = the length of V = the number of orig vars */
     457  /* check assumes/exceptions */
     458  /* r->N is a multiple of lV */
     459
     460  if (p==NULL) return(p);
     461
     462  assume(p_LmCheckIsFromRing(p,r));
     463  assume(p_CheckIsFromRing(pNext(p),strat->tailRing));
     464
     465  poly q   = NULL;
     466  poly s   = p_mShrink(p, lV, r); // lm in currRing
     467  poly pp = pNext(p);
     468 
     469  while (pp != NULL)
     470  {
     471    //    q = p_Add_q(q, p_mShrink(pp,uptodeg,lV,strat->tailRing),strat->tailRing);
     472    q = p_Add_q(q, p_mShrink(pp,lV,strat->tailRing),strat->tailRing);
     473    pIter(pp);
     474  }
     475  pNext(s) = q;
     476  return(s);
     477}
     478
     479poly p_Shrink(poly p, int lV, const ring r)
     480{
     481  /* proc shrinks the poly p in ring r */
     482  /* lV = the length of V = the number of orig vars */
     483  /* check assumes/exceptions */
     484  /* r->N is a multiple of lV */
     485
     486  if (p==NULL) return(p);
     487  assume(p_CheckIsFromRing(p,r));
     488  poly q = NULL;
     489  poly pp = p;
     490 
     491  while (pp != NULL)
     492  {
     493    q = p_Add_q(q, p_mShrink(pp,lV,r),r);
     494    pIter(pp);
     495  }
     496  return(q);
     497}
     498
     499poly p_mShrink(poly p, int lV, const ring r)
     500{
     501  /* shrinks the monomial p in ring r */
     502  /* lV = the length of V = the number of orig vars */
     503
     504  /* check assumes/exceptions */
     505  /* r->N is a multiple of lV */
     506
     507  int *e = (int *)omAlloc0((r->N+1)*sizeof(int));
     508  int  b = (int)((r->N +lV-1)/lV); /* the number of blocks */
     509  //  int *B = (int *)omAlloc0((b+1)*sizeof(int)); /* the num of elements in a block */
     510  int *S = (int *)omAlloc0((r->N+1)*sizeof(int)); /* the shrinked exponent */
     511  p_GetExpV(p,e,r);
     512  int i,j; int cnt = 1; //counter for blocks in S
     513  for (j=1; j<=b; j++)
     514  {
     515    /* we go through all the vars */
     516    /* by blocks in lV vars */
     517    for (i=(j-1)*lV + 1; i<= j*lV; i++)
     518    {
     519      if (e[i]==1)
     520      {
     521        //      B[j] = B[j]+1; // for control in V?
     522         S[(cnt-1)*lV + (i - (j-1)*lV)] = e[i];
     523         /* assuming we are in V, can interrupt here */
     524         cnt++;
     525         //  break; //results in incomplete shrink!
     526         i = j*lV; // manual break under assumption p is in V
     527      }
     528    }
     529  }
     530#ifdef PDEBUG
     531  //  Print("p_mShrink: cnt = [%d], b = %d\n",cnt,b);
     532#endif
     533  // cnt -1 <= b  must hold!
     534  //  freeT(B, b);
     535  poly s = p_ISet(1,r);
     536  p_SetExpV(s,S,r);
     537  freeT(e, r->N);
     538  freeT(S, r->N);
     539  /*  p_Setm(s,r); // done by p_SetExpV */
     540  p_SetComp(s,p_GetComp(p,r),r); // component is preserved
     541  p_SetCoeff(s,p_GetCoeff(p,r),r);  // coeff is preserved
     542#ifdef PDEBUG
     543  //  Print("p_mShrink: from "); p_wrp(p,r); Print(" to "); p_wrp(s,r); PrintLn();
     544#endif
     545  return(s);
     546}
    441547
    442548/* shiftgb stuff */

  • kernel/shiftgb.h

    r411ea98 rad1c3b  
    44*  Computer Algebra System SINGULAR     *
    55****************************************/
    6 /* $Id: shiftgb.h,v 1.3 2008-02-23 20:12:53 levandov Exp $ */
     6/* $Id: shiftgb.h,v 1.4 2008-03-13 19:25:49 levandov Exp $ */
    77/*
    88* ABSTRACT: kernel: utils for kStd
    … …  
    1414poly p_LPshiftT(poly p, int sh, int uptodeg, int lV, kStrategy strat, const ring r);
    1515int p_LastVblockT(poly p, int lV, kStrategy strat, const ring r);
     16
     17poly p_ShrinkT(poly p, int lV, kStrategy strat, const ring r);
     18poly p_Shrink(poly p, int lV, const ring r);
     19poly p_mShrink(poly p, int lV, const ring r);
     20//poly p_Shrink(poly p, int uptodeg, int lV, kStrategy strat, const ring r);
     21//poly p_mShrink(poly p, int uptodeg, int lV, const ring r);
    1622
    1723poly p_LPshift(poly p, int sh, int uptodeg, int lV,const ring r);
Note: See TracChangeset for help on using the changeset viewer.