source: git/kernel/f5gb.cc @ d11734

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