Changeset d51339 in git


Ignore:
Timestamp:
Feb 18, 2009, 9:43:05 PM (15 years ago)
Author:
Christian Eder
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '4188d308699580d975efd0f6cca8dcb41c396f70')
Children:
eab144e3329d02244a62975d1bb6e77d4754f131
Parents:
93a7f7b1c20c3c886dd4dff521c518039f3824e7
Message:
new written reduction process, still problems getting the right rules in criterion2()
->lastRuleTested shouldnt be part of the CPair as it is a characteristic of an LPoly


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

Legend:

Unmodified
Added
Removed
  • kernel/f5data.cc

    r93a7f7 rd51339  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5data.cc,v 1.6 2009-02-15 20:33:56 ederc Exp $ */
     4/* $Id: f5data.cc,v 1.7 2009-02-18 20:43:05 ederc Exp $ */
    55/*
    66* ABSTRACT: lpolynomial definition
     
    150150}
    151151
     152void CPair::setLastRuleTested(Rule* r) {
     153    lastRuleTested   =   r;
     154}
     155
    152156/*
    153157===================================
  • kernel/f5data.h

    r93a7f7 rd51339  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5data.h,v 1.5 2009-02-11 21:24:07 ederc Exp $ */
     4/* $Id: f5data.h,v 1.6 2009-02-18 20:43:05 ederc Exp $ */
    55/*
    66* ABSTRACT: labeled polynomial interface
     
    7575        int     getLp2Index();
    7676        Rule*   getLastRuleTested();
     77        void    setLastRuleTested(Rule* r);
    7778};
    7879
  • kernel/f5gb.cc

    r93a7f7 rd51339  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.cc,v 1.29 2009-02-16 14:23:42 ederc Exp $ */
     4/* $Id: f5gb.cc,v 1.30 2009-02-18 20:43:05 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
     
    7474    pWrite(gPrev->getFirst()->getPoly());
    7575    gPrev->insert(ONE,i,f_i);
     76    // tag the first element in gPrev of the current index for findReductor()
     77    lTag->setFirstCurrentIdx(gPrev->getFirst());
    7678    Print("1st gPrev: ");
    7779    pWrite(gPrev->getFirst()->getPoly());
     
    8183    CList* critPairs        =   new CList();
    8284    CNode* critPairsMinDeg  =   new CNode();   
    83     // computation of critical pairs with checking of criterion 1 and criterion 2
    84     critPairs               =   criticalPair(gPrev, critPairs, lTag, rTag, rules);
     85    // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
     86    // in the list critPairs
     87    criticalPair(gPrev, critPairs, lTag, rTag, rules);
    8588    static LList* sPolyList        =   new LList();
    8689    // labeled polynomials which have passed reduction() and have to be added to list gPrev
    8790    static LList* completed        =   new LList();
    88     Print("_____________________________________________________________________________%p\n",completed->getFirst()->getLPoly());
    8991    // the reduced labeled polynomials which are returned from subalgorithm reduction()
    9092    static LList* reducedLPolys     =   new LList();
     
    9395        // critPairs->getMinDeg() deletes the first elements of minimal degree from
    9496        // critPairs, thus the while loop is not infinite.
    95         critPairs->print();
    9697        critPairsMinDeg =   critPairs->getMinDeg();
    9798        // adds all to be reduced S-polynomials in the list sPolyList and adds
     
    108109            temp    =   temp->getNext();
    109110        }
    110         //while(NULL != sPolyList->getFirst()->getLPoly()) {
    111             reduction(sPolyList, completed, gPrev, rules, lTag, rTag, gbPrev);
    112         //}
    113     }
    114     Print("HIER123\n");
     111        // reduction process of new S-polynomials and also adds new critical pairs to critPairs
     112        reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
     113    }
     114    Print("REDUCTION DONE\n");
    115115    Print("%p\n",rules->getFirst());
    116116    Print("%p\n",rTag->getFirst());
     
    122122        Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
    123123    }
    124     lTag->insert(gPrev->getFirst());
     124    lTag->insert(lTag->getFirstCurrentIdx());
     125    Print("LTAG LIST: \n");
     126    LNode* tempTag = lTag->getFirst();
     127    Print("INDEX: %d\n",tempTag->getIndex());
     128    pWrite(tempTag->getPoly());
    125129    Print("COMPLETED FIRST IN F5INC: \n");
     130    Print("1st gPrev: ");
     131    pWrite(gPrev->getFirst()->getPoly());
     132    Print("2nd gPrev: ");
     133    pWrite(gPrev->getFirst()->getNext()->getPoly());
     134    Print("3rd gPrev: ");
     135    pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly());
     136 
     137 
    126138    return gPrev;
    127139}
     
    136148================================================================
    137149*/
    138 CList* criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
     150void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
    139151    // initialization for usage in pLcm()
    140152    number nOne         =   nInit(1);
    141     LNode* first        =   gPrev->getFirst();
    142     LNode* l            =   first->getNext();
    143     poly* u1            =   new poly(pInit());
    144     poly* u2            =   new poly(pInit());
    145     poly* lcm           =   new poly(pInit());
    146     poly t              =   pHead(first->getPoly());
     153    LNode* newElement   =   gPrev->getLast();
     154    LNode* temp         =   gPrev->getFirst();
     155    poly u1             =   pOne();
     156    poly u2             =   pOne();
     157    poly lcm            =   pOne();
     158    poly t              =   pHead(newElement->getPoly());
    147159    // computation of critical pairs
    148     while( NULL != l) {
     160    while( gPrev->getLast() != temp) {
    149161        //pWrite( *(gPrev->getFirst()->getPoly()) );
    150162        //pWrite( *(l->getPoly()) );
    151         pLcm(first->getPoly(), l->getPoly(), *lcm);
    152         pSetCoeff(*lcm,nOne);
     163        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
     164        pSetCoeff(lcm,nOne);
    153165        // computing factors u2 for new labels
    154         pWrite(t);
    155         *u1 = pDivide(*lcm,t);
    156         pWrite(*u1);
    157         pSetCoeff(*u1,nOne);
    158         pWrite(pHead(l->getPoly()));
    159         *u2 = pDivide(*lcm, pHead(l->getPoly()));
    160         pSetCoeff(*u2,nOne);
     166        u1 = pDivide(lcm,t);
     167        pSetCoeff(u1,nOne);
     168        u2 = pDivide(lcm, pHead(temp->getPoly()));
     169        pSetCoeff(u2,nOne);
    161170        Print("IN CRITPAIRS\n");
    162         pWrite(*u2);
     171        pWrite(u1);
     172        Print("1st ELEMENT: ");
     173        pWrite(newElement->getPoly());
     174        Print("2nd ELEMENT: ");
     175        pWrite(temp->getPoly());
    163176        // testing both new labels by the F5 Criterion
    164         if(!criterion1(u1, first, lTag) && !criterion1(u2, l, lTag) &&
    165            !criterion2(u1, first, rules, rTag) && !criterion2(u2, l, rules, rTag)) {
     177        if(!criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag) &&
     178           !criterion2(u1, newElement, rules, rTag) && !criterion2(u2, temp, rules, rTag)) {
    166179            // if they pass the test, add them to CList critPairs, having the LPoly with greater
    167180            // label as first element in the CPair
    168             if(first->getIndex() == l->getIndex() &&
    169             pMult(*u1, first->getTerm()) < pMult(*u2, l->getTerm())) {
    170                 CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u2,
    171                                 l->getLPoly(), *u1, first->getLPoly());                   
    172                     critPairs->insert(cp);
     181            if(newElement->getIndex() == temp->getIndex() &&
     182            ppMult_qq(u1, newElement->getTerm()) < ppMult_qq(u2, temp->getTerm())) {
     183                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
     184                                temp->getLPoly(), u1, newElement->getLPoly());                   
     185                critPairs->insert(cp);
    173186            }
    174187            else {
    175                 CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u1,
    176                                 first->getLPoly(), *u2, l->getLPoly());                   
    177                     critPairs->insert(cp);
     188                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
     189                                newElement->getLPoly(), u2, temp->getLPoly());                   
     190                critPairs->insert(cp);
    178191            }
    179192        }
     
    181194        }
    182195       
    183         // for debugging
    184         if(NULL != critPairs) {
    185             critPairs->print();
    186         }
    187         l   =   l->getNext();
    188     }
    189     return critPairs;
     196        Print("\n\n");
     197        temp    =   temp->getNext();
     198    }
     199    // for debugging
     200    if(NULL != critPairs) {
     201        critPairs->print();
     202    }
     203}
     204
     205
     206
     207/*
     208================================================================
     209computes a list of critical pairs for the next reduction process
     210first element in gPrev is always the newest element which must
     211build critical pairs with all other elements in gPrev
     212NOTE: this is a special version for the call inside reduction()
     213      which adds to the already existing critical pairs new ones
     214================================================================
     215*/
     216void criticalPairRed(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
     217    // initialization for usage in pLcm()
     218    number nOne         =   nInit(1);
     219    LNode* newElement   =   gPrev->getLast();
     220    LNode* temp         =   gPrev->getFirst();
     221    poly u1             =   pOne();
     222    poly u2             =   pOne();
     223    poly lcm            =   pOne();
     224    poly t              =   pHead(newElement->getPoly());
     225    // computation of critical pairs
     226    while( gPrev->getLast() != temp) {
     227        //pWrite( *(gPrev->getFirst()->getPoly()) );
     228        //pWrite( *(l->getPoly()) );
     229        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
     230        pSetCoeff(lcm,nOne);
     231        // computing factors u2 for new labels
     232        u1 = pDivide(lcm,t);
     233        pSetCoeff(u1,nOne);
     234        u2 = pDivide(lcm, pHead(temp->getPoly()));
     235        pSetCoeff(u2,nOne);
     236        Print("IN CRITPAIRS\n");
     237        // testing both new labels by the F5 Criterion
     238        if(!criterion1(gPrev,u1, newElement, lTag) && !criterion1(gPrev,u2, temp, lTag) &&
     239           !criterion2(u1, newElement, rules, rTag) && !criterion2(u2, temp, rules, rTag)) {
     240            // if they pass the test, add them to CList critPairs, having the LPoly with greater
     241            // label as first element in the CPair
     242            if(newElement->getIndex() == temp->getIndex() &&
     243            pMult(u1, newElement->getTerm()) < pMult(u2, temp->getTerm())) {
     244                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
     245                                temp->getLPoly(), u1, newElement->getLPoly());                   
     246                critPairs->insert(cp);
     247            }
     248            else {
     249                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
     250                                newElement->getLPoly(), u2, temp->getLPoly());                   
     251                critPairs->insert(cp);
     252            }
     253        }
     254        else {
     255        }
     256       
     257       
     258        temp    =   temp->getNext();
     259    }
     260    // for debugging
     261    if(NULL != critPairs) {
     262        critPairs->print();
     263    }
    190264}
    191265
     
    197271========================================
    198272*/
    199 bool criterion1(poly* t, LNode* l, LTagList* lTag) {
     273bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) {
    200274    // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
    201         LNode* testNode =   lTag->get(l->getIndex());
    202         // save the monom t1*label_term(l) as it is tested various times in the following
    203     poly u1 = ppMult_qq(*t,l->getTerm());
    204     while(NULL != testNode && NULL != testNode->getLPoly()) {
    205         if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
    206             Print("Criterion 1 NOT passed!\n");
    207             return true;
    208         }
    209         //pWrite(testNode->getNext()->getPoly());
    210                 testNode    =   testNode->getNext();
    211         Print("ADDRESS OF TEST NODE: %p\n",testNode);
    212     Print("Hier\n");
    213     }
    214     Print("HIER DRIN CRITERION 1\n");
    215        
    216     return false;
     275        int idx =   l->getIndex();
     276    if(idx == 1) {
     277        return false;
     278    }
     279    else {
     280        LNode* testNode =   gPrev->getFirst();
     281        // save the monom t1*label_term(l) as it is tested various times in the following
     282        poly u1 = ppMult_qq(t,l->getTerm());
     283        Print("------------------------------IN CRITERION 1-----------------------------------------\n");
     284        Print("TESTED ELEMENT: ");
     285        pWrite(l->getPoly());
     286        pWrite(ppMult_qq(t,l->getTerm()));
     287        Print("%d\n\n",l->getIndex());
     288        while(testNode->getIndex() < idx && NULL != testNode->getLPoly()) {
     289            pWrite(testNode->getPoly());
     290            Print("%d\n",testNode->getIndex());
     291            if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
     292                Print("Criterion 1 NOT passed!\n");
     293                return true;
     294            }
     295            //pWrite(testNode->getNext()->getPoly());
     296            testNode    =   testNode->getNext();
     297        }
     298        return false;
     299    }
    217300}
    218301
     
    224307=====================================
    225308*/
    226 bool criterion2(poly* t, LNode* l, RList* rules, RTagList* rTag) {
    227         Print("HIER DRIN CRITERION 2:=========================\n");
    228     // start at the previously added element to gPrev, as all other elements will have the same index for sure
    229         Print("%d\n",l->getIndex());
     309bool criterion2(poly t, LNode* l, RList* rules, RTagList* rTag) {
     310    Print("------------------------------IN CRITERION 2-----------------------------------------\n");
     311        Print("RULES: \n");
     312        RNode* tempR    =   rules->getFirst();
     313        while(NULL != tempR->getRule()) {
     314            pWrite(tempR->getRuleTerm());
     315            Print("%d\n\n",tempR->getRuleIndex());
     316            tempR   =   tempR->getNext();
     317        }
     318Print("TESTED ELEMENT: ");
     319        pWrite(l->getPoly());
     320        pWrite(ppMult_qq(t,l->getTerm()));
     321        Print("%d\n\n",l->getIndex());
     322// start at the previously added element to gPrev, as all other elements will have the same index for sure
    230323    RNode* testNode =   new RNode();
    231324    if(NULL == rTag->getFirst()->getRule()) {
     
    233326    }
    234327    else {
    235         Print("%d\n",l->getIndex());
    236         Print("%d\n",rTag->getFirst()->getRuleIndex());
    237 pWrite(rTag->getFirst()->getRuleTerm());
    238328        if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
    239329            testNode    =   rules->getFirst();
    240             Print("TEST NODE: %p\n",testNode);
    241330        }
    242331        else {
     
    245334    }
    246335        // save the monom t1*label_term(l) as it is tested various times in the following
    247     poly u1 = ppMult_qq(*t,l->getTerm());
    248         pWrite(u1);
     336    poly u1 = ppMult_qq(t,l->getTerm());
    249337    // first element added to rTag was NULL, check for this
    250     pWrite(l->getPoly());
    251338    //Print("%p\n",testNode->getRule());
    252     Print("HIER !!!!\n");
    253339    // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
    254340    while(NULL != testNode && NULL != testNode->getRule() && testNode->getRule() != l->getRule()
    255341          && l->getIndex() == testNode->getRuleIndex()) {
    256                 pWrite(ppMult_qq(*t,l->getTerm()));
    257                 pWrite(testNode->getRuleTerm());
    258                 if(pLmDivisibleBy(ppMult_qq(*t,l->getTerm()),testNode->getRuleTerm())) {
     342        pWrite(testNode->getRuleTerm());
     343                if(pLmDivisibleBy(ppMult_qq(t,l->getTerm()),testNode->getRuleTerm())) {
    259344            Print("Criterion 2 NOT passed!\n");
    260345            return true;
     
    272357=================================================================================================================
    273358*/
    274 bool criterion2(poly* t, LPoly* l, RList* rules, Rule* lastRuleTested) {
    275     // start at the previously added element to gPrev, as all other elements will have the same index for sure
     359bool criterion2(poly t, LPoly* l, RList* rules, Rule* lastRuleTested) {
     360    Print("------------------------------IN CRITERION 2-----------------------------------------\n");
     361    Print("LAST RULE TESTED: %p",lastRuleTested);
     362    Print("RULES: \n");
     363        RNode* tempR    =   rules->getFirst();
     364        while(NULL != tempR->getRule()) {
     365            pWrite(tempR->getRuleTerm());
     366            Print("%d\n\n",tempR->getRuleIndex());
     367            tempR   =   tempR->getNext();
     368        }
     369        Print("TESTED ELEMENT: ");
     370        pWrite(l->getPoly());
     371        pWrite(ppMult_qq(t,l->getTerm()));
     372        Print("%d\n\n",l->getIndex());
     373// start at the previously added element to gPrev, as all other elements will have the same index for sure
    276374        RNode* testNode =   rules->getFirst();
    277375    // save the monom t1*label_term(l) as it is tested various times in the following
    278     poly u1 = ppMult_qq(*t,l->getTerm());
     376    poly u1 = ppMult_qq(t,l->getTerm());
    279377        // first element added to rTag was NULL, check for this
    280         while(NULL != testNode->getRule() && l->getRule() != lastRuleTested) {
    281         if(pLmDivisibleBy(testNode->getRuleTerm(),ppMult_qq(*t,l->getTerm()))) {
     378        while(NULL != testNode->getRule() && testNode->getRule() != lastRuleTested) {
     379        pWrite(testNode->getRuleTerm());
     380        if(pLmDivisibleBy(testNode->getRuleTerm(),ppMult_qq(t,l->getTerm()))) {
    282381            Print("Criterion 2 NOT passed!\n");
    283382            return true;
     
    285384                testNode    =   testNode->getNext();
    286385    }
     386    lastRuleTested = testNode->getRule();
    287387    return false;
    288388}
     
    302402        // only if a new rule was added since the last test in subalgorithm criticalPair()
    303403        //if(rules->getFirst() != rTag->getFirst()) {
    304             Print("IN SPOLS => NEW RULES AVAILABLE\n");
    305             if(!criterion2(temp->getAdT1(),temp->getAdLp1(),rules,temp->getLastRuleTested())) {
     404            if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getLastRuleTested())) {
    306405                // the second component is tested only when it has the actual index, otherwise there is
    307406                // no new rule to test since the last test in subalgorithm criticalPair()
    308407                if(temp->getLp2Index() == temp->getLp1Index()) {
    309                     if(!criterion2(temp->getAdT2(),temp->getAdLp2(),rules,temp->getLastRuleTested())) {
     408                    if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getLastRuleTested())) {
    310409                        // computation of S-polynomial
    311410                        sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
     
    324423                                                        reductionsToZero++;
    325424                            rules->insert(temp->getLp1Index(),temp->getT1());
     425                            Print("RULE ADDED: \n");
     426                            pWrite(rules->getFirst()->getRuleTerm());
    326427                            // as sp = NULL, delete it
    327428                            delete(&sp);
     
    329430                        else {
    330431                            rules->insert(temp->getLp1Index(),temp->getT1());
    331                             sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
     432                            Print("RULE ADDED: \n");
     433                            pWrite(rules->getFirst()->getRuleTerm()); 
     434                            sPolyList->insertSP(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
    332435                        }
    333436                        // data is saved in sPolyList or zero => delete sp
     
    339442                                     ppMult_qq(temp->getT2(),temp->getLp2Poly()));
    340443                    Print("BEGIN SPOLY2\n====================\n");
     444                    pNorm(sp);
    341445                    pWrite(sp);
    342446                    Print("END SPOLY2\n====================\n");
     
    349453                        reductionsToZero++;
    350454                        rules->insert(temp->getLp1Index(),temp->getT1());
     455                        Print("RULE ADDED: \n");
     456                        pWrite(rules->getFirst()->getRuleTerm());
    351457                        // as sp = NULL, delete it
    352458                        delete(&sp);
     
    354460                    else {
    355461                        rules->insert(temp->getLp1Index(),temp->getT1());
    356                         sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
     462                        Print("RULE ADDED: \n");
     463                        pWrite(rules->getFirst()->getRuleTerm());
     464                        Print("%p\n",sPolyList->getFirst());
     465                        sPolyList->insertSP(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
    357466                    }
    358467                    // data is saved in sPolyList or zero => delete sp
     
    375484========================================================================
    376485*/
    377 void reduction(LList* sPolyList, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
     486void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
    378487                 ideal gbPrev) {
    379488    Print("##########################################In REDUCTION!########################################\n");
    380      // LNode* saving the last element in gPrev before the completed elements from the reduction process are added
    381     // this is needed to get the new critical pairs computed
    382     LNode* gPrevTag = gPrev->getLast();
    383     //for debugging
    384     pWrite(gPrevTag->getPoly());
    385489    // check if sPolyList has any elements
    386490    // NOTE: due to initialization sPolyList always has a default NULL element
    387     while(sPolyList->getLength() > 1) {
     491    while(sPolyList->getLength() > 0) {
     492        Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
     493        sPolyList->print();
    388494        // temp is the first element in the sPolyList which should be reduced
    389495        // due to earlier sorting this is the element of minimal degree AND
    390496        // minimal label
    391497        LNode* temp =   sPolyList->getFirst();
     498        pWrite(temp->getPoly());
    392499        // delete the above first element from sPolyList, temp will be either reduced to
    393500        // zero or added to gPrev, but never come back to sPolyList
    394501        sPolyList->setFirst(temp->getNext());
     502        Print("HALLO %p\n",temp->getPoly());
     503        Print("%p\n",temp->getPoly());
    395504        pWrite(temp->getPoly());
    396505        poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
     
    404513            // with label index = current label index: this is done such that there
    405514            // is no label corruption during the reduction process
    406             topReduction(temp,completed,gPrev,rules,lTag,rTag);
     515            topReduction(temp,sPolyList,gPrev,rules,lTag,rTag);
     516        LNode* tempLoop = gPrev->getFirst();
     517                while(NULL != tempLoop) {
     518                    pWrite(tempLoop->getPoly());
     519                    tempLoop = tempLoop->getNext();
     520                    }
     521        }
     522        if(NULL != temp->getPoly()) {
     523            //CList* newCritPairs = new CList;
     524            criticalPair(gPrev,critPairs,lTag,rTag,rules);
     525        }
     526        else {
     527            delete temp;
    407528        }
    408529    }
     
    417538=====================================================================================
    418539*/
    419 void topReduction(LNode* l, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag) {
     540void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag) {
    420541    Print("##########################################In topREDUCTION!########################################\n");
    421 
     542    // try l as long as there are reductors found by findReductor()
     543    do {
     544        LNode* tempRed  =   new LNode();
     545        tempRed  =   findReductor(l,gPrev,rules,lTag,rTag);
     546        // if a reductor for l is found and saved in tempRed
     547        if(NULL != tempRed) {
     548            // if label of reductor is greater than the label of l we have to built a new element
     549            // and add it to sPolyList
     550            if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
     551                poly temp   =   pSub(tempRed->getPoly(),l->getPoly());
     552                pWrite(temp);
     553                if(NULL != temp) {
     554                    tempRed->setPoly(temp);
     555                    // for debugging
     556                    pWrite(tempRed->getPoly());
     557                    Print("RULE ADDED\n");
     558                    rules->insert(tempRed->getIndex(),tempRed->getTerm());
     559                   
     560                    tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
     561                    sPolyList->insertByLabel(tempRed);
     562                }
     563                else {
     564                    pDelete(&temp);
     565                    reductionsToZero++;
     566                    Print("RULE ADDED\n");
     567                    rules->insert(tempRed->getIndex(),tempRed->getTerm());
     568                    delete tempRed;
     569                }
     570            }
     571            // label of reductor is smaller than the label of l, subtract reductor from l and delete the
     572            // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
     573            // after subtraction
     574            else {
     575                poly temp   =   pSub(l->getPoly(),tempRed->getPoly());
     576                pWrite(temp);
     577                if(NULL != temp) {
     578                    l->setPoly(temp);
     579                    l->setGPrevRedCheck(NULL);
     580                }
     581                else {
     582                    pDelete(&temp);
     583                    l->setPoly(NULL);
     584                }
     585            }   
     586        }
     587        else {
     588            if(NULL != l->getPoly()) {
     589                Print("ADDED TO GPREV IN TOPREDUCTION: ");
     590                pWrite(l->getPoly());
     591                gPrev->insert(l->getLPoly());
     592                Print("GPREV: \n");
     593                LNode* tempLoop = gPrev->getFirst();
     594                while(NULL != tempLoop) {
     595                    pWrite(tempLoop->getPoly());
     596                    tempLoop = tempLoop->getNext();
     597                }
     598            }
     599            break;
     600        }
     601    } while(1);
    422602}
    423603
     
    428608=====================================================================
    429609*/
    430 LNode* findReductor(LNode* l,LList* completed,LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag,
    431                     LNode* gPrevRedCheck) {
    432    Print("HIER DU NULL!\n");
    433     return NULL;
     610LNode* findReductor(LNode* l, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag) {
     611    // allociation of memory for the possible reductor
     612    poly u      =   pOne();
     613    poly red    =   pOne();
     614    number nOne =   nInit(1);
     615    LNode* temp =   new LNode();
     616    // head term of actual element such that we do not have to call pHead at each new reductor test
     617    poly t      =   pHead(l->getPoly());
     618    // if l was already checked use the information in gPrevRedCheck such
     619    // that we can start searching for new reducers from this point and
     620    // not from the first element of gPrev with the current index
     621    if(NULL != l->getGPrevRedCheck()) {
     622        temp    =   l->getGPrevRedCheck()->getNext();
     623    }
     624    // no reductors were searched for l before, thus start at the first
     625    // element of gPrev with the current index, tagged by lTag
     626    else {
     627        temp    =   lTag->getFirstCurrentIdx();
     628    }
     629    // search for reductors until we are at the end of gPrev resp. at the
     630    // end of the elements of the current index
     631    while(NULL != temp && temp->getIndex() == l->getIndex()) {
     632        // does the head of the element of gPrev divides the head of
     633        // the to be reduced element?
     634        if(pLmDivisibleByNoComp(temp->getPoly(),t)) {
     635            // get all the information needed for the following tests
     636            // of the criteria
     637            u   =   pDivide(t,pHead(temp->getPoly()));
     638            pSetCoeff(u,nOne);
     639            red =   ppMult_qq(u,temp->getPoly());
     640            pNorm(red);
     641            u   =   ppMult_qq(u,temp->getTerm());
     642            pSetCoeff(u,nOne);
     643            // check if both have the same label
     644            if(pLmCmp(u,l->getTerm()) != 0) {
     645                // passing criterion2 ?
     646                if(!criterion2(u,temp,rules,rTag)) {
     647                    // passing criterion1 ?
     648                    if(!criterion1(gPrev,u,temp,lTag)) {
     649                            l->setGPrevRedCheck(temp);
     650                            LNode* redNode  =   new LNode(u,temp->getIndex(),red,NULL,NULL);
     651                            return redNode;
     652                    }
     653                }
     654            }
     655        }
     656        temp = temp->getNext();
     657    }
     658   
     659//    delete temp;
     660   Print("1st gPrev: ");
     661    pWrite(gPrev->getFirst()->getPoly());
     662    Print("2nd gPrev: ");
     663    pWrite(gPrev->getFirst()->getNext()->getPoly());
     664 return NULL;
    434665}
    435666
     
    472703
    473704    lTag->insert(gPrev->getFirst());
     705    lTag->setFirstCurrentIdx(gPrev->getFirst());
    474706    // computing the groebner basis of the elements of index < actual index
    475707    gbLength    =   gPrev->getLength();
     
    482714
    483715    for(i=2; i<=IDELEMS(id); i++) {
     716        LNode* gPrevTag =   gPrev->getLast();
     717        Print("Last POlynomial in GPREV: ");
     718        Print("%p\n",gPrevTag);   
     719        pWrite(gPrevTag->getPoly());
    484720        gPrev   =   F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag);
    485721        // comuting new groebner basis gbPrev
    486         ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
    487         LNode*  temp    =   gPrev->getFirst();
     722        if(gPrev->getLength() > gbLength) {
     723            ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
     724        LNode*  temp    =   gPrevTag;
     725        Print("%p\n",gPrevTag);   
     726        Print("%p\n",gPrev->getLast());   
     727        pWrite(temp->getPoly());
     728        Print("LENGTH OF GPREV LIST: %d\n",gPrev->getLength());
     729        Print("%d\n",gbLength);
    488730        for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
     731            Print("YES\n");
    489732            gbAdd->m[j] =   temp->getPoly();
     733            pWrite(temp->getPoly());
    490734            temp        =   temp->getNext();
    491735        }
     736        gbLength    =   gPrev->getLength();
    492737        gbPrev  =   idAdd(gbPrev,gbAdd);
     738        }
    493739        Print("GROEBNER BASIS:\n====================================================\n");
    494740        idShow(gbPrev);
  • kernel/f5gb.h

    r93a7f7 rd51339  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.h,v 1.26 2009-02-16 14:23:42 ederc Exp $ */
     4/* $Id: f5gb.h,v 1.27 2009-02-18 20:43:05 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
     
    4444================================================================
    4545*/
    46 CList* criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
     46void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
     47
     48/*
     49================================================================
     50computes a list of critical pairs for the next reduction process
     51first element in gPrev is always the newest element which must
     52build critical pairs with all other elements in gPrev
     53NOTE: this is a special version for the call inside reduction()
     54      which adds to the already existing critical pairs new ones
     55================================================================
     56*/
     57void criticalPairRed(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
    4758
    4859/*
     
    5162========================================
    5263*/
    53 bool criterion1(poly* t, LNode* l, LTagList* lTag);
     64bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
    5465
    5566/*
     
    5869=====================================
    5970*/
    60 bool criterion2(poly* t, LNode* l, RList* rules, RTagList* rTag);
     71bool criterion2(poly t, LNode* l, RList* rules, RTagList* rTag);
    6172
    6273/*
     
    6576==========================================================================================================
    6677*/
    67 bool criterion2(poly* t, LPoly* l, RList* rules, Rule* lastRuleTested);
     78bool criterion2(poly t, LPoly* l, RList* rules, Rule* lastRuleTested);
    6879
    6980/*
     
    7990========================================================================
    8091*/
    81 void reduction(LList* sPolyList, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
     92void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
    8293                 ideal gbPrev);
    8394
     
    8899=====================================================================================
    89100*/
    90 void topReduction(LNode* l, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag);
     101void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag);
    91102
    92103/*
     
    95106=====================================================================
    96107*/
    97 LNode* findReductor(LNode* l,LList* completed,LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag,
    98                     LNode* gPrevRedCheck);
     108LNode* findReductor(LNode* l, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag);
    99109
    100110/*
  • kernel/f5lists.cc

    r93a7f7 rd51339  
    7070}
    7171       
    72 // insert new elements to the list always in front (labeled / classical polynomial view)
     72// insert new elements to the list always at the end (labeled / classical polynomial view)
     73// needed for list gPrev
    7374LNode* LNode::insert(LPoly* lp) {
    74     Print("HIER\n");
    75     LNode* newElement = new LNode(lp, this);
     75    Print("INSERTION: \n");
     76    Print("LAST GPREV: ");
     77    pWrite(this->getPoly());
     78LNode* newElement   =   new LNode(lp, NULL);
     79    this->next          =   newElement;
    7680    return newElement;
    7781}
    7882       
    7983LNode* LNode::insert(poly t, int i, poly p, Rule* r) {
    80     LNode* newElement = new LNode(t, i, p, r, NULL, this);
     84    LNode* newElement   =   new LNode(t, i, p, r, NULL, NULL);
     85    this->next          =   newElement;
    8186    return newElement;
    8287}
    8388
    84 LNode* LNode::append(poly t, int i, poly p, Rule* r) {
    85     LNode* newElement   =   new LNode(t,i,p,r,NULL);
    86     this->next          =   newElement;
    87 }
    88 
     89// insert new elements to the list always in front (labeled / classical polynomial view)
     90// needed for sPolyList
     91LNode* LNode::insertSP(LPoly* lp) {
     92    LNode* newElement   =   new LNode(lp, this);
     93    return newElement;
     94}
     95       
     96LNode* LNode::insertSP(poly t, int i, poly p, Rule* r) {
     97    LNode* newElement   =   new LNode(t, i, p, r, NULL, this);
     98    return newElement;
     99}
    89100// insert new elemets to the list w.r.t. increasing labels
    90101// only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
     
    122133    return next;
    123134}
    124        
     135
    125136// get the LPoly* out of LNode*
    126137LPoly* LNode::getLPoly() {
     
    182193}
    183194
     195// for debugging
     196void LNode::print() {
     197    LNode* temp = this;
     198    Print("___________________List of S-polynomials______________________:\n");
     199    while(NULL != temp->data) {
     200        Print("Index: %d\n",temp->getIndex());
     201        Print("Term: ");
     202        pWrite(temp->getTerm());
     203        Print("Poly: ");
     204        pWrite(temp->getPoly());
     205        Print("\n");
     206        temp = temp->next;
     207    }
     208}
     209
     210
    184211/*
    185212====================================
     
    210237}
    211238
    212 // insertion in front of the list
     239// insertion at the end of the list, needed for gPrev
    213240void LList::insert(LPoly* lp) {
    214     first = first->insert(lp);
     241    last = last->insert(lp);
     242    Print("NEW LAST GPREV: ");
     243    pWrite(last->getPoly());
    215244    length++;
     245    Print("LENGTH %d\n",length);
    216246}
    217247
    218248void LList::insert(poly t,int i, poly p, Rule* r) {
    219     first = first->insert(t,i,p,r);
     249    last = last->insert(t,i,p,r);
    220250    length++;
    221 }
    222 
    223 void LList::append(poly t, int i, poly p, Rule* r) {
    224     last    =   last->append(t,i,p,r);
     251    Print("LENGTH %d\n",length);
     252}
     253
     254// insertion in front of the list, needed for sPolyList
     255void LList::insertSP(LPoly* lp) {
     256    first = first->insertSP(lp);
    225257    length++;
    226 }
     258    Print("LENGTH %d\n",length);
     259}
     260
     261void LList::insertSP(poly t,int i, poly p, Rule* r) {
     262    first = first->insertSP(t,i,p,r);
     263    length++;
     264    Print("LENGTH %d\n",length);
     265}
     266
    227267
    228268void LList::insertByLabel(poly t, int i, poly p, Rule* r) {
    229269    first = first->insertByLabel(t,i,p,r);
    230270    length++;
     271    Print("LENGTH %d\n",length);
    231272}
    232273
     
    234275    first = first->insertByLabel(l->getTerm(),l->getIndex(),l->getPoly(),l->getRule());
    235276    length++;
     277    Print("LENGTH %d\n",length);
    236278}
    237279
     
    252294}
    253295
    254 LNode* LList::getNext(LNode* l) {
    255     return l->getNext();
    256 }
    257 
    258296int LList::getLength() {
    259297    return length;
     
    261299
    262300void LList::setFirst(LNode* l) {
    263     LNode* temp =   first;
    264301    first       =   l;
    265     delete(temp);
    266302    length--;
    267303}
    268304
    269 
     305void LList::print() {
     306    first->print();
     307}
    270308
    271309/*
     
    302340LNode* LTagNode::getLNode() {
    303341    return this->data;
     342}
     343
     344LTagNode* LTagNode::getNext() {
     345    return next;
    304346}
    305347
     
    329371LTagList::LTagList() {
    330372    LTagNode* first =   new LTagNode();
     373   
    331374    length          =   0;
    332375}
     
    343386}
    344387
     388void LTagList::setFirstCurrentIdx(LNode* l) {
     389    firstCurrentIdx =   l;
     390}
     391
    345392LNode* LTagList::get(int idx) {
    346393    return first->get(idx, length);
     
    351398}
    352399
     400LNode* LTagList::getFirstCurrentIdx() {
     401    return firstCurrentIdx;
     402}
    353403
    354404/*
     
    579629void CNode::print() {
    580630    CNode* temp = this;
    581     Print("List of critical pairs:\n");
     631    Print("___________________List of critical pairs______________________:\n");
    582632    while(NULL != temp->data) {
    583         Print("Index: %d\n",temp->getLp1Index());
     633        Print("LP1 Index: %d\n",temp->getLp1Index());
    584634        Print("T1: ");
    585635        pWrite(temp->getT1());
    586         Print("Lp1 Term: ");
     636        Print("LP1 Term: ");
    587637        pWrite(temp->getLp1Term());
    588         Print("%d\n",temp->getLp2Index());
     638        Print("LP1 Poly: ");
     639        pWrite(temp->getLp1Poly());
     640        Print("LP2 Index: %d\n",temp->getLp2Index());
     641        Print("T2: ");
    589642        pWrite(temp->getT2());
     643        Print("LP2 Term: ");
    590644        pWrite(temp->getLp2Term());
     645        Print("LP2 Poly: ");
     646        pWrite(temp->getLp2Poly());
    591647        Print("\n");
    592648        temp = temp->next;
    593649    }
     650}
     651
     652void CNode::setLastRuleTested(Rule* r) {
     653    data->setLastRuleTested(r);
    594654}
    595655
  • kernel/f5lists.h

    r93a7f7 rd51339  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5lists.h,v 1.9 2009-02-16 14:23:42 ederc Exp $ */
     4/* $Id: f5lists.h,v 1.10 2009-02-18 20:43:05 ederc Exp $ */
    55/*
    66* ABSTRACT: list interface
     
    4949                LNode(LNode* ln);
    5050                ~LNode();
    51         // insert new elements to the list in first place from the labeled / classical polynomial view
     51        // insert new elements to the list at the end from the labeled / classical polynomial view
     52        // needed for gPrev
    5253        LNode*  insert(LPoly* lp);
    5354        LNode*  insert(poly t, int i, poly p, Rule* r);
    54         //appends elements to the end of the list, done in reduction() in f5gb.cc
    55         LNode*  append(poly t, int i, poly p, Rule* r);
     55        // insert new elements to the list in front from the labeled / classical polynomial view
     56        // needed for sPolyList
     57        LNode*  insertSP(LPoly* lp);
     58        LNode*  insertSP(poly t, int i, poly p, Rule* r);
    5659        // insert new elements to the list with resp. to increasing labels
    5760        // only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
    5861        LNode*  insertByLabel(poly t, int i, poly p, Rule* r);
    5962        // deletes the first elements of the list with the same degree
    60         // get next from current LNode
     63        // get next & prev from current LNode
    6164        LNode*  getNext();
     65        LNode*  getPrev();
    6266        // only used for the S-polys, which are already sorted by increasing degree by CList
    6367        LNode*  deleteByDeg();
     
    7882        bool    polyTest(poly* p);
    7983        LNode*  getNext(LNode* l);
     84        void    print();
    8085};
    8186
     
    96101                LList(poly t,int i,poly p, Rule* r = NULL);
    97102                ~LList();
     103        // insertion at the end of the list
     104        // needed for gPrev
    98105        void    insert(LPoly* lp);
    99         // insertion in front of the list
    100106        void    insert(poly t,int i, poly p, Rule* r = NULL);
     107         // insertion in front of the list
     108        // needed for sPolyList
     109        void    insertSP(LPoly* lp);
     110        void    insertSP(poly t,int i, poly p, Rule* r = NULL);
    101111        void    insertByLabel(poly t, int i, poly p, Rule* r = NULL);
    102112        void    insertByLabel(LNode* l);
    103         void    append(poly t, int i, poly p, Rule* r=NULL);
    104113        void    deleteByDeg();
    105114        bool    polyTest(poly* p);
    106115        LNode*  getFirst();
    107116        LNode*  getLast();
    108         LNode*  getNext(LNode* l);
    109117        int     getLength();
    110118        void    setFirst(LNode* l);
     119        void    print();
    111120};
    112121
     
    130139        LTagNode*   insert(LNode* l);
    131140        LNode*      getLNode();
     141        LTagNode*   getNext();
    132142        LNode*      get(int i, int length);
    133143};
     
    142152    private:
    143153        LTagNode*   first;
     154        LNode*      firstCurrentIdx;
    144155        int         length;
    145156    public:
     
    149160        // declaration with first as parameter in LTagNode due to sorting of LTagList
    150161        void    insert(LNode* l);
     162        void    setFirstCurrentIdx(LNode* l);
    151163        LNode*  get(int idx);
    152164        LNode*  getFirst();
     165        LNode*  getFirstCurrentIdx();
    153166};
    154167
     
    207220        Rule*   getLastRuleTested();
    208221        void    print();
     222        void    setLastRuleTested(Rule* r);
    209223};
    210224
Note: See TracChangeset for help on using the changeset viewer.