Changeset ab76b4 in git


Ignore:
Timestamp:
Mar 8, 2010, 11:49:06 AM (13 years ago)
Author:
Christian Eder
Branches:
(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
Children:
c1a5fdccad23660f683eef44f4ca207fa4050c1c
Parents:
56b0c82650ffab78c72a5629796b5fe751482448
Message:
latest F5 version including F5,F5R,F5C & F5+

git-svn-id: file:///usr/local/Singular/svn/trunk@12620 2c84dea3-7e68-4137-9b89-c4e89433aadc
Files:
9 added
8 edited

Legend:

Unmodified
Added
Removed

  • Singular/extra.cc

    r56b0c8 rab76b4  
    27182718        opt = 2;
    27192719      }
     2720      h = h->next;
     2721      int plus;
     2722      if(h != NULL) {
     2723        plus = (int) (long) h->Data();
     2724      }
     2725      else {
     2726        plus = 0;
     2727      }
     2728      h = h->next;
     2729      int termination;
     2730      if(h != NULL) {
     2731        termination = (int) (long) h->Data();
     2732      }
     2733      else {
     2734        termination = 0;
     2735      }
    27202736      res->rtyp=IDEAL_CMD;
    2721       res->data=(ideal) F5main(G,r,opt);
     2737      res->data=(ideal) F5main(G,r,opt,plus,termination);
    27222738      return FALSE;
    27232739    }

  • Singular/mod2.h.in

    r56b0c8 rab76b4  
    191191/* procedures to compute groebner bases with the f5 implementation */
    192192/* still testing */
    193 #undef HAVE_F5
     193#define HAVE_F5 1
    194194
    195195/* procedures to compute groebner bases with the f5c implementation */

  • kernel/f5data.h

    r56b0c8 rab76b4  
    3636    public:
    3737        inline          LPolyOld(poly t, int i, poly p, RuleOld* r=NULL);
     38 //       inline          LPolyOld(poly t, int i, poly p, RuleOld* r=NULL, bool b=0);
    3839        inline  void    setPoly(poly p);
    3940        inline  poly    getPoly();
    … …  
    5556}
    5657
     58/*LPolyOld::LPolyOld(poly t,int i,poly p, RuleOld* r, bool b) {
     59    set(t,i,p,r);
     60    del =   b;
     61}
     62*/
    5763void LPolyOld::setPoly(poly p)  {
    5864    //poly _p     =   pInit();

  • kernel/f5gb.cc

    r56b0c8 rab76b4  
    99#ifdef HAVE_F5
    1010#include <unistd.h>
     11#include <omp.h>
    1112#include "structs.h"
    1213#include "kutil.h"
    … …  
    3637int numberUsefulPairs   =   0;
    3738int numberUselessPairs  =   0;
     39int numberUsefulPairsMinDeg = 0;
     40int highestDegreeGBCriticalPair = 0;
     41int numberRejectedF5CriticalPairs = 0;
     42int numberOfReductions  = 0;
     43int numberOfSpolys  = 0;
    3844/*
    3945====================================================================
    … …  
    114120==================================================
    115121*/
    116 LList* F5inc(int i, poly f_i, LList* gPrev, LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag, int termination) {
     122LList* F5inc(int i, poly f_i, LList* gPrev, LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag, int plus, int termination) {
    117123    //Print("in f5inc\n");           
    118124    //pWrite(rules->getFirst()->getRuleTerm());
     125    int iterationstep = i;
    119126    int j;
    120127    //Print("%p\n",gPrev->getFirst());
    … …  
    133140    CListOld* critPairs        =   new CListOld();
    134141    CNode* critPairsMinDeg  =   new CNode();   
     142    PList* rejectedGBList = new PList();
    135143    // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
    136144    // in the list critPairs
    137     criticalPair(gPrev, critPairs, lTag, rTag, rules);
     145    criticalPair(gPrev, critPairs, lTag, rTag, rules, rejectedGBList, plus);
    138146    static LList* sPolyList        =   new LList();
    139147    //sPolyList->print();
    … …  
    146154        // critPairs->getMinDeg() deletes the first elements of minimal degree from
    147155        // critPairs, thus the while loop is not infinite.
    148         critPairsMinDeg =   critPairs->getMinDeg();
    149156        // adds all to be reduced S-polynomials in the list sPolyList and adds
    150157        // the corresponding rules to the list rules
    … …  
    154161        //startTimer();
    155162        //critPairs->print();
    156         if(numberUsefulPairs > 0) {
    157           Print("number of useful pairs:  %d\n",numberUsefulPairs);
    158           Print("number of useless pairs: %d\n\n",numberUselessPairs);
    159           computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
    160         }
    161         else {
    162           return gPrev;
    163         }
     163
     164        //definition of a local numberUsefulPairs variable for the next degree
     165        //step:
     166        //if in this degree all pairs are useless, skip this degree step
     167        //completely!
     168        //long arrideg = critPairs->getFirst()->getData()->getDeg();
     169        //if(plus && highestDegreeGBCriticalPair < critPairs->getFirst()->getData()->getDeg()) {
     170        //  return gPrev;
     171        //}
     172        //else {
     173        critPairsMinDeg =   critPairs->getMinDeg();
     174        //numberUsefulPairsMinDeg = computeUsefulMinDeg(critPairsMinDeg);
     175        //if(numberUsefulPairs > 0) {
     176          //if(numberUsefulPairsMinDeg > 0) {
     177            //Print("number of useful pairs:  %d\n",numberUsefulPairs);
     178            //Print("number of useless pairs: %d\n\n",numberUselessPairs);
     179          //Print("Degree of following reduction: %d\n",critPairsMinDeg->getData()->getDeg()); 
     180        long degreecheck = critPairsMinDeg->getData()->getDeg();
     181       
     182          computeSPols(critPairsMinDeg,rTag,rules,sPolyList, rejectedGBList);
     183        //}
     184          //}
     185        //}
     186        //else {
     187        //  return gPrev;
     188        //}
    164189        //timer4  =   getTimer();
    165190        //Print("SPOLS TIMER: %d\n",timer4);
    … …  
    177202        //sPolyList->print();
    178203        //reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
    179         Print("BEFORE REDUCTION: \n");
    180         Print("number of useful pairs:  %d\n",numberUsefulPairs);
    181         Print("number of useless pairs: %d\n\n",numberUselessPairs);
    182         newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination);
     204        //Print("BEFORE REDUCTION: \n");
     205        //Print("number of useful pairs:  %d\n",numberUsefulPairs);
     206        //Print("number of useless pairs: %d\n\n",numberUselessPairs);
     207        newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination, rejectedGBList, plus);
     208        //Print("ITERATION:  %d",iterationstep);
     209        //Print("NAECHSTER GRAD:  %ld",degreecheck);
     210        //sleep(5);
     211        //if(i == 5 && pDeg(gPrev->getLast()->getPoly()) == 8) {
     212        //  Print("RAUS BEI DEG 8 \n");
     213        //  return gPrev;
     214        //}
     215        //Print("ARRIS DEG: %ld\n",arrideg);
     216        // Arris idea stated by John in an email
     217        //if(arrisCheck(critPairs->getFirst(),gPrev->getFirst(),arrideg)) {
     218        //  Print("ARRIS DEGREE: %ld\n", arrideg);
     219        //  return gPrev;
     220        //}
     221       
     222       
     223        //bool aha = checkDGB(gPrev);
     224       
     225
    183226        //timer3      =  getTimer();
    184227        //reductionTime = reductionTime + timer3;
    … …  
    246289
    247290
     291bool checkDGB(LList* gPrev) {
     292  Print("D-GB CHECK at degree %ld\n",pDeg(gPrev->getLast()->getPoly()));
     293  LNode* temp = gPrev->getFirst();
     294  LNode* temp2;
     295  bool isDGb = 0;
     296  // construct the d-GB gb
     297  ideal gb =   idInit(gPrev->getLength(),1);
     298  for(int j=0;j<=gPrev->getLength()-1;j++) {
     299          gb->m[j] =   temp->getPoly();
     300          pWrite(gb->m[j]);
     301          temp        =   temp->getNext();
     302  }
     303  /*
     304  Kstd1_deg = pDeg(gPrev->getLast()->getPoly());
     305  BITSET save = test;
     306  test |= Sy_bit(OPT_DEGBOUND);
     307  kStd();
     308  test = save;
     309  */
     310  temp = gPrev->getFirst();
     311  while(NULL != temp) {
     312    temp2 = temp->getNext();
     313    number nOne = nInit(1);
     314    poly lcm = pOne();
     315    poly sp = pOne();
     316    while(NULL != temp2) {
     317      pLcm(temp->getPoly(),temp2->getPoly(),lcm);
     318      pSetCoeff(lcm,nOne);
     319      pSetm(lcm);
     320      Print("LCM:   ");
     321      pWrite(lcm);
     322      if(pDeg(lcm) <= pDeg(gPrev->getLast()->getPoly())) {
     323        poly u1 = pOne();
     324        poly u2 = pOne();
     325        u1  = pDivide(lcm,pHead(temp->getPoly()));
     326        pSetCoeff(u1,nOne);
     327        u2  = pDivide(lcm,pHead(temp2->getPoly()));
     328        pSetCoeff(u2,nOne);
     329        sp      =   ksOldSpolyRedNew(ppMult_qq(u1,temp->getPoly()),
     330            ppMult_qq(u2,temp2->getPoly()));
     331        pNorm(sp);
     332     
     333        poly reducer  = pOne();
     334        //reducer       = gb->m[0];
     335        int i         = 0;
     336        pWrite(pHead(sp));
     337       
     338        while(i<IDELEMS(gb)) {
     339          reducer = gb->m[i];
     340          if(pDivisibleBy(reducer,pHead(sp))) {
     341            poly uReducer = pOne();
     342            uReducer = pDivide(lcm,pHead(reducer));
     343            pSetCoeff(uReducer,nOne);
     344            sp = ksOldSpolyRedNew(sp,ppMult_qq(uReducer,reducer));
     345            //pNorm(tempSP);
     346            //sp = tempSP;
     347            pNorm(sp);
     348            pWrite(sp);
     349            i = 0;
     350          }
     351          else {
     352            i++;
     353          }
     354        }
     355       
     356        pWrite(pHead(sp));
     357      }
     358      temp2 = temp2->getNext();
     359    }
     360    temp  = temp->getNext();
     361  }
     362  Print("------------------\n");
     363  return isDGb;
     364}
     365
     366/*
     367 * Arris Check if we are finished after the current degree step:
     368 * Checks all remaining critical pairs, i.e. those of higher degree,
     369 * by the two Buchberger criteria.
     370 * return value: 0, if all remaining critical pairs are deleted by
     371 *                  Buchberger's criteria
     372 *               1, otherwise
     373 */
     374bool arrisCheck(CNode* first, LNode* firstGCurr, long arrideg) {
     375  CNode* temp = first;
     376 
     377  //product criterion check
     378  while(NULL != temp) {
     379    if(!pLmEqual(pHead(temp->getLp2Poly()),temp->getT1())) {
     380        return 0;
     381    }
     382    temp = temp->getNext();
     383  }
     384
     385  // chain criterion
     386  LNode* tempPoly = firstGCurr;
     387  while(NULL != tempPoly) {
     388    LNode* tempPoly2 = tempPoly->getNext();
     389    while(NULL != tempPoly2) {
     390      number nOne = nInit(1);
     391      poly lcm = pOne();
     392      pLcm(tempPoly->getPoly(),tempPoly2->getPoly(),lcm);
     393      pSetCoeff(lcm,nOne);
     394      pSetm(lcm);
     395      if(pDeg(lcm) > arrideg) {
     396        LNode* tempPoly3 = firstGCurr;
     397        while(NULL != tempPoly3) {
     398          if(tempPoly3 != tempPoly2 && tempPoly3 != tempPoly && pDivisibleBy(tempPoly3->getPoly(),lcm)) {
     399        poly lcm1 = pOne();
     400        poly lcm2 = pOne();
     401        pLcm(tempPoly3->getPoly(),tempPoly->getPoly(),lcm1);
     402        pSetCoeff(lcm1,nOne);
     403        pSetm(lcm1);
     404        pLcm(tempPoly3->getPoly(),tempPoly2->getPoly(),lcm2);
     405        pSetCoeff(lcm2,nOne);
     406        pSetm(lcm2);
     407        if(pDeg(lcm1) < pDeg(lcm) && pDeg(lcm2) < pDeg(lcm)) {
     408          return 0;
     409        }
     410      }
     411        tempPoly3 = tempPoly3->getNext();
     412        }
     413      }
     414      tempPoly2 = tempPoly2->getNext();
     415    }
     416    tempPoly = tempPoly->getNext();
     417  }
     418  return 1;
     419}
     420
     421 
     422 
    248423/*
    249424================================================================
    … …  
    256431================================================================
    257432*/
    258 inline void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
     433inline void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList, int plus) {
    259434    //Print("IN CRITPAIRS\n");
    260435    // initialization for usage in pLcm()
    … …  
    267442    poly t              =   pHead(newElement->getPoly());
    268443    RuleOld* testedRuleOld    =   NULL;
     444    //Print("NEW:   ");
     445    //pWrite(newElement->getPoly());
     446    //Print("ADDRESS:  %p",newElement);
    269447    if(NULL != rules->getFirst()) {
    270448        testedRuleOld  =   rules->getFirst()->getRuleOld();
    … …  
    272450    // computation of critical pairs
    273451    while( gPrev->getLast() != temp) {
     452        //Print("TEMP:  ");
     453        //pWrite(pHead(temp->getPoly()));
     454        //Print("ADDRESS:  %p",temp);
    274455        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
    275456        pSetCoeff(lcm,nOne);
    … …  
    282463        u2 = pDivide(lcm,pHead(temp->getPoly()));
    283464        pSetCoeff(u2,nOne);
     465        int degree = pDeg(ppMult_qq(u2,pHead(temp->getPoly())));
    284466        // testing both new labels by the F5 Criterion
    285467        if(!temp->getDel()) {
     468          if(plus && highestDegreeGBCriticalPair < degree) {
     469            highestDegreeGBCriticalPair = degree;
     470          }
    286471          if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
    287472            && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
    … …  
    305490              }
    306491          }
     492          else {
     493            // TODO: generate a list of lcms of rejected GB critical pairs and
     494            //       check F5 critical pairs with it at their creation
     495            //Print("--------------------------------------------------------------------\n");
     496            //Print("--------------------------------------------------------------------\n");
     497            pSetm(lcm);
     498            rejectedGBList->insert(lcm);
     499            //Print("-----------------------REJECTED IN CRIT PAIR------------------------\n");
     500            //pWrite(lcm);
     501            //Print("--------------------------------------------------------------------\n");
     502            //rejectedGBList->print();
     503          }
    307504        }
    308505        else {
     506        //Print("LABEL:  ");
     507        //pWrite(ppMult_qq(u1,newElement->getTerm()));
     508          //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair
     509            if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
     510              && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
     511              && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
     512                // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
     513                // label as first element in the CPairOld
     514                if(newElement->getIndex() == temp->getIndex() &&
     515                -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
     516                    CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
     517                                    temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);                   
     518                    critPairs->insert(cp);
     519                    numberUselessPairs++;
     520                }
     521                else {
     522                    CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
     523                                    newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);                   
     524                    critPairs->insert(cp);
     525                    numberUselessPairs++;
     526                }
     527            }
     528          //}
     529        }
     530        temp    =   temp->getNext();
     531    }
     532}
     533
     534
     535
     536/*
     537================================================================
     538computes a list of critical pairs for the next reduction process
     539the first element is always "useless" thus the critical pair
     540computed is "useless".
     541first element in gPrev is always the newest element which must
     542build critical pairs with all other elements in gPrev
     543================================================================
     544*/
     545inline void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList) {
     546    //Print("IN CRITPAIRS\n");
     547    // initialization for usage in pLcm()
     548    number nOne         =   nInit(1);
     549    LNode* newElement   =   gPrev->getLast();
     550    LNode* temp         =   gPrev->getFirst();
     551    poly u1             =   pOne();
     552    poly u2             =   pOne();
     553    poly lcm            =   pOne();
     554    poly t              =   pHead(newElement->getPoly());
     555    RuleOld* testedRuleOld    =   NULL;
     556    if(NULL != rules->getFirst()) {
     557        testedRuleOld  =   rules->getFirst()->getRuleOld();
     558    }
     559    // computation of critical pairs
     560    while( gPrev->getLast() != temp) {
     561        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
     562        pSetCoeff(lcm,nOne);
     563        // computing factors u2 for new labels
     564        u1 = pDivide(lcm,t);
     565        if(NULL == u1) {
     566            break;
     567        }
     568        pSetCoeff(u1,nOne);
     569        u2 = pDivide(lcm,pHead(temp->getPoly()));
     570        pSetCoeff(u2,nOne);
     571       // testing both new labels by the F5 Criterion
     572        //Print("LABEL:  ");
     573        //pWrite(ppMult_qq(u1,newElement->getTerm()));
     574        //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair
    309575          if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
    310576            && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
    … …  
    326592              }
    327593          }
    328         }
    329         temp    =   temp->getNext();
    330     }
    331 }
    332 
    333 
    334 
    335 /*
    336 ================================================================
    337 computes a list of critical pairs for the next reduction process
    338 the first element is always "useless" thus the critical pair
    339 computed is "useless".
    340 first element in gPrev is always the newest element which must
    341 build critical pairs with all other elements in gPrev
    342 ================================================================
    343 */
    344 inline void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
    345     //Print("IN CRITPAIRS\n");
    346     // initialization for usage in pLcm()
    347     number nOne         =   nInit(1);
    348     LNode* newElement   =   gPrev->getLast();
    349     LNode* temp         =   gPrev->getFirst();
    350     poly u1             =   pOne();
    351     poly u2             =   pOne();
    352     poly lcm            =   pOne();
    353     poly t              =   pHead(newElement->getPoly());
    354     RuleOld* testedRuleOld    =   NULL;
    355     if(NULL != rules->getFirst()) {
    356         testedRuleOld  =   rules->getFirst()->getRuleOld();
    357     }
    358     // computation of critical pairs
    359     while( gPrev->getLast() != temp) {
    360         pLcm(newElement->getPoly(), temp->getPoly(), lcm);
    361         pSetCoeff(lcm,nOne);
    362         // computing factors u2 for new labels
    363         u1 = pDivide(lcm,t);
    364         if(NULL == u1) {
    365             break;
    366         }
    367         pSetCoeff(u1,nOne);
    368         u2 = pDivide(lcm,pHead(temp->getPoly()));
    369         pSetCoeff(u2,nOne);
    370         // testing both new labels by the F5 Criterion
    371         if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
    372            && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag)
    373            && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
    374             // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
    375             // label as first element in the CPairOld
    376             if(newElement->getIndex() == temp->getIndex() &&
    377             -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
    378                 CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
    379                                 temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);                   
    380                 critPairs->insert(cp);
    381                 numberUselessPairs++;
    382             }
    383             else {
    384                 CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
    385                                 newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);                   
    386                 critPairs->insert(cp);
    387                 numberUselessPairs++;
    388             }
    389         }
     594        //}
    390595        temp    =   temp->getNext();
    391596    }
    … …  
    610815}
    611816
    612 
    613 
     817/*
     818 * check for useful pairs in the given subset of critical pairs
     819 */
     820int computeUsefulMinDeg(CNode* first) {
     821  CNode* temp = first;
     822  int numberUsefulPairsMinDeg = 0;
     823  while(NULL != temp) {
     824    if(!temp->getDel()) {
     825      numberUsefulPairsMinDeg++;
     826    }
     827    temp = temp->getNext();
     828  }
     829  return numberUsefulPairsMinDeg;
     830}
    614831/*
    615832==================================
    … …  
    617834==================================
    618835*/
    619 void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) {
     836void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList, PList* rejectedGBList) {
    620837    CNode* temp         =   first;
     838    //Print("\nDegree:  %d\n",temp->getData()->getDeg());
     839    // only GB-critical pairs are computed
     840    //while(NULL != temp && temp->getDel()) {
     841    //  temp = temp->getNext();
     842    //}
     843    //if(temp->getData()->getDeg() == 11) {
     844    //  Print("PAIRS OF DEG 11:\n");
     845    //}
     846    RList* f5rules = new RList();
     847    CListOld* f5pairs = new CListOld();
    621848    poly sp     =   pInit();
    622849    number sign =   nInit(-1);   
    623850    //Print("###############################IN SPOLS##############################\n");
    624851    //first->print();
    625 
     852/*
     853 * first of all: do everything for GB critical pairs
     854 */
    626855    while(NULL != temp) {
    627         // counting the number of useful pairs
    628         if(!temp->getDel()) {
    629           //Print("%d\n",numberUsefulPairs);
    630           numberUsefulPairs--;
     856    //  if(temp->getData()->getDeg() == 11) {
     857        //Print("--------------------------\n");
     858        //Print("redundant? %d\n",temp->getDel());
     859        //pWrite(pHead(temp->getLp1Poly()));
     860        //Print("redundant: %d\n",temp->getAdLp1()->getDel());
     861        //pWrite(pHead(temp->getLp2Poly()));
     862        //Print("redundant: %d\n",temp->getAdLp2()->getDel());
     863        //pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
     864        //  sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
     865        //      ppMult_qq(temp->getT2(),temp->getLp2Poly()));
     866          //Print("BEGIN SPOLY2\n====================\n");
     867        //  pNorm(sp);
     868        //  pWrite(pHead(sp));
     869        //Print("--------------------------\n");
     870      //}
     871      if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
     872      //if(temp->getDel() == 0 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
     873        if(temp->getLp2Index() == temp->getLp1Index()) {
     874          if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) {
     875            sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
     876                ppMult_qq(temp->getT2(),temp->getLp2Poly()));
     877            pNorm(sp);
     878            if(NULL == sp) {
     879              reductionsToZero++;
     880              rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     881              numberOfRules++;
     882              pDelete(&sp);
     883            }
     884            else {
     885              rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     886              numberOfRules++;
     887              sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
     888            //Print("INSERTED\n");
     889              numberOfSpolys++;
     890            }
     891          }
     892          else {
     893            if(highestDegreeGBCriticalPair < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) {
     894              highestDegreeGBCriticalPair = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()));
     895            }
     896            rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
     897            //Print("rejected!\n"); 
     898
     899            //Print("CRITERION 2 in SPOLS 2nd generator\n");
     900          }
     901        }
     902        else {
     903          sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
     904              ppMult_qq(temp->getT2(),temp->getLp2Poly()));
     905          //Print("BEGIN SPOLY2\n====================\n");
     906          pNorm(sp);
     907          //pWrite(sp);
     908          //Print("END SPOLY2\n====================\n");
     909          if(NULL == sp) {
     910            reductionsToZero++;
     911            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     912            numberOfRules++;
     913            pDelete(&sp);
     914          }
     915          else {
     916            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     917            numberOfRules++;
     918            sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
     919            //Print("INSERTED\n");
     920            numberOfSpolys++;
     921          }
     922        }
     923      }
     924      /*     
     925      if(temp->getDel() == 0 && criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
     926        //Print("rejected!\n"); 
     927        rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
     928      }
     929     
     930       
     931      if(temp->getDel() == 1 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
     932        if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) {
     933          highestDegree   = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()));
     934        }   
     935        if(temp->getLp2Index() == temp->getLp1Index()) {
     936          if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) {
     937            sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
     938                ppMult_qq(temp->getT2(),temp->getLp2Poly()));
     939            pNorm(sp);
     940            if(NULL == sp) {
     941              reductionsToZero++;
     942              rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     943              numberOfRules++;
     944              pDelete(&sp);
     945            }
     946            else {
     947              rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     948              numberOfRules++;
     949
     950
     951              // save the address of the rule again in a different
     952              // list
     953
     954              f5rules->insert(rules->getFirst()->getRuleOld());
     955              f5pairs->insertWithoutSort(temp->getData());       
     956              ///////////////////////////////////////
     957
     958              //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
     959            }
     960          }
     961        }
     962        else {
     963          sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
     964              ppMult_qq(temp->getT2(),temp->getLp2Poly()));
     965          //Print("BEGIN SPOLY2\n====================\n");
     966          pNorm(sp);
     967          //pWrite(sp);
     968          //Print("END SPOLY2\n====================\n");
     969          if(NULL == sp) {
     970            reductionsToZero++;
     971            //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     972            numberOfRules++;
     973            pDelete(&sp);
     974          }
     975          else {
     976            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     977            numberOfRules++;
     978            // save the address of the rule again in a different
     979            // list
     980
     981            f5rules->insert(rules->getFirst()->getRuleOld());
     982            f5pairs->insertWithoutSort(temp->getData());       
     983            ///////////////////////////////////////
     984            //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
     985            //  numberOfSpolys++;
     986          }
     987        }
     988      }
     989        // the following else is not needed at all as we are checking
     990        // F5-critical pairs in this step
     991        /*
     992           else {
     993           if(!temp->getDel()) {
     994           rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
     995           }
     996
     997           }
     998           */
     999
     1000        temp    =   temp->getNext();
     1001
     1002      }
     1003     
     1004      /*
     1005      temp = f5pairs->getFirst();
     1006      RNode* tempRule = f5rules->getFirst();
     1007      int howmany = 1;
     1008      while(NULL != temp) {
     1009        //Print("RULE:  ");
     1010        //pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term()));
     1011        sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
     1012                                     ppMult_qq(temp->getT2(),temp->getLp2Poly()));
     1013        pNorm(sp);
     1014        if(rejectedGBList->check(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())))) { //|| (temp->getData()->getDeg() == 10 && howmany == 2)) {
     1015          if((temp->getData()->getDeg() == 10) && (howmany == 2)) {
     1016            //Print("HIER DRIN IM SAFTLADEN\n");
     1017          }
     1018          sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld());
     1019              numberOfSpolys++;
     1020              howmany++;
    6311021        }
    6321022        else {
    633           numberUselessPairs--;
    634         }
    635         //Print("JA\n");
    636         // only if a new RuleOld was added since the last test in subalgorithm criticalPair()
    637         //if(rules->getFirst() != rTag->getFirst()) {
    638         if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
    639                 // the second component is tested only when it has the actual index, otherwise there is
    640                 // no new RuleOld to test since the last test in subalgorithm criticalPair()
    641                 if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) {
    642                     highestDegree   = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()));
    643                     //pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
    644                 }   
    645                 if(temp->getLp2Index() == temp->getLp1Index()) {
    646                     if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) {
    647                         // computation of S-polynomial
    648                         //poly p1 =   temp->getLp1Poly();
    649                         //poly p2 =   temp->getLp2Poly();
    650                         //pIter(p1);
    651                         //pIter(p2);
    652                         //sp  =   pAdd(ppMult_qq(temp->getT1(),p1),pMult_nn(ppMult_qq(temp->getT2(),p2),sign)); 
    653                         sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
    654                                          ppMult_qq(temp->getT2(),temp->getLp2Poly()));
    655                         //Print("BEGIN SPOLY1\n====================\n");
    656                         pNorm(sp);
    657                         //pWrite(sp);
    658                         //Print("END SPOLY1\n====================\n");
    659                         if(NULL == sp) {
    660                             // as rules consist only of pointers we need to save the labeled
    661                             // S-polynomial also of a zero S-polynomial
    662                             //zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
    663                             // origin of RuleOld can be set NULL as the labeled polynomial
    664                             // will never be used again as it is zero => no problems with
    665                             // further criterion2() tests and termination conditions
    666                             //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
    667                                                         reductionsToZero++;
    668                         //Print("IN SPOLS 1\n");
    669                             //Rule* rNew  =  new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
    670                             //rules->insertOrdered(rNew);
    671                             rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
    672                             numberOfRules++;
    673                             //Print("RuleOld ADDED: \n");
    674                             //pWrite(rules->getFirst()->getRuleTerm());
    675                             //rules->print();
    676                             // as sp = NULL, delete it
    677                             pDelete(&sp);
    678                             //Print("HIER\n");
    679                         }
    680                         else {
    681                         //Print("IN SPOLS 2\n");
    682                             //Rule* rNew  =  new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
    683                             //rules->insertOrdered(rNew);
    684                             rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
    685                             numberOfRules++;
    686                             //Print("RuleOld ADDED: \n");
    687                             //pWrite(rules->getFirst()->getRuleTerm()); 
    688                             //rules->print();
    689                             sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
    690                             //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rNew);
    691                         }
    692                         // data is saved in sPolyList or zero => delete sp
    693                     }
    694                     else {
    695                       Print("CRITERION 2 in SPOLS 2nd generator\n");
    696                     }
    697                 }
    698                 else { // temp->getLp2Index() < temp->getLp1Index()
    699                     // computation of S-polynomial
    700                         //poly p1 =   temp->getLp1Poly();
    701                         //poly p2 =   temp->getLp2Poly();
    702                         //pIter(p1);
    703                         //pIter(p2);
    704                         //sp  =   pAdd(ppMult_qq(temp->getT1(),p1),pMult_nn(ppMult_qq(temp->getT2(),p2),sign)); 
    705                     sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
    706                                      ppMult_qq(temp->getT2(),temp->getLp2Poly()));
    707                     //Print("BEGIN SPOLY2\n====================\n");
    708                     pNorm(sp);
    709                     //pWrite(sp);
    710                     //Print("END SPOLY2\n====================\n");
    711                     if(NULL == sp) {
    712                         // zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
    713                         // origin of RuleOld can be set NULL as the labeled polynomial
    714                         // will never be used again as it is zero => no problems with
    715                         // further criterion2() tests and termination conditions
    716                             //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
    717                         reductionsToZero++;
    718                         //Print("IN SPOLS 3\n");
    719                         rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
    720                         numberOfRules++;
    721                         //Print("RuleOld ADDED: \n");
    722                         //pWrite(rules->getFirst()->getRuleTerm());
    723                         //rules->print();
    724                         // as sp = NULL, delete it
    725                         pDelete(&sp);
    726                     }
    727                     else {
    728                         //Print("IN SPOLS 4\n");
    729                        
    730                         //////////////////////////////////////////////////////////
    731                         //////////////////////////////////////////////////////////
    732                         // TODO: Rules inserted ordered by their label monomial!//
    733                         //////////////////////////////////////////////////////////
    734                         //////////////////////////////////////////////////////////
    735 
    736                         //Rule* rNew      =   new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
    737                         //RNode* rNodeNew =   new RNode(rNew);
    738                         //rules->insertOrdered(rNew);
    739                         rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
    740                         numberOfRules++;
    741                         //Print("RuleOld ADDED: \n");
    742                         //pWrite(rules->getFirst()->getRuleTerm());
    743                         //rules->print();
    744                         //Print("%d\n",rules->getFirst()->getRuleIndex());
    745                         //Print("%p\n",sPolyList->getFirst());
    746                         sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
    747                         //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rNew);
    748                     }
    749                 }
    750             }
    751             else {
    752               Print("CRITERION 2 in SPOLS 1st generator\n");
    753             }
    754         //}
    755         //Print("%p\n",temp);
    756         temp    =   temp->getNext();
    757         //Print("%p\n",temp);
    758         //Print("%p\n",temp->getData());
    759         //pWrite(temp->getLp1Poly());
    760     }
    761     // these critical pairs can be deleted now as they are either useless for further computations or
    762     // already saved as an S-polynomial to be reduced in the following
    763     delete first;   
     1023          numberRejectedF5CriticalPairs++;
     1024              howmany++;
     1025          if(numberRejectedF5CriticalPairs < -1) { // ||
     1026          }
     1027          else {
     1028             //numberRejectedF5CriticalPairs == 7) {
     1029            /*
     1030            Print("--------------------------------- rejected F5-critical pair-------------------------------------\n");
     1031            pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
     1032            Print("Label: ");
     1033            pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term()));
     1034            Print("%d\n",temp->getDel());
     1035            Print("Comes from:\n ");
     1036            pWrite(pHead(temp->getLp1Poly()));
     1037            Print("Label: ");
     1038            pWrite(temp->getLp1Term());
     1039            Print("%d\n",temp->getLp1Index());
     1040            pWrite(pHead(temp->getLp2Poly()));
     1041            Print("Label: ");
     1042            pWrite(temp->getLp2Term());
     1043            Print("%d\n",temp->getLp2Index());
     1044            //Print("--------------------------------------LIST OF GB PAIRS REJECTED-----------------------------------------\n");
     1045            //rejectedGBList->print();
     1046            Print("--------------------------------------------------------------------------------------------------------\n");
     1047            //if(temp->getLp1Index() < 7) {
     1048              sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld());
     1049           
     1050            //}
     1051          //numberOfSpolys++;
     1052          }
     1053        //pSetExp(tempRule->getRuleOld()->getTerm(),1,1000);
     1054        }
     1055        temp      = temp->getNext();
     1056        tempRule  = tempRule->getNext();
     1057
     1058      }
     1059      */
     1060      // these critical pairs can be deleted now as they are either useless for further computations or
     1061      // already saved as an S-polynomial to be reduced in the following
     1062      delete first;   
     1063//Print("NUMBER SPOLYS: %d\n", numberOfSpolys);
     1064//Print("SPOLY LIST: \n");
     1065//LNode* tempSpoly = sPolyList->getFirst();
     1066//if(NULL != tempSpoly) {
     1067//  pWrite(pHead(tempSpoly->getPoly()));
     1068//  tempSpoly = tempSpoly->getNext();
     1069//}
     1070//Print("-----SP------\n");
     1071//else {
     1072//  Print("EMPTY SPOLYLIST!\n");
     1073//}
    7641074}
    765 
    766 
    7671075
    7681076/*
    … …  
    7721080*/
    7731081void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
    774                  ideal gbPrev) {
     1082                 ideal gbPrev, PList* rejectedGBList, int plus) {
    7751083    //Print("##########################################In REDUCTION!########################################\n");
    7761084    // check if sPolyList has any elements
    … …  
    7961104            //Print("lower label reduction:  ");
    7971105            //pWrite(tempNF);
    798             topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev);
     1106            topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus);
    7991107       
    8001108        }
    … …  
    8181126*/
    8191127void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag,
    820                  ideal gbPrev, int termination) {
     1128                 ideal gbPrev, int termination, PList* rejectedGBList, int plus) {
    8211129    //Print("##########################################In REDUCTION!########################################\n");
    8221130    // check if sPolyList has any elements
    … …  
    8241132    //Print("--1--\n");
    8251133    LNode* temp = sPolyList->getFirst();
     1134    //Print("START OF REDUCTION:  ");
    8261135    while(NULL != temp) {
     1136        numberOfReductions++;
    8271137        // temp is the first element in the sPolyList which should be reduced
    8281138        // due to earlier sorting this is the element of minimal degree AND
    … …  
    8341144        //pWrite(sPolyList->getFirst()->getPoly());
    8351145        sPolyList->setFirst(temp->getNext());
     1146        //if(pDeg(temp->getPoly()) > 11) {
     1147        //  Print("YES!!!!!!!!!!!!!!!!\n");
     1148        //}
    8361149        //pWrite(temp->getPoly());
    8371150        //poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
    … …  
    8451158            // with label index = current label index: this is done such that there
    8461159            // is no label corruption during the reduction process
    847             findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination);
     1160            findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus);
    8481161        //}
    8491162        //else {
    … …  
    8791192 * ================================================================================
    8801193*/
    881 void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, LList* reducers, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination) {
     1194void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, LList* reducers, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination, PList* rejectedGBList, int plus) {
    8821195    int canonicalize    =   0;
    8831196    //int timerRed        =   0;
    … …  
    9171230                    //Print("U:  ");
    9181231                    //pWrite(u);
     1232                    if(pLmCmp(u,pOne()) != 0) { // else u = 1 and no test need to be done!
    9191233                    if(tempRed->getIndex() != idx) {
    9201234                            // passing criterion1 ?
    … …  
    9221236                                    poly tempRedPoly    =   tempRed->getPoly();
    9231237                                    //Print("REDUCER: ");
    924                                     //pWrite(ppMult_qq(u,tempRedPoly));
     1238                                    //pWrite(tempRedPoly);
    9251239                                    pIter(tempRedPoly);
    9261240                                    int lTempRedPoly    =   pLength(tempRedPoly);
    … …  
    9691283                                        poly tempRedPoly    =   tempRed->getPoly();
    9701284                                        //Print("REDUCER: ");
    971                                         //pWrite(ppMult_qq(u,tempRedPoly));
     1285                                        //pWrite(tempRedPoly);
    9721286                                        pIter(tempRedPoly);
    9731287                                        int lTempRedPoly    =   pLength(tempRedPoly);
    … …  
    10281342                        }
    10291343                    }
    1030                    
     1344                    }
     1345                    else { // u = 1 => reduce without checking criteria
     1346                        poly tempRedPoly    =   tempRed->getPoly();
     1347                        //Print("REDUCER: ");
     1348                        //pWrite(tempRedPoly);
     1349                        pIter(tempRedPoly);
     1350                        int lTempRedPoly    =   pLength(tempRedPoly);
     1351                        kBucketExtractLm(bucket);
     1352                        kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
     1353                        canonicalize++;
     1354                        //Print("Reduction\n");
     1355                        if(!(canonicalize % 50)) {
     1356                            kBucketCanonicalize(bucket);
     1357                        }
     1358                        tempPoly    =   kBucketGetLm(bucket);
     1359                        //Print("TEMPPOLY:  ");
     1360                        //pWrite(tempPoly);
     1361                        if(NULL != tempPoly) {
     1362                            tempRed     =   gPrev->getFirst();
     1363                            continue;
     1364                        }
     1365                        else {
     1366                            break;
     1367                        }
     1368                     
     1369                    }
    10311370                }
    10321371                tempRed =   tempRed->getNext();
    … …  
    11831522            Print("\nELEMENT ADDED TO GPREV: ");
    11841523            pNorm(redPoly);
     1524              if(highestDegree < pDeg(redPoly)) {
     1525                  highestDegree   = pDeg(redPoly);
     1526              }   
    11851527            pWrite(pHead(redPoly));
    1186             pWrite(l->getTerm());
     1528            //pWrite(l->getTerm());
    11871529            //Print("%d\n",canonicalize);
    11881530            l->setPoly(redPoly);
    … …  
    11901532            // (addToG = 1)
    11911533            l->setDel(!addToG);
     1534            Print("redundant? %d\n\n",l->getDel());
    11921535            if(addToG == 0 && termination == 1) {
    11931536              reducers->insert(l->getLPolyOld());
    … …  
    12001543            if(addToG) {
    12011544              //Print("----------------HERE?-----------------\n");
    1202               criticalPair(gPrev,critPairs,lTag,rTag,rules);
     1545              criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
    12031546            }
    12041547            else {
    … …  
    12141557            else {
    12151558              if(!l->getDel()) {
    1216                 criticalPair(gPrev,critPairs,lTag,rTag,rules);
     1559                criticalPair(gPrev,critPairs,lTag,rTag,rules,rejectedGBList,plus);
    12171560              }
    12181561              else {
    1219                 criticalPair2(gPrev,critPairs,lTag,rTag,rules);
     1562                criticalPair2(gPrev,critPairs,lTag,rTag,rules, rejectedGBList);
    12201563              }
    12211564            }
    … …  
    13491692=====================================================================================
    13501693*/
    1351 void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs,  RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev) {
     1694void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs,  RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, PList* rejectedGBList, int plus) {
    13521695    //Print("##########################################In topREDUCTION!########################################\n");
    13531696    // try l as long as there are reductors found by findReductor()
    … …  
    14441787                //pWrite(l->getTerm());
    14451788                //rules->print();
    1446                 criticalPair(gPrev,critPairs,lTag,rTag,rules);
     1789                criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
    14471790                //Print("LIST OF CRITICAL PAIRS:    \n");
    14481791                //critPairs->print();
    … …  
    14591802=====================================================================
    14601803*/
    1461 LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag) {
     1804LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag, PList* rejectedGBList) {
    14621805    // allociation of memory for the possible reductor
    14631806    //Print("LPOLY:  ");
    … …  
    15341877==========================================================================
    15351878*/
    1536 ideal F5main(ideal id, ring r, int opt, int termination) {
     1879ideal F5main(ideal id, ring r, int opt, int plus, int termination) {
    15371880  switch(opt) { 
    15381881    case 0:
    … …  
    15491892      return id;
    15501893  }
     1894 
    15511895    int timer   =   initTimer();
    15521896    startTimer();
    … …  
    16231967        //Print("%p\n",gPrevTag);   
    16241968        //pWrite(gPrevTag->getPoly());
    1625         gPrev   =   F5inc(i, id->m[i-1], gPrev, reducers, gbPrev, ONE, lTag, rules, rTag, termination);
     1969        Print("Iteration: %d\n\n",i);
     1970        gPrev   =   F5inc(i, id->m[i-1], gPrev, reducers, gbPrev, ONE, lTag, rules, rTag, plus, termination);
    16261971        //Print("%d\n",gPrev->count(gPrevTag->getNext()));
    16271972        //Print("%d\n",gPrev->getLength());
    … …  
    16672012                gbPrev          =   idAdd(gbPrev,gbAdd);
    16682013            }
    1669             if(i == IDELEMS(id)) {
    1670                 ideal tempId        =   kInterRed(gbPrev);
    1671                 gbPrev              =   tempId;
    1672             }
     2014            //if(i == IDELEMS(id)) {
     2015            //    ideal tempId        =   kInterRed(gbPrev);
     2016            //    gbPrev              =   tempId;
     2017            //}
    16732018        }
    16742019        gbLength    =   gPrev->getLength();
    … …  
    17052050            // interreduction stuff
    17062051            // comment this out if you want F5 instead of F5R
    1707             //if(i<IDELEMS(id)) {
     2052            if(i<IDELEMS(id)) {
    17082053                ideal tempId    =   kInterRed(gbPrev);
    17092054                gbPrev          =   tempId;
    1710             //}
     2055            }
    17112056        }
    17122057        gbLength    =   gPrev->getLength();
    … …  
    17652110    Print("\n\nNumber of zero-reductions:           %d\n",reductionsToZero);
    17662111    Print("Number of rules:                     %d\n",numberOfRules);
     2112    Print("Number of rejected F5-critical pairs:%d\n",numberRejectedF5CriticalPairs);
     2113    Print("Number of reductions:                %d\n",numberOfReductions);
    17672114    Print("Elements not added to G:             %d\n",notInG);
    17682115    Print("Highest Degree during computations:  %d\n",highestDegree);
     2116    Print("Degree d_0 in F5+:                   %d\n",highestDegreeGBCriticalPair);
    17692117    Print("Time for computations:               %d/1000 seconds\n",timer);
    17702118    Print("Number of elements in gb:            %d\n",IDELEMS(gbPrev));
    … …  
    17782126    delete rTag;
    17792127    delete gPrev;
    1780     notInG              =   0;
    1781     numberOfRules       =   0;
    1782     reductionsToZero    =   0;
    1783     highestDegree       =   0;
    1784     reductionTime       =   0;
    1785     spolsTime           =   0;
    1786     numberUselessPairs  =   0;
    1787     numberUsefulPairs   =   0;
     2128    notInG                        =   0;
     2129    numberOfRules                 =   0;
     2130    reductionsToZero              =   0;
     2131    highestDegree                 =   0;
     2132    highestDegreeGBCriticalPair   =   0;
     2133    reductionTime                 =   0;
     2134    spolsTime                     =   0;
     2135    numberUselessPairs            =   0;
     2136    numberUsefulPairs             =   0;
     2137    numberRejectedF5CriticalPairs =   0;
     2138    numberOfReductions            =   0;
     2139    numberOfSpolys                =   0;
    17882140    return(gbPrev);
    17892141

  • kernel/f5gb.h

    r56b0c8 rab76b4  
    4343==================================================
    4444*/
    45 LList* F5inc(int i, poly f_i, LList* gPrev,LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag,int termination);
     45LList* F5inc(int i, poly f_i, LList* gPrev,LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag, int plus ,int termination);
    4646
    4747/*
    … …  
    5555================================================================
    5656*/
    57 void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds);
     57void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds, PList* rejectedGBList, int plus);
     58
     59
     60bool checkDGB(LList* gPrev);
     61
     62
     63/*
     64 * Arris Check if we are finished after the current degree step:
     65 * Checks all remaining critical pairs, i.e. those of higher degree,
     66 * by the two Buchberger criteria.
     67 * return value: 0, if all remaining critical pairs are deleted by
     68 *                  Buchberger's criteria
     69 *               1, otherwise
     70 */
     71bool arrisCheck(CNode* first,LNode* firstGCurr, long arrisdeg);
    5872
    5973/*
    … …  
    6680================================================================
    6781*/
    68 void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds);
     82void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds, PList* rejectedGBList);
    6983
    7084/*
    … …  
    90104
    91105/*
     106 * check for useful pairs in the given subset of critical pairs
     107 */
     108int computeUsefulMinDeg(CNode* first);
     109
     110/*
    92111==================================
    93112Computation of S-Polynomials in F5
    94113==================================
    95114*/
    96 inline void computeSPols(CNode* first, RTagList* rTag, RList* RuleOlds, LList* sPolyList);
     115inline void computeSPols(CNode* first, RTagList* rTag, RList* RuleOlds, LList* sPolyList, PList* rejectedGBList);
    97116
    98117/*
    … …  
    102121*/
    103122inline void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* RuleOlds, LTagList* lTag, RTagList* rTag,
    104                  ideal gbPrev);
     123                 ideal gbPrev, PList* rejectedGBList, int plus);
    105124
    106125/*
    … …  
    109128========================================================================
    110129*/
    111 inline void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, int termination);
     130inline void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, int termination, PList* rejectedGBList, int plus);
    112131
    113132/*!
    … …  
    123142 * ================================================================================
    124143 */
    125 void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, LList* reducers, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination);
     144void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, LList* reducers, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination, PList* rejectedGBList, int plus);
    126145
    127146/*
    … …  
    131150=====================================================================================
    132151*/
    133 inline void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* RuleOlds, LTagList* lTag, RTagList* rTag, ideal gbPrev);
     152inline void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* RuleOlds, LTagList* lTag, RTagList* rTag, ideal gbPrev, PList* rejectedGBList, int plus);
    134153
    135154/*
    … …  
    154173======================================
    155174*/
    156 ideal F5main(ideal i, ring r, int opt, int termination);
     175ideal F5main(ideal i, ring r, int opt, int plus, int termination);
    157176
    158177#endif

  • kernel/f5lists.cc

    r56b0c8 rab76b4  
    1919#include "f5lists.h"
    2020
     21/**
     22 * functions working on the class PNode
     23 */
     24PNode::PNode(poly p, PNode* n) {
     25  data  = p;
     26  next  = n;
     27}
     28
     29poly PNode::getPoly() {
     30  return this->data;
     31}
     32
     33PNode* PNode::getNext() {
     34  return this->next;
     35}
     36PNode* PNode::insert(poly p) {
     37  poly q = pOne();
     38  q = pCopy(p);
     39  PNode* temp = this;
     40  if(NULL == temp) {
     41    PNode* pn = new PNode(q,temp);
     42    return pn;
     43  }
     44  if(1 == pLmCmp(q,temp->getPoly())) {
     45    PNode* pn = new PNode(q,temp);
     46    return pn;
     47  }
     48  if(0 == pLmCmp(q,temp->getPoly())) {
     49    return this;
     50  }
     51  if(-1 == pLmCmp(q,temp->getPoly())) {
     52    while(NULL != temp->getNext() && -1 == pLmCmp(q,temp->getNext()->getPoly())) {
     53      temp = temp->getNext();
     54    }
     55    if(NULL == temp->getNext() || 1 == pLmCmp(q,temp->getNext()->getPoly())) {
     56      PNode* pn = new PNode(q,temp->getNext());
     57      temp->next = pn;
     58      return this;
     59    }
     60    if(0 == pLmCmp(q,temp->getNext()->getPoly())) {
     61      return this;
     62    }
     63  }
     64}
     65/*
     66PNode* PNode::insert(poly p) {
     67  PNode* pn = new PNode(p,this);
     68  return pn;
     69}
     70*/
     71/**
     72 * functions working on the class PList
     73 */
     74PList::PList() {
     75  first = NULL;
     76}
     77
     78
     79void PList::insert(poly p) {
     80  first = first->insert(p);
     81}
     82 
     83
     84/*
     85PNode* PList::insert(poly p) {
     86  PNode* temp = first;
     87  PNode* pn   = new PNode(p,temp);
     88  first       = pn;
     89  return first;
     90}
     91*/
     92bool PList::check(poly p) {
     93  PNode* temp = first;
     94  //Print("\nCHECK: \n");
     95  //pWrite(p);
     96  //Print("-----\n");
     97  while(NULL != temp) {
     98    //pWrite(temp->getPoly());
     99    //pWrite(p);
     100    //Print("COMAPRE: %d\n",pLmEqual(p,temp->getPoly()));
     101    if(1 == pLmEqual(p,temp->getPoly())) {
     102      //Print("YES!\n");
     103      //pWrite(pHead(temp->getPoly()));
     104      //Print("YES!\n");
     105      return 1;
     106    }
     107    temp = temp->getNext();
     108  }
     109  //Print("NOTHING!\n");
     110  return 0;
     111}
     112
     113void PList::print() {
     114  Print("-----LIST-----\n");
     115  PNode* temp = first;
     116  while(NULL != temp) {
     117    pWrite(temp->getPoly());
     118    temp = temp->getNext();
     119  }
     120}
    21121/*
    22122====================================
    … …  
    293393    LNode* temp = this;
    294394    Print("___________________List of S-polynomials______________________:\n");
    295     Print("%p\n",this);
    296395    while(NULL != temp && NULL != temp->data) {
    297396        Print("Index: %d\n",temp->getIndex());
    … …  
    300399        Print("Poly: ");
    301400        pWrite(temp->getPoly());
    302         Print("%p\n",temp->getPoly());
    303         Print("DELETE? %d\n",temp->getDel());
    304401        temp = temp->next;
    305402    }
    … …  
    695792}
    696793
     794
     795CNode* CNode::insertWithoutSort(CPairOld* cp) {
     796    CNode* newElement = new CNode(cp);
     797    newElement->next  = this;
     798    return newElement;
     799}
     800
     801
    697802// get the first elements from CListOld which by the above sorting have minimal degree
    698803CNode* CNode::getMinDeg() {
    … …  
    831936}
    832937
     938void CListOld::insertWithoutSort(CPairOld* c) {
     939    first = first->insertWithoutSort(c);
     940}
     941
    833942CNode* CListOld::getFirst() {
    834943    return first;

  • kernel/f5lists.h

    r56b0c8 rab76b4  
    1818============================
    1919*/
     20class PNode;
     21class PList;
    2022class LNode;
    2123class LList;
    … …  
    3032
    3133
     34/**
     35 * class PNode of nodes of polynomials
     36 */
     37class PNode {
     38  private:
     39    poly   data;
     40    PNode*  next;
     41  public:
     42    PNode(poly p, PNode* n);
     43    poly getPoly();
     44    PNode* getNext();
     45    PNode* insert(poly p);
     46};
     47
     48/**
     49 * class PList of lists of PNodes
     50 */
     51class PList {
     52  private:
     53    PNode* first;
     54  public:
     55    PList();
     56    void insert(poly p);
     57    bool check(poly p);
     58    void print();
     59};
     60   
    3261/*
    3362=======================================
    … …  
    212241                ~CNode();
    213242        CNode*  insert(CPairOld* c);
     243        CNode*  insertWithoutSort(CPairOld* cp);
    214244        CNode*  getMinDeg();
    215245        CPairOld*  getData();
    … …  
    248278        CNode*  getFirst();
    249279        void    insert(CPairOld* c);
     280        void    insertWithoutSort(CPairOld* c);
    250281        CNode*  getMinDeg();
    251282        void    print();

  • kernel/mod2.h.in

    r56b0c8 rab76b4  
    191191/* procedures to compute groebner bases with the f5 implementation */
    192192/* still testing */
    193 #undef HAVE_F5
     193#define HAVE_F5 1
    194194
    195195/* procedures to compute groebner bases with the f5c implementation */
Note: See TracChangeset for help on using the changeset viewer.