Changeset 418bd6 in git


Ignore:
Timestamp:
Oct 1, 2009, 3:40:16 PM (15 years ago)
Author:
Christian Eder
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'b52fc4b2495505785981d640dcf7eb3e456778ef')
Children:
963eebd7c227d74888d6c990014a2db02a856401
Parents:
1d9469b7feae9ba3731cc5bd89f2a2a7f1611efd
Message:
added idea for termination of F5: split critical pairs in "useful" and "useless"
ones, check later on if there are "useful" ones left, else terminate the algorithm.


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

Legend:

Unmodified
Added
Removed
  • kernel/f5data.h

    r1d9469 r418bd6  
    33*  Computer Algebra System SINGULAR     *
    44****************************************/
    5 /* $Id: f5data.h,v 1.14 2009-08-31 13:55:46 ederc Exp $ */
     5/* $Id: f5data.h,v 1.15 2009-10-01 13:40:16 ederc Exp $ */
    66/*
    77* ABSTRACT: labeled polynomial interface
     
    124124        LPolyOld*  lp2;            // second labeled poly
    125125        RuleOld*   testedRuleOld;     // already tested by RuleOlds up to lastRuleOldTested
     126        bool  del;
    126127    public:
    127         inline          CPairOld(long degree, poly term1, LPolyOld* LPolyOld1, poly term2, LPolyOld* LPolyOld2, RuleOld* r = NULL);
     128        inline          CPairOld(long degree, poly term1, LPolyOld* LPolyOld1, poly term2, LPolyOld* LPolyOld2, bool useless, RuleOld* r = NULL);
    128129        inline  long    getDeg();
    129130        inline  poly    getT1();
     
    139140        inline  poly    getLp2Term();
    140141        inline  int     getLp2Index();
     142        inline  bool    getDel();
    141143        inline  RuleOld*   getTestedRuleOld();
    142144        inline  void    setTestedRuleOld(RuleOld* r);
    143145};
    144146
    145 CPairOld::CPairOld(long degree, poly term1, LPolyOld* LPolyOld1, poly term2, LPolyOld* LPolyOld2, RuleOld* r) {
     147CPairOld::CPairOld(long degree, poly term1, LPolyOld* LPolyOld1, poly term2, LPolyOld* LPolyOld2, bool useless, RuleOld* r) {
    146148   deg              =   degree;
    147149   t1               =   term1;
     
    150152   lp2              =   LPolyOld2;
    151153   testedRuleOld       =   r;
     154   del              =   useless;
    152155}
    153156
     
    202205int CPairOld::getLp2Index() {
    203206    return lp2->getIndex();
     207}
     208
     209bool CPairOld::getDel() {
     210  return del;
    204211}
    205212
  • kernel/f5gb.cc

    r1d9469 r418bd6  
    3434int highestDegree       =   0;
    3535int degreeBound         =   0;
     36int numberUsefulPairs   =   0;
     37int numberUselessPairs  =   0;
    3638/*
    3739====================================================================
     
    152154        //startTimer();
    153155        //critPairs->print();
    154         computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
     156        if(numberUsefulPairs > 0) {
     157          Print("number of useful pairs:  %d\n",numberUsefulPairs);
     158          Print("number of useless pairs: %d\n\n",numberUselessPairs);
     159          computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
     160        }
     161        else {
     162          return gPrev;
     163        }
    155164        //timer4  =   getTimer();
    156165        //Print("SPOLS TIMER: %d\n",timer4);
     
    168177        //sPolyList->print();
    169178        //reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
     179        Print("BEFORE REDUCTION: \n");
     180        Print("number of useful pairs:  %d\n",numberUsefulPairs);
     181        Print("number of useless pairs: %d\n\n",numberUselessPairs);
    170182        newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination);
    171183        //timer3      =  getTimer();
     
    237249================================================================
    238250computes a list of critical pairs for the next reduction process
     251the first element is always "useful" thus the critical pair
     252computed is either "useful" or "useless" depending on the second
     253element which generates the critical pair.
    239254first element in gPrev is always the newest element which must
    240255build critical pairs with all other elements in gPrev
     
    268283        pSetCoeff(u2,nOne);
    269284        // testing both new labels by the F5 Criterion
     285        if(!temp->getDel()) {
     286          if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
     287            && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
     288            && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
     289              // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
     290              // label as first element in the CPairOld
     291              if(newElement->getIndex() == temp->getIndex() &&
     292              -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
     293                  CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
     294                                  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 0 , testedRuleOld);                   
     295                  critPairs->insert(cp);
     296                  // counting the number of useful pairs
     297                  numberUsefulPairs++;
     298              }
     299              else {
     300                  CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
     301                                  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 0, testedRuleOld);                   
     302                  critPairs->insert(cp);
     303                  // counting the number of useful pairs
     304                  numberUsefulPairs++;
     305              }
     306          }
     307        }
     308        else {
     309          if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
     310            && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
     311            && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
     312              // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
     313              // label as first element in the CPairOld
     314              if(newElement->getIndex() == temp->getIndex() &&
     315              -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
     316                  CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
     317                                  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);                   
     318                  critPairs->insert(cp);
     319                  numberUselessPairs++;
     320              }
     321              else {
     322                  CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
     323                                  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);                   
     324                  critPairs->insert(cp);
     325                  numberUselessPairs++;
     326              }
     327          }
     328        }
     329        temp    =   temp->getNext();
     330    }
     331}
     332
     333
     334
     335/*
     336================================================================
     337computes a list of critical pairs for the next reduction process
     338the first element is always "useless" thus the critical pair
     339computed is "useless".
     340first element in gPrev is always the newest element which must
     341build critical pairs with all other elements in gPrev
     342================================================================
     343*/
     344inline void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
     345    //Print("IN CRITPAIRS\n");
     346    // initialization for usage in pLcm()
     347    number nOne         =   nInit(1);
     348    LNode* newElement   =   gPrev->getLast();
     349    LNode* temp         =   gPrev->getFirst();
     350    poly u1             =   pOne();
     351    poly u2             =   pOne();
     352    poly lcm            =   pOne();
     353    poly t              =   pHead(newElement->getPoly());
     354    RuleOld* testedRuleOld    =   NULL;
     355    if(NULL != rules->getFirst()) {
     356        testedRuleOld  =   rules->getFirst()->getRuleOld();
     357    }
     358    // computation of critical pairs
     359    while( gPrev->getLast() != temp) {
     360        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
     361        pSetCoeff(lcm,nOne);
     362        // computing factors u2 for new labels
     363        u1 = pDivide(lcm,t);
     364        if(NULL == u1) {
     365            break;
     366        }
     367        pSetCoeff(u1,nOne);
     368        u2 = pDivide(lcm,pHead(temp->getPoly()));
     369        pSetCoeff(u2,nOne);
     370        // testing both new labels by the F5 Criterion
    270371        if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
    271372           && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
     
    276377            -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
    277378                CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
    278                                 temp->getLPolyOld(), u1, newElement->getLPolyOld(), testedRuleOld);                   
     379                                temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);                   
    279380                critPairs->insert(cp);
     381                numberUselessPairs++;
    280382            }
    281383            else {
    282384                CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
    283                                 newElement->getLPolyOld(), u2, temp->getLPolyOld(), testedRuleOld);                   
     385                                newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);                   
    284386                critPairs->insert(cp);
    285             }
    286         }
    287         else {
     387                numberUselessPairs++;
     388            }
    288389        }
    289390        temp    =   temp->getNext();
    290391    }
    291392}
    292 
    293 
    294 
    295 
    296393
    297394
     
    528625
    529626    while(NULL != temp) {
     627        // counting the number of useful pairs
     628        if(!temp->getDel()) {
     629          //Print("%d\n",numberUsefulPairs);
     630          numberUsefulPairs--;
     631        }
     632        else {
     633          numberUselessPairs--;
     634        }
    530635        //Print("JA\n");
    531636        // only if a new RuleOld was added since the last test in subalgorithm criticalPair()
     
    587692                        // data is saved in sPolyList or zero => delete sp
    588693                    }
     694                    else {
     695                      Print("CRITERION 2 in SPOLS 2nd generator\n");
     696                    }
    589697                }
    590698                else { // temp->getLp2Index() < temp->getLp1Index()
     
    640748                    }
    641749                }
     750            }
     751            else {
     752              Print("CRITERION 2 in SPOLS 1st generator\n");
    642753            }
    643754        //}
     
    840951                                      //pWrite(tempRed->getTerm());
    841952                                      //pWrite(pHead(tempRed->getPoly()));
    842                                       //addToG  = 0;
     953                                      addToG  = 0;
    843954                        }
    844955                        if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) {
     
    10701181        }
    10711182        else {
    1072             //Print("\nELEMENT ADDED TO GPREV: ");
     1183            Print("\nELEMENT ADDED TO GPREV: ");
    10731184            pNorm(redPoly);
    1074             //pWrite(pHead(redPoly));
    1075             //pWrite(l->getTerm());
     1185            pWrite(pHead(redPoly));
     1186            pWrite(l->getTerm());
    10761187            //Print("%d\n",canonicalize);
    10771188            l->setPoly(redPoly);
     1189            // give "l" the label if it is "useful" (addToG = 0) or "useless"
     1190            // (addToG = 1)
     1191            l->setDel(!addToG);
    10781192            if(addToG == 0 && termination == 1) {
    10791193              reducers->insert(l->getLPolyOld());
     
    10951209            }
    10961210            }
     1211            // case in which all new elements are added to gPrev!
     1212            // using boolean "addToG" to know if the element is "useful" (0) or
     1213            // "useless" (1)
    10971214            else {
    1098               criticalPair(gPrev,critPairs,lTag,rTag,rules);
     1215              if(!l->getDel()) {
     1216                criticalPair(gPrev,critPairs,lTag,rTag,rules);
     1217              }
     1218              else {
     1219                criticalPair2(gPrev,critPairs,lTag,rTag,rules);
     1220              }
    10991221            }
    11001222        }
     
    16621784    reductionTime       =   0;
    16631785    spolsTime           =   0;
     1786    numberUselessPairs  =   0;
     1787    numberUsefulPairs   =   0;
    16641788    return(gbPrev);
    16651789
  • kernel/f5gb.h

    r1d9469 r418bd6  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.h,v 1.44 2009-08-31 13:55:46 ederc Exp $ */
     4/* $Id: f5gb.h,v 1.45 2009-10-01 13:40:16 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
     
    4848================================================================
    4949computes a list of critical pairs for the next reduction process
     50the first element is always "useful" thus the critical pair
     51computed is either "useful" or "useless" depending on the second
     52element which generates the critical pair.
    5053first element in gPrev is always the newest element which must
    5154build critical pairs with all other elements in gPrev
     
    5356*/
    5457void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds);
     58
     59/*
     60================================================================
     61computes a list of critical pairs for the next reduction process
     62the first element is always "useless" thus the critical pair
     63computed is "useless".
     64first element in gPrev is always the newest element which must
     65build critical pairs with all other elements in gPrev
     66================================================================
     67*/
     68void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds);
    5569
    5670/*
  • kernel/f5lists.cc

    r1d9469 r418bd6  
    767767}
    768768
     769bool CNode::getDel() {
     770  return data->getDel();
     771}
     772
    769773RuleOld* CNode::getTestedRuleOld() {
    770774    return this->data->getTestedRuleOld();
  • kernel/f5lists.h

    r1d9469 r418bd6  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5lists.h,v 1.24 2009-08-31 13:55:46 ederc Exp $ */
     4/* $Id: f5lists.h,v 1.25 2009-10-01 13:40:16 ederc Exp $ */
    55/*
    66* ABSTRACT: list interface
     
    227227        int     getLp1Index();
    228228        int     getLp2Index();
     229        bool    getDel();
    229230        RuleOld*   getTestedRuleOld();
    230231        void    print();
Note: See TracChangeset for help on using the changeset viewer.