source: git/kernel/f5gb.cc @ eedd22

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