source: git/kernel/GBEngine/f5gb.cc @ f9b0bd

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