Changeset 6b0aa2 in git


Ignore:
Timestamp:
Apr 20, 2009, 3:54:50 PM (15 years ago)
Author:
Christian Eder
Branches:
(u'spielwiese', '4a9821a93ffdc22a6696668bd4f6b8c9de3e6c5f')
Children:
f85223c462c7704fe0b5d7c8e916ba08f7ca4e86
Parents:
694257b820eac75a8100417ebf8f059879a873fd
Message:
new alternative reduction - still in progress!


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

Legend:

Unmodified
Added
Removed

  • kernel/f5gb.cc

    r694257b r6b0aa2  
    147147        //int timer4  =   initTimer();
    148148        //startTimer();
     149        critPairs->print();
    149150        computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
    150151        //timer4  =   getTimer();
    … …  
    161162        //int timer3  =   initTimer();
    162163        //startTimer();
     164        sPolyList->print();
    163165        reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
     166        //newReduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
    164167        //timer3      =  getTimer();
    165168        //reductionTime = reductionTime + timer3;
    … …  
    354357            //Print("%d\n",testNode->getIndex());
    355358            if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
    356                 //Print("Criterion 1 NOT passed!\n");
     359                Print("Criterion 1 NOT passed!\n");
    357360                return true;
    358361            }
    … …  
    479482        //Print("%d\n",testNode->getRuleIndex());
    480483        if(pLmDivisibleByNoComp(testNode->getRuleTerm(),u1)) {
    481             //Print("-----------------Criterion 2 NOT passed!-----------------------------------\n");
     484            Print("-----------------Criterion 2 NOT passed!-----------------------------------\n");
    482485            //Print("INDEX: %d\n",l->getIndex());
    483486            pDelete(&u1);
    … …  
    525528        //pWrite(testNode->getRuleTerm());
    526529        if(pLmDivisibleByNoComp(testNode->getRuleTerm(),u1)) {
    527             //Print("--------------------------Criterion 2 NOT passed!------------------------------\n");
     530            Print("--------------------------Criterion 2 NOT passed!------------------------------\n");
    528531            //Print("INDEX: %d\n",l->getIndex());
    529532            pDelete(&u1);
    … …  
    686689}   
    687690
    688 
     691/*
     692========================================================================
     693reduction including subalgorithm topReduction() using Faugere's criteria
     694========================================================================
     695*/
     696void newReduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
     697                 ideal gbPrev) {
     698    //Print("##########################################In REDUCTION!########################################\n");
     699    // check if sPolyList has any elements
     700    // NOTE: due to initialization sPolyList always has a default NULL element
     701    LNode* temp = sPolyList->getFirst();
     702    while(NULL != temp) {
     703        // temp is the first element in the sPolyList which should be reduced
     704        // due to earlier sorting this is the element of minimal degree AND
     705        // minimal label
     706        // delete the above first element from sPolyList, temp will be either reduced to
     707        // zero or added to gPrev, but never come back to sPolyList
     708        sPolyList->setFirst(temp->getNext());
     709        poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
     710        if(NULL != tempNF) {
     711            pNorm(tempNF);
     712            temp->setPoly(tempNF);
     713            // try further reductions of temp with polynomials in gPrev
     714            // with label index = current label index: this is done such that there
     715            // is no label corruption during the reduction process
     716            findReducers(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag);
     717        }
     718        else {
     719            reductionsToZero++;
     720            delete temp;
     721        }
     722        //if(NULL != temp->getPoly()) {
     723        //    criticalPair(gPrev,critPairs,lTag,rTag,rules);
     724        //}
     725        temp =   sPolyList->getFirst();
     726    }
     727    //sPolyList->print();
     728    //delete sPolyList;
     729}     
     730
     731
     732/*!
     733 * ================================================================================
     734 * searches for reducers of temp similar to the symbolic preprocessing of F4  and
     735 * divides them into a "good" and "bad" part:
     736 *
     737 * the "good" ones are the reducers which do not corrupt the label of temp, with
     738 * these the normal form of temp is computed
     739 *
     740 * the "bad" ones are the reducers which corrupt the label of temp, they are tested
     741 * later on for possible new rules and S-polynomials to be added to the algorithm
     742 * ================================================================================
     743*/
     744void findReducers(LNode* l, LList* sPolyList, LList* gPrev, CList* critPairs, RList* rules, LTagList* lTag, RTagList* rTag) {
     745    LList* good         =   new LList();
     746    LList* bad          =   new LList();
     747    LList* monomials    =   new LList(l->getLPoly());
     748    poly u              =   pOne();
     749    number nOne         =   nInit(1);
     750    LNode* tempRed      =   lTag->getFirstCurrentIdx();
     751    LNode* tempMon      =   monomials->getFirst();
     752    Print("IN FIND REDUCERS:  ");
     753    pWrite(l->getPoly());
     754    while(NULL != tempMon) {
     755        // iteration over all monomials in tempMon
     756        poly tempPoly   =   tempMon->getPoly();
     757        while(NULL != tempPoly) {
     758            // iteration of all elements in gPrev of the current index
     759            while(NULL != tempRed) {
     760                if(pDivisibleBy(tempRed->getPoly(),tempPoly)) {
     761                    u   =   pDivide(pHead(tempPoly),pHead(tempRed->getPoly()));
     762                    pSetCoeff(u,nOne);
     763                    //poly red =   ppMult_qq(u,temp->getPoly());
     764                    //pNorm(red);
     765                    // check if both have the same label
     766                    if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),tempMon->getTerm()) != 0) {
     767                        // passing criterion2 ?
     768                        if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) {
     769                            // passing criterion1 ?
     770                            if(!criterion1(gPrev,u,tempRed,lTag)) {
     771                                if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),tempMon->getTerm()) == 1) {
     772    //Print("HIER1\n");
     773                                    bad->insertSP(tempRed->getLPoly());
     774                                }
     775                                else {
     776                                    monomials->insertSP(tempRed->getLPoly());
     777                                    good->insertSP(tempRed->getLPoly());
     778    //Print("HIER2\n");
     779                                }
     780                            }   
     781                   
     782                        }
     783                    }
     784                }
     785                tempRed =   tempRed->getNext();
     786            }
     787            pIter(tempPoly);
     788        }
     789        tempMon =   tempMon->getNext();
     790    }
     791    // if there are reducers than reduce l
     792    if(NULL != good->getFirst()) {
     793        LNode* tempGood         =   good->getFirst();
     794        ideal reductionId       =   idInit(good->getLength(),1);
     795        int i;
     796        for(i=0;i<good->getLength();i++) {
     797            reductionId->m[i]   =   tempGood->getPoly();
     798            tempGood            =   tempGood->getNext();
     799        }
     800        poly temp   =   kNF(reductionId,currQuotient,l->getPoly());
     801        if(NULL != temp) {
     802            pNorm(temp);
     803            Print("NEW REDUCTION:  ");
     804            pWrite(temp);
     805            l->setPoly(temp);
     806            pWrite(l->getPoly());
     807            gPrev->insert(l->getLPoly());
     808            rules->print();
     809            criticalPair(gPrev,critPairs,lTag,rTag,rules);
     810        }
     811        else {
     812            reductionsToZero++;
     813            pDelete(&temp);
     814        }
     815        //pWrite(temp);
     816        for(i=0;i<IDELEMS(reductionId);i++) {
     817            reductionId->m[i]    =   NULL;
     818        }
     819        idDelete(&reductionId);
     820   
     821    }
     822    else {
     823        //pWrite(l->getPoly());
     824        gPrev->insert(l->getLPoly());
     825        Print("GENAU HIER:  ");
     826        pWrite(l->getPoly());
     827        criticalPair(gPrev,critPairs,lTag,rTag,rules);
     828    }
     829    // if there are "bad" reducers than try to compute new S-polynomials and rules
     830    if(NULL != bad->getFirst()) {
     831        LNode* tempBad  =   bad->getFirst();
     832        while(NULL != tempBad) {
     833            if(pDivisibleBy(tempBad->getPoly(),l->getPoly())) {
     834                u   =   pDivide(pHead(l->getPoly()),pHead(tempBad->getPoly()));
     835                pSetCoeff(u,nOne);
     836                if(pLmCmp(ppMult_qq(u,tempBad->getTerm()),l->getTerm()) != 0) {
     837                    // passing criterion2 ?
     838                    if(!criterion2(gPrev->getFirst()->getIndex(), u,tempBad,rules,rTag)) {
     839                        // passing criterion1 ?
     840                        if(!criterion1(gPrev,u,tempBad,lTag)) {
     841
     842                            rules->insert(tempBad->getIndex(),ppMult_qq(u,tempBad->getTerm()));
     843                            poly temp   =   pSub(ppMult_qq(u,tempBad->getPoly()),l->getPoly());
     844                            LNode* tempBadNew   =   new LNode(ppMult_qq(u,tempBad->getTerm()),tempBad->getIndex(),temp,rules->getFirst()->getRule());
     845                            //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
     846                            tempBadNew->setDel(1);
     847                            sPolyList->insertByLabel(tempBadNew);
     848                        }
     849                    }
     850                }
     851            }
     852            tempBad =   tempBad->getNext();
     853        }
     854    }
     855
     856}
    689857
    690858/*
    … …  
    703871        //int timer5  =   initTimer();
    704872        //startTimer();
     873        //Print("TOP REDUCTION:  ");
     874        //pWrite(l->getPoly());
    705875        tempRed  =   findReductor(l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag);
    706876        //timer5  =   getTimer();
    … …  
    710880            // if label of reductor is greater than the label of l we have to built a new element
    711881            // and add it to sPolyList
     882           
    712883            if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
    713884                // needed sinc pSub destroys the arguments!
    … …  
    738909                }
    739910            }
     911           
    740912            // label of reductor is smaller than the label of l, subtract reductor from l and delete the
    741913            // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
    … …  
    773945                pNorm(l->getPoly());
    774946                gPrev->insert(l->getLPoly());
     947                Print("TEMP RED == 0  ");
     948                pWrite(l->getPoly());
     949                pWrite(l->getTerm());
     950                rules->print();
    775951                criticalPair(gPrev,critPairs,lTag,rTag,rules);
    776952            }
    … …  
    813989            pNorm(red);
    814990            // check if both have the same label
    815             if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) == -1) {
     991            if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) != 0) {
    816992                // passing criterion2 ?
    817993                if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) {

  • kernel/f5gb.h

    r694257b r6b0aa2  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.h,v 1.36 2009-04-07 13:30:01 ederc Exp $ */
     4/* $Id: f5gb.h,v 1.37 2009-04-20 13:54:50 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    9898
    9999/*
     100========================================================================
     101reduction including subalgorithm topReduction() using Faugere's criteria
     102========================================================================
     103*/
     104inline void newReduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
     105                 ideal gbPrev);
     106
     107/*!
     108 * ================================================================================
     109 * searches for reducers of temp similar to the symbolic preprocessing of F4  and
     110 * divides them into a "good" and "bad" part:
     111 *
     112 * the "good" ones are the reducers which do not corrupt the label of temp, with
     113 * these the normal form of temp is computed
     114 *
     115 * the "bad" ones are the reducers which corrupt the label of temp, they are tested
     116 * later on for possible new rules and S-polynomials to be added to the algorithm
     117 * ================================================================================
     118 */
     119void findReducers(LNode* l, LList* sPolyList, LList* gPrev, CList* critPairs, RList* rules, LTagList* lTag, RTagList* rTag);
     120
     121/*
    100122=====================================================================================
    101123top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of

  • kernel/f5lists.cc

    r694257b r6b0aa2  
    431431
    432432 LTagNode::~LTagNode() {
    433     delete next;
    434433    delete data;   
    435434}
    … …  
    481480    LTagNode* first =   new LTagNode(l);
    482481    length          =   1;
     482}
     483
     484LTagList::~LTagList() {
     485    LTagNode* temp;
     486    while(first) {
     487        temp    =   first;
     488        first   =   first->getNext();
     489        delete  temp;
     490        //Print("%p\n",first);
     491    }
    483492}
    484493
    … …  
    889898}
    890899
     900void RNode::print() {
     901    RNode* temp  =   this;
     902    while(NULL != temp) {
     903        pWrite(temp->getRuleTerm());
     904        Print("%d\n\n",temp->getRuleIndex());
     905        temp    =   temp->getNext();
     906    }
     907}
     908
    891909/*
    892910====================================
    … …  
    936954}
    937955
     956void RList::print() {
     957    first->print();
     958}
     959
    938960/*
    939961=======================================

  • kernel/f5lists.h

    r694257b r6b0aa2  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5lists.h,v 1.16 2009-03-29 17:17:09 ederc Exp $ */
     4/* $Id: f5lists.h,v 1.17 2009-04-20 13:54:50 ederc Exp $ */
    55/*
    66* ABSTRACT: list interface
    … …  
    266266        int     getRuleIndex();
    267267        poly    getRuleTerm();
     268        void    print();
    268269};
    269270
    … …  
    286287        RNode*  getFirst();
    287288        Rule*   getRule();
     289        void    print();
    288290};
    289291
Note: See TracChangeset for help on using the changeset viewer.