Changeset 36605f in git for kernel/kstd1.cc


Ignore:
Timestamp:
Sep 16, 2008, 2:35:32 PM (15 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
Children:
e7c6b22d3f7122e485ba322d4f68e0891f97fbd6
Parents:
e259fe4beb4f8b56640f55874fdf60e4a99aaa9b
Message:
kInterRed, kInterRedBba, kInterRedOld


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

Legend:

Unmodified
Added
Removed

  • kernel/kstd1.cc

    re259fe r36605f  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: kstd1.cc,v 1.38 2008-09-10 16:41:12 Singular Exp $ */
     4/* $Id: kstd1.cc,v 1.39 2008-09-16 12:35:32 Singular Exp $ */
    55/*
    66* ABSTRACT:
    … …  
    17351735#ifdef HAVE_SHIFTBBA
    17361736ideal kStdShift(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
    1737                 int newIdeal, intvec *vw, int uptodeg, int lV)
     1737                int newIdeal, intvec *vw, int uptodeg, int lV)
    17381738{
    17391739  ideal r;
    … …  
    19661966
    19671967  poly pp = p;
    1968  
     1968
    19691969#ifdef HAVE_PLURAL
    19701970  if(rIsSCA(currRing))
    … …  
    19781978  }
    19791979#endif
    1980  
     1980
    19811981  poly res;
    19821982
    … …  
    19911991    p_Delete(&pp, currRing);
    19921992#endif
    1993  
     1993
    19941994  return res;
    19951995}
    … …  
    20292029#endif
    20302030
    2031  
    20322031  return res;
    20332032}
    … …  
    20362035*interreduces F
    20372036*/
    2038 #if 0
    2039 // new version
    2040 ideal kInterRed (ideal F, ideal Q)
    2041 {
    2042   int   srmax,lrmax, red_result = 1;
    2043   int   olddeg,reduc,j;
    2044   BOOLEAN need_update=FALSE;
    2045 
    2046   kStrategy strat = new skStrategy;
    2047   strat->kHEdgeFound = ppNoether != NULL;
    2048   strat->kNoether=pCopy(ppNoether);
    2049   strat->ak = idRankFreeModule(F);
    2050   initBuchMoraCrit(strat);
    2051   initBuchMoraPos(strat);
    2052   strat->NotUsedAxis = (BOOLEAN *)omAlloc((pVariables+1)*sizeof(BOOLEAN));
    2053   for (j=pVariables; j>0; j--) strat->NotUsedAxis[j] = TRUE;
    2054   strat->enterS      = enterSBba;
    2055   strat->posInT      = posInT17;
    2056   strat->initEcart   = initEcartNormal;
    2057   strat->sl          = -1;
    2058   strat->tl          = -1;
    2059   strat->Ll          = -1;
    2060   strat->tmax        = setmaxT;
    2061   strat->Lmax        = setmaxL;
    2062   strat->T           = initT();
    2063   strat->R           = initR();
    2064   strat->L           = initL();
    2065   strat->sevT        = initsevT();
    2066   strat->red         = redLazy;
    2067 #ifdef HAVE_RINGS  //TODO Oliver
    2068   if (rField_is_Ring(currRing)) {
    2069     strat->red = redRing;
    2070   }
    2071 #endif
    2072   strat->tailRing    = currRing;
    2073   if (pOrdSgn == -1)
    2074     strat->honey = TRUE;
    2075   initSL(F,Q,strat);
    2076   for(j=strat->Ll; j>=0; j--)
    2077     strat->L[j].tailRing=currRing;
    2078   if (TEST_OPT_REDSB)
    2079     strat->noTailReduction=FALSE;
    2080 
    2081   srmax = strat->sl;
    2082   reduc = olddeg = lrmax = 0;
    2083 
    2084 #ifndef NO_BUCKETS
    2085   if (!TEST_OPT_NOT_BUCKETS)
    2086     strat->use_buckets = 1;
    2087 #endif
    2088 
    2089   // strat->posInT = posInT_pLength;
    2090   kTest_TS(strat);
    2091 
    2092   /* compute------------------------------------------------------- */
    2093   while (strat->Ll >= 0)
    2094   {
    2095     if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
    2096     #ifdef KDEBUG
    2097     if (TEST_OPT_DEBUG) messageSets(strat);
    2098     #endif
    2099     if (strat->Ll== 0) strat->interpt=TRUE;
    2100     /* picks the last element from the lazyset L */
    2101     strat->P = strat->L[strat->Ll];
    2102     strat->Ll--;
    2103 
    2104     // for input polys, prepare reduction
    2105     strat->P.PrepareRed(strat->use_buckets);
    2106 
    2107     if (strat->P.p == NULL && strat->P.t_p == NULL)
    2108     {
    2109       red_result = 0;
    2110     }
    2111     else
    2112     {
    2113       if (TEST_OPT_PROT)
    2114         message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
    2115                 &olddeg,&reduc,strat, red_result);
    2116 
    2117       /* reduction of the element choosen from L */
    2118       red_result = strat->red(&strat->P,strat);
    2119     }
    2120 
    2121     // reduction to non-zero new poly
    2122     if (red_result == 1)
    2123     {
    2124       /* statistic */
    2125       if (TEST_OPT_PROT) PrintS("s");
    2126 
    2127       // get the polynomial (canonicalize bucket, make sure P.p is set)
    2128       strat->P.GetP(strat->lmBin);
    2129 
    2130       int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
    2131 
    2132       // reduce the tail and normalize poly
    2133       if (TEST_OPT_INTSTRATEGY)
    2134       {
    2135         strat->P.pCleardenom();
    2136         if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
    2137         {
    2138           strat->P.p = redtailBba(&(strat->P),pos-1,strat, FALSE);
    2139           strat->P.pCleardenom();
    2140         }
    2141       }
    2142       else
    2143       {
    2144         strat->P.pNorm();
    2145         if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
    2146           strat->P.p = redtailBba(&(strat->P),pos-1,strat, FALSE);
    2147       }
    2148 
    2149 #ifdef KDEBUG
    2150       if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
    2151 #endif
    2152 
    2153       // enter into S, L, and T
    2154       enterT(strat->P, strat);
    2155       // posInS only depends on the leading term
    2156       strat->enterS(strat->P, pos, strat, strat->tl);
    2157       if (pos<strat->sl)
    2158       {
    2159         need_update=TRUE;
    2160 #if 0
    2161         LObject h;
    2162         for(j=strat->sl;j>pos;j--)
    2163         {
    2164           if (TEST_OPT_PROT) { PrintS("+"); mflush(); }
    2165           memset(&h, 0, sizeof(h));
    2166           h.p=strat->S[j];
    2167           int i;
    2168           for(i=strat->tl;i>=0;i--)
    2169           {
    2170             if (pLmCmp(h.p,strat->T[i].p)==0)
    2171             {
    2172               if (i < strat->tl)
    2173               {
    2174 #ifdef ENTER_USE_MEMMOVE
    2175                 memmove(&(strat->T[i]), &(strat->T[i+1]),
    2176                    (strat->tl-i)*sizeof(TObject));
    2177                 memmove(&(strat->sevT[i]), &(strat->sevT[i+1]),
    2178                    (strat->tl-i)*sizeof(unsigned long));
    2179 #endif
    2180                 for (int l=i; l<strat->tl; l++)
    2181                 {
    2182 #ifndef ENTER_USE_MEMMOVE
    2183                   strat->T[l] = strat->T[l+1];
    2184                   strat->sevT[l] = strat->sevT[l+1];
    2185 #endif
    2186                   strat->R[strat->T[l].i_r] = &(strat->T[l]);
    2187                 }
    2188               }
    2189               strat->tl--;
    2190               break;
    2191             }
    2192           }
    2193           strat->S[j]=NULL;
    2194           strat->sl--;
    2195           if (TEST_OPT_INTSTRATEGY)
    2196           {
    2197             //pContent(h.p);
    2198             h.pCleardenom(); // also does a pContent
    2199           }
    2200           else
    2201           {
    2202             h.pNorm();
    2203           }
    2204           strat->initEcart(&h);
    2205                     if (strat->Ll==-1)
    2206             pos =0;
    2207           else
    2208             pos = strat->posInL(strat->L,strat->Ll,&h,strat);
    2209           h.sev = pGetShortExpVector(h.p);
    2210           enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
    2211         }
    2212 #endif
    2213       }
    2214       if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
    2215       if (strat->sl>srmax) srmax = strat->sl;
    2216     }
    2217 #ifdef KDEBUG
    2218     memset(&(strat->P), 0, sizeof(strat->P));
    2219 #endif
    2220     kTest_TS(strat);
    2221   }
    2222 #ifdef KDEBUG
    2223   if (TEST_OPT_DEBUG) messageSets(strat);
    2224 #endif
    2225   /* complete reduction of the standard basis--------- */
    2226   if (TEST_OPT_REDSB)
    2227   {
    2228     completeReduce(strat);
    2229     if (strat->completeReduce_retry)
    2230     {
    2231       // completeReduce needed larger exponents, retry
    2232       // to reduce with S (instead of T)
    2233       // and in currRing (instead of strat->tailRing)
    2234       cleanT(strat);strat->tailRing=currRing;
    2235       int i;
    2236       for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
    2237       completeReduce(strat);
    2238     }
    2239   }
    2240   else if (TEST_OPT_PROT) PrintLn();
    2241 
    2242   /* release temp data-------------------------------- */
    2243   if (TEST_OPT_PROT) messageStat(srmax,lrmax,0,strat);
    2244   if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
    2245   ideal shdl=strat->Shdl;
    2246   idSkipZeroes(shdl);
    2247   pDelete(&strat->kHEdge);
    2248   omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
    2249   omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
    2250   omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
    2251   omFreeSize((ADDRESS)strat->NotUsedAxis,(pVariables+1)*sizeof(BOOLEAN));
    2252   omFreeSize((ADDRESS)strat->L,(strat->Lmax)*sizeof(LObject));
    2253   omfree(strat->sevT);
    2254   omfree(strat->S_2_R);
    2255   omfree(strat->R);
    2256 
    2257   if (strat->fromQ)
    2258   {
    2259     for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
    2260     {
    2261       if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
    2262     }
    2263     omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
    2264     strat->fromQ=NULL;
    2265   }
    2266   delete(strat);
    2267 #if 0
    2268   if (need_update)
    2269   {
    2270     ideal res=kInterRed(shdl,Q);
    2271     idDelete(&shdl);
    2272     shdl=res;
    2273   }
    2274 #endif
    2275   return shdl;
    2276 }
    2277 #else
    22782037// old version
    2279 ideal kInterRed (ideal F, ideal Q)
     2038ideal kInterRedOld (ideal F, ideal Q)
    22802039{
    22812040  int j;
    … …  
    23692128  return shdl;
    23702129}
    2371 #endif
     2130// new version
     2131ideal kInterRedBba (ideal F, ideal Q, int &need_retry)
     2132{
     2133  need_retry=0;
     2134  int   srmax,lrmax, red_result = 1;
     2135  int   olddeg,reduc;
     2136  BOOLEAN withT = FALSE;
     2137  BOOLEAN b=pLexOrder;
     2138  BOOLEAN toReset=FALSE;
     2139  kStrategy strat=new skStrategy;
     2140  tHomog h;
     2141  intvec * w=NULL;
     2142
     2143  if (rField_has_simple_inverse())
     2144    strat->LazyPass=20;
     2145  else
     2146    strat->LazyPass=2;
     2147  strat->LazyDegree = 1;
     2148  strat->ak = idRankFreeModule(F);
     2149  strat->syzComp = strat->ak;
     2150  strat->kModW=kModW=NULL;
     2151  strat->kHomW=kHomW=NULL;
     2152  if (strat->ak == 0)
     2153  {
     2154    h = (tHomog)idHomIdeal(F,Q);
     2155    w=NULL;
     2156  }
     2157  else if (!TEST_OPT_DEGBOUND)
     2158  {
     2159    h = (tHomog)idHomModule(F,Q,&w);
     2160  }
     2161  pLexOrder=b;
     2162  if (h==isHomog)
     2163  {
     2164    if (strat->ak > 0 && (w!=NULL) && (w!=NULL))
     2165    {
     2166      strat->kModW = kModW = w;
     2167      pFDegOld = pFDeg;
     2168      pLDegOld = pLDeg;
     2169      pSetDegProcs(kModDeg);
     2170      toReset = TRUE;
     2171    }
     2172    pLexOrder = TRUE;
     2173    strat->LazyPass*=2;
     2174  }
     2175  strat->homog=h;
     2176#ifdef KDEBUG
     2177  idTest(F);
     2178#endif
     2179
     2180  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
     2181  initBuchMoraPos(strat);
     2182  initBba(F,strat);
     2183  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
     2184  strat->posInL=posInL0; /* ord according pComp */
     2185
     2186  /*Shdl=*/initBuchMora(F, Q,strat);
     2187  srmax = strat->sl;
     2188  reduc = olddeg = lrmax = 0;
     2189
     2190#ifndef NO_BUCKETS
     2191  if (!TEST_OPT_NOT_BUCKETS)
     2192    strat->use_buckets = 1;
     2193#endif
     2194
     2195  // redtailBBa against T for inhomogenous input
     2196  if (!K_TEST_OPT_OLDSTD)
     2197    withT = ! strat->homog;
     2198
     2199  // strat->posInT = posInT_pLength;
     2200  kTest_TS(strat);
     2201
     2202#ifdef HAVE_TAIL_RING
     2203  kStratInitChangeTailRing(strat);
     2204#endif
     2205
     2206  /* compute------------------------------------------------------- */
     2207  while (strat->Ll >= 0)
     2208  {
     2209    if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
     2210    #ifdef KDEBUG
     2211      #ifdef HAVE_RINGS
     2212        if (TEST_OPT_DEBUG) PrintS("--- next step ---\n");
     2213      #endif
     2214      if (TEST_OPT_DEBUG) messageSets(strat);
     2215    #endif
     2216    if (strat->Ll== 0) strat->interpt=TRUE;
     2217    /* picks the last element from the lazyset L */
     2218    strat->P = strat->L[strat->Ll];
     2219    strat->Ll--;
     2220
     2221    if (strat->P.p1 == NULL)
     2222    {
     2223      // for input polys, prepare reduction
     2224      strat->P.PrepareRed(strat->use_buckets);
     2225    }
     2226
     2227    if (strat->P.p == NULL && strat->P.t_p == NULL)
     2228    {
     2229      red_result = 0;
     2230    }
     2231    else
     2232    {
     2233      if (TEST_OPT_PROT)
     2234        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
     2235                &olddeg,&reduc,strat, red_result);
     2236
     2237      /* reduction of the element choosen from L */
     2238      red_result = strat->red(&strat->P,strat);
     2239    }
     2240
     2241    // reduction to non-zero new poly
     2242    if (red_result == 1)
     2243    {
     2244      /* statistic */
     2245      if (TEST_OPT_PROT) PrintS("s");
     2246
     2247      // get the polynomial (canonicalize bucket, make sure P.p is set)
     2248      strat->P.GetP(strat->lmBin);
     2249
     2250      int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
     2251
     2252      // reduce the tail and normalize poly
     2253      // in the ring case we cannot expect LC(f) = 1,
     2254      // therefore we call pContent instead of pNorm
     2255      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
     2256      {
     2257        strat->P.pCleardenom();
     2258        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
     2259        {
     2260          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
     2261          strat->P.pCleardenom();
     2262        }
     2263      }
     2264      else
     2265      {
     2266        strat->P.pNorm();
     2267        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
     2268          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
     2269      }
     2270
     2271#ifdef KDEBUG
     2272      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
     2273#endif
     2274
     2275      // enter into S, L, and T
     2276      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
     2277        enterT(strat->P, strat);
     2278      // posInS only depends on the leading term
     2279      strat->enterS(strat->P, pos, strat, strat->tl);
     2280
     2281      if (strat->P.lcm!=NULL)
     2282#ifdef HAVE_RINGS
     2283        pLmDelete(strat->P.lcm);
     2284#else
     2285        pLmFree(strat->P.lcm);
     2286#endif
     2287      if (strat->sl>srmax) srmax = strat->sl;
     2288      if (pos<strat->sl)
     2289        need_retry++;
     2290    }
     2291
     2292#ifdef KDEBUG
     2293    memset(&(strat->P), 0, sizeof(strat->P));
     2294#endif
     2295    kTest_TS(strat);
     2296  }
     2297#ifdef KDEBUG
     2298  //if (TEST_OPT_DEBUG) messageSets(strat);
     2299#endif
     2300  /* complete reduction of the standard basis--------- */
     2301
     2302  //if (TEST_OPT_REDSB)
     2303  if(need_retry==0)
     2304  {
     2305    completeReduce(strat);
     2306#ifdef HAVE_TAIL_RING
     2307    if (strat->completeReduce_retry)
     2308    {
     2309      // completeReduce needed larger exponents, retry
     2310      // to reduce with S (instead of T)
     2311      // and in currRing (instead of strat->tailRing)
     2312      cleanT(strat);strat->tailRing=currRing;
     2313      int i;
     2314      for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
     2315      completeReduce(strat);
     2316    }
     2317#endif
     2318  }
     2319  else if (TEST_OPT_PROT) PrintLn();
     2320
     2321  /* release temp data-------------------------------- */
     2322  exitBuchMora(strat);
     2323  if (TEST_OPT_WEIGHTM)
     2324  {
     2325    pRestoreDegProcs(pFDegOld, pLDegOld);
     2326    if (ecartWeights)
     2327    {
     2328      omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
     2329      ecartWeights=NULL;
     2330    }
     2331  }
     2332  //if (TEST_OPT_PROT) messageStat(srmax,lrmax,0/*hilbcount*/,strat);
     2333  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
     2334  ideal res=strat->Shdl;
     2335  strat->Shdl=NULL;
     2336  delete strat;
     2337  if (w!=NULL) delete w;
     2338  return res;
     2339}
     2340ideal kInterRed (ideal F, ideal Q)
     2341{
     2342#ifdef HAVE_PLURAL
     2343  if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
     2344#endif
     2345  if(pOrdSgn==-1) return kInterRedOld(F,Q);
     2346
     2347  int need_retry;
     2348  int counter=3;
     2349  int elems=idElem(F);
     2350  ideal res=kInterRedBba(F,Q,need_retry);
     2351  while (need_retry && (counter>0))
     2352  {
     2353    ideal res1=kInterRedBba(res,Q,need_retry);
     2354    int new_elems=idElem(res1);
     2355    counter -= (new_elems >= elems);
     2356    elems = new_elems;
     2357    idDelete(&res);
     2358    res = res1;
     2359  }
     2360  idSkipZeroes(res);
     2361  return res;
     2362}
     2363
    23722364
    23732365// returns TRUE if mora should use buckets, false otherwise
Note: See TracChangeset for help on using the changeset viewer.