Changeset 418bd6 in git for kernel/f5gb.cc


Ignore:
Timestamp:
Oct 1, 2009, 3:40:16 PM (15 years ago)
Author:
Christian Eder
Branches:
(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')
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
File:
1 edited

Legend:

Unmodified
Added
Removed

  • 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
Note: See TracChangeset for help on using the changeset viewer.