source: git/kernel/f5gb.cc @ abe5c8

fieker-DuValspielwiese
Last change on this file since abe5c8 was 762407, checked in by Oleksandr Motsak <motsak@…>, 12 years ago
config.h is for sources files only FIX: config.h should only be used by source (not from inside kernel/mod2.h!) NOTE: each source file should better include mod2.h right after config.h, while headers should better not include mod2.h.
  • Property mode set to 100644
File size: 87.6 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/*
5* ABSTRACT: f5gb interface
6*/
7
8#include "config.h"
9#include <kernel/mod2.h>
10#ifdef HAVE_F5
11#include <unistd.h>
12#include <omp.h>
13#include <kernel/structs.h>
14#include <kernel/kutil.h>
15#include <omalloc/omalloc.h>
16#include <kernel/polys.h>
17#include <polys/monomials/p_polys.h>
18#include <polys/templates/p_Procs.h>
19#include <kernel/ideals.h>
20#include <kernel/febase.h>
21#include <kernel/kstd1.h>
22#include <kernel/khstd.h>
23#include <polys/kbuckets.h>
24#include <polys/weight.h>
25#include <misc/intvec.h>
26#include <kernel/polys.h>
27#include <kernel/f5gb.h>
28#include <kernel/f5data.h>
29#include <kernel/f5lists.h>
30#include <kernel/timer.h>
31int notInG              =   0;
32int numberOfRules       =   0;
33int reductionsToZero    =   0;
34int reductionTime       =   0;
35int spolsTime           =   0;
36int highestDegree       =   0;
37int degreeBound         =   0;
38int numberUsefulPairs   =   0;
39int numberUselessPairs  =   0;
40int numberUsefulPairsMinDeg = 0;
41int highestDegreeGBCriticalPair = 0;
42int numberRejectedF5CriticalPairs = 0;
43int numberOfReductions  = 0;
44int numberOfSpolys  = 0;
45/*
46====================================================================
47sorting ideals by decreasing total degree "left" and "right" are the
48pointer of the first and last polynomial in the considered ideal
49====================================================================
50*/
51void qsortDegree(poly* left, poly* right) {
52    poly* ptr1 = left;
53    poly* ptr2 = right;
54    poly p1,p2;
55    p2 = *(left + (right - left >> 1));
56    do {
57            while(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)) {
58                    ptr1++;
59            } 
60            while(pTotaldegree(*ptr2, currRing) > pTotaldegree(p2,currRing)) {
61                    ptr2--;
62            }
63            if(ptr1 > ptr2) {
64                    break;
65            }
66            p1    = *ptr1;
67            *ptr1 = *ptr2;
68            *ptr2 = p1;
69    } while(++ptr1 <= --ptr2);
70
71    if(left < ptr2) {
72            qsortDegree(left,ptr2);
73    }
74    if(ptr1 < right) {
75            qsortDegree(ptr1,right);
76    }
77}
78
79/*!
80 * ======================================================================
81 * builds the sum of the entries of the exponent vectors, i.e. the degree
82 * of the corresponding monomial
83 * ======================================================================
84*/
85long sumVector(int* v, int k) {
86    int i;
87    long sum =  0;
88    for(i=1; i<=k; i++) {
89        Print("%d\n",v[i]);
90        Print("%ld\n",sum);
91        sum =   sum + v[i];
92    }
93    return sum;
94}
95
96/*!
97==========================================================================
98compares monomials, i.e. divisibility tests for criterion 1 and criterion 2
99==========================================================================
100*/
101bool compareMonomials(int* m1, int** m2, int numberOfRules, int k) {
102    int i,j;
103    long sumM1  =   sumVector(m1,k);
104    //int k   =   sizeof(m1) / sizeof(int);
105    for(i=0; i<numberOfRules; i++) {
106        if(sumVector(m2[i],k) <= sumM1) {
107            for(j=1; j<=k; j++) {
108                if(m1[j]>m2[i][j]) {
109                    return true;
110                }
111            }   
112        }
113    }
114    return false;
115}
116
117/*
118==================================================
119computes incrementally gbs of subsets of the input
120gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
121==================================================
122*/
123LList* F5inc(int i, poly f_i, LList* gPrev, LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag, int plus, int termination) {
124    //Print("in f5inc\n");           
125    //pWrite(rules->getFirst()->getRuleTerm());
126    int iterationstep = i;
127    int j;
128    //Print("%p\n",gPrev->getFirst());
129    //pWrite(gPrev->getFirst()->getPoly());
130    poly tempNF =   kNF(gbPrev,currQuotient,f_i);
131    f_i         =   tempNF;
132    //gPrev->insert(ONE,i,f_i);
133    gPrev->insert(ONE,gPrev->getLength()+1,f_i);
134    // tag the first element in gPrev of the current index for findReductor()
135    lTag->setFirstCurrentIdx(gPrev->getLast());
136    //Print("1st gPrev: ");
137    //pWrite(gPrev->getFirst()->getPoly());
138    //Print("2nd gPrev: ");
139    //pWrite(gPrev->getFirst()->getNext()->getPoly());
140    //pWrite(gPrev->getFirst()->getNext()->getPoly());   
141    CListOld* critPairs        =   new CListOld();
142    CNode* critPairsMinDeg  =   new CNode();   
143    PList* rejectedGBList = new PList();
144    // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
145    // in the list critPairs
146    criticalPair(gPrev, critPairs, lTag, rTag, rules, rejectedGBList, plus);
147    static LList* sPolyList        =   new LList();
148    //sPolyList->print();
149    // labeled polynomials which have passed reduction() and have to be added to list gPrev
150    static LList* completed        =   new LList();
151    // the reduced labeled polynomials which are returned from subalgorithm reduction()
152    static LList* reducedLPolys     =   new LList();
153    // while there are critical pairs to be further checked and deleted/computed
154    while(NULL != critPairs->getFirst()) { 
155        // critPairs->getMinDeg() deletes the first elements of minimal degree from
156        // critPairs, thus the while loop is not infinite.
157        // adds all to be reduced S-polynomials in the list sPolyList and adds
158        // the corresponding rules to the list rules
159        // NOTE: inside there is a second check of criterion 2 if new rules are
160        // added
161        //int timer4  =   initTimer();
162        //startTimer();
163        //critPairs->print();
164
165        //definition of a local numberUsefulPairs variable for the next degree
166        //step:
167        //if in this degree all pairs are useless, skip this degree step
168        //completely!
169        //long arrideg = critPairs->getFirst()->getData()->getDeg();
170        //if(plus && highestDegreeGBCriticalPair < critPairs->getFirst()->getData()->getDeg()) {
171        //  return gPrev;
172        //}
173        //else {
174        critPairsMinDeg =   critPairs->getMinDeg();
175        //numberUsefulPairsMinDeg = computeUsefulMinDeg(critPairsMinDeg);
176        //if(numberUsefulPairs > 0) {
177          //if(numberUsefulPairsMinDeg > 0) {
178            //Print("number of useful pairs:  %d\n",numberUsefulPairs);
179            //Print("number of useless pairs: %d\n\n",numberUselessPairs);
180          //Print("Degree of following reduction: %d\n",critPairsMinDeg->getData()->getDeg()); 
181        long degreecheck = critPairsMinDeg->getData()->getDeg(); 
182       
183          computeSPols(critPairsMinDeg,rTag,rules,sPolyList, rejectedGBList);
184        //}
185          //}
186        //}
187        //else {
188        //  return gPrev;
189        //}
190        //timer4  =   getTimer();
191        //Print("SPOLS TIMER: %d\n",timer4);
192        //spolsTime  =   spolsTime  +   timer4;
193        // DEBUG STUFF FOR SPOLYLIST
194        LNode* temp     =   sPolyList->getFirst();
195        //while(NULL != temp && NULL != temp->getLPoly()) {
196            //Print("Spolylist element: ");
197            //pWrite(temp->getPoly());
198            //temp    =   temp->getNext();
199        //}
200        // reduction process of new S-polynomials and also adds new critical pairs to critPairs
201        //int timer3  =   initTimer();
202        //startTimer();
203        //sPolyList->print();
204        //reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
205        //Print("BEFORE REDUCTION: \n");
206        //Print("number of useful pairs:  %d\n",numberUsefulPairs);
207        //Print("number of useless pairs: %d\n\n",numberUselessPairs);
208        newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination, rejectedGBList, plus);
209        //Print("ITERATION:  %d",iterationstep);
210        //Print("NAECHSTER GRAD:  %ld",degreecheck);
211        //sleep(5);
212        //if(i == 5 && pDeg(gPrev->getLast()->getPoly()) == 8) {
213        //  Print("RAUS BEI DEG 8 \n");
214        //  return gPrev;
215        //}
216        //Print("ARRIS DEG: %ld\n",arrideg);
217        // Arris idea stated by John in an email
218        //if(arrisCheck(critPairs->getFirst(),gPrev->getFirst(),arrideg)) {
219        //  Print("ARRIS DEGREE: %ld\n", arrideg);
220        //  return gPrev;
221        //}
222       
223       
224        //bool aha = checkDGB(gPrev);
225       
226
227        //timer3      =  getTimer();
228        //reductionTime = reductionTime + timer3;
229        //Print("REDUCTION TIMER: %d\n",timer3);
230        // DEBUG STUFF FOR GPREV
231        //temp    =   gPrev->getFirst();
232        //int number  =   1;
233        //Print("\n\n");
234        //while(NULL != temp) {
235        //    Print("%d.  ",number);
236        //    pWrite(temp->getPoly());
237        //    temp    =   temp->getNext();
238        //    number++;
239        //    Print("\n");
240        //}
241        //sleep(5);
242   
243    }
244    //Print("REDUCTION DONE\n");
245    //Print("%p\n",rules->getFirst());
246    //Print("%p\n",rTag->getFirst());
247    //if(rules->getFirst() != rTag->getFirst()) {
248        //Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n");
249        //rTag->insert(rules->getFirst());
250    //}
251    //else {
252        //Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
253    //}
254    lTag->insert(lTag->getFirstCurrentIdx());
255    //Print("INDEX: %d\n",tempTag->getIndex());
256    //pWrite(tempTag->getPoly());
257    //Print("COMPLETED FIRST IN F5INC: \n");
258    //Print("1st gPrev: ");
259    //pWrite(gPrev->getFirst()->getPoly());
260    //Print("2nd gPrev: ");
261    //pWrite(gPrev->getFirst()->getNext()->getPoly());
262    //Print("3rd gPrev: ");
263    //pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly());
264    //delete sPolyList;
265    //critPairs->print();
266    delete critPairs;
267    //Print("IN F5INC\n");
268    /*
269    Print("\n\n\nRULES: \n");
270        RNode* tempR    =   rules->getFirst();
271        Print("%p\n",tempR);
272        int t   = 1;
273        while(NULL != tempR) {
274            Print("ADDRESS OF %d RNODE: %p\n",t,tempR);
275            Print("ADDRESS OF RULE: %p\n",tempR->getRule());
276            pWrite(tempR->getRuleTerm());
277            Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
278            Print("%d\n\n",tempR->getRuleIndex());
279            tempR   =   tempR->getNext();
280            t++;
281        }
282    */
283    //gPrev->print();
284    //Print("COMPLETE REDUCTION TIME UNTIL NOW: %d\n",reductionTime);
285    //Print("COMPLETE SPOLS TIME UNTIL NOW:     %d\n",spolsTime);
286    degreeBound = 0;
287    return gPrev;
288}
289
290
291
292bool checkDGB(LList* gPrev) {
293  Print("D-GB CHECK at degree %ld\n",pDeg(gPrev->getLast()->getPoly()));
294  LNode* temp = gPrev->getFirst();
295  LNode* temp2;
296  bool isDGb = 0;
297  // construct the d-GB gb
298  ideal gb =   idInit(gPrev->getLength(),1);
299  for(int j=0;j<=gPrev->getLength()-1;j++) {
300          gb->m[j] =   temp->getPoly();
301          pWrite(gb->m[j]);
302          temp        =   temp->getNext();
303  }
304  /*
305  Kstd1_deg = pDeg(gPrev->getLast()->getPoly());
306  BITSET save = test;
307  test |= Sy_bit(OPT_DEGBOUND);
308  kStd();
309  test = save;
310  */
311  temp = gPrev->getFirst();
312  while(NULL != temp) {
313    temp2 = temp->getNext();
314    number nOne = nInit(1);
315    poly lcm = pOne();
316    poly sp = pOne();
317    while(NULL != temp2) {
318      pLcm(temp->getPoly(),temp2->getPoly(),lcm);
319      pSetCoeff(lcm,nOne);
320      pSetm(lcm);
321      Print("LCM:   ");
322      pWrite(lcm);
323      if(pDeg(lcm) <= pDeg(gPrev->getLast()->getPoly())) {
324        poly u1 = pOne();
325        poly u2 = pOne();
326        u1  = pDivide(lcm,pHead(temp->getPoly()));
327        pSetCoeff(u1,nOne);
328        u2  = pDivide(lcm,pHead(temp2->getPoly()));
329        pSetCoeff(u2,nOne);
330        sp      =   ksOldSpolyRedNew(ppMult_qq(u1,temp->getPoly()),
331            ppMult_qq(u2,temp2->getPoly()));
332        pNorm(sp);
333     
334        poly reducer  = pOne();
335        //reducer       = gb->m[0];
336        int i         = 0;
337        pWrite(pHead(sp));
338       
339        while(i<IDELEMS(gb)) {
340          reducer = gb->m[i];
341          if(pDivisibleBy(reducer,pHead(sp))) {
342            poly uReducer = pOne();
343            uReducer = pDivide(lcm,pHead(reducer));
344            pSetCoeff(uReducer,nOne);
345            sp = ksOldSpolyRedNew(sp,ppMult_qq(uReducer,reducer));
346            //pNorm(tempSP);
347            //sp = tempSP;
348            pNorm(sp);
349            pWrite(sp);
350            i = 0;
351          }
352          else {
353            i++;
354          }
355        }
356       
357        pWrite(pHead(sp));
358      }
359      temp2 = temp2->getNext();
360    }
361    temp  = temp->getNext();
362  }
363  Print("------------------\n");
364  return isDGb;
365}
366
367/*
368 * Arris Check if we are finished after the current degree step:
369 * Checks all remaining critical pairs, i.e. those of higher degree,
370 * by the two Buchberger criteria.
371 * return value: 0, if all remaining critical pairs are deleted by
372 *                  Buchberger's criteria
373 *               1, otherwise
374 */
375bool arrisCheck(CNode* first, LNode* firstGCurr, long arrideg) {
376  CNode* temp = first;
377 
378  //product criterion check
379  while(NULL != temp) {
380    if(!pLmEqual(pHead(temp->getLp2Poly()),temp->getT1())) {
381        return 0;
382    }
383    temp = temp->getNext();
384  }
385
386  // chain criterion
387  LNode* tempPoly = firstGCurr;
388  while(NULL != tempPoly) {
389    LNode* tempPoly2 = tempPoly->getNext();
390    while(NULL != tempPoly2) {
391      number nOne = nInit(1);
392      poly lcm = pOne();
393      pLcm(tempPoly->getPoly(),tempPoly2->getPoly(),lcm);
394      pSetCoeff(lcm,nOne);
395      pSetm(lcm);
396      if(pDeg(lcm) > arrideg) {
397        LNode* tempPoly3 = firstGCurr;
398        while(NULL != tempPoly3) {
399          if(tempPoly3 != tempPoly2 && tempPoly3 != tempPoly && pDivisibleBy(tempPoly3->getPoly(),lcm)) {
400        poly lcm1 = pOne();
401        poly lcm2 = pOne();
402        pLcm(tempPoly3->getPoly(),tempPoly->getPoly(),lcm1);
403        pSetCoeff(lcm1,nOne);
404        pSetm(lcm1);
405        pLcm(tempPoly3->getPoly(),tempPoly2->getPoly(),lcm2);
406        pSetCoeff(lcm2,nOne);
407        pSetm(lcm2);
408        if(pDeg(lcm1) < pDeg(lcm) && pDeg(lcm2) < pDeg(lcm)) {
409          return 0;
410        }
411      }
412        tempPoly3 = tempPoly3->getNext();
413        }
414      }
415      tempPoly2 = tempPoly2->getNext();
416    }
417    tempPoly = tempPoly->getNext();
418  }
419  return 1;
420}
421
422 
423 
424/*
425================================================================
426computes a list of critical pairs for the next reduction process
427the first element is always "useful" thus the critical pair
428computed is either "useful" or "useless" depending on the second
429element which generates the critical pair.
430first element in gPrev is always the newest element which must
431build critical pairs with all other elements in gPrev
432================================================================
433*/
434inline void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList, int plus) {
435    //Print("IN CRITPAIRS\n");
436    // initialization for usage in pLcm()
437    number nOne         =   nInit(1);
438    LNode* newElement   =   gPrev->getLast();
439    LNode* temp         =   gPrev->getFirst();
440    poly u1             =   pOne();
441    poly u2             =   pOne();
442    poly lcm            =   pOne();
443    poly t              =   pHead(newElement->getPoly());
444    RuleOld* testedRuleOld    =   NULL;
445    //Print("NEW:   ");
446    //pWrite(newElement->getPoly());
447    //Print("ADDRESS:  %p",newElement);
448    if(NULL != rules->getFirst()) {
449        testedRuleOld  =   rules->getFirst()->getRuleOld();
450    }
451    // computation of critical pairs
452    while( gPrev->getLast() != temp) {
453        //Print("TEMP:  ");
454        //pWrite(pHead(temp->getPoly()));
455        //Print("ADDRESS:  %p",temp);
456        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
457        pSetCoeff(lcm,nOne);
458        // computing factors u2 for new labels
459        u1 = pDivide(lcm,t);
460        if(NULL == u1) {
461            break;
462        }
463        pSetCoeff(u1,nOne);
464        u2 = pDivide(lcm,pHead(temp->getPoly()));
465        pSetCoeff(u2,nOne);
466        int degree = pDeg(ppMult_qq(u2,pHead(temp->getPoly()))); 
467        // testing both new labels by the F5 Criterion
468        if(!temp->getDel()) {
469          if(plus && highestDegreeGBCriticalPair < degree) {
470            highestDegreeGBCriticalPair = degree;
471          }
472          if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
473            && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag) 
474            && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
475              // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
476              // label as first element in the CPairOld
477              if(newElement->getIndex() == temp->getIndex() && 
478              -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
479                  CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, 
480                                  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 0 , testedRuleOld);                   
481                  critPairs->insert(cp);
482                  // counting the number of useful pairs
483                  numberUsefulPairs++;
484              }
485              else {
486                  CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, 
487                                  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 0, testedRuleOld);                   
488                  critPairs->insert(cp);
489                  // counting the number of useful pairs
490                  numberUsefulPairs++;
491              }
492          }
493          else {
494            // TODO: generate a list of lcms of rejected GB critical pairs and
495            //       check F5 critical pairs with it at their creation
496            //Print("--------------------------------------------------------------------\n");
497            //Print("--------------------------------------------------------------------\n");
498            pSetm(lcm);
499            rejectedGBList->insert(lcm);
500            //Print("-----------------------REJECTED IN CRIT PAIR------------------------\n");
501            //pWrite(lcm);
502            //Print("--------------------------------------------------------------------\n");
503            //rejectedGBList->print();
504          }
505        }
506        else {
507        //Print("LABEL:  ");
508        //pWrite(ppMult_qq(u1,newElement->getTerm()));
509          //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair
510            if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
511              && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag) 
512              && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
513                // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
514                // label as first element in the CPairOld
515                if(newElement->getIndex() == temp->getIndex() && 
516                -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
517                    CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, 
518                                    temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);                   
519                    critPairs->insert(cp);
520                    numberUselessPairs++;
521                }
522                else {
523                    CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, 
524                                    newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);                   
525                    critPairs->insert(cp);
526                    numberUselessPairs++;
527                }
528            }
529          //}
530        }
531        temp    =   temp->getNext();
532    }
533}
534
535
536
537/*
538================================================================
539computes a list of critical pairs for the next reduction process
540the first element is always "useless" thus the critical pair
541computed is "useless".
542first element in gPrev is always the newest element which must
543build critical pairs with all other elements in gPrev
544================================================================
545*/
546inline void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList) {
547    //Print("IN CRITPAIRS\n");
548    // initialization for usage in pLcm()
549    number nOne         =   nInit(1);
550    LNode* newElement   =   gPrev->getLast();
551    LNode* temp         =   gPrev->getFirst();
552    poly u1             =   pOne();
553    poly u2             =   pOne();
554    poly lcm            =   pOne();
555    poly t              =   pHead(newElement->getPoly());
556    RuleOld* testedRuleOld    =   NULL;
557    if(NULL != rules->getFirst()) {
558        testedRuleOld  =   rules->getFirst()->getRuleOld();
559    }
560    // computation of critical pairs
561    while( gPrev->getLast() != temp) {
562        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
563        pSetCoeff(lcm,nOne);
564        // computing factors u2 for new labels
565        u1 = pDivide(lcm,t);
566        if(NULL == u1) {
567            break;
568        }
569        pSetCoeff(u1,nOne);
570        u2 = pDivide(lcm,pHead(temp->getPoly()));
571        pSetCoeff(u2,nOne);
572       // testing both new labels by the F5 Criterion
573        //Print("LABEL:  ");
574        //pWrite(ppMult_qq(u1,newElement->getTerm()));
575        //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair
576          if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
577            && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag) 
578            && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
579              // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater
580              // label as first element in the CPairOld
581              if(newElement->getIndex() == temp->getIndex() && 
582              -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
583                  CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, 
584                                  temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);                   
585                  critPairs->insert(cp);
586                  numberUselessPairs++;
587              }
588              else {
589                  CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, 
590                                  newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);                   
591                  critPairs->insert(cp);
592                  numberUselessPairs++;
593              }
594          }
595        //}
596        temp    =   temp->getNext();
597    }
598}
599
600
601
602/*
603========================================
604Criterion 1, i.e. Faugere's F5 Criterion
605========================================
606*/
607inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) {
608    // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
609        int idx =   l->getIndex();
610    int i;
611    if(idx == 1) {
612        //Print("HIER\n");
613        return false;
614    }
615    else {
616        LNode* testNode =   gPrev->getFirst();
617        // save the monom t1*label_term(l) as it is tested various times in the following
618        poly u1 = ppMult_qq(t,l->getTerm());
619        //Print("------------------------------IN CRITERION 1-----------------------------------------\n");
620        //Print("TESTED ELEMENT: ");
621        //pWrite(l->getPoly());
622        //pWrite(l->getTerm());
623        //pWrite(ppMult_qq(t,l->getTerm()));
624        //Print("%d\n\n",l->getIndex());
625        while(testNode->getIndex() < idx) { // && NULL != testNode->getLPoly()) {
626            //pWrite(testNode->getPoly());
627            //Print("%d\n",testNode->getIndex());
628            if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
629                //Print("Criterion 1 NOT passed!\n");
630                if(idx != gPrev->getLast()->getIndex()) {
631                    //Print("DOCH!\n");
632                }
633                return true;
634            }
635            //pWrite(testNode->getNext()->getPoly());
636            testNode    =   testNode->getNext();
637        }
638        /*
639        ideal testId    =   idInit(idx-1,1);
640        for(i=0;i<idx-1;i++) {
641            testId->m[i]  =   pHead(testNode->getPoly());
642            testNode        =   testNode->getNext();
643        }
644        poly temp   =   kNF(testId,currQuotient,u1);
645        //pWrite(temp);
646        for(i=0;i<IDELEMS(testId);i++) {
647            testId->m[i]    =   NULL;
648        }
649        idDelete(&testId);
650        if(NULL == temp) {
651            //if(l->getIndex() != gPrev->getFirst()->getIndex()) {
652            //    Print("----------------------------Criterion1 not passed----------------------------------\n");
653            //}
654            return true;
655        }
656        */
657        return false;
658    }
659}
660
661
662
663/*
664=====================================
665Criterion 2, i.e. Rewritten Criterion
666=====================================
667*/
668inline bool criterion2(int idx, poly t, LNode* l, RList* rules, RTagList* rTag) {
669    //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n");
670    /* 
671    Print("RULES: \n");
672        RNode* tempR    =   rules->getFirst();
673        Print("%p\n",tempR);
674        int i   = 1;
675        while(NULL != tempR) {
676            Print("ADDRESS OF %d RNODE: %p\n",i,tempR);
677            Print("ADDRESS OF RULE: %p\n",tempR->getRule());
678            pWrite(tempR->getRuleTerm());
679            Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
680            Print("%d\n\n",tempR->getRuleIndex());
681            tempR   =   tempR->getNext();
682            i++;
683        }
684        //Print("TESTED ELEMENT: ");
685        //pWrite(l->getPoly());
686        //pWrite(l->getTerm());
687        //pWrite(ppMult_qq(t,l->getTerm()));
688        //Print("%d\n\n",l->getIndex());
689      */
690// start at the previously added element to gPrev, as all other elements will have the same index for sure
691    if(idx > l->getIndex()) {
692        return false;
693    }
694   
695    RNode* testNode; // =   new RNode();
696    testNode    =   rules->getFirst();
697    /*
698     if(NULL == rTag->getFirst()) {
699        if(NULL != rules->getFirst()) {
700            testNode    =   rules->getFirst();
701        }
702        else {
703            return false;
704        }
705    }
706   
707     else {
708
709        if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
710            testNode    =   rules->getFirst();
711        }
712        else {
713       //Print("HIER\n");
714            //Print("DEBUG\n");
715        //Print("L INDEX: %d\n",l->getIndex());
716            *-------------------------------------
717             * TODO: WHEN INTERREDUCING THE GB THE
718             *       INDEX OF THE PREVIOUS ELEMENTS
719             *       GETS HIGHER!
720             *-----------------------------------*
721            //testNode    =   rules->getFirst();
722            testNode    =   rTag->get(l->getIndex());
723            if(NULL == testNode) {
724                testNode    =   rules->getFirst();
725            }
726            //Print("TESTNODE ADDRESS: %p\n",testNode);
727        }
728    }
729    */
730    //testNode    =   rules->getFirst();
731        // save the monom t1*label_term(l) as it is tested various times in the following
732    poly u1 = ppMult_qq(t,l->getTerm());
733    // first element added to rTag was NULL, check for this
734    //Print("%p\n",testNode->getRule());
735    // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
736    //Print("TESTNODE: %p\n",testNode);
737    //pWrite(testNode->getRuleTerm());
738    if(NULL != testNode ) {   
739        //pWrite(testNode->getRuleTerm());
740    }
741    if(NULL != testNode) {
742        if(testNode->getRuleOld() == l->getRuleOld()) {
743            //Print("%p\n%p\n",testNode->getRule(),l->getRule());
744            //Print("EQUAL\n");
745        }
746        else {
747            //Print("NOT EQUAL\n");
748        }
749    }
750    while(NULL != testNode && testNode->getRuleOld() != l->getRuleOld() 
751          && l->getIndex() == testNode->getRuleOldIndex()) {
752        //Print("%p\n",testNode);
753        //pWrite(testNode->getRuleTerm());
754        //pWrite(t);
755        //pWrite(l->getTerm());
756        //pWrite(u1);
757        //Print("%d\n",testNode->getRuleIndex());
758        if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) {
759            //Print("-----------------Criterion 2 NOT passed!-----------------------------------\n");
760            //Print("INDEX: %d\n",l->getIndex());
761            pDelete(&u1);
762    //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
763            return true;
764        }
765                testNode    =   testNode->getNext();
766    }
767    //delete testNode;
768    pDelete(&u1);
769    //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
770    return false;
771}
772
773
774
775/*
776=================================================================================================================
777Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter
778=================================================================================================================
779*/
780inline bool criterion2(poly t, LPolyOld* l, RList* rules, RuleOld* testedRuleOld) {
781    //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n");
782    //Print("LAST RuleOld TESTED: %p",testedRuleOld);
783    /*
784    Print("RULES: \n");
785        RNode* tempR    =   rules->getFirst();
786        while(NULL != tempR) {
787            pWrite(tempR->getRuleTerm());
788            Print("%d\n\n",tempR->getRuleIndex());
789            tempR   =   tempR->getNext();
790        }
791        //Print("TESTED ELEMENT: ");
792        //pWrite(l->getPoly());
793        //pWrite(l->getTerm());
794        //pWrite(ppMult_qq(t,l->getTerm()));
795        //Print("%d\n\n",l->getIndex());
796    */
797// start at the previously added element to gPrev, as all other elements will have the same index for sure
798        RNode* testNode =   rules->getFirst();
799    // save the monom t1*label_term(l) as it is tested various times in the following
800    poly u1 = ppMult_qq(t,l->getTerm());
801        // first element added to rTag was NULL, check for this
802        while(NULL != testNode && testNode->getRuleOld() != testedRuleOld) {
803        //pWrite(testNode->getRuleTerm());
804        if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) {
805            //Print("--------------------------Criterion 2 NOT passed!------------------------------\n");
806            //Print("INDEX: %d\n",l->getIndex());
807            pDelete(&u1);
808    //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
809            return true;
810        }
811                testNode    =   testNode->getNext();
812    }
813    pDelete(&u1);
814    //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
815    return false;
816}
817
818/*
819 * check for useful pairs in the given subset of critical pairs
820 */
821int computeUsefulMinDeg(CNode* first) {
822  CNode* temp = first;
823  int numberUsefulPairsMinDeg = 0;
824  while(NULL != temp) {
825    if(!temp->getDel()) {
826      numberUsefulPairsMinDeg++;
827    }
828    temp = temp->getNext();
829  }
830  return numberUsefulPairsMinDeg;
831}
832/*
833==================================
834Computation of S-Polynomials in F5
835==================================
836*/
837void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList, PList* rejectedGBList) { 
838    CNode* temp         =   first;
839    //Print("\nDegree:  %d\n",temp->getData()->getDeg());
840    // only GB-critical pairs are computed
841    //while(NULL != temp && temp->getDel()) {
842    //  temp = temp->getNext();
843    //}
844    //if(temp->getData()->getDeg() == 11) {
845    //  Print("PAIRS OF DEG 11:\n");
846    //}
847    RList* f5rules = new RList();
848    CListOld* f5pairs = new CListOld();
849    poly sp     =   pInit();
850    number sign =   nInit(-1);   
851    //Print("###############################IN SPOLS##############################\n");
852    //first->print();
853/*
854 * first of all: do everything for GB critical pairs
855 */
856    while(NULL != temp) {
857    //  if(temp->getData()->getDeg() == 11) {
858        //Print("--------------------------\n");
859        //Print("redundant? %d\n",temp->getDel());
860        //pWrite(pHead(temp->getLp1Poly()));
861        //Print("redundant: %d\n",temp->getAdLp1()->getDel());
862        //pWrite(pHead(temp->getLp2Poly()));
863        //Print("redundant: %d\n",temp->getAdLp2()->getDel());
864        //pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
865        //  sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
866        //      ppMult_qq(temp->getT2(),temp->getLp2Poly()));
867          //Print("BEGIN SPOLY2\n====================\n");
868        //  pNorm(sp);
869        //  pWrite(pHead(sp));
870        //Print("--------------------------\n");
871      //}
872      if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
873      //if(temp->getDel() == 0 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
874        if(temp->getLp2Index() == temp->getLp1Index()) {
875          if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) {
876            sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
877                ppMult_qq(temp->getT2(),temp->getLp2Poly()));
878            pNorm(sp);
879            if(NULL == sp) {
880              reductionsToZero++;
881              rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
882              numberOfRules++;
883              pDelete(&sp);
884            }
885            else {
886              rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
887              numberOfRules++;
888              sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
889            //Print("INSERTED\n");
890              numberOfSpolys++;
891            }
892          }
893          else {
894            if(highestDegreeGBCriticalPair < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) {
895              highestDegreeGBCriticalPair = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()));
896            }
897            rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
898            //Print("rejected!\n"); 
899
900            //Print("CRITERION 2 in SPOLS 2nd generator\n");
901          }
902        }
903        else { 
904          sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
905              ppMult_qq(temp->getT2(),temp->getLp2Poly()));
906          //Print("BEGIN SPOLY2\n====================\n");
907          pNorm(sp);
908          //pWrite(sp);
909          //Print("END SPOLY2\n====================\n");
910          if(NULL == sp) {
911            reductionsToZero++;
912            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
913            numberOfRules++;
914            pDelete(&sp);
915          }
916          else {
917            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
918            numberOfRules++;
919            sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
920            //Print("INSERTED\n");
921            numberOfSpolys++;
922          }
923        }
924      }
925      /*     
926      if(temp->getDel() == 0 && criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
927        //Print("rejected!\n"); 
928        rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
929      }
930     
931       
932      if(temp->getDel() == 1 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) {
933        if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) {
934          highestDegree   = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()));
935        }   
936        if(temp->getLp2Index() == temp->getLp1Index()) {
937          if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) {
938            sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
939                ppMult_qq(temp->getT2(),temp->getLp2Poly()));
940            pNorm(sp);
941            if(NULL == sp) {
942              reductionsToZero++;
943              rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
944              numberOfRules++;
945              pDelete(&sp);
946            }
947            else {
948              rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
949              numberOfRules++;
950
951
952              // save the address of the rule again in a different
953              // list
954
955              f5rules->insert(rules->getFirst()->getRuleOld());
956              f5pairs->insertWithoutSort(temp->getData());       
957              ///////////////////////////////////////
958
959              //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
960            }
961          }
962        }
963        else {
964          sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
965              ppMult_qq(temp->getT2(),temp->getLp2Poly()));
966          //Print("BEGIN SPOLY2\n====================\n");
967          pNorm(sp);
968          //pWrite(sp);
969          //Print("END SPOLY2\n====================\n");
970          if(NULL == sp) {
971            reductionsToZero++;
972            //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
973            numberOfRules++;
974            pDelete(&sp);
975          }
976          else {
977            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
978            numberOfRules++;
979            // save the address of the rule again in a different
980            // list
981
982            f5rules->insert(rules->getFirst()->getRuleOld());
983            f5pairs->insertWithoutSort(temp->getData());       
984            ///////////////////////////////////////
985            //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
986            //  numberOfSpolys++;
987          }
988        }
989      }
990        // the following else is not needed at all as we are checking
991        // F5-critical pairs in this step
992        /*
993           else {
994           if(!temp->getDel()) {
995           rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
996           }
997
998           }
999           */
1000
1001        temp    =   temp->getNext();
1002
1003      }
1004     
1005      /*
1006      temp = f5pairs->getFirst();
1007      RNode* tempRule = f5rules->getFirst();
1008      int howmany = 1;
1009      while(NULL != temp) {
1010        //Print("RULE:  ");
1011        //pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term()));
1012        sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
1013                                     ppMult_qq(temp->getT2(),temp->getLp2Poly()));
1014        pNorm(sp);
1015        if(rejectedGBList->check(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())))) { //|| (temp->getData()->getDeg() == 10 && howmany == 2)) {
1016          if((temp->getData()->getDeg() == 10) && (howmany == 2)) {
1017            //Print("HIER DRIN IM SAFTLADEN\n");
1018          }
1019          sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld());
1020              numberOfSpolys++;
1021              howmany++;
1022        }
1023        else {
1024          numberRejectedF5CriticalPairs++;
1025              howmany++;
1026          if(numberRejectedF5CriticalPairs < -1) { // ||
1027          }
1028          else {
1029             //numberRejectedF5CriticalPairs == 7) {
1030            /*
1031            Print("--------------------------------- rejected F5-critical pair-------------------------------------\n");
1032            pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
1033            Print("Label: ");
1034            pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term()));
1035            Print("%d\n",temp->getDel());
1036            Print("Comes from:\n ");
1037            pWrite(pHead(temp->getLp1Poly()));
1038            Print("Label: ");
1039            pWrite(temp->getLp1Term());
1040            Print("%d\n",temp->getLp1Index());
1041            pWrite(pHead(temp->getLp2Poly()));
1042            Print("Label: ");
1043            pWrite(temp->getLp2Term());
1044            Print("%d\n",temp->getLp2Index());
1045            //Print("--------------------------------------LIST OF GB PAIRS REJECTED-----------------------------------------\n");
1046            //rejectedGBList->print();
1047            Print("--------------------------------------------------------------------------------------------------------\n");
1048            //if(temp->getLp1Index() < 7) {
1049              sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld());
1050           
1051            //}
1052          //numberOfSpolys++;
1053          }
1054        //pSetExp(tempRule->getRuleOld()->getTerm(),1,1000);
1055        }
1056        temp      = temp->getNext();
1057        tempRule  = tempRule->getNext();
1058
1059      }
1060      */ 
1061      // these critical pairs can be deleted now as they are either useless for further computations or
1062      // already saved as an S-polynomial to be reduced in the following
1063      delete first;   
1064//Print("NUMBER SPOLYS: %d\n", numberOfSpolys);
1065//Print("SPOLY LIST: \n");
1066//LNode* tempSpoly = sPolyList->getFirst();
1067//if(NULL != tempSpoly) {
1068//  pWrite(pHead(tempSpoly->getPoly()));
1069//  tempSpoly = tempSpoly->getNext();
1070//}
1071//Print("-----SP------\n");
1072//else {
1073//  Print("EMPTY SPOLYLIST!\n");
1074//}
1075}
1076
1077/*
1078========================================================================
1079reduction including subalgorithm topReduction() using Faugere's criteria
1080========================================================================
1081*/
1082void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, 
1083                 ideal gbPrev, PList* rejectedGBList, int plus) { 
1084    //Print("##########################################In REDUCTION!########################################\n");
1085    // check if sPolyList has any elements
1086    // NOTE: due to initialization sPolyList always has a default NULL element
1087    LNode* temp = sPolyList->getFirst();
1088    while(NULL != temp) {
1089        // temp is the first element in the sPolyList which should be reduced
1090        // due to earlier sorting this is the element of minimal degree AND
1091        // minimal label
1092        // delete the above first element from sPolyList, temp will be either reduced to
1093        // zero or added to gPrev, but never come back to sPolyList
1094        //pWrite(sPolyList->getFirst()->getPoly());
1095        //Print("LIST OF SPOLYNOMIALS!\n");
1096        //sPolyList->print();
1097        sPolyList->setFirst(temp->getNext());
1098        poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
1099        if(NULL != tempNF) {
1100            pNorm(tempNF);
1101            temp->setPoly(tempNF);
1102            // try further reductions of temp with polynomials in gPrev
1103            // with label index = current label index: this is done such that there
1104            // is no label corruption during the reduction process
1105            //Print("lower label reduction:  ");
1106            //pWrite(tempNF);
1107            topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus);
1108       
1109        }
1110        else {
1111            reductionsToZero++;
1112            delete temp;
1113        }
1114        //if(NULL != temp->getPoly()) {
1115        //    criticalPair(gPrev,critPairs,lTag,rTag,rules);
1116        //}
1117        temp =   sPolyList->getFirst();
1118    }
1119    //sPolyList->print();
1120    //delete sPolyList;
1121}   
1122
1123/*
1124========================================================================
1125reduction including subalgorithm topReduction() using Faugere's criteria
1126========================================================================
1127*/
1128void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag, 
1129                 ideal gbPrev, int termination, PList* rejectedGBList, int plus) { 
1130    //Print("##########################################In REDUCTION!########################################\n");
1131    // check if sPolyList has any elements
1132    // NOTE: due to initialization sPolyList always has a default NULL element
1133    //Print("--1--\n");
1134    LNode* temp = sPolyList->getFirst();
1135    //Print("START OF REDUCTION:  ");
1136    while(NULL != temp) {
1137        numberOfReductions++;
1138        // temp is the first element in the sPolyList which should be reduced
1139        // due to earlier sorting this is the element of minimal degree AND
1140        // minimal label
1141        // delete the above first element from sPolyList, temp will be either reduced to
1142        // zero or added to gPrev, but never come back to sPolyList
1143        //Print("LIST OF SPOLYNOMIALS!\n");
1144        //sPolyList->print();
1145        //pWrite(sPolyList->getFirst()->getPoly());
1146        sPolyList->setFirst(temp->getNext());
1147        //if(pDeg(temp->getPoly()) > 11) {
1148        //  Print("YES!!!!!!!!!!!!!!!!\n");
1149        //}
1150        //pWrite(temp->getPoly());
1151        //poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
1152        //Print("!!!\n");
1153        //if(NULL != tempNF) {
1154            //pNorm(tempNF);
1155            //temp->setPoly(tempNF);
1156            //Print("lower label reduction:  ");
1157            //pWrite(tempNF);
1158            // try further reductions of temp with polynomials in gPrev
1159            // with label index = current label index: this is done such that there
1160            // is no label corruption during the reduction process
1161            findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus); 
1162        //}
1163        //else {
1164        //    reductionsToZero++;
1165        //    delete temp;
1166        //}
1167        //if(NULL != temp->getPoly()) {
1168        //    criticalPair(gPrev,critPairs,lTag,rTag,rules);
1169        //}
1170        //Print("HIER AUCH ?\n");
1171        //Print("--2--\n");
1172        //sPolyList->print();
1173        //critPairs->print();
1174        temp =   sPolyList->getFirst();
1175        //Print("%p\n",temp);
1176    }
1177    //sPolyList->print();
1178    //delete sPolyList;
1179    //Print("REDUCTION FERTIG\n");
1180}     
1181
1182
1183/*!
1184 * ================================================================================
1185 * searches for reducers of temp similar to the symbolic preprocessing of F4  and
1186 * divides them into a "good" and "bad" part:
1187 *
1188 * the "good" ones are the reducers which do not corrupt the label of temp, with
1189 * these the normal form of temp is computed
1190 *
1191 * the "bad" ones are the reducers which corrupt the label of temp, they are tested
1192 * later on for possible new rules and S-polynomials to be added to the algorithm
1193 * ================================================================================
1194*/
1195void 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) {
1196    int canonicalize    =   0;
1197    //int timerRed        =   0;
1198    bool addToG         =   1;
1199    number sign         =   nInit(-1);
1200    LList* good         =   new LList();
1201    LList* bad          =   new LList();
1202    LList* monomials    =   new LList(l->getLPolyOld());
1203    poly u              =   pOne();
1204    number nOne         =   nInit(1);
1205    LNode* tempRed      =   lTag->getFirstCurrentIdx();
1206    LNode* tempMon      =   monomials->getFirst();
1207    poly tempPoly       =   pInit();
1208    poly redPoly        =   NULL;
1209    int idx             =   l->getIndex();
1210    //Print("IN FIND REDUCERS:  ");
1211    //pWrite(l->getPoly());
1212    tempPoly    =   pCopy(l->getPoly());
1213    //tempMon->setPoly(tempPoly);
1214    //while(NULL != tempMon) {
1215        // iteration over all monomials in tempMon
1216        kBucket* bucket  =   kBucketCreate(currRing);
1217        kBucketInit(bucket,tempPoly,0);
1218        tempPoly    =   kBucketGetLm(bucket);
1219        //Print("\n\n\nTO BE REDUCED:  ");
1220        //pWrite(l->getPoly());
1221        //pWrite(l->getTerm());
1222        //pWrite(tempPoly);
1223        while(NULL != tempPoly) {
1224            // iteration of all elements in gPrev of the current index
1225            tempRed =   gPrev->getFirst();
1226            while(NULL != tempRed) {
1227                //Print("TEMPREDPOLY:  ");
1228                //pWrite(tempRed->getPoly());
1229                if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
1230                    u   =   pDivideM(pHead(tempPoly),pHead(tempRed->getPoly()));
1231                    //Print("U:  ");
1232                    //pWrite(u);
1233                    if(pLmCmp(u,pOne()) != 0) { // else u = 1 and no test need to be done!
1234                    if(tempRed->getIndex() != idx) {
1235                            // passing criterion1 ?
1236                            if(!criterion1(gPrev,u,tempRed,lTag)) {
1237                                    poly tempRedPoly    =   tempRed->getPoly();
1238                                    //Print("REDUCER: ");
1239                                    //pWrite(tempRedPoly);
1240                                    pIter(tempRedPoly);
1241                                    int lTempRedPoly    =   pLength(tempRedPoly);
1242                                    kBucketExtractLm(bucket);
1243                                    kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1244                                    canonicalize++;
1245                                    //Print("Reduction\n");
1246                                    if(!(canonicalize % 50)) {
1247                                        kBucketCanonicalize(bucket);
1248                                    }
1249                                    tempPoly    =   kBucketGetLm(bucket);
1250                                    //Print("TEMPPOLY:  ");
1251                                    //pWrite(tempPoly);
1252                                    if(NULL != tempPoly) {
1253                                        tempRed     =   gPrev->getFirst();
1254                                        continue;
1255                                    }
1256                                    else {
1257                                        break;
1258                                    }
1259                             }   
1260                   
1261                    }
1262                    else {
1263                        if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) {
1264                         //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n");
1265                                      //pWrite(u);
1266                                      //pWrite(tempRed->getTerm());
1267                                      //pWrite(pHead(tempRed->getPoly()));
1268                                      addToG  = 0;
1269                        }
1270                        if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) {
1271                            // passing criterion2 ?
1272                            if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) {
1273                                // passing criterion1 ?
1274                                if(!criterion1(gPrev,u,tempRed,lTag)) {
1275                                    if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1276                                        if(NULL == redPoly) {
1277                                            bad->insert(tempRed->getLPolyOld());
1278                                            addToG  = 1;
1279                                            //poly tempRedPoly    =   tempRed->getPoly();
1280                                            //break;
1281                                        }
1282                                    }
1283                                    else {
1284                                        poly tempRedPoly    =   tempRed->getPoly();
1285                                        //Print("REDUCER: ");
1286                                        //pWrite(tempRedPoly);
1287                                        pIter(tempRedPoly);
1288                                        int lTempRedPoly    =   pLength(tempRedPoly);
1289                                        //Print("HEAD MONOMIAL KBUCKET: ");
1290                                        //pWrite(kBucketGetLm(bucket));
1291                                        kBucketExtractLm(bucket);
1292                                        kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1293                                        canonicalize++;
1294                                        //Print("REDUCTION\n");
1295                                        addToG  = 1;
1296                                        if(!(canonicalize % 50)) {
1297                                            kBucketCanonicalize(bucket);
1298                                        }
1299                                        //Print("HEAD MONOMIAL KBUCKET: ");
1300                                        //pWrite(kBucketGetLm(bucket));
1301                                        tempPoly    =   kBucketGetLm(bucket);
1302                                        //Print("TEMPPOLY:  ");
1303                                        //pWrite(tempPoly);
1304                                        if(NULL != tempPoly) {
1305                                            tempRed     =   gPrev->getFirst();
1306                                            continue;
1307                                        }
1308                                        else {
1309                                            break;
1310                                        }
1311                                    }
1312                                }   
1313                            }
1314                            else {
1315                              //Print("CRIT 1  ");
1316                                   
1317                                      if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) {
1318                                      //Print("NOT ALLOWED REDUCER, CRIT 1:\n");
1319                                      //pWrite(u);
1320                                      //pWrite(tempRed->getTerm());
1321                                      //pWrite(tempRed->getPoly());
1322                                      if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1323                                        //Print("REDUCER LABEL:  ");
1324                                        //pWrite(tempRed->getTerm());
1325addToG  = 0;
1326                                      }
1327                                    }
1328                            }
1329                        }
1330                        else {
1331                          //Print("CRIT 2  ");
1332                                    if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1333                                      //Print("NOT ALLOWED REDUCER, CRIT 2:\n");
1334                                      //pWrite(u);
1335                                      //pWrite(tempRed->getTerm());
1336                                      //pWrite(tempRed->getPoly());
1337                                      if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1338                                        //Print("REDUCER LABEL:  ");
1339                                        //pWrite(tempRed->getTerm());
1340addToG  = 0;
1341                                      }
1342                                    }
1343                        }
1344                    }
1345                    }
1346                    else { // u = 1 => reduce without checking criteria
1347                        poly tempRedPoly    =   tempRed->getPoly();
1348                        //Print("REDUCER: ");
1349                        //pWrite(tempRedPoly);
1350                        pIter(tempRedPoly);
1351                        int lTempRedPoly    =   pLength(tempRedPoly);
1352                        kBucketExtractLm(bucket);
1353                        kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1354                        canonicalize++;
1355                        //Print("Reduction\n");
1356                        if(!(canonicalize % 50)) {
1357                            kBucketCanonicalize(bucket);
1358                        }
1359                        tempPoly    =   kBucketGetLm(bucket);
1360                        //Print("TEMPPOLY:  ");
1361                        //pWrite(tempPoly);
1362                        if(NULL != tempPoly) {
1363                            tempRed     =   gPrev->getFirst();
1364                            continue;
1365                        }
1366                        else {
1367                            break;
1368                        }
1369                     
1370                    }
1371                }
1372                tempRed =   tempRed->getNext();
1373            }
1374            // reduction process with elements in LList* reducers
1375          if(NULL != tempPoly) {
1376            //Print("HERE\n");
1377            tempRed =   reducers->getFirst();
1378            while(NULL != tempRed) {
1379                //Print("TEMPREDPOLY:  ");
1380                //pWrite(tempRed->getPoly());
1381              //pWrite(tempPoly); 
1382              if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
1383                    //Print("A\n");
1384                    u   =   pDivideM(pHead(tempPoly),pHead(tempRed->getPoly()));
1385                    //Print("U:  ");
1386                    //pWrite(u);
1387                    if(tempRed->getIndex() != idx) {
1388                            // passing criterion1 ?
1389                            if(!criterion1(gPrev,u,tempRed,lTag)) {
1390                                    poly tempRedPoly    =   tempRed->getPoly();
1391                                    //Print("REDUCER: ");
1392                                    //pWrite(ppMult_qq(u,tempRedPoly));
1393                                    pIter(tempRedPoly);
1394                                    int lTempRedPoly    =   pLength(tempRedPoly);
1395                                    kBucketExtractLm(bucket);
1396                                    kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1397                                    canonicalize++;
1398                                    //Print("Reduction\n");
1399                                    if(!(canonicalize % 50)) {
1400                                        kBucketCanonicalize(bucket);
1401                                    }
1402                                    tempPoly    =   kBucketGetLm(bucket);
1403                                    //Print("TEMPPOLY:  ");
1404                                    //pWrite(tempPoly);
1405                                    if(NULL != tempPoly) {
1406                                        tempRed     =   gPrev->getFirst();
1407                                        continue;
1408                                    }
1409                                    else {
1410                                        break;
1411                                    }
1412                             }   
1413                   
1414                    }
1415                    else {
1416                        if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) {
1417                         //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n");
1418                                      //pWrite(u);
1419                                      //pWrite(tempRed->getTerm());
1420                                      //pWrite(pHead(tempRed->getPoly()));
1421                                      //addToG  = 0;
1422                        }
1423                        if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) {
1424                            // passing criterion2 ?
1425                            if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) {
1426                                // passing criterion1 ?
1427                                if(!criterion1(gPrev,u,tempRed,lTag)) {
1428                                    if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1429                                        if(NULL == redPoly) {
1430                                            bad->insert(tempRed->getLPolyOld());
1431                                            addToG  = 1;
1432                                            //poly tempRedPoly    =   tempRed->getPoly();
1433                                            //break;
1434                                        }
1435                                    }
1436                                    else {
1437                                        poly tempRedPoly    =   tempRed->getPoly();
1438                                        //Print("REDUCER: ");
1439                                        //pWrite(ppMult_qq(u,tempRedPoly));
1440                                        pIter(tempRedPoly);
1441                                        int lTempRedPoly    =   pLength(tempRedPoly);
1442                                        //Print("HEAD MONOMIAL KBUCKET: ");
1443                                        //pWrite(kBucketGetLm(bucket));
1444                                        kBucketExtractLm(bucket);
1445                                        kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
1446                                        canonicalize++;
1447                                        //Print("REDUCTION\n");
1448                                        addToG  = 1;
1449                                        if(!(canonicalize % 50)) {
1450                                            kBucketCanonicalize(bucket);
1451                                        }
1452                                        //Print("HEAD MONOMIAL KBUCKET: ");
1453                                        //pWrite(kBucketGetLm(bucket));
1454                                        tempPoly    =   kBucketGetLm(bucket);
1455                                        //Print("TEMPPOLY:  ");
1456                                        //pWrite(tempPoly);
1457                                        if(NULL != tempPoly) {
1458                                            tempRed     =   gPrev->getFirst();
1459                                            continue;
1460                                        }
1461                                        else {
1462                                            break;
1463                                        }
1464                                    }
1465                                }   
1466                            }
1467                            else {
1468                              //Print("CRIT 1  ");
1469                                   
1470                                      if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) {
1471                                      //Print("NOT ALLOWED REDUCER, CRIT 1:\n");
1472                                      //pWrite(u);
1473                                      //pWrite(tempRed->getTerm());
1474                                      //pWrite(tempRed->getPoly());
1475                                      if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1476                                        //Print("REDUCER LABEL:  ");
1477                                        //pWrite(tempRed->getTerm());
1478                                        addToG  = 0;
1479                                      }
1480                                    }
1481                            }
1482                        }
1483                        else {
1484                          //Print("CRIT 2  ");
1485                                    if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
1486                                      //Print("NOT ALLOWED REDUCER, CRIT 2:\n");
1487                                      //pWrite(u);
1488                                      //pWrite(tempRed->getTerm());
1489                                      //pWrite(tempRed->getPoly());
1490                                      if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) {
1491                                        //Print("REDUCER LABEL:  ");
1492                                        //pWrite(tempRed->getTerm());
1493addToG  = 0;
1494                                      }
1495                                    }
1496                        }
1497                    }
1498                   
1499                }
1500                tempRed =   tempRed->getNext();
1501            }
1502          }
1503            if(NULL != tempPoly) {
1504                if(NULL == redPoly) {
1505                    redPoly =   kBucketExtractLm(bucket);
1506                }
1507                else {
1508                    redPoly     =   p_Merge_q(redPoly,kBucketExtractLm(bucket),currRing);
1509                }
1510               // for top-reduction only
1511               redPoly  = p_Merge_q(redPoly,kBucketClear(bucket),currRing);
1512               break;
1513               // end for top-reduction only
1514               tempPoly    =   kBucketGetLm(bucket);
1515               
1516            }
1517        }
1518        if(NULL == redPoly) {
1519            reductionsToZero++;
1520            //pDelete(&redPoly);
1521        }
1522        else {
1523            Print("\nELEMENT ADDED TO GPREV: ");
1524            pNorm(redPoly);
1525              if(highestDegree < pDeg(redPoly)) { 
1526                  highestDegree   = pDeg(redPoly);
1527              }   
1528            pWrite(pHead(redPoly));
1529            //pWrite(l->getTerm());
1530            //Print("%d\n",canonicalize);
1531            l->setPoly(redPoly);
1532            // give "l" the label if it is "useful" (addToG = 0) or "useless"
1533            // (addToG = 1)
1534            l->setDel(!addToG);
1535            Print("redundant? %d\n\n",l->getDel());
1536            if(addToG == 0 && termination == 1) {
1537              reducers->insert(l->getLPolyOld());
1538            }
1539            else {
1540              gPrev->insert(l->getLPolyOld());
1541            }
1542            //Print("%d\n\n",termination);
1543            if(termination == 1) {
1544            if(addToG) {
1545              //Print("----------------HERE?-----------------\n");
1546              criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1547            }
1548            else {
1549              notInG++;
1550              //Print("\nNONONO");
1551              //pWrite(pHead(l->getPoly()));
1552              //pWrite(l->getTerm());
1553            }
1554            }
1555            // case in which all new elements are added to gPrev!
1556            // using boolean "addToG" to know if the element is "useful" (0) or
1557            // "useless" (1)
1558            else {
1559              if(!l->getDel()) {
1560                criticalPair(gPrev,critPairs,lTag,rTag,rules,rejectedGBList,plus);
1561              }
1562              else {
1563                criticalPair2(gPrev,critPairs,lTag,rTag,rules, rejectedGBList);
1564              }
1565            }
1566        }
1567   
1568    // if there are "bad" reducers than try to compute new S-polynomials and rules
1569   
1570    if(NULL != bad->getFirst()) {
1571        //Print("BAD STUFF LIST:\n");
1572        //bad->print();
1573        LNode* tempBad  =   bad->getFirst();
1574        //pWrite(l->getPoly());
1575        while(NULL != tempBad) {
1576            if(pDivisibleBy(tempBad->getPoly(),l->getPoly())) {
1577                //Print("BAD STUFF\n");
1578                //pWrite(l->getPoly());
1579                //pWrite(tempBad->getPoly());
1580                u   =   pDivide(pHead(l->getPoly()),pHead(tempBad->getPoly()));
1581                //Print("MULTIPLIER:  ");
1582                //pWrite(u);
1583                pSetCoeff(u,nOne);
1584                if(pLmCmp(ppMult_qq(u,tempBad->getTerm()),l->getTerm()) != 0) {
1585                    // passing criterion2 ?
1586                    if(!criterion2(gPrev->getFirst()->getIndex(), u,tempBad,rules,rTag)) {
1587                        // passing criterion1 ?
1588                        if(!criterion1(gPrev,u,tempBad,lTag)) {
1589                            //Print("HIERHIERHIERHIERHIERHIER\n");
1590                            rules->insert(tempBad->getIndex(),ppMult_qq(u,tempBad->getTerm()));
1591                            numberOfRules++;
1592                            //gPrev->print();
1593                            //pWrite(l->getPoly());
1594                            poly temp   =   ksOldSpolyRedNew(ppMult_qq(u,tempBad->getPoly()),l->getPoly());
1595                            //pWrite(l->getPoly());
1596                            //Print("%p\n",temp);
1597                            //gPrev->print();
1598                            if(NULL != temp) {
1599                                pNorm(temp);
1600                                LNode* tempBadNew   =   new LNode(ppMult_qq(u,tempBad->getTerm()),tempBad->getIndex(),temp,rules->getFirst()->getRuleOld());
1601                                //pWrite(temp);
1602                                //pWrite(tempBadNew->getPoly());
1603                                //pWrite(tempBadNew->getTerm());
1604                                //pWrite(pHead(tempBadNew->getPoly()));
1605                                //Print("%p\n",tempBadNew->getPoly());
1606                                //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
1607                                tempBadNew->setDel(1);
1608                           
1609                                sPolyList->insertByLabel(tempBadNew);
1610                                //Print("BAD SPOLYLIST: \n");
1611                                //sPolyList->print();
1612                            }
1613                        }
1614                    }
1615                }
1616            }
1617        //Print("HIER\n");
1618            tempBad =   tempBad->getNext();
1619            //Print("%p\n",tempBad);
1620        }
1621       // Print("-------------------BAD STUFF LIST-----------------------------\n");
1622    }
1623        //Print("HIER AUCH\n");
1624        //Print("SPOLYLIST IN BAD: \n");
1625        //sPolyList->print();
1626    //Print("END FIND REDUCERS\n");
1627}
1628
1629/*
1630=======================================================================================
1631merging 2 polynomials p & q without requiring that all monomials of p & q are different
1632if there are equal monomials in p & q only one of these monomials (always that of p!)
1633is taken into account
1634=======================================================================================
1635
1636poly p_MergeEq_q(poly p, poly q, const ring r) {
1637  assume(p != NULL && q != NULL);
1638  p_Test(p, r);
1639  p_Test(q, r);
1640#if PDEBUG > 0
1641  int l = pLength(p) + pLength(q);
1642#endif
1643
1644  spolyrec rp;
1645  poly a = &rp;
1646  DECLARE_LENGTH(const unsigned long length = r->CmpL_Size);
1647  DECLARE_ORDSGN(const long* ordsgn = r->ordsgn);
1648
1649  Top:     // compare p and q w.r.t. monomial ordering
1650  p_MemCmp(p->exp, q->exp, length, ordsgn, goto Equal, goto Greater , goto Smaller);
1651
1652  Equal:
1653  a =   pNext(a)    =   p;
1654  pIter(p);
1655  pIter(q);
1656  if(NULL == p) {
1657      if(NULL == q) {
1658          goto Finish;
1659      }
1660      else {
1661          pNext(a)  =   q;
1662          goto Finish;
1663      }
1664  }
1665  goto Top;
1666
1667  Greater:
1668  a = pNext(a) = p;
1669  pIter(p);
1670  if (p==NULL) { pNext(a) = q; goto Finish;}
1671  goto Top;
1672
1673  Smaller:
1674  a = pNext(a) = q;
1675  pIter(q);
1676  if (q==NULL) { pNext(a) = p; goto Finish;}
1677  goto Top;
1678
1679  Finish:
1680
1681  p_Test(pNext(&rp), r);
1682#if PDEBUG > 0
1683  pAssume1(l - pLength(pNext(&rp)) == 0);
1684#endif
1685  return pNext(&rp);
1686}
1687*/
1688
1689/*
1690=====================================================================================
1691top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
1692the same index whereas the labels are taken into account
1693=====================================================================================
1694*/
1695void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs,  RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, PList* rejectedGBList, int plus) {
1696    //Print("##########################################In topREDUCTION!########################################\n");
1697    // try l as long as there are reductors found by findReductor()
1698    LNode* gPrevRedCheck    =   lTag->getFirstCurrentIdx();
1699    LNode* tempRed;
1700    poly pOne               =   pOne();
1701    do {
1702        //int timer5  =   initTimer();
1703        //startTimer();
1704        //Print("TOP REDUCTION:  ");
1705        //pWrite(l->getPoly());
1706        tempRed  =   findReductor(l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag);
1707        //timer5  =   getTimer();
1708        //reductionTime   =   reductionTime   +   timer5;
1709        // if a reductor for l is found and saved in tempRed
1710        if(NULL != tempRed) {
1711            // if label of reductor is greater than the label of l we have to built a new element
1712            // and add it to sPolyList
1713           
1714            if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
1715                // needed sinc pSub destroys the arguments!
1716                //poly temp_poly_l    =   pInit();
1717                //temp_poly_l         =   pCopy(l->getPoly());
1718                //Print("VORHER: ");
1719                //pWrite(tempRed->getPoly());
1720                //poly temp           =   pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1721                poly temp   =   ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1722                rules->insert(tempRed->getIndex(),tempRed->getTerm());
1723                //Print("NACHHER: ");
1724                //pWrite(tempRed->getPoly());
1725                //Print("TEMP: ");
1726                //pWrite(temp);
1727                if(NULL != temp) {
1728                    pNorm(temp);
1729                    //tempRed->setPoly(temp);
1730                    //tempRed->setDel(1);
1731                    //rules->insert(tempRed->getIndex(),tempRed->getTerm());
1732                    LNode* tempRedNew   =   new LNode(tempRed->getTerm(),tempRed->getIndex(),temp,rules->getFirst()->getRuleOld());
1733                    //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
1734                    tempRedNew->setDel(1);
1735                    sPolyList->insertByLabel(tempRedNew);
1736                }
1737                else {
1738                    pDelete(&temp);
1739                    reductionsToZero++;
1740                    //delete tempRed;
1741                }
1742            }
1743           
1744            // label of reductor is smaller than the label of l, subtract reductor from l and delete the
1745            // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
1746            // after subtraction
1747            else {
1748               
1749                //poly temp_poly_l    =   pInit();
1750                //temp_poly_l         =   pCopy(l->getPoly());
1751                //poly temp   =   pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1752                //Print("REDUCER: ");
1753                //pWrite(tempRed->getPoly());
1754                //pWrite(tempRed->getTerm());
1755                poly temp   =   ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1756                //Print("REDUCED ELEMENT:  ");
1757                if(NULL != temp) {
1758                    pNorm(temp);
1759                    //pWrite(temp);
1760                    poly tempNF =   kNF(gbPrev,currQuotient,temp); 
1761                    pNorm(tempNF);
1762                    if(NULL == tempNF) {
1763                        reductionsToZero++;
1764                        pDelete(&tempNF);
1765                        l->setPoly(NULL);
1766                        break;
1767                    }
1768                    l->setPoly(tempNF);
1769                   
1770                    gPrevRedCheck   =   lTag->getFirstCurrentIdx();
1771                }
1772                else {
1773                    reductionsToZero++;
1774                    pDelete(&temp);
1775                    l->setPoly(NULL);
1776                    break;
1777                }
1778            }   
1779        }
1780        else {
1781            if(NULL != l->getPoly()) {
1782                pNorm(l->getPoly());
1783                //Print("ELEMENT ADDED TO GPREV: ");
1784                //pWrite(l->getPoly());
1785                gPrev->insert(l->getLPolyOld());
1786                //Print("TEMP RED == 0  ");
1787                //pWrite(l->getPoly());
1788                //pWrite(l->getTerm());
1789                //rules->print();
1790                criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1791                //Print("LIST OF CRITICAL PAIRS:    \n");
1792                //critPairs->print();
1793            }
1794            break;
1795        }
1796    } while(1);
1797}
1798
1799
1800/*
1801=====================================================================
1802subalgorithm to find a possible reductor for the labeled polynomial l
1803=====================================================================
1804*/
1805LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag, PList* rejectedGBList) {
1806    // allociation of memory for the possible reductor
1807    //Print("LPOLY:  ");
1808    //pWrite(l->getPoly());
1809    poly u      =   pOne();
1810    poly red;
1811    number nOne =   nInit(1);
1812    LNode* temp;
1813    // head term of actual element such that we do not have to call pHead at each new reductor test
1814    poly t      =   pHead(l->getPoly());
1815    // if l was already checked use the information in gPrevRedCheck such
1816    // that we can start searching for new reducers from this point and
1817    // not from the first element of gPrev with the current index
1818    temp    =   gPrevRedCheck;
1819    // search for reductors until we are at the end of gPrev resp. at the
1820    // end of the elements of the current index
1821    while(NULL != temp && temp->getIndex() == l->getIndex()) {
1822        // does the head of the element of gPrev divides the head of
1823        // the to be reduced element?
1824        if(pLmDivisibleByNoComp(pHead(temp->getPoly()),t)) {
1825            // get all the information needed for the following tests
1826            // of the criteria
1827            u   =   pDivide(t,pHead(temp->getPoly()));
1828            pSetCoeff(u,nOne);
1829            red =   ppMult_qq(u,temp->getPoly());
1830            pNorm(red);
1831            // check if both have the same label
1832            if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) != 0) {
1833                // passing criterion2 ?
1834                if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) {
1835                    // passing criterion1 ?
1836                    if(!criterion1(gPrev,u,temp,lTag)) {
1837                            gPrevRedCheck   =   temp->getNext();
1838                            LNode* redNode  =   new LNode(ppMult_qq(u,temp->getTerm()),temp->getIndex(),red,NULL,NULL);
1839                            return redNode;
1840                    }
1841                }
1842            }
1843            if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) == 1) {
1844                // passing criterion2 ?
1845                if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) {
1846                    // passing criterion1 ?
1847                    if(!criterion1(gPrev,u,temp,lTag)) {
1848                        poly tempSpoly  =   ksOldSpolyRedNew(red,l->getPoly());
1849                        rules->insert(temp->getIndex(),ppMult_qq(u,temp->getTerm()));
1850                        gPrevRedCheck   =   temp->getNext();
1851                        if(NULL != tempSpoly) {
1852                            pNorm(tempSpoly);
1853                            sPolyList->insertByLabel(ppMult_qq(u,temp->getTerm()),temp->getIndex(),tempSpoly,rules->getFirst()->getRuleOld());
1854                    //Print("NEW ONE: ");
1855                    //pWrite(tempSpoly);
1856                    //Print("HIER\n");
1857                            //sPolyList->print();
1858                            //sleep(5);
1859                        }
1860                    }
1861                }
1862            }
1863        }
1864        //Print("AUCH HIER\n");
1865        temp = temp->getNext();
1866    }
1867   
1868//    delete temp;
1869 return NULL;
1870}
1871
1872
1873
1874/*
1875==========================================================================
1876MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
1877OPTIONS: INTEGER "opt" is to be set "0" for F5, "1" for F5R, "2" for F5C
1878==========================================================================
1879*/
1880ideal F5main(ideal id, ring r, int opt, int plus, int termination) {
1881  switch(opt) { 
1882    case 0:
1883      Print("\nComputations are done by the standard F5 Algorithm");
1884      break;
1885    case 1:
1886      Print("\nComputations are done by the variant F5R of the F5 Algorithm");
1887      break;
1888    case 2:
1889      Print("\nComputations are done by the variant F5C of the F5 Algorithm");
1890      break;
1891    default:
1892      WerrorS("\nThe option can only be set to \"0\", \"1\" or \"2\":\n\"0\": standard F5 Algorithm\n\"1\": variant F5R\n\"2\": variant F5C\nComputations are aborted!\n");
1893      return id;
1894  }
1895 
1896    int timer   =   initTimer();
1897    startTimer();
1898    int i,j,k,l;
1899    int gbLength;
1900    // 1 polynomial for defining initial labels & further tests
1901    poly ONE = pOne();
1902    poly pOne   =   pOne();
1903    number nOne =   nInit(1);
1904    // tag the first element of index i-1 for criterion 1
1905    //Print("LTAG BEGINNING: %p\n",lTag);
1906   
1907    // DEBUGGING STUFF START
1908    //Print("NUMBER: %d\n",r->N);
1909    /*
1910    int* ev = new int[r->N +1];
1911    for(i=0;i<IDELEMS(id);i++) {
1912        pGetExpV(id->m[i],ev);
1913        //ev2  =   pGetExp(id->m[i],1);
1914        pWrite(id->m[i]);
1915        Print("EXP1: %d\n",ev[1]);
1916        Print("EXP2: %d\n",ev[2]);
1917        Print("EXP3: %d\n\n",ev[3]);
1918        Print("SUM: %ld\n\n\n",sumVector(ev,r->N));
1919    }
1920    delete ev;
1921    */
1922    /*DEBUGGING STUFF END */
1923   
1924    // first element in rTag is first element of rules which is NULL RNode,
1925    // this must be done due to possible later improvements
1926    RList* rules    =   new RList();
1927    //Print("RULES FIRST: %p\n",rules->getFirst());
1928    //Print("RULES FIRST DATA: %p\n",rules->getFirst()->getRule());
1929    //RTagList* rTag  =   new RTagList(rules->getFirst());
1930    RTagList* rTag  =   NULL;
1931    i = 1;
1932    /*for(j=0; j<IDELEMS(id); j++) {
1933        if(NULL != id->m[j]) {
1934            if(pComparePolys(id->m[j],ONE)) {
1935                Print("One Polynomial in Input => Computations stopped\n");
1936                ideal idNew = idInit(1,1);
1937                idNew->m[0] = ONE;
1938                return(idNew);
1939            }   
1940        }
1941    }*/ 
1942    ideal idNew     =   kInterRed(id); 
1943    id              =   idNew;
1944    //qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
1945    //idShow(id);
1946    LList* gPrev    =   new LList(ONE, i, id->m[0]);
1947    LList* reducers =   new LList();
1948    //idShow(id);
1949    //Print("%p\n",id->m[0]);
1950    //pWrite(id->m[0]);
1951    //Print("%p\n",gPrev->getFirst()->getPoly());
1952    //pWrite(gPrev->getFirst()->getPoly());
1953
1954    LTagList* lTag  =   new LTagList(gPrev->getFirst());
1955    //lTag->insert(gPrev->getFirst());
1956    lTag->setFirstCurrentIdx(gPrev->getFirst());
1957    // computing the groebner basis of the elements of index < actual index
1958    gbLength    =   gPrev->getLength();
1959    //Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
1960    ideal gbPrev    =   idInit(gbLength,1);
1961    // initializing the groebner basis of elements of index < actual index
1962    gbPrev->m[0]    =   gPrev->getFirst()->getPoly();
1963    //idShow(gbPrev);
1964    //idShow(currQuotient);
1965    for(i=2; i<=IDELEMS(id); i++) {
1966        LNode* gPrevTag =   gPrev->getLast();
1967        //Print("Last POlynomial in GPREV: ");
1968        //Print("%p\n",gPrevTag);   
1969        //pWrite(gPrevTag->getPoly());
1970        Print("Iteration: %d\n\n",i);
1971        gPrev   =   F5inc(i, id->m[i-1], gPrev, reducers, gbPrev, ONE, lTag, rules, rTag, plus, termination);
1972        //Print("%d\n",gPrev->count(gPrevTag->getNext()));
1973        //Print("%d\n",gPrev->getLength());
1974        //Print("____________________________________ITERATION STEP DONE________________________________________\n");
1975       
1976        // DEBUGGING STUFF
1977        LNode* temp    =   gPrev->getFirst();
1978   
1979
1980        /////////////////////////////////////////////////////////////////////////////////
1981        //                                                                             //
1982        // one needs to choose one of the following 3 implementations of the algorithm //
1983        // F5,F5R or F5C                                                               //
1984        //                                                                             //
1985        /////////////////////////////////////////////////////////////////////////////////                                                                           
1986       
1987       
1988        //   
1989        // standard "F5"
1990        //
1991        if(0 == opt) { 
1992          if(gPrev->getLength() > gbLength) {
1993            if(i < IDELEMS(id)) {
1994                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
1995                LNode*  temp =   gPrevTag;
1996                int counter =   0;
1997                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
1998                    temp        =   temp->getNext();
1999                    if(0 == temp->getDel()) {
2000                        counter++;
2001                        gbAdd->m[j] =   temp->getPoly();
2002                    }
2003                }
2004                    gbPrev          =   idAdd(gbPrev,gbAdd);
2005            }
2006            else {
2007                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
2008                LNode*  temp =   gPrevTag;
2009                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2010                    temp        =   temp->getNext();
2011                    gbAdd->m[j] =   temp->getPoly();
2012                }
2013                gbPrev          =   idAdd(gbPrev,gbAdd);
2014            }
2015            //if(i == IDELEMS(id)) {
2016            //    ideal tempId        =   kInterRed(gbPrev);
2017            //    gbPrev              =   tempId;
2018            //}
2019        }
2020        gbLength    =   gPrev->getLength();
2021        }
2022       
2023
2024        //
2025        //  "F5R"
2026        //
2027        if(1 == opt) {
2028        if(gPrev->getLength() > gbLength) {
2029            if(i < IDELEMS(id)) {
2030                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
2031                LNode*  temp =   gPrevTag;
2032                int counter =   0;
2033                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2034                    temp        =   temp->getNext();
2035                    if(0 == temp->getDel()) {
2036                        counter++;
2037                        gbAdd->m[j] =   temp->getPoly();
2038                    }
2039                }
2040                    gbPrev          =   idAdd(gbPrev,gbAdd);
2041            }
2042            else {
2043                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
2044                LNode*  temp =   gPrevTag;
2045                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2046                    temp        =   temp->getNext();
2047                    gbAdd->m[j] =   temp->getPoly();
2048                }
2049                gbPrev          =   idAdd(gbPrev,gbAdd);
2050            }
2051            // interreduction stuff
2052            // comment this out if you want F5 instead of F5R
2053            if(i<IDELEMS(id)) {
2054                ideal tempId    =   kInterRed(gbPrev);
2055                gbPrev          =   tempId;
2056            }
2057        }
2058        gbLength    =   gPrev->getLength();
2059        }
2060       
2061
2062        //
2063        // "F5C"
2064        //
2065        if(2 == opt) { 
2066        if(gPrev->getLength() > gbLength) {
2067            if(i < IDELEMS(id)) {
2068                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
2069                LNode*  temp =   gPrevTag;
2070                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2071                    temp        =   temp->getNext();
2072                        gbAdd->m[j] =   temp->getPoly();
2073                }
2074                    gbPrev          =   idAdd(gbPrev,gbAdd);
2075            }
2076            else {
2077                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
2078                LNode*  temp =   gPrevTag;
2079                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
2080                    temp        =   temp->getNext();
2081                    gbAdd->m[j] =   temp->getPoly();
2082                }
2083                gbPrev          =   idAdd(gbPrev,gbAdd);
2084            }
2085            if(i<IDELEMS(id)) {
2086                ideal tempId    =   kInterRed(gbPrev);
2087                gbPrev          =   tempId;
2088                delete gPrev;
2089                delete rules;
2090                gPrev    =   new LList(pOne,1,gbPrev->m[0]);
2091                gPrev->insert(pOne,1,gbPrev->m[1]);
2092                rules    =   new RList();
2093                //rTag     =   new RTagList(rules->getFirst());
2094                for(k=2; k<IDELEMS(gbPrev); k++) {
2095                    gPrev->insert(pOne,k+1,gbPrev->m[k]);
2096                    /*
2097                    for(l=0; l<k; l++) {
2098                    }
2099                    rTag->insert(rules->getFirst());
2100                    */
2101                }
2102            }
2103            gbLength    =   gPrev->getLength(); 
2104        } 
2105        }
2106
2107
2108    }
2109    timer   =   getTimer();
2110    //Print("\n\nADDING TIME IN REDUCTION: %d\n\n",reductionTime);
2111    Print("\n\nNumber of zero-reductions:           %d\n",reductionsToZero);
2112    Print("Number of rules:                     %d\n",numberOfRules); 
2113    Print("Number of rejected F5-critical pairs:%d\n",numberRejectedF5CriticalPairs); 
2114    Print("Number of reductions:                %d\n",numberOfReductions); 
2115    Print("Elements not added to G:             %d\n",notInG); 
2116    Print("Highest Degree during computations:  %d\n",highestDegree);
2117    Print("Degree d_0 in F5+:                   %d\n",highestDegreeGBCriticalPair);
2118    Print("Time for computations:               %d/1000 seconds\n",timer);
2119    Print("Number of elements in gb:            %d\n",IDELEMS(gbPrev));
2120    //LNode* temp    =   gPrev->getFirst();
2121    //while(NULL != temp) {
2122    //    pWrite(temp->getPoly());
2123    //    temp    =   temp->getNext();
2124    // }
2125    //gPrev->print();
2126    //delete lTag;
2127    delete rTag;
2128    delete gPrev;
2129    notInG                        =   0;
2130    numberOfRules                 =   0;
2131    reductionsToZero              =   0;
2132    highestDegree                 =   0;
2133    highestDegreeGBCriticalPair   =   0;
2134    reductionTime                 =   0; 
2135    spolsTime                     =   0;
2136    numberUselessPairs            =   0;
2137    numberUsefulPairs             =   0;
2138    numberRejectedF5CriticalPairs =   0;
2139    numberOfReductions            =   0;
2140    numberOfSpolys                =   0;
2141    return(gbPrev);
2142
2143
2144}
2145
2146#endif
Note: See TracBrowser for help on using the repository browser.