Changeset 416ea2 in git


Ignore:
Timestamp:
Feb 16, 2009, 3:23:42 PM (14 years ago)
Author:
Christian Eder
Branches:
(u'spielwiese', '828514cf6e480e4bafc26df99217bf2a1ed1ef45')
Children:
d59666cfeced5db8d8654b6ae282bedc5855d28f
Parents:
61d32c91fe3976149b9b30938476f2c3c1257eee
Message:
new try on reduction procedures, no longer list of completed elements, adding a "last" node to LLists for more flexibility using the lists


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

Legend:

Unmodified
Added
Removed

  • kernel/f5gb.cc

    r61d32c r416ea2  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.cc,v 1.28 2009-02-15 20:33:56 ederc Exp $ */
     4/* $Id: f5gb.cc,v 1.29 2009-02-16 14:23:42 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    8181    CList* critPairs        =   new CList();
    8282    CNode* critPairsMinDeg  =   new CNode();   
    83     LNode* sPolys           =   new LNode();
    8483    // computation of critical pairs with checking of criterion 1 and criterion 2
    8584    critPairs               =   criticalPair(gPrev, critPairs, lTag, rTag, rules);
    … …  
    9493        // critPairs->getMinDeg() deletes the first elements of minimal degree from
    9594        // critPairs, thus the while loop is not infinite.
     95        critPairs->print();
    9696        critPairsMinDeg =   critPairs->getMinDeg();
    9797        // adds all to be reduced S-polynomials in the list sPolyList and adds
    … …  
    108108            temp    =   temp->getNext();
    109109        }
    110         reducedLPolys   =   reduction(sPolyList, completed, gPrev, rules, lTag, rTag, gbPrev);
     110        //while(NULL != sPolyList->getFirst()->getLPoly()) {
     111            reduction(sPolyList, completed, gPrev, rules, lTag, rTag, gbPrev);
     112        //}
    111113    }
    112114    Print("HIER123\n");
    … …  
    122124    lTag->insert(gPrev->getFirst());
    123125    Print("COMPLETED FIRST IN F5INC: \n");
    124     pWrite(completed->getFirst()->getPoly());
    125126    return gPrev;
    126127}
    … …  
    374375========================================================================
    375376*/
    376 LList* reduction(LList* sPolyList, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
     377void reduction(LList* sPolyList, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
    377378                 ideal gbPrev) {
    378379    Print("##########################################In REDUCTION!########################################\n");
    379     // temporary normal form and zero polynomial for testing
    380     static poly tempNF =   pInit();
    381     TopRed* ret =   new TopRed();
    382     // compute only if there are any S-polynomials to be reduced
    383     Print("LENGTH OF SPOLYLIST: %d\n",sPolyList->getLength());
    384     if(NULL != sPolyList->getFirst()->getLPoly()) {
     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());
     385    // check if sPolyList has any elements
     386    // NOTE: due to initialization sPolyList always has a default NULL element
     387    while(sPolyList->getLength() > 1) {
     388        // temp is the first element in the sPolyList which should be reduced
     389        // due to earlier sorting this is the element of minimal degree AND
     390        // minimal label
    385391        LNode* temp =   sPolyList->getFirst();
    386                 Print("SPOLYLIST FIRST START: %p\n",temp);                     
    387         while(NULL != temp && NULL != temp->getLPoly()) {
    388             if(NULL != completed->getFirst()->getLPoly()) {
    389                                 Print("BIS HIERHIN UND NICHT WEITER\n");       
    390                                 Print("%p\n",completed->getFirst());
    391                                 pWrite(completed->getFirst()->getPoly());
    392                 Print("ADDRESS OF TERM: %p\n",completed->getFirst()->getTerm());
    393                 pWrite(completed->getFirst()->getTerm());
    394                         }
    395                         tempNF = kNF(gbPrev,currQuotient,temp->getPoly()); 
     392        // delete the above first element from sPolyList, temp will be either reduced to
     393        // zero or added to gPrev, but never come back to sPolyList
     394        sPolyList->setFirst(temp->getNext());
     395        pWrite(temp->getPoly());
     396        poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
     397        Print("LENGTH: %d\n",sPolyList->getLength());
     398        pWrite(tempNF);
     399        pWrite(temp->getPoly());
     400        if(NULL != tempNF) {
     401            // write the reduced polynomial in temp
    396402            temp->setPoly(tempNF);
    397             // test if normal form is zero
    398             if(NULL == tempNF) {
    399                 reductionsToZero++;
    400                 // TODO: sPolyList -> delete first element of list as it is zero and done
    401                 // TODO: problem is that when deleting the first element, the origin of the
    402                 // corresponding rule is deleted!
    403                 Print("LENGTH OF SPOLYLIST: %d\n",sPolyList->getLength());
    404                 //temp    =   temp->getNext();
    405                 //sPolyList->setFirst(temp);
    406                 Print("///////////////////////////////////////////////////////////////////////\n");
    407                 Print("SPOLYLIST FIRST ELEMENT: %p\n",temp);
    408                 //Print("%p\n",temp->getLPoly());
    409                 Print("///////////////////////////////////////////////////////////////////////\n");
    410             }
    411             else {
    412                 ret =   topReduction(temp, completed, gPrev, rules, lTag, rTag);
    413                 // in topReduction() the investigated first element of sPolyList will be deleted after its
    414                 // reduction has finished => the next to be investigated element is the newly first element
    415                 // in sPolyList => the while loop is finite
    416                 // first possible after implementation of topReduction(): temp = sPolyList->getFirst();
    417                
    418                                 completed   =   ret->getCompleted();
    419                 Print("ZURUECK IN REDUCTION COMPLETED TERM ADDRESS: %p\n",completed->getFirst()->getTerm());
    420                 pWrite(completed->getFirst()->getTerm());
    421                 if(NULL != ret->getToDo()) {
    422                     sPolyList->insertByLabel(ret->getToDo()->getFirst());
    423                 }
    424             }
    425             if(NULL != temp) {
    426                 sPolyList->setFirst(temp->getNext());
    427                 temp    =       sPolyList->getFirst();
    428             }
    429             else {
    430                 return completed;
    431             }
    432     Print("ADDRESS OF TERM: %p\n",completed->getFirst()->getTerm());
    433 
    434                         //pWrite(completed->getFirst()->getPoly());
    435                         Print("SPOLYLIST FIRST NOW: %p\n",temp);                       
    436             //pWrite(temp->getPoly());
    437         }
    438     }
    439     Print("RETURN VALUE OF REDUCTION(): %p\n",completed->getFirst());
    440     Print("ADDRESS OF TERM: %p\n",completed->getFirst()->getTerm());
    441     Print("ADDRESS OF POLY: %p\n",completed->getFirst()->getPoly());
    442     pWrite(completed->getFirst()->getPoly());
    443     return completed;
     403            // try further reductions of temp with polynomials in gPrev
     404            // with label index = current label index: this is done such that there
     405            // is no label corruption during the reduction process
     406            topReduction(temp,completed,gPrev,rules,lTag,rTag);
     407        }
     408    }
    444409}   
    445410
    … …  
    452417=====================================================================================
    453418*/
    454 TopRed* topReduction(LNode* l, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag) {
     419void topReduction(LNode* l, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag) {
    455420    Print("##########################################In topREDUCTION!########################################\n");
    456                         Print("L BEGIN TOP RED: %p\n",l->getLPoly());
    457             pWrite(l->getPoly());
    458             pWrite(l->getTerm());
    459             Print("ADDRESS OF TERM: %p\n",l->getTerm());
    460             //pWrite(completed->getFirst()->getPoly());
    461             LNode* red   =   new LNode();
    462    
    463     do {
    464         red  =   findReductor(l, completed, gPrev, rules, lTag, rTag,
    465                               red->getGPrevRedCheck(), red->getCompletedRedCheck());
    466         // no reductor found
    467         if(NULL == red) {
    468             completed->insert(l->getLPoly());
    469             Print("AT INSERTION IN COMPLETED ADDRESS OF TERM: %p\n",l->getTerm());
    470             Print("AT INSERTION IN COMPLETED ADDRESS OF TERM II: %p\n",completed->getFirst()->getTerm());
    471             pWrite(completed->getFirst()->getTerm());
    472             TopRed* ret =   new TopRed(completed,NULL);
    473             return ret;
    474         }
    475         // reductor found
    476         else {
    477             red->setPoly(ppMult_nn(red->getPoly(),pGetCoeff(l->getPoly())));
    478         }           
    479     } while(NULL != red);
    480 }
    481 
     421
     422}
    482423
    483424
    … …  
    488429*/
    489430LNode* findReductor(LNode* l,LList* completed,LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag,
    490                     LNode* gPrevRedCheck, LNode* completedRedCheck) {
    491     Print("HIER FIND REDUCTOR\n");
    492         number nOne     =   nInit(1);
    493     poly u          =   pOne();
    494     poly redPoly    =   pOne();
    495     poly t          =   pHead(l->getPoly());
    496     LNode* temp     =   new LNode();
    497     // setting starting point for search of reductors in gPrev
    498     if(NULL != gPrevRedCheck) {
    499         temp =   gPrevRedCheck;
    500     }
    501     else {
    502         temp =   gPrev->getFirst();
    503     }
    504     // search only for reductors with the same index, as reductions with elements of lower
    505     // index were already done in reduction() beforehand
    506     while(NULL != temp && NULL != temp->getLPoly() && temp->getIndex() == l->getIndex()) {
    507         // divides head term t?
    508         if(pLmDivisibleByNoComp(temp->getPoly(),t)) {
    509             u       =   pDivide(t,pHead(temp->getPoly()));
    510             pSetCoeff(u,nOne);
    511             // multiply reductor with factor and normalize it, i.e. LC = 1
    512             redPoly =   ppMult_qq(u,temp->getPoly());
    513             pNorm(redPoly);
    514             u       =   ppMult_qq(u,temp->getTerm());
    515             pSetCoeff(u,nOne);
    516             Print("IN FIND REDUCTOR:  ");
    517             pWrite(u);
    518             pWrite(redPoly);
    519             // same label? NOTE: also used to
    520             if(pLmCmp(u,l->getTerm()) != 0) {
    521                 // passing criterion 2?
    522                 if(!criterion2(&u,temp, rules, rTag)) {
    523                     // passing criterion 1?
    524                     if(!criterion1(&u,temp,lTag)) {
    525                         // set tag findRedCheck such that you can start at this point when the
    526                         // next time a reductor is searched for in findReductor()
    527                         LNode* red      =   new LNode(u,temp->getIndex(),redPoly,NULL,temp->getNext(),completedRedCheck);
    528                         return red;
    529                     }
    530                 }
    531             }
    532         }
    533         temp    =   temp->getNext();
    534     }
    535     if(0 != completed->getLength()) {
    536     // do the same as above now for the elements in completed
    537     if(NULL != completedRedCheck) {
    538         temp    =   completedRedCheck;
    539     }
    540     else {
    541         Print("HIER DRIN\n");
    542         temp    =   completed->getFirst();
    543         pWrite(temp->getTerm());
    544     }
    545     // search only for reductors with the same index, as reductions with elements of lower
    546     // index where already done in reduction() beforehand
    547     while(NULL != temp && NULL != temp->getLPoly() && NULL != temp->getPoly()) {
    548         // divides head term t?
    549         if(pLmDivisibleByNoComp(temp->getPoly(),t)) {
    550             u       =   pDivide(t,pHead(temp->getPoly()));
    551             pSetCoeff(u,nOne);
    552             pWrite(u);
    553             redPoly =   ppMult_qq(u,temp->getPoly());
    554             pWrite(temp->getPoly());
    555             pWrite(temp->getTerm());
    556             u       =   ppMult_qq(u,temp->getTerm());
    557             // same label? NOTE: also used to
    558         if(pLmCmp(u,l->getTerm()) != 0) {
    559                 // passing criterion 2?
    560                 if(!criterion2(&u,temp, rules, rTag)) {
    561                     // passing criterion 1?
    562                     if(!criterion1(&u,temp,lTag)) {
    563                         // set tag findRedCheck such that you can start at this point when the
    564                         // next time a reductor is searched for in findReductor()
    565                         LNode* red      =   new LNode(u,temp->getIndex(),redPoly,NULL,gPrevRedCheck,temp->getNext());
    566                         return red;
    567                     }
    568                 }
    569             }
    570         }
    571         temp    =   temp->getNext();
    572     }
    573     }
    574     // no reductor found
    575     Print("HIER DU NULL!\n");
     431                    LNode* gPrevRedCheck) {
     432   Print("HIER DU NULL!\n");
    576433    return NULL;
    577434}

  • kernel/f5gb.h

    r61d32c r416ea2  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.h,v 1.25 2009-02-12 12:43:31 ederc Exp $ */
     4/* $Id: f5gb.h,v 1.26 2009-02-16 14:23:42 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    7979========================================================================
    8080*/
    81 LList* reduction(LList* sPolyList, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
     81void reduction(LList* sPolyList, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
    8282                 ideal gbPrev);
    8383
    … …  
    8888=====================================================================================
    8989*/
    90 TopRed* topReduction(LNode* l, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag);
     90void topReduction(LNode* l, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag);
    9191
    9292/*
    … …  
    9696*/
    9797LNode* findReductor(LNode* l,LList* completed,LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag,
    98                     LNode* gPrevRedCheck, LNode* completedRedCheck);
     98                    LNode* gPrevRedCheck);
    9999
    100100/*

  • kernel/f5lists.cc

    r61d32c r416ea2  
    3030    next                =   NULL;
    3131    gPrevRedCheck       =   NULL;
    32     completedRedCheck   =   NULL;
    3332}
    3433 LNode::LNode(LPoly* lp) {
    … …  
    3635    next                =   NULL;
    3736    gPrevRedCheck       =   NULL;
    38     completedRedCheck   =   NULL;
    3937}
    4038       
    … …  
    4442    next                =   l;
    4543    gPrevRedCheck       =   NULL;
    46     completedRedCheck   =   NULL;
    47 }
    48 
    49 LNode::LNode(poly t, int i, poly p, Rule* r, LNode* gPCheck, LNode* CompCheck) {
     44}
     45
     46LNode::LNode(poly t, int i, poly p, Rule* r, LNode* gPCheck) {
    5047LPoly* lp           =   new LPoly(t,i,p,r);
    5148data                =   lp;
    5249next                =   NULL;
    5350gPrevRedCheck       =   gPCheck;
    54 completedRedCheck   =   CompCheck;
    5551}
    5652       
    57 LNode::LNode(poly t, int i, poly p, Rule* r, LNode* gPCheck, LNode* CompCheck, LNode* l) {
     53LNode::LNode(poly t, int i, poly p, Rule* r, LNode* gPCheck, LNode* l) {
    5854    LPoly* lp           =   new LPoly(t,i,p,r);
    5955    data                =   lp;
    6056    next                =   l;
    6157    gPrevRedCheck       =   gPCheck;
    62     completedRedCheck   =   CompCheck;
    6358}
    6459
    … …  
    6762    next                =   ln->getNext();
    6863    gPrevRedCheck       =   NULL;
    69     completedRedCheck   =   NULL;
    7064}
    7165       
    7266LNode::~LNode() {
    73     delete next;
     67    //delete next;
    7468    delete gPrevRedCheck;
    75     delete completedRedCheck;
    7669    delete data;   
    7770}
    … …  
    8578       
    8679LNode* LNode::insert(poly t, int i, poly p, Rule* r) {
    87     LNode* newElement = new LNode(t, i, p, r, NULL, NULL, this);
     80    LNode* newElement = new LNode(t, i, p, r, NULL, this);
    8881    return newElement;
    8982}
    90        
     83
     84LNode* 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
    9189// insert new elemets to the list w.r.t. increasing labels
    9290// only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
    … …  
    151149}
    152150
    153 LNode* LNode::getCompletedRedCheck() {
    154     return completedRedCheck;
    155 }
    156 
    157151// set the data from the LPoly saved in LNode
    158152void LNode::setPoly(poly p) {
    … …  
    170164void LNode::setGPrevRedCheck(LNode* l) {
    171165    gPrevRedCheck   =   l;
    172 }
    173 
    174 void LNode::setCompletedRedCheck(LNode* l) {
    175     completedRedCheck   =   l;
    176166}
    177167
    … …  
    200190LList::LList() {
    201191    first   =   new LNode();
     192    last    =   first;
    202193    length  =   0;
    203194}
    … …  
    205196LList::LList(LPoly* lp) {
    206197    first   =   new LNode(lp);
     198    last    =   first;
    207199    length  =   1;
    208200}
    … …  
    210202LList::LList(poly t,int i,poly p,Rule* r) {
    211203    first   =   new LNode(t,i,p,r);
     204    last    =   first;
    212205    length  =   1;
    213206}
    … …  
    228221}
    229222
     223void LList::append(poly t, int i, poly p, Rule* r) {
     224    last    =   last->append(t,i,p,r);
     225    length++;
     226}
     227
    230228void LList::insertByLabel(poly t, int i, poly p, Rule* r) {
    231229    first = first->insertByLabel(t,i,p,r);
    … …  
    248246LNode* LList::getFirst() {
    249247    return first;
     248}
     249
     250LNode* LList::getLast() {
     251    return last;
    250252}
    251253
    … …  
    262264    first       =   l;
    263265    delete(temp);
     266    length--;
    264267}
    265268

  • kernel/f5lists.h

    r61d32c r416ea2  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5lists.h,v 1.8 2009-02-11 21:24:08 ederc Exp $ */
     4/* $Id: f5lists.h,v 1.9 2009-02-16 14:23:42 ederc Exp $ */
    55/*
    66* ABSTRACT: list interface
    … …  
    4040        LNode*  next;
    4141        LNode*  gPrevRedCheck;
    42         LNode*  completedRedCheck;
    4342    public:
    4443        // generating new list elements from the labeled / classical polynomial view
    … …  
    4645                LNode(LPoly* lp);
    4746                LNode(LPoly* lp, LNode* l);
    48                 LNode(poly t, int i, poly p, Rule* r=NULL, LNode* gPCheck=NULL, LNode* CompCheck=NULL);
    49                 LNode(poly t, int i, poly p, Rule* r, LNode* gPCheck, LNode* CompCheck, LNode* l);
     47                LNode(poly t, int i, poly p, Rule* r=NULL, LNode* gPCheck=NULL);
     48                LNode(poly t, int i, poly p, Rule* r, LNode* gPCheck, LNode* l);
    5049                LNode(LNode* ln);
    5150                ~LNode();
    … …  
    5352        LNode*  insert(LPoly* lp);
    5453        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);
    5556        // insert new elements to the list with resp. to increasing labels
    5657        // only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
    … …  
    6970        Rule*   getRule();
    7071        LNode*  getGPrevRedCheck();
    71         LNode*  getCompletedRedCheck();
    7272        // set the data from the LPoly saved in LNode
    7373        void    setPoly(poly p);
    … …  
    7575        void    setIndex(int i);
    7676        void    setGPrevRedCheck(LNode* l);
    77         void    setCompletedRedCheck(LNode* l);
    7877        // test if for any list element the polynomial part of the data is equal to *p
    7978        bool    polyTest(poly* p);
    … …  
    9089    private:
    9190        LNode*  first;
     91        LNode*  last;
    9292        int     length;
    9393    public:
    … …  
    101101        void    insertByLabel(poly t, int i, poly p, Rule* r = NULL);
    102102        void    insertByLabel(LNode* l);
     103        void    append(poly t, int i, poly p, Rule* r=NULL);
    103104        void    deleteByDeg();
    104105        bool    polyTest(poly* p);
    105         LNode*  getFirst();
     106        LNode*  getFirst();
     107        LNode*  getLast();
    106108        LNode*  getNext(LNode* l);
    107109        int     getLength();
Note: See TracChangeset for help on using the changeset viewer.