Changeset fbc7cb in git


Ignore:
Timestamp:
Nov 28, 2013, 8:17:04 AM (10 years ago)
Author:
Christian Eder
Branches:
(u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
Children:
f1cef21d1357296b505525dc298415759bdb20c8
Parents:
c91ffe336985180edd91ef17bf401793443ccb4d
git-author:
Christian Eder <ederc@mathematik.uni-kl.de>2013-11-28 08:17:04+01:00
git-committer:
Christian Eder <ederc@mathematik.uni-kl.de>2013-12-12 13:51:25+01:00
Message:
moves sba tail reduction stuff to kstd2
Location:
kernel
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • kernel/kInline.h

    rc91ffe3 rfbc7cb  
    10741074}
    10751075
    1076 KINLINE int ksReducePolyTailSig(LObject* PR, TObject* PW, LObject* Red)
    1077 {
    1078   BOOLEAN ret;
    1079   number coef;
    1080 
    1081   assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
    1082   Red->HeadNormalize();
    1083   /*
    1084   printf("------------------------\n");
    1085   pWrite(Red->GetLmCurrRing());
    1086   */
    1087   ret = ksReducePolySig(Red, PW, 1, NULL, &coef);
    1088   if (!ret)
    1089   {
    1090     if (! n_IsOne(coef, currRing->cf))
    1091     {
    1092       PR->Mult_nn(coef);
    1093       // HANNES: mark for Normalize
    1094     }
    1095     n_Delete(&coef, currRing->cf);
    1096   }
    1097   return ret;
    1098 }
    1099 
    11001076/***************************************************************
    11011077 *
  • kernel/kstd2.cc

    rc91ffe3 rfbc7cb  
    529529    }
    530530  }
     531}
     532
     533KINLINE int ksReducePolyTailSig(LObject* PR, TObject* PW, LObject* Red)
     534{
     535  BOOLEAN ret;
     536  number coef;
     537
     538  assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
     539  Red->HeadNormalize();
     540  /*
     541  printf("------------------------\n");
     542  pWrite(Red->GetLmCurrRing());
     543  */
     544  ret = ksReducePolySig(Red, PW, 1, NULL, &coef);
     545
     546
     547  if (!ret)
     548  {
     549    if (! n_IsOne(coef, currRing->cf))
     550    {
     551      PR->Mult_nn(coef);
     552      // HANNES: mark for Normalize
     553    }
     554    n_Delete(&coef, currRing->cf);
     555  }
     556  return ret;
    531557}
    532558
     
    706732    }
    707733  }
     734}
     735
     736// tail reduction for SBA
     737poly redtailSba (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
     738{
     739#define REDTAIL_CANONICALIZE 100
     740  strat->redTailChange=FALSE;
     741  if (strat->noTailReduction) return L->GetLmCurrRing();
     742  poly h, p;
     743  p = h = L->GetLmTailRing();
     744  if ((h==NULL) || (pNext(h)==NULL))
     745    return L->GetLmCurrRing();
     746
     747  TObject* With;
     748  // placeholder in case strat->tl < 0
     749  TObject  With_s(strat->tailRing);
     750
     751  LObject Ln(pNext(h), strat->tailRing);
     752  Ln.sig      = L->sig;
     753  Ln.sevSig   = L->sevSig;
     754  Ln.pLength  = L->GetpLength() - 1;
     755
     756  pNext(h) = NULL;
     757  if (L->p != NULL) pNext(L->p) = NULL;
     758  L->pLength = 1;
     759
     760  Ln.PrepareRed(strat->use_buckets);
     761
     762  int cnt=REDTAIL_CANONICALIZE;
     763  while(!Ln.IsNull())
     764  {
     765    loop
     766    {
     767      Ln.SetShortExpVector();
     768      if (withT)
     769      {
     770        int j;
     771        j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, &Ln);
     772        if (j < 0) break;
     773        With = &(strat->T[j]);
     774      }
     775      else
     776      {
     777        With = kFindDivisibleByInS(strat, pos, &Ln, &With_s);
     778        if (With == NULL) break;
     779      }
     780      cnt--;
     781      if (cnt==0)
     782      {
     783        cnt=REDTAIL_CANONICALIZE;
     784        /*poly tmp=*/Ln.CanonicalizeP();
     785        if (normalize)
     786        {
     787          Ln.Normalize();
     788          //pNormalize(tmp);
     789          //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
     790        }
     791      }
     792      if (normalize && (!TEST_OPT_INTSTRATEGY) && (!nIsOne(pGetCoeff(With->p))))
     793      {
     794        With->pNorm();
     795      }
     796      strat->redTailChange=TRUE;
     797      int ret = ksReducePolyTailSig(L, With, &Ln);
     798#if SBA_PRINT_REDUCTION_STEPS
     799      if (ret != 3)
     800        sba_reduction_steps++;
     801#endif
     802#if SBA_PRINT_OPERATIONS
     803      if (ret != 3)
     804        sba_operations  +=  pLength(With->p);
     805#endif
     806      if (ret)
     807      {
     808        // reducing the tail would violate the exp bound
     809        //  set a flag and hope for a retry (in bba)
     810        strat->completeReduce_retry=TRUE;
     811        if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
     812        do
     813        {
     814          pNext(h) = Ln.LmExtractAndIter();
     815          pIter(h);
     816          L->pLength++;
     817        } while (!Ln.IsNull());
     818        goto all_done;
     819      }
     820      if (Ln.IsNull()) goto all_done;
     821      if (! withT) With_s.Init(currRing);
     822    }
     823    pNext(h) = Ln.LmExtractAndIter();
     824    pIter(h);
     825    pNormalize(h);
     826    L->pLength++;
     827  }
     828
     829  all_done:
     830  Ln.Delete();
     831  if (L->p != NULL) pNext(L->p) = pNext(p);
     832
     833  if (strat->redTailChange)
     834  {
     835    L->length = 0;
     836  }
     837
     838  //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
     839  //L->Normalize(); // HANNES: should have a test
     840  assume(kTest_L(L));
     841  return L->GetLmCurrRing();
    708842}
    709843
  • kernel/kutil.cc

    rc91ffe3 rfbc7cb  
    54695469      strat->redTailChange=TRUE;
    54705470      if (ksReducePolyTail(L, With, &Ln))
    5471       {
    5472         // reducing the tail would violate the exp bound
    5473         //  set a flag and hope for a retry (in bba)
    5474         strat->completeReduce_retry=TRUE;
    5475         if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
    5476         do
    5477         {
    5478           pNext(h) = Ln.LmExtractAndIter();
    5479           pIter(h);
    5480           L->pLength++;
    5481         } while (!Ln.IsNull());
    5482         goto all_done;
    5483       }
    5484       if (Ln.IsNull()) goto all_done;
    5485       if (! withT) With_s.Init(currRing);
    5486     }
    5487     pNext(h) = Ln.LmExtractAndIter();
    5488     pIter(h);
    5489     pNormalize(h);
    5490     L->pLength++;
    5491   }
    5492 
    5493   all_done:
    5494   Ln.Delete();
    5495   if (L->p != NULL) pNext(L->p) = pNext(p);
    5496 
    5497   if (strat->redTailChange)
    5498   {
    5499     L->length = 0;
    5500   }
    5501 
    5502   //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
    5503   //L->Normalize(); // HANNES: should have a test
    5504   assume(kTest_L(L));
    5505   return L->GetLmCurrRing();
    5506 }
    5507 
    5508 // tail reduction for SBA
    5509 poly redtailSba (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
    5510 {
    5511 #define REDTAIL_CANONICALIZE 100
    5512   strat->redTailChange=FALSE;
    5513   if (strat->noTailReduction) return L->GetLmCurrRing();
    5514   poly h, p;
    5515   p = h = L->GetLmTailRing();
    5516   if ((h==NULL) || (pNext(h)==NULL))
    5517     return L->GetLmCurrRing();
    5518 
    5519   TObject* With;
    5520   // placeholder in case strat->tl < 0
    5521   TObject  With_s(strat->tailRing);
    5522 
    5523   LObject Ln(pNext(h), strat->tailRing);
    5524   Ln.sig      = L->sig;
    5525   Ln.sevSig   = L->sevSig;
    5526   Ln.pLength  = L->GetpLength() - 1;
    5527 
    5528   pNext(h) = NULL;
    5529   if (L->p != NULL) pNext(L->p) = NULL;
    5530   L->pLength = 1;
    5531 
    5532   Ln.PrepareRed(strat->use_buckets);
    5533 
    5534   int cnt=REDTAIL_CANONICALIZE;
    5535   while(!Ln.IsNull())
    5536   {
    5537     loop
    5538     {
    5539       Ln.SetShortExpVector();
    5540       if (withT)
    5541       {
    5542         int j;
    5543         j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, &Ln);
    5544         if (j < 0) break;
    5545         With = &(strat->T[j]);
    5546       }
    5547       else
    5548       {
    5549         With = kFindDivisibleByInS(strat, pos, &Ln, &With_s);
    5550         if (With == NULL) break;
    5551       }
    5552       cnt--;
    5553       if (cnt==0)
    5554       {
    5555         cnt=REDTAIL_CANONICALIZE;
    5556         /*poly tmp=*/Ln.CanonicalizeP();
    5557         if (normalize)
    5558         {
    5559           Ln.Normalize();
    5560           //pNormalize(tmp);
    5561           //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
    5562         }
    5563       }
    5564       if (normalize && (!TEST_OPT_INTSTRATEGY) && (!nIsOne(pGetCoeff(With->p))))
    5565       {
    5566         With->pNorm();
    5567       }
    5568       strat->redTailChange=TRUE;
    5569       if (ksReducePolyTailSig(L, With, &Ln))
    55705471      {
    55715472        // reducing the tail would violate the exp bound
Note: See TracChangeset for help on using the changeset viewer.