Changeset a2466f in git


Ignore:
Timestamp:
Jun 12, 2006, 2:07:12 AM (17 years ago)
Author:
Oliver Wienand <wienand@…>
Branches:
(u'spielwiese', '828514cf6e480e4bafc26df99217bf2a1ed1ef45')
Children:
c4c516319dd7380d23251f74e2a664cdb5664571
Parents:
30f22c1ce9b7faf89c70d82bed9c82dd6d7b4979
Message:
[oliver] @hannes: Please check changes to kutil.cc(pDivComp).

kutil.cc:
* pDivComp now distinguishes between equal and incomparable monoms
* changes to chainCritRing, in progress

ringgb.*:
* changes to testGB, now tests also inclusion of I

polys.cc:
* just doc


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

Legend:

Unmodified
Added
Removed

  • kernel/kutil.cc

    r30f22c ra2466f  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: kutil.cc,v 1.24 2006-06-07 18:44:23 wienand Exp $ */
     4/* $Id: kutil.cc,v 1.25 2006-06-12 00:07:11 wienand Exp $ */
    55/*
    66* ABSTRACT: kernel: utils for kStd
    … …  
    5252#define KDEBUG 2
    5353#endif
     54#define pDivComp_EQUAL 2
     55#define pDivComp_LESS 1
     56#define pDivComp_GREATER -1
     57#define pDivComp_INCOMP 0
     58
    5459
    5560#ifdef ENTER_USE_MYMEMMOVE
    … …  
    100105static poly redBba (poly h,int maxIndex,kStrategy strat);
    101106
     107/* Checks the relation of LM(p) and LM(q)
     108     LM(p) = LM(q) => return pDivComp_EQUAL
     109     LM(p) | LM(q) => return pDivComp_LESS
     110     LM(q) | LM(p) => return pDivComp_GREATER
     111     else return pDivComp_INCOMP */
    102112static inline int pDivComp(poly p, poly q)
    103113{
    … …  
    132142    if (a) return 1;
    133143    if (b) return -1;
     144    if (!a & !b) return pDivComp_EQUAL;
    134145  }
    135146  return 0;
    … …  
    438449}
    439450
     451#ifdef HAVE_RING2TOM
     452//void initLMtest(kStrategy strat)
     453//{
     454//  strat->lmtest = (unsigned int *)omAlloc0((strat->sl*strat->sl/2+2)*sizeof(BOOLEAN));
     455//}
     456#endif
     457
    440458/*2
    441459*test whether (p1,p2) or (p2,p1) is in L up position length
    … …  
    9961014  else
    9971015  {
    998     if (b % 2 == 1) 
     1016    if (b % 2 == 1)
    9991017    {
    10001018      return 0;
    … …  
    10261044  pSetm(Lp.lcm);
    10271045  pSetCoeff(Lp.lcm, nLcm(pGetCoeff(p), pGetCoeff(strat->S[i]), currRing));
    1028   if (strat->sugarCrit)
    1029   {
    1030         WarnS("Sugar Criterion not yet available on in the ring case");
    1031   }
    1032   else /*sugarcrit*/
    1033   {
    1034       // basic product criterion
    1035       if (pHasNotCF(p,strat->S[i]) && (long) pGetCoeff(p) % 2 == 1 && (long) pGetCoeff(strat->S[i]) % 2 == 1)
    1036       {
    1037           strat->cp++;
     1046  assume(!strat->sugarCrit);
     1047  // basic product criterion
     1048  if (pHasNotCF(p,strat->S[i]) && (long) pGetCoeff(p) % 2 == 1 && (long) pGetCoeff(strat->S[i]) % 2 == 1)
     1049  {
     1050      strat->cp++;
     1051      pLmFree(Lp.lcm);
     1052      Lp.lcm=NULL;
     1053      return;
     1054  }
     1055  assume(!strat->fromT);
     1056  /*
     1057  *the set B collects the pairs of type (S[j],p)
     1058  *suppose (r,p) is in B and (s,p) is the new pair and lcm(s,p) != lcm(r,p)
     1059  *if the leading term of s devides lcm(r,p) then (r,p) will be canceled
     1060  *if the leading term of r devides lcm(s,p) then (s,p) will not enter B
     1061  */
     1062  for(j = strat->Bl;j>=0;j--)
     1063  {
     1064    compare=pDivComp(strat->B[j].lcm,Lp.lcm);
     1065    compareCoeff = nComp((long) pGetCoeff(strat->B[j].lcm), (long) pGetCoeff(Lp.lcm));
     1066    if (compareCoeff == 0 || compare == compareCoeff)
     1067    {
     1068      if (compare == 1)
     1069      {
     1070        strat->c3++;
     1071        if ((strat->fromQ==NULL) || (isFromQ==0) || (strat->fromQ[i]==0))
     1072        {
    10381073          pLmFree(Lp.lcm);
    1039           Lp.lcm=NULL;
    10401074          return;
    1041       }
    1042       if (strat->fromT) // && (strat->ecartS[i]>ecart))
    1043       {
    1044           WarnS("Sugar Criterion not yet available on in the ring case");
    1045       }
    1046       /*
    1047       *the set B collects the pairs of type (S[j],p)
    1048       *suppose (r,p) is in B and (s,p) is the new pair and lcm(s,p)#lcm(r,p)
    1049       *if the leading term of s devides lcm(r,p) then (r,p) will be canceled
    1050       *if the leading term of r devides lcm(s,p) then (s,p) will not enter B
    1051       */
    1052       for(j = strat->Bl;j>=0;j--)
    1053       {
    1054         compare=pDivComp(strat->B[j].lcm,Lp.lcm);
    1055         compareCoeff = nComp((long) pGetCoeff(strat->B[j].lcm), (long) pGetCoeff(Lp.lcm));
    1056         if (compareCoeff == 0 || compare == compareCoeff)
    1057         {
    1058           if (compare==1)
    1059           {
    1060             strat->c3++;
    1061             if ((strat->fromQ==NULL) || (isFromQ==0) || (strat->fromQ[i]==0))
    1062             {
    1063               pLmFree(Lp.lcm);
    1064               return;
    1065             }
    1066             break;
    1067           }
    1068           else
    1069           if (compare ==-1)
    1070           {
    1071             deleteInL(strat->B,&strat->Bl,j,strat);
    1072             strat->c3++;
    1073           }
    1074         }
    1075       }
    1076     }
     1075        }
     1076        break;
     1077      }
     1078      else
     1079      if (compare == -1)
     1080      {
     1081        deleteInL(strat->B,&strat->Bl,j,strat);
     1082        strat->c3++;
     1083      }
     1084    }
     1085    if (compare == pDivComp_EQUAL)
     1086    {
     1087      // Add hint for same LM and direction of LC (later) (TODO Oliver)
     1088      if (compareCoeff == 1)
     1089      {
     1090        strat->c3++;
     1091        if ((strat->fromQ==NULL) || (isFromQ==0) || (strat->fromQ[i]==0))
     1092        {
     1093          pLmFree(Lp.lcm);
     1094          return;
     1095        }
     1096        break;
     1097      }
     1098      else
     1099      if (compareCoeff == -1)
     1100      {
     1101        deleteInL(strat->B,&strat->Bl,j,strat);
     1102        strat->c3++;
     1103      }
     1104    }
     1105  }
    10771106  /*
    10781107  *the pair (S[i],p) enters B if the spoly != 0
    … …  
    10831112  if ((strat->fromQ!=NULL) && (isFromQ!=0) && (strat->fromQ[i]!=0))
    10841113  {
    1085     WarnS("Oliver weiss nicht, was dieses genau macht.");
     1114    // Is from a previous computed GB, therefore we know that spoly will
     1115    // reduce to zero. Oliver.
    10861116    Lp.p=NULL;
    10871117  }
    … …  
    17551785{
    17561786  int i,j,l;
    1757 
    17581787  /*
    17591788  *pairtest[i] is TRUE if spoly(S[i],p) == 0.
    … …  
    17831812    strat->pairtest=NULL;
    17841813  }
    1785   if (strat->Gebauer || strat->fromT)
    1786   {
    1787     WarnS("Gebauer or fromT not tested yet in chainCritRing.");
    1788     if (strat->sugarCrit)
    1789     {
    1790         WarnS("Sugar Criterion not yet available for coefficient rings.");
    1791     }
    1792     else /*sugarCrit*/
    1793     {
    1794       /*
    1795       *suppose L[j] == (s,r) and p/lcm(s,r)
    1796       *and lcm(s,r)#lcm(s,p) and lcm(s,r)#lcm(r,p)
    1797       *and in case the sugar is o.k. then L[j] can be canceled
    1798       */
    1799       for (j=strat->Ll; j>=0; j--)
    1800       {
    1801         if (pCompareChain(p,strat->L[j].p1,strat->L[j].p2,strat->L[j].lcm))
    1802         {
    1803           if ((pNext(strat->L[j].p) == strat->tail)||(pOrdSgn==1))
    1804           {
    1805             deleteInL(strat->L,&strat->Ll,j,strat);
    1806             strat->c3++;
    1807           }
    1808         }
    1809       }
    1810       /*
    1811       *this is GEBAUER-MOELLER:
    1812       *in B all elements with the same lcm except the "best"
    1813       *(i.e. the last one in B with this property) will be canceled
    1814       */
    1815       j = strat->Bl;
    1816       loop   /*cannot be changed into a for !!! */
    1817       {
    1818         if (j <= 0) break;
    1819         for(i=j-1; i>=0; i--)
    1820         {
    1821           if (pLmEqual(strat->B[j].lcm,strat->B[i].lcm))
    1822           {
    1823             strat->c3++;
    1824             deleteInL(strat->B,&strat->Bl,i,strat);
    1825             j--;
    1826           }
    1827         }
    1828         j--;
    1829       }
    1830     }
    1831     /*
    1832     *the elements of B enter L/their order with respect to B is kept
    1833     *j = posInL(L,j,B[i]) would permutate the order
    1834     *if once B is ordered different from L
    1835     *then one should use j = posInL(L,Ll,B[i])
    1836     */
    1837     j = strat->Ll+1;
    1838     for (i=strat->Bl; i>=0; i--)
    1839     {
    1840       j = strat->posInL(strat->L,j-1,&(strat->B[i]),strat);
    1841       enterL(&strat->L,&strat->Ll,&strat->Lmax,strat->B[i],j);
    1842     }
    1843     strat->Bl = -1;
    1844   }
    1845   else /* Gebauer or fromT */
    1846   {
    1847     for (j=strat->Ll; j>=0; j--)
     1814  assume(!(strat->Gebauer || strat->fromT));
     1815  for (j=strat->Ll; j>=0; j--)
     1816  {
     1817    if (nGreater(pGetCoeff(strat->L[j].lcm), pGetCoeff(p)))
    18481818    {
    18491819      if (pCompareChain(p,strat->L[j].p1,strat->L[j].p2,strat->L[j].lcm))
    18501820      {
    1851         if ((pNext(strat->L[j].p) == strat->tail)||(pOrdSgn==1))
     1821        if ((pNext(strat->L[j].p) == strat->tail) || (pOrdSgn==1))
    18521822        {
    18531823          deleteInL(strat->L,&strat->Ll,j,strat);
    18541824          strat->c3++;
    1855         }
    1856       }
    1857     }
    1858     /*
    1859     *this is our MODIFICATION of GEBAUER-MOELLER:
    1860     *First the elements of B enter L,
    1861     *then we fix a lcm and the "best" element in L
    1862     *(i.e the last in L with this lcm and of type (s,p))
    1863     *and cancel all the other elements of type (r,p) with this lcm
    1864     *except the case the element (s,r) has also the same lcm
    1865     *and is on the worst position with respect to (s,p) and (r,p)
    1866     */
    1867     /*
    1868     *B enters to L/their order with respect to B is permutated for elements
    1869     *B[i].p with the same leading term
    1870     */
    1871     j = strat->Ll;
    1872     for (i=strat->Bl; i>=0; i--)
    1873     {
    1874       j = strat->posInL(strat->L,j,&(strat->B[i]),strat);
    1875       enterL(&strat->L,&strat->Ll,&strat->Lmax,strat->B[i],j);
    1876     }
    1877     strat->Bl = -1;
    1878     j = strat->Ll;
    1879     loop  /*cannot be changed into a for !!! */
    1880     {
    1881       if (j <= 0)
    1882       {
    1883         /*now L[0] cannot be canceled any more and the tail can be removed*/
    1884         if (strat->L[0].p2 == strat->tail) strat->L[0].p2 = p;
    1885         break;
    1886       }
    1887       if (strat->L[j].p2 == p)
    1888       {
    1889         i = j-1;
    1890         loop
    1891         {
    1892           if (i < 0)  break;
    1893           if ((strat->L[i].p2 == p) && pLmEqual(strat->L[j].lcm,strat->L[i].lcm))
     1825          Print("|UL|");
     1826        }
     1827      }
     1828    }
     1829  }
     1830  /*
     1831  *this is our MODIFICATION of GEBAUER-MOELLER:
     1832  *First the elements of B enter L,
     1833  *then we fix a lcm and the "best" element in L
     1834  *(i.e the last in L with this lcm and of type (s,p))
     1835  *and cancel all the other elements of type (r,p) with this lcm
     1836  *except the case the element (s,r) has also the same lcm
     1837  *and is on the worst position with respect to (s,p) and (r,p)
     1838  */
     1839  /*
     1840  *B enters to L/their order with respect to B is permutated for elements
     1841  *B[i].p with the same leading term
     1842  */
     1843  j = strat->Ll;
     1844  for (i=strat->Bl; i>=0; i--)
     1845  {
     1846    j = strat->posInL(strat->L,j,&(strat->B[i]),strat);
     1847    enterL(&strat->L,&strat->Ll,&strat->Lmax,strat->B[i],j);
     1848  }
     1849  strat->Bl = -1;
     1850  j = strat->Ll;
     1851  loop  /*cannot be changed into a for !!! */
     1852  {
     1853    if (j <= 0)
     1854    {
     1855      /*now L[0] cannot be canceled any more and the tail can be removed*/
     1856      if (strat->L[0].p2 == strat->tail) strat->L[0].p2 = p;
     1857      break;
     1858    }
     1859    if (strat->L[j].p2 == p) // Was the element added from B?
     1860    {
     1861      i = j-1;
     1862      loop
     1863      {
     1864        if (i < 0)  break;
     1865        // Element is from B and has the same lcm as L[j]
     1866        if ((strat->L[i].p2 == p) && pLmEqual(strat->L[j].lcm,strat->L[i].lcm)
     1867#ifdef HAVE_RING2TOM
     1868          && nGreater(pGetCoeff(strat->L[j].lcm), pGetCoeff(strat->L[i].lcm))
     1869#endif
     1870        )
     1871        {
     1872          /*L[i] could be canceled but we search for a better one to cancel*/
     1873          strat->c3++;
     1874          Print("|EP|");
     1875          if (isInPairsetL(i-1,strat->L[j].p1,strat->L[i].p1,&l,strat)
     1876          && (pNext(strat->L[l].p) == strat->tail)
     1877          && (!pLmEqual(strat->L[i].p,strat->L[l].p))
     1878#ifdef HAVE_RING2TOM
     1879//        && 1 == 0
     1880#endif
     1881          && pDivisibleBy(p,strat->L[l].lcm))
    18941882          {
    1895             /*L[i] could be canceled but we search for a better one to cancel*/
    1896             strat->c3++;
    1897             if (isInPairsetL(i-1,strat->L[j].p1,strat->L[i].p1,&l,strat)
    1898             && (pNext(strat->L[l].p) == strat->tail)
    1899             && (!pLmEqual(strat->L[i].p,strat->L[l].p))
    1900             && pDivisibleBy(p,strat->L[l].lcm))
    1901             {
    1902               /*
    1903               *"NOT equal(...)" because in case of "equal" the element L[l]
    1904               *is "older" and has to be from theoretical point of view behind
    1905               *L[i], but we do not want to reorder L
    1906               */
    1907               strat->L[i].p2 = strat->tail;
    1908               /*
    1909               *L[l] will be canceled, we cannot cancel L[i] later on,
    1910               *so we mark it with "tail"
    1911               */
    1912               deleteInL(strat->L,&strat->Ll,l,strat);
    1913               i--;
    1914             }
    1915             else
    1916             {
    1917               deleteInL(strat->L,&strat->Ll,i,strat);
    1918             }
    1919             j--;
     1883            /*
     1884            *"NOT equal(...)" because in case of "equal" the element L[l]
     1885            *is "older" and has to be from theoretical point of view behind
     1886            *L[i], but we do not want to reorder L
     1887            */
     1888            strat->L[i].p2 = strat->tail;
     1889            /*
     1890            *L[l] will be canceled, we cannot cancel L[i] later on,
     1891            *so we mark it with "tail"
     1892            */
     1893            deleteInL(strat->L,&strat->Ll,l,strat);
     1894            i--;
    19201895          }
    1921           i--;
    1922         }
    1923       }
    1924       else if (strat->L[j].p2 == strat->tail)
    1925       {
    1926         /*now L[j] cannot be canceled any more and the tail can be removed*/
    1927         strat->L[j].p2 = p;
    1928       }
    1929       j--;
    1930     }
     1896          else
     1897          {
     1898            deleteInL(strat->L,&strat->Ll,i,strat);
     1899          }
     1900          j--;
     1901        }
     1902        i--;
     1903      }
     1904    }
     1905    else if (strat->L[j].p2 == strat->tail)
     1906    {
     1907      /*now L[j] cannot be canceled any more and the tail can be removed*/
     1908      strat->L[j].p2 = p;
     1909    }
     1910    j--;
    19311911  }
    19321912}
    … …  
    19861966    }
    19871967
    1988     if (new_pair) chainCrit(h,ecart,strat);
     1968    if (new_pair) chainCritRing(h,ecart,strat);
    19891969
    19901970  }
    … …  
    45404520  }
    45414521#endif
     4522#ifdef HAVE_RING2TOM
     4523  // Coefficient ring?
     4524  if (currRing->cring == 1)
     4525  {
     4526    strat->sugarCrit = FALSE;
     4527    strat->Gebauer = FALSE ;
     4528    strat->honey = FALSE;
     4529  }
     4530#endif
    45424531  if (TEST_OPT_DEBUG)
    45434532  {

  • kernel/polys.cc

    r30f22c ra2466f  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: polys.cc,v 1.8 2006-03-20 20:33:57 wienand Exp $ */
     4/* $Id: polys.cc,v 1.9 2006-06-12 00:07:11 wienand Exp $ */
    55
    66/*
    … …  
    921921}
    922922
     923/* Returns TRUE if
     924     * LM(p) | LM(lcm)
     925     * LC(p) | LC(lcm) only if ring
     926     * Exists i, j:
     927         * LE(p, i)  != LE(lcm, i)
     928         * LE(p1, i) != LE(lcm, i)   ==> LCM(p1, p) != lcm
     929         * LE(p, j)  != LE(lcm, j)
     930         * LE(p2, j) != LE(lcm, j)   ==> LCM(p2, p) != lcm
     931*/
    923932BOOLEAN pCompareChain (poly p,poly p1,poly p2,poly lcm)
    924933{
    … …  
    926935
    927936  if (lcm==NULL) return FALSE;
    928   #ifdef HAVE_RING2TOM 
     937  #ifdef HAVE_RING2TOM
    929938  // In coefficient rings, the coefficient plays a role in chain crit TODO
    930939  if (currRing->cring == 1 && !pLmDivisibleByNoComp(p, lcm)) return FALSE;

  • kernel/ringgb.cc

    r30f22c ra2466f  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: ringgb.cc,v 1.10 2006-06-09 23:17:04 wienand Exp $ */
     4/* $Id: ringgb.cc,v 1.11 2006-06-12 00:07:12 wienand Exp $ */
    55/*
    66* ABSTRACT: ringgb interface
    … …  
    192192}
    193193
    194 int testGB(ideal GI) {
     194int testGB(ideal I, ideal GI) {
    195195  poly f, g, h;
    196196  int i = 0;
    197197  int j = 0;
    198   for (i = 0; i < IDELEMS(GI) - 1; i++) {
     198  for (i = 0; i < IDELEMS(I); i++) {
     199    if (ringNF(I->m[i], GI, currRing) != NULL) {
     200      Print("Not reduced to zero from I: ");
     201      wrp(I->m[i]);
     202      Print(" --> ");
     203      wrp(ringNF(I->m[i], GI, currRing));
     204      PrintLn();
     205      return(0);
     206    }
     207    pDelete(&h);
     208  }
     209  Print("I");
     210  for (i = 0; i < IDELEMS(GI); i++) {
    199211    Print("-");
    200212    for (j = i + 1; j < IDELEMS(GI); j++) {
    … …  
    203215      h = plain_spoly(f, g);
    204216      if (ringNF(h, GI, currRing) != NULL) {
     217        Print("spoly(");
    205218        wrp(GI->m[i]);
    206         PrintLn();
     219        Print(", ");
    207220        wrp(GI->m[j]);
    208         PrintLn();
     221        Print(") = ");
    209222        wrp(h);
    210         PrintLn();
     223        Print(" --> ");
    211224        wrp(ringNF(h, GI, currRing));
    212225        PrintLn();

  • kernel/ringgb.h

    r30f22c ra2466f  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: ringgb.h,v 1.3 2006-06-08 21:56:54 wienand Exp $ */
     4/* $Id: ringgb.h,v 1.4 2006-06-12 00:07:12 wienand Exp $ */
    55/*
    66* ABSTRACT: ringgb interface
    … …  
    1515poly ringNF(poly f, ideal G, ring r);
    1616poly plain_spoly(poly f, poly g);
    17 int testGB(ideal GI);
     17int testGB(ideal I, ideal GI);
    1818
    1919#endif
Note: See TracChangeset for help on using the changeset viewer.