Changeset c3efd3b in git for kernel


Ignore:
Timestamp:
May 13, 2009, 6:55:03 PM (15 years ago)
Author:
Christian Eder
Branches:
(u'spielwiese', '2a584933abf2a2d3082034c7586d38bb6de1a30a')
Children:
1f360ddcb028459e8e23efc70ca75275fbc54b7d
Parents:
cb6cdaaa807284703d4425ec7714979ea30194ae
Message:
first bucket stuff implemented, timings for the preprocessing given


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

Legend:

Unmodified
Added
Removed

  • kernel/f5gb.cc

    rcb6cda rc3efd3b  
    1414#include "polys.h"
    1515#include "p_polys.h"
     16#include "p_Procs.h"
    1617#include "ideals.h"
    1718#include "febase.h"
    … …  
    555556void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) {
    556557    CNode* temp         =   first;
    557     poly sp      =   pInit();
     558    poly sp     =   pInit();
     559    number sign =   nInit(-1);   
    558560    //Print("###############################IN SPOLS##############################\n");
    559561    //first->print();
    … …  
    573575                    if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRule())) {
    574576                        // computation of S-polynomial
    575                         sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
    576                                          ppMult_qq(temp->getT2(),temp->getLp2Poly()));
     577                        poly p1 =   temp->getLp1Poly();
     578                        poly p2 =   temp->getLp2Poly();
     579                        pIter(p1);
     580                        pIter(p2);
     581
     582                        sp  =   pAdd(ppMult_qq(temp->getT1(),p1),pMult_nn(ppMult_qq(temp->getT2(),p2),sign)); 
     583                        //sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
     584                        //                 ppMult_qq(temp->getT2(),temp->getLp2Poly()));
    577585                        //Print("BEGIN SPOLY1\n====================\n");
    578586                        pNorm(sp);
    … …  
    771779*/
    772780void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, CList* critPairs, RList* rules, LTagList* lTag, RTagList* rTag) {
     781    int timerRed        =   0;
     782    number sign         =   nInit(-1);
    773783    LList* good         =   new LList();
    774784    LList* bad          =   new LList();
    … …  
    781791    //Print("IN FIND REDUCERS:  ");
    782792    //pWrite(l->getPoly());
    783    
     793    tempPoly    =   pCopy(l->getPoly());
     794    //tempMon->setPoly(tempPoly);
    784795    while(NULL != tempMon) {
    785796        // iteration over all monomials in tempMon
    786         tempPoly   =   pCopy(l->getPoly());
     797        //tempPoly    =   pCopy(l->getPoly());
     798        //tempPoly    =   tempMon->getPoly();
     799        //pWrite(tempPoly);
    787800        //Print("______________________NEW POLYNOMIAL TESTED IN MONOMIALS_______________________\n");
    788        
     801        //kBucket* bucket  =   kBucketCreate();
     802        //kBucketInit(bucket,tempPoly,0);
     803        //tempPoly    =   kBucketGetLm(bucket);
     804        //pWrite(tempPoly);
    789805        while(NULL != tempPoly) {
    790806            // iteration of all elements in gPrev of the current index
    … …  
    793809            //Print("%p\n",tempPoly);
    794810            //pWrite(tempPoly);
    795             pNorm(tempPoly);
     811            //Print("RED\n");
     812            //Print("L:  ");
     813            //pWrite(l->getPoly());
     814            //pNorm(tempPoly);
    796815            //pWrite(l->getTerm());
    797816            tempRed =   gPrev->getFirst();
    … …  
    804823                //pWrite(tempPoly);
    805824                //Print("DIVISIBLE? %d\n",pDivisibleBy(tempRed->getPoly(),tempPoly));
    806                     if(pDivisibleBy(tempRed->getPoly(),tempPoly)) {
    807                     u   =   pDivide(pHead(tempPoly),pHead(tempRed->getPoly()));
    808                     pSetCoeff(u,nOne);
    809                     poly red =   ppMult_qq(u,tempRed->getPoly());
    810                     pNorm(red);
     825                if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
     826                    u   =   pDivideM(pHead(tempPoly),pHead(tempRed->getPoly()));
     827                    //number n    =  pGetCoeff(tempPoly) / pGetCoeff
     828                    //Print("U: ");
     829                    //pWrite(u);
     830                    //pSetCoeff(u,nOne);
     831                    //pWrite(u);
     832                    //poly red =   ppMult_qq(u,tempRed->getPoly());
     833                    //pNorm(red);
    811834                    //pWrite(red);
    812835                    // check if both have the same label
    … …  
    822845                                    //Print("%d\n",tempRed->getIndex());
    823846                                    //Print("+++++++++++++LIST OF MONOMIALS1+++++++++++++++++\n");
    824                                     poly tempRedPoly    =  ksOldSpolyRedNew(ppMult_qq(u,tempRed->getPoly()),pHead(ppMult_qq(u,tempRed->getPoly())));
     847                                    //poly tempRedPoly    =  ksOldSpolyRedNew(ppMult_qq(u,tempRed->getPoly()),pHead(ppMult_qq(u,tempRed->getPoly())));
     848                                    poly tempRedPoly    =   tempRed->getPoly();
     849                                    //Print("TEMPREDPOLY: \n");
     850                                    //pWrite(tempRedPoly);
     851                                    pIter(tempRedPoly);
     852                                    //pWrite(tempRedPoly);
     853                                    //Print("U: ");
     854                                    //pWrite(u);
     855                                    tempRedPoly =   ppMult_qq(u,tempRedPoly);
     856                                    //Print("TEMPPOLYRED\n");
     857                                    //pWrite(tempRedPoly);
     858                                    pMult_nn(tempRedPoly,sign);
     859                                    //pWrite(tempRedPoly);
     860                                    // throw away head monomial as it cancels when computing "bucket - u * tempRedPoly"
     861                                    //Print("MULTIPLICATION DONE: \n");
     862                                    //pWrite(tempRedPoly);
     863                                    //pWrite(ppMult_qq(u,tempRed->getPoly()));
     864                                    //int lRedPoly   =   pLength(tempRedPoly);
     865                                    //kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lRedPoly);
     866                                    //pWrite(tempPoly);
     867                                    //pWrite(tempRedPoly);
    825868                                    pAdd(tempPoly,tempRedPoly);
     869                                    //Print("MERGED POLYNOMIAL: ");
     870                                    //pWrite(tempPoly);
    826871                                    //Print("REDUCTION STEP: \n");
    827872                                    //pWrite(l->getPoly());
    … …  
    832877                                    //Print("+++++++++++++LIST OF MONOMIALS2+++++++++++++++++\n");
    833878                                    //monomials->print();
     879
    834880                                    good->insert(pOne(),1,ppMult_qq(u,tempRed->getPoly()),NULL);
    835881                                    //Print("GOOD ELEMENTS: \n");
    … …  
    848894                                if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
    849895                                    //Print("BAD REDUCTION STUFF\n");
    850                                     //pWrite(tempRed->getPoly());
     896                                    //pWrite(ppMult_qq(u,tempRed->getPoly()));
    851897                                    //pWrite(ppMult_qq(u,tempRed->getTerm()));
     898                                    //rules->print();
    852899                                    //rules->insert(tempRed->getIndex(),ppMult_qq(u,tempRed->getTerm()));
    853900                                    //l->setTerm(ppMult_qq(u,tempRed->getTerm()));
     901                                    //l->setRule(rules->getFirst()->getRule());
     902                                    //poly tempRedPoly    =  ksOldSpolyRedNew(ppMult_qq(u,tempRed->getPoly()),pHead(ppMult_qq(u,tempRed->getPoly())));
     903                                    //pAdd(tempPoly,tempRedPoly);
    854904                                    //Print("NEW TERM: ");
    855905                                    //pWrite(l->getTerm());
    … …  
    857907                                    //rules->print();
    858908                                    bad->insert(tempRed->getLPoly());
    859                                     //good->insertSP(pOne(),1,ppMult_qq(u,tempRed->getPoly()),NULL);
     909                                    //good->insert(pOne(),1,ppMult_qq(u,tempRed->getPoly()),NULL);
    860910                                    //pWrite(tempRed->getPoly());
    861911                                    //sleep(5);
    … …  
    871921                                    //Print("%d\n",tempRed->getIndex());
    872922                                    //Print("+++++++++++++LIST OF MONOMIALS1+++++++++++++++++\n");
    873                                     poly tempRedPoly    =  ksOldSpolyRedNew(ppMult_qq(u,tempRed->getPoly()),pHead(ppMult_qq(u,tempRed->getPoly())));
     923                                    //pIter(tempRedPoly);
     924                                    poly tempRedPoly    =   tempRed->getPoly();
     925                                    // throw away head monomial as it cancels when computing "bucket - u * tempRedPoly"
     926                                    pIter(tempRedPoly);
     927                                    tempRedPoly =   ppMult_qq(u,tempRedPoly);
     928                                    pMult_nn(tempRedPoly,sign);
     929                                    //Print("HERE\n");
     930                                    //int lRedPoly    =   pLength(tempRedPoly);
     931                                    //kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lRedPoly);
     932                                    //poly tempRedPoly    =  ksOldSpolyRedNew(ppMult_qq(u,tempRed->getPoly()),pHead(ppMult_qq(u,tempRed->getPoly())));
     933                                    timerRed    =   initTimer();
     934                                    startTimer();
    874935                                    pAdd(tempPoly,tempRedPoly);
     936                                    timerRed    =   getTimer();
     937                                    reductionTime   = reductionTime + timerRed;
     938                                    //Print("MERGED POLYNOMIAL: ");
     939                                    //pWrite(tempPoly);
    875940                                    //Print("REDUCTION STEP: \n");
    876941                                    //pWrite(l->getPoly());
    … …  
    888953                                }
    889954                            }   
    890                    
    891955                        }
    892956                    }
    … …  
    898962                //pWrite(tempRed->getPoly());
    899963            }
     964            //pWrite(tempPoly);
    900965            pIter(tempPoly);
     966            //Print("ITERATION\n");
     967            //Print("L:  ");
     968            //pWrite(l->getPoly());
    901969            //Print("ITERATION:  ");
    902970            //pWrite(tempPoly);
    … …  
    914982                // if there are reducers than reduce l
    915983    if(NULL != good->getFirst()) {
     984       
     985        //Print("TO BE REDUCED:\n");
     986        //pWrite(l->getPoly());
     987        LNode* tempGood =   good->getFirst();
     988        kBucket* bucket =   kBucketCreate();
     989        kBucketInit(bucket,l->getPoly(),0);
     990        //Print("\nREDUCERS: \n");
     991        while(NULL != tempGood) {
     992            //pWrite(tempGood->getPoly());
     993            int lTempGood   =   pLength(tempGood->getPoly());
     994            kBucket_Minus_m_Mult_p(bucket,pOne(),tempGood->getPoly(),&lTempGood);
     995            //Print("KBUCKET:  ");
     996            //pWrite(kBucketGetLm(bucket));
     997            tempGood    =   tempGood->getNext();
     998        }
     999        poly temp   =  kBucketClear(bucket);
     1000        //pWrite(temp);
     1001        //Print("\n");
     1002        if(NULL != temp) {
     1003            pNorm(temp);
     1004            //Print("NEW REDUCTION:  ");
     1005            //pWrite(temp);
     1006            l->setPoly(temp);
     1007            //Print("ELEMENT ADDED TO GPREV1: ");
     1008            //pWrite(l->getPoly());
     1009            //pWrite(l->getTerm());
     1010            //Print("%p\n",gPrev->getLast());
     1011            //pWrite(gPrev->getLast()->getPoly());
     1012            gPrev->insert(l->getLPoly());
     1013            //Print("%p\n",gPrev->getLast());
     1014            //pWrite(gPrev->getLast()->getPoly());
     1015            //rules->print();
     1016            criticalPair(gPrev,critPairs,lTag,rTag,rules);
     1017            //Print("LIST OF CRITICAL PAIRS:    \n");
     1018            //critPairs->print();
     1019            //gPrev->print();
     1020        }
     1021        else {
     1022            reductionsToZero++;
     1023            //Print("ZERO REDUCTION\n");
     1024            pDelete(&temp);
     1025        }
     1026         
     1027        /*
    9161028        //Print("HIER IN GOOD REDUCTION\n");
    9171029        LNode* tempGood         =   good->getFirst();
    … …  
    9191031        int i;
    9201032        //Print("\n\n");
     1033        //good->print();
    9211034        for(i=0;i<good->getLength();i++) {
    9221035            reductionId->m[i]   =   tempGood->getPoly();
    … …  
    9311044        //idDelMultiples(reductionId);
    9321045        //idShow(reductionId);
     1046        //pWrite(l->getPoly());
    9331047        poly temp   =   kNF(reductionId,currQuotient,l->getPoly());
    9341048        //pWrite(temp);
    … …  
    9681082        idDelete(&reductionId);
    9691083        //Print("HIER\n");
    970     }
     1084        */
     1085
     1086    }
     1087   
     1088
    9711089    else {
    9721090        //pWrite(l->getPoly());
    … …  
    10421160
    10431161}
     1162
     1163/*
     1164=======================================================================================
     1165merging 2 polynomials p & q without requiring that all monomials of p & q are different
     1166if there are equal monomials in p & q only one of these monomials (always that of p!)
     1167is taken into account
     1168=======================================================================================
     1169
     1170poly p_MergeEq_q(poly p, poly q, const ring r) {
     1171  assume(p != NULL && q != NULL);
     1172  p_Test(p, r);
     1173  p_Test(q, r);
     1174#if PDEBUG > 0
     1175  int l = pLength(p) + pLength(q);
     1176#endif
     1177
     1178  spolyrec rp;
     1179  poly a = &rp;
     1180  DECLARE_LENGTH(const unsigned long length = r->CmpL_Size);
     1181  DECLARE_ORDSGN(const long* ordsgn = r->ordsgn);
     1182
     1183  Top:     // compare p and q w.r.t. monomial ordering
     1184  p_MemCmp(p->exp, q->exp, length, ordsgn, goto Equal, goto Greater , goto Smaller);
     1185
     1186  Equal:
     1187  a =   pNext(a)    =   p;
     1188  pIter(p);
     1189  pIter(q);
     1190  if(NULL == p) {
     1191      if(NULL == q) {
     1192          goto Finish;
     1193      }
     1194      else {
     1195          pNext(a)  =   q;
     1196          goto Finish;
     1197      }
     1198  }
     1199  goto Top;
     1200
     1201  Greater:
     1202  a = pNext(a) = p;
     1203  pIter(p);
     1204  if (p==NULL) { pNext(a) = q; goto Finish;}
     1205  goto Top;
     1206
     1207  Smaller:
     1208  a = pNext(a) = q;
     1209  pIter(q);
     1210  if (q==NULL) { pNext(a) = p; goto Finish;}
     1211  goto Top;
     1212
     1213  Finish:
     1214
     1215  p_Test(pNext(&rp), r);
     1216#if PDEBUG > 0
     1217  pAssume1(l - pLength(pNext(&rp)) == 0);
     1218#endif
     1219  return pNext(&rp);
     1220}
     1221*/
    10441222
    10451223/*
    … …  
    14401618        //idShow(gbPrev);
    14411619    }
     1620    Print("\n\nADDING TIME IN REDUCTION: %d\n\n",reductionTime);
    14421621    Print("\n\nNumber of zero-reductions:  %d\n",reductionsToZero);
    14431622    timer   =   getTimer();

  • kernel/f5gb.h

    rcb6cda rc3efd3b  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.h,v 1.38 2009-05-04 13:30:53 ederc Exp $ */
     4/* $Id: f5gb.h,v 1.39 2009-05-13 16:55:03 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    127127
    128128/*
     129=======================================================================================
     130merging 2 polynomials p & q without requiring that all monomials of p & q are different
     131if there are equal monomials in p & q only one of these monomials (always that of p!)
     132is taken into account
     133=======================================================================================
     134
     135poly p_MergeEq_q(poly p, poly q, const ring r);
     136*/   
     137/*
    129138=====================================================================
    130139subalgorithm to find a possible reductor for the labeled polynomial l

  • kernel/f5lists.cc

    rcb6cda rc3efd3b  
    242242Rule* LNode::getRule() {
    243243    return data->getRule();
     244}
     245
     246void LNode::setRule(Rule* r) {
     247    return data->setRule(r);
    244248}
    245249

  • kernel/f5lists.h

    rcb6cda rc3efd3b  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5lists.h,v 1.18 2009-05-07 08:48:36 ederc Exp $ */
     4/* $Id: f5lists.h,v 1.19 2009-05-13 16:55:03 ederc Exp $ */
    55/*
    66* ABSTRACT: list interface
    … …  
    8181        void    setIndex(int i);
    8282        void    setNext(LNode* l);
     83        void    setRule(Rule* r);
    8384        void    setDel(bool d);
    8485        // test if for any list element the polynomial part of the data is equal to *p
Note: See TracChangeset for help on using the changeset viewer.