Changeset e90881 in git


Ignore:
Timestamp:
Mar 29, 2009, 7:17:09 PM (14 years ago)
Author:
Christian Eder
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')
Children:
c6512c014a0813cb992533ab4dd571597c561ea4
Parents:
53e33d93f45a825808d84cade536120482dc46c3
Message:
implemented deletion of known useless polynomials before the interreduction of gprev takes place


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

Legend:

Unmodified
Added
Removed

  • kernel/f5data.h

    r53e33d9 re90881  
    33*  Computer Algebra System SINGULAR     *
    44****************************************/
    5 /* $Id: f5data.h,v 1.9 2009-03-05 14:30:23 ederc Exp $ */
     5/* $Id: f5data.h,v 1.10 2009-03-29 17:17:09 ederc Exp $ */
    66/*
    77* ABSTRACT: labeled polynomial interface
    … …  
    3333        poly    polynomial;     //standard polynomial data
    3434        Rule*   _rule;
     35        bool    del;
    3536    public:
    3637        inline          LPoly(poly t, int i, poly p, Rule* r=NULL);
    … …  
    4344        inline  void    setRule(Rule* r);
    4445        inline  Rule*   getRule();
     46        inline  void    setDel(bool d);
     47        inline  bool    getDel();
    4548        inline  void    set(poly t, int i, poly p, Rule* r);
    4649        inline  LPoly*  get();
    … …  
    4952LPoly::LPoly(poly t,int i,poly p, Rule* r) {
    5053    set(t,i,p,r);
     54    del =   0;
    5155}
    5256
    … …  
    7175}
    7276
     77void LPoly::setDel(bool d) {
     78    del =   d;
     79}
     80
    7381poly LPoly::getPoly() {
    7482    return polynomial;
    … …  
    8593Rule* LPoly::getRule() {
    8694    return _rule;
     95}
     96
     97bool LPoly::getDel() {
     98    return del;
    8799}
    88100

  • kernel/f5gb.cc

    r53e33d9 re90881  
    2626#include "f5lists.h"
    2727#include "timer.h"
    28 int reductionsToZero   =  0;
    29 
     28int reductionsToZero    =   0;
     29int reductionTime       =   0;
     30int spolsTime           =   0;
     31int highestDegree       =   0;
    3032/*
    3133====================================================================
    … …  
    9193    // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
    9294    // in the list critPairs
    93     Print("END F5INC\n");
    9495    criticalPair(gPrev, critPairs, lTag, rTag, rules);
    9596    static LList* sPolyList        =   new LList();
    … …  
    108109        // NOTE: inside there is a second check of criterion 2 if new rules are
    109110        // added
     111        int timer4  =   initTimer();
     112        startTimer();
    110113        computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
     114        timer4  =   getTimer();
     115        Print("SPOLS TIMER: %d\n",timer4);
     116        spolsTime  =   spolsTime  +   timer4;
    111117        // DEBUG STUFF FOR SPOLYLIST
    112118        LNode* temp     =   sPolyList->getFirst();
    … …  
    117123        //}
    118124        // reduction process of new S-polynomials and also adds new critical pairs to critPairs
     125        int timer3  =   initTimer();
     126        startTimer();
    119127        reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
    120        
     128        timer3      =  getTimer();
     129        reductionTime = reductionTime + timer3;
     130        Print("REDUCTION TIMER: %d\n",timer3);
    121131        // DEBUG STUFF FOR GPREV
    122132        //temp    =   gPrev->getFirst();
    … …  
    173183    */
    174184    //gPrev->print();
     185    Print("COMPLETE REDUCTION TIME UNTIL NOW: %d\n",reductionTime);
     186    Print("COMPLETE SPOLS TIME UNTIL NOW:     %d\n",spolsTime);
    175187    return gPrev;
    176188}
    … …  
    510522                // the second component is tested only when it has the actual index, otherwise there is
    511523                // no new rule to test since the last test in subalgorithm criticalPair()
     524                if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) {
     525                    highestDegree   = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()));
     526                    //pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
     527                }   
    512528                if(temp->getLp2Index() == temp->getLp1Index()) {
    513529                    if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRule())) {
    … …  
    719735                    pNorm(temp);
    720736                    tempRed->setPoly(temp);
    721                     //pWrite(tempRed->getPoly());
     737                    tempRed->setDel(1);
    722738                    // for debugging
    723739                    //pWrite(tempRed->getPoly());
    … …  
    900916    //Print("LTAG BEGINNING: %p\n",lTag);
    901917   
    902     //DEBUGGING STUFF START
     918    // DEBUGGING STUFF START
    903919    //Print("NUMBER: %d\n",r->N);
    904     int* ev = new int[r->N];
    905     for(i=0;i<IDELEMS(id);i++) {
    906         pGetExpV(id->m[i],ev);
    907         pWrite(id->m[i]);
    908         Print("EXP1: %d\n",ev[1]);
    909         Print("EXP2: %d\n",ev[2]);
    910         Print("EXP3: %d\n\n",ev[3]);
    911     }
     920   
     921    //int* ev = new int[r->N];
     922    //int  ev2;
     923    //for(i=0;i<IDELEMS(id);i++) {
     924        //pGetExpV(id->m[i],ev);
     925        //ev2  =   pGetExp(id->m[i],1);
     926        //pWrite(id->m[i]);
     927        //Print("%d\n",ev2);
     928        //Print("EXP1: %d\n",ev[1]);
     929        //Print("EXP2: %d\n",ev[2]);
     930        //Print("EXP3: %d\n\n",ev[3]);
     931    //}
    912932    //delete ev;
    913     //DEBUGGING STUFF END
     933   
     934    /*DEBUGGING STUFF END */
    914935   
    915936    // first element in rTag is first element of rules which is NULL RNode,
    … …  
    957978        //pWrite(gPrevTag->getPoly());
    958979        gPrev   =   F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag);
     980        Print("%d\n",gPrev->count(gPrevTag->getNext()));
     981        Print("%d\n",gPrev->getLength());
    959982        //Print("____________________________________ITERATION STEP DONE________________________________________\n");
    960983       
    … …  
    963986    // computing new groebner basis gbPrev
    964987        if(gPrev->getLength() > gbLength) {
    965             ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
    966             LNode*  temp =   gPrevTag;
    967         //Print("%p\n",gPrevTag);   
    968         //Print("%p\n",gPrev->getLast());   
    969         //pWrite(temp->getPoly());
    970         //Print("LENGTH OF GPREV LIST: %d\n",gPrev->getLength());
    971         //Print("%d\n",gbLength);
    972         //Print("%d\n",gPrev->getLength()-gbLength-1);
    973             for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
    974                 //Print("YES\n");
    975                 temp        =   temp->getNext();
    976                 if(temp) {
    977                     //Print("%p\n",temp);
    978                     //pWrite(temp->getPoly());
    979                     //Print("%p\n",temp->getNext());
     988            if(i < IDELEMS(id)) {
     989                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
     990                LNode*  temp =   gPrevTag;
     991                int counter =   0;
     992                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
     993                    temp        =   temp->getNext();
     994                    if(0 == temp->getDel()) {
     995                        counter++;
     996                        gbAdd->m[j] =   temp->getPoly();
     997                    }
     998                        //if(1 == temp->getDel()) {
     999                        //    pWrite(temp->getPoly());
     1000                        //}
    9801001                }
    981                 gbAdd->m[j] =   temp->getPoly();
    982                 //pWrite(temp->getPoly());
    983             }
    984             //Print("HIER AUCH\n");
    985             gbPrev          =   idAdd(gbPrev,gbAdd);
    986            
    987            
     1002                if(counter != gPrev->count(gPrevTag->getNext())) {
     1003                    Print("----------------------------------WRONG COUNTING---------------------------\n");
     1004                }
     1005                    gbPrev          =   idAdd(gbPrev,gbAdd);
     1006                    //idShow(gbPrev);
     1007            }
     1008            else {
     1009                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
     1010                LNode*  temp =   gPrevTag;
     1011                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
     1012                    temp        =   temp->getNext();
     1013                    gbAdd->m[j] =   temp->getPoly();
     1014                }
     1015                gbPrev          =   idAdd(gbPrev,gbAdd);
     1016            }
    9881017            // interreduction stuff
    9891018            if(i<IDELEMS(id)) {
     1019                int timer2  =   initTimer();
     1020                startTimer();
    9901021                ideal tempId    =   kInterRed(gbPrev);
     1022               
    9911023                //idShow(tempId);
    9921024                gbPrev          =   tempId;
     1025                timer2  =   getTimer();
     1026                Print("Timer INTERREDUCTION: %d\n",timer2);
     1027                //idShow(gbPrev);
    9931028                //qsortDegree(&gbPrev->m[0],&gbPrev->m[IDELEMS(gbPrev)-1]);
    9941029                delete gPrev;
    … …  
    10351070                }
    10361071            }
    1037            
    10381072            gbLength    =   gPrev->getLength();
    10391073            //Print("HIER\n");
    … …  
    10531087        //Print("===================================================\n");
    10541088        //Print("JA\n");
     1089        Print("LENGTH OF GPREV: %d\n",gPrev->getLength());
    10551090    }
    10561091        //idShow(gbPrev);
    10571092    Print("\n\nNumber of zero-reductions:  %d\n",reductionsToZero);
    10581093    timer   =   getTimer();
     1094    Print("Highest Degree during computations: %d\n",highestDegree);
    10591095    Print("Time for computations: %d/1000 seconds\n",timer);
    10601096    //LNode* temp    =   gPrev->getFirst();
    … …  
    10671103    //delete rTag;
    10681104    //delete gPrev;
     1105    reductionTime   =   0;
     1106    spolsTime       =   0;
    10691107    return(gbPrev);
    10701108

  • kernel/f5lists.cc

    r53e33d9 re90881  
    151151}
    152152
     153inline LNode* LNode::insertByLabel(LNode* l) {
     154    //Print("ADDING SOLYS TO THE LIST\n");
     155    //Print("new element: ");
     156    //pWrite(t);
     157       if(NULL == this) { // || NULL == data) {
     158        l->next =   this;
     159        return l;
     160    }
     161    else {
     162         //Print("tested element1: ");
     163    //pWrite(this->getTerm());
     164        if(-1 == pLmCmp(l->getTerm(),this->getTerm())) {
     165            //Print("HIERDRIN\n");
     166            l->next =   this;
     167            //Print("%p\n",this);
     168            //Print("%p\n",newElement->next);
     169            return l;
     170        }
     171        else {
     172            LNode* temp = this;
     173            while(NULL != temp->next && NULL != temp->next->data) {
     174                //Print("tested element: ");
     175                //pWrite(temp->getTerm());
     176                if(-1 == pLmCmp(l->getTerm(),temp->next->getTerm())) {
     177                    l->next     =   temp->next;
     178                    temp->next  =   l;
     179                    return this;
     180                }
     181                else {
     182                    temp = temp->next;
     183                    //Print("%p\n",temp);
     184                    //Print("%p\n",temp->data);
     185                   
     186                    //Print("%p\n",temp->next);
     187                }
     188            }
     189        //Print("HIER\n");
     190            l->next     =   temp->next;
     191            temp->next  =   l;
     192            return this;
     193        }
     194    }
     195}
     196
    153197// deletes the first elements of the list with the same degree
    154198// only used for the S-polys, which are already sorted by increasing degree by CList
    … …  
    184228}
    185229
     230bool LNode::getDel() {
     231    return data->getDel();
     232}
     233
    186234// set the data from the LPoly saved in LNode
    187235void LNode::setPoly(poly p) {
    … …  
    199247void LNode::setNext(LNode* l) {
    200248    next    =   l;
     249}
     250
     251void LNode::setDel(bool d) {
     252    data->setDel(d);
    201253}
    202254
    … …  
    229281        pWrite(temp->getPoly());
    230282        Print("%p\n",temp->next);
     283        Print("DELETE? %d\n",temp->getDel());
    231284        temp = temp->next;
    232285    }
    … …  
    234287}
    235288
     289int LNode::count(LNode* l) {
     290    int nonDel  =   0;
     291    LNode* temp =   l;
     292    while(NULL != temp) {
     293        if(!temp->getDel()) {
     294            nonDel++;
     295            temp    =   temp->next;
     296        }
     297        else {
     298            temp    =   temp->next;
     299        }
     300    }
     301    return nonDel;
     302}
    236303
    237304/*
    … …  
    304371
    305372void LList::insertByLabel(LNode* l) {
    306     first = first->insertByLabel(l->getTerm(),l->getIndex(),l->getPoly(),l->getRule());
     373    first = first->insertByLabel(l);
    307374    length++;
    308375    //Print("LENGTH %d\n",length);
    … …  
    340407}
    341408
     409int LList::count(LNode* l) {
     410    return first->count(l);
     411}
    342412/*
    343413=======================================

  • kernel/f5lists.h

    r53e33d9 re90881  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5lists.h,v 1.15 2009-03-12 09:43:53 ederc Exp $ */
     4/* $Id: f5lists.h,v 1.16 2009-03-29 17:17:09 ederc Exp $ */
    55/*
    66* ABSTRACT: list interface
    … …  
    6060        // only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
    6161        LNode*  insertByLabel(poly t, int i, poly p, Rule* r);
     62        LNode*  insertByLabel(LNode* l);
    6263        // deletes the first elements of the list with the same degree
    6364        // get next & prev from current LNode
    … …  
    7374        int     getIndex();
    7475        Rule*   getRule();
     76        bool    getDel();
    7577        // set the data from the LPoly saved in LNode
    7678        void    setPoly(poly p);
    … …  
    7880        void    setIndex(int i);
    7981        void    setNext(LNode* l);
     82        void    setDel(bool d);
    8083        // test if for any list element the polynomial part of the data is equal to *p
    8184        bool    polyTest(poly* p);
    8285        LNode*  getNext(LNode* l);
    8386        void    print();
     87        int     count(LNode* l);
    8488};
    8589
    … …  
    117121        void    setFirst(LNode* l);
    118122        void    print();
     123        int     count(LNode* l);
    119124};
    120125
Note: See TracChangeset for help on using the changeset viewer.