Changeset 416ea2 in git for kernel/f5gb.cc


Ignore:
Timestamp:
Feb 16, 2009, 3:23:42 PM (15 years ago)
Author:
Christian Eder
Branches:
(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
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
File:
1 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}
Note: See TracChangeset for help on using the changeset viewer.