source: git/kernel/f5gb.cc @ d4cec61

spielwiese
Last change on this file since d4cec61 was d4cec61, checked in by Christian Eder, 14 years ago
implemented test for termination ideas git-svn-id: file:///usr/local/Singular/svn/trunk@12088 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 62.6 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/*
5* ABSTRACT: f5gb interface
6*/
7
8#include "mod2.h"
9#ifdef HAVE_F5
10#include <unistd.h>
11#include "structs.h"
12#include "kutil.h"
13#include "omalloc.h"
14#include "polys.h"
15#include "p_polys.h"
16#include "p_Procs.h"
17#include "ideals.h"
18#include "febase.h"
19#include "kstd1.h"
20#include "khstd.h"
21#include "kbuckets.h"
22#include "weight.h"
23#include "intvec.h"
24#include "pInline1.h"
25#include "f5gb.h"
26#include "f5data.h"
27#include "f5lists.h"
28#include "timer.h"
29int notInG              =   0;
30int numberOfRules       =   0;
31int reductionsToZero    =   0;
32int reductionTime       =   0;
33int spolsTime           =   0;
34int highestDegree       =   0;
35int degreeBound         =   0;
36/*
37====================================================================
38sorting ideals by decreasing total degree "left" and "right" are the
39pointer of the first and last polynomial in the considered ideal
40====================================================================
41*/
42void qsortDegree(poly* left, poly* right) {
43    poly* ptr1 = left;
44    poly* ptr2 = right;
45    poly p1,p2;
46    p2 = *(left + (right - left >> 1));
47    do {
48            while(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)) {
49                    ptr1++;
50            } 
51            while(pTotaldegree(*ptr2, currRing) > pTotaldegree(p2,currRing)) {
52                    ptr2--;
53            }
54            if(ptr1 > ptr2) {
55                    break;
56            }
57            p1    = *ptr1;
58            *ptr1 = *ptr2;
59            *ptr2 = p1;
60    } while(++ptr1 <= --ptr2);
61
62    if(left < ptr2) {
63            qsortDegree(left,ptr2);
64    }
65    if(ptr1 < right) {
66            qsortDegree(ptr1,right);
67    }
68}
69
70/*!
71 * ======================================================================
72 * builds the sum of the entries of the exponent vectors, i.e. the degree
73 * of the corresponding monomial
74 * ======================================================================
75*/
76long sumVector(int* v, int k) {
77    int i;
78    long sum =  0;
79    for(i=1; i<=k; i++) {
80        Print("%d\n",v[i]);
81        Print("%ld\n",sum);
82        sum =   sum + v[i];
83    }
84    return sum;
85}
86
87/*!
88==========================================================================
89compares monomials, i.e. divisibility tests for criterion 1 and criterion 2
90==========================================================================
91*/
92bool compareMonomials(int* m1, int** m2, int numberOfRules, int k) {
93    int i,j;
94    long sumM1  =   sumVector(m1,k);
95    //int k   =   sizeof(m1) / sizeof(int);
96    for(i=0; i<numberOfRules; i++) {
97        if(sumVector(m2[i],k) <= sumM1) {
98            for(j=1; j<=k; j++) {
99                if(m1[j]>m2[i][j]) {
100                    return true;
101                }
102            }   
103        }
104    }
105    return false;
106}
107
108/*
109==================================================
110computes incrementally gbs of subsets of the input
111gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
112==================================================
113*/
114LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag, int termination) {
115    //Print("in f5inc\n");           
116    //pWrite(rules->getFirst()->getRuleTerm());
117    int j;
118    //Print("%p\n",gPrev->getFirst());
119    //pWrite(gPrev->getFirst()->getPoly());
120    poly tempNF =   kNF(gbPrev,currQuotient,f_i);
121    f_i         =   tempNF;
122    //gPrev->insert(ONE,i,f_i);
123    gPrev->insert(ONE,gPrev->getLength()+1,f_i);
124    // tag the first element in gPrev of the current index for findReductor()
125    lTag->setFirstCurrentIdx(gPrev->getLast());
126    //Print("1st gPrev: ");
127    //pWrite(gPrev->getFirst()->getPoly());
128    //Print("2nd gPrev: ");
129    //pWrite(gPrev->getFirst()->getNext()->getPoly());
130    //pWrite(gPrev->getFirst()->getNext()->getPoly());   
131    CListOld* critPairs        =   new CListOld();
132    CNode* critPairsMinDeg  =   new CNode();   
133    // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
134    // in the list critPairs
135    criticalPair(gPrev, critPairs, lTag, rTag, rules);
136    static LList* sPolyList        =   new LList();
137    //sPolyList->print();
138    // labeled polynomials which have passed reduction() and have to be added to list gPrev
139    static LList* completed        =   new LList();
140    // the reduced labeled polynomials which are returned from subalgorithm reduction()
141    static LList* reducedLPolys     =   new LList();
142    // while there are critical pairs to be further checked and deleted/computed
143    while(NULL != critPairs->getFirst()) { 
144        // critPairs->getMinDeg() deletes the first elements of minimal degree from
145        // critPairs, thus the while loop is not infinite.
146        critPairsMinDeg =   critPairs->getMinDeg();
147        // adds all to be reduced S-polynomials in the list sPolyList and adds
148        // the corresponding rules to the list rules
149        // NOTE: inside there is a second check of criterion 2 if new rules are
150        // added
151        //int timer4  =   initTimer();
152        //startTimer();
153        //critPairs->print();
154        computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
155        //timer4  =   getTimer();
156        //Print("SPOLS TIMER: %d\n",timer4);
157        //spolsTime  =   spolsTime  +   timer4;
158        // DEBUG STUFF FOR SPOLYLIST
159        LNode* temp     =   sPolyList->getFirst();
160        //while(NULL != temp && NULL != temp->getLPoly()) {
161            //Print("Spolylist element: ");
162            //pWrite(temp->getPoly());
163            //temp    =   temp->getNext();
164        //}
165        // reduction process of new S-polynomials and also adds new critical pairs to critPairs
166        //int timer3  =   initTimer();
167        //startTimer();
168        //sPolyList->print();
169        //reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
170        newReduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev, termination);
171        //timer3      =  getTimer();
172        //reductionTime = reductionTime + timer3;
173        //Print("REDUCTION TIMER: %d\n",timer3);
174        // DEBUG STUFF FOR GPREV
175        //temp    =   gPrev->getFirst();
176        //int number  =   1;
177        //Print("\n\n");
178        //while(NULL != temp) {
179        //    Print("%d.  ",number);
180        //    pWrite(temp->getPoly());
181        //    temp    =   temp->getNext();
182        //    number++;
183        //    Print("\n");
184        //}
185        //sleep(5);
186   
187    }
188    //Print("REDUCTION DONE\n");
189    //Print("%p\n",rules->getFirst());
190    //Print("%p\n",rTag->getFirst());
191    //if(rules->getFirst() != rTag->getFirst()) {
192        //Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n");
193        //rTag->insert(rules->getFirst());
194    //}
195    //else {
196        //Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
197    //}
198    lTag->insert(lTag->getFirstCurrentIdx());
199    //Print("INDEX: %d\n",tempTag->getIndex());
200    //pWrite(tempTag->getPoly());
201    //Print("COMPLETED FIRST IN F5INC: \n");
202    //Print("1st gPrev: ");
203    //pWrite(gPrev->getFirst()->getPoly());
204    //Print("2nd gPrev: ");
205    //pWrite(gPrev->getFirst()->getNext()->getPoly());
206    //Print("3rd gPrev: ");
207    //pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly());
208    //delete sPolyList;
209    //critPairs->print();
210    delete critPairs;
211    //Print("IN F5INC\n");
212    /*
213    Print("\n\n\nRULES: \n");
214        RNode* tempR    =   rules->getFirst();
215        Print("%p\n",tempR);
216        int t   = 1;
217        while(NULL != tempR) {
218            Print("ADDRESS OF %d RNODE: %p\n",t,tempR);
219            Print("ADDRESS OF RULE: %p\n",tempR->getRule());
220            pWrite(tempR->getRuleTerm());
221            Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
222            Print("%d\n\n",tempR->getRuleIndex());
223            tempR   =   tempR->getNext();
224            t++;
225        }
226    */
227    //gPrev->print();
228    //Print("COMPLETE REDUCTION TIME UNTIL NOW: %d\n",reductionTime);
229    //Print("COMPLETE SPOLS TIME UNTIL NOW:     %d\n",spolsTime);
230    degreeBound = 0;
231    return gPrev;
232}
233
234
235
236/*
237================================================================
238computes a list of critical pairs for the next reduction process
239first element in gPrev is always the newest element which must
240build critical pairs with all other elements in gPrev
241================================================================
242*/
243inline void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
244    //Print("IN CRITPAIRS\n");
245    // initialization for usage in pLcm()
246    number nOne         =   nInit(1);
247    LNode* newElement   =   gPrev->getLast();
248    LNode* temp         =   gPrev->getFirst();
249    poly u1             =   pOne();
250    poly u2             =   pOne();
251    poly lcm            =   pOne();
252    poly t              =   pHead(newElement->getPoly());
253    Rule* testedRule    =   NULL;
254    if(NULL != rules->getFirst()) {
255        testedRule  =   rules->getFirst()->getRule();
256    }
257    // computation of critical pairs
258    while( gPrev->getLast() != temp) {
259        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
260        pSetCoeff(lcm,nOne);
261        // computing factors u2 for new labels
262        u1 = pDivide(lcm,t);
263        if(NULL == u1) {
264            break;
265        }
266        pSetCoeff(u1,nOne);
267        u2 = pDivide(lcm,pHead(temp->getPoly()));
268        pSetCoeff(u2,nOne);
269        // testing both new labels by the F5 Criterion
270        if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
271           && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag) 
272           && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
273            // if they pass the test, add them to CListOld critPairs, having the LPoly with greater
274            // label as first element in the CPairOld
275            if(newElement->getIndex() == temp->getIndex() && 
276            -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
277                CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, 
278                                temp->getLPoly(), u1, newElement->getLPoly(), testedRule);                   
279                critPairs->insert(cp);
280            }
281            else {
282                CPairOld* cp   =   new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, 
283                                newElement->getLPoly(), u2, temp->getLPoly(), testedRule);                   
284                critPairs->insert(cp);
285            }
286        }
287        else {
288        }
289        temp    =   temp->getNext();
290    }
291}
292
293
294
295
296
297
298
299/*
300========================================
301Criterion 1, i.e. Faugere's F5 Criterion
302========================================
303*/
304inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) {
305    // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
306        int idx =   l->getIndex();
307    int i;
308    if(idx == 1) {
309        //Print("HIER\n");
310        return false;
311    }
312    else {
313        LNode* testNode =   gPrev->getFirst();
314        // save the monom t1*label_term(l) as it is tested various times in the following
315        poly u1 = ppMult_qq(t,l->getTerm());
316        //Print("------------------------------IN CRITERION 1-----------------------------------------\n");
317        //Print("TESTED ELEMENT: ");
318        //pWrite(l->getPoly());
319        //pWrite(l->getTerm());
320        //pWrite(ppMult_qq(t,l->getTerm()));
321        //Print("%d\n\n",l->getIndex());
322        while(testNode->getIndex() < idx) { // && NULL != testNode->getLPoly()) {
323            //pWrite(testNode->getPoly());
324            //Print("%d\n",testNode->getIndex());
325            if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
326                //Print("Criterion 1 NOT passed!\n");
327                if(idx != gPrev->getLast()->getIndex()) {
328                    //Print("DOCH!\n");
329                }
330                return true;
331            }
332            //pWrite(testNode->getNext()->getPoly());
333            testNode    =   testNode->getNext();
334        }
335        /*
336        ideal testId    =   idInit(idx-1,1);
337        for(i=0;i<idx-1;i++) {
338            testId->m[i]  =   pHead(testNode->getPoly());
339            testNode        =   testNode->getNext();
340        }
341        poly temp   =   kNF(testId,currQuotient,u1);
342        //pWrite(temp);
343        for(i=0;i<IDELEMS(testId);i++) {
344            testId->m[i]    =   NULL;
345        }
346        idDelete(&testId);
347        if(NULL == temp) {
348            //if(l->getIndex() != gPrev->getFirst()->getIndex()) {
349            //    Print("----------------------------Criterion1 not passed----------------------------------\n");
350            //}
351            return true;
352        }
353        */
354        return false;
355    }
356}
357
358
359
360/*
361=====================================
362Criterion 2, i.e. Rewritten Criterion
363=====================================
364*/
365inline bool criterion2(int idx, poly t, LNode* l, RList* rules, RTagList* rTag) {
366    //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n");
367    /* 
368    Print("RULES: \n");
369        RNode* tempR    =   rules->getFirst();
370        Print("%p\n",tempR);
371        int i   = 1;
372        while(NULL != tempR) {
373            Print("ADDRESS OF %d RNODE: %p\n",i,tempR);
374            Print("ADDRESS OF RULE: %p\n",tempR->getRule());
375            pWrite(tempR->getRuleTerm());
376            Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
377            Print("%d\n\n",tempR->getRuleIndex());
378            tempR   =   tempR->getNext();
379            i++;
380        }
381        //Print("TESTED ELEMENT: ");
382        //pWrite(l->getPoly());
383        //pWrite(l->getTerm());
384        //pWrite(ppMult_qq(t,l->getTerm()));
385        //Print("%d\n\n",l->getIndex());
386      */
387// start at the previously added element to gPrev, as all other elements will have the same index for sure
388    if(idx > l->getIndex()) {
389        return false;
390    }
391   
392    RNode* testNode; // =   new RNode();
393    testNode    =   rules->getFirst();
394    /*
395     if(NULL == rTag->getFirst()) {
396        if(NULL != rules->getFirst()) {
397            testNode    =   rules->getFirst();
398        }
399        else {
400            return false;
401        }
402    }
403   
404     else {
405
406        if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
407            testNode    =   rules->getFirst();
408        }
409        else {
410       //Print("HIER\n");
411            //Print("DEBUG\n");
412        //Print("L INDEX: %d\n",l->getIndex());
413            *-------------------------------------
414             * TODO: WHEN INTERREDUCING THE GB THE
415             *       INDEX OF THE PREVIOUS ELEMENTS
416             *       GETS HIGHER!
417             *-----------------------------------*
418            //testNode    =   rules->getFirst();
419            testNode    =   rTag->get(l->getIndex());
420            if(NULL == testNode) {
421                testNode    =   rules->getFirst();
422            }
423            //Print("TESTNODE ADDRESS: %p\n",testNode);
424        }
425    }
426    */
427    //testNode    =   rules->getFirst();
428        // save the monom t1*label_term(l) as it is tested various times in the following
429    poly u1 = ppMult_qq(t,l->getTerm());
430    // first element added to rTag was NULL, check for this
431    //Print("%p\n",testNode->getRule());
432    // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
433    //Print("TESTNODE: %p\n",testNode);
434    //pWrite(testNode->getRuleTerm());
435    if(NULL != testNode ) {   
436        //pWrite(testNode->getRuleTerm());
437    }
438    if(NULL != testNode) {
439        if(testNode->getRule() == l->getRule()) {
440            //Print("%p\n%p\n",testNode->getRule(),l->getRule());
441            //Print("EQUAL\n");
442        }
443        else {
444            //Print("NOT EQUAL\n");
445        }
446    }
447    while(NULL != testNode && testNode->getRule() != l->getRule() 
448          && l->getIndex() == testNode->getRuleIndex()) {
449        //Print("%p\n",testNode);
450        //pWrite(testNode->getRuleTerm());
451        //pWrite(t);
452        //pWrite(l->getTerm());
453        //pWrite(u1);
454        //Print("%d\n",testNode->getRuleIndex());
455        if(pLmDivisibleByNoComp(testNode->getRuleTerm(),u1)) {
456            //Print("-----------------Criterion 2 NOT passed!-----------------------------------\n");
457            //Print("INDEX: %d\n",l->getIndex());
458            pDelete(&u1);
459    //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
460            return true;
461        }
462                testNode    =   testNode->getNext();
463    }
464    //delete testNode;
465    pDelete(&u1);
466    //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
467    return false;
468}
469
470
471
472/*
473=================================================================================================================
474Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter
475=================================================================================================================
476*/
477inline bool criterion2(poly t, LPoly* l, RList* rules, Rule* testedRule) {
478    //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n");
479    //Print("LAST RULE TESTED: %p",testedRule);
480    /*
481    Print("RULES: \n");
482        RNode* tempR    =   rules->getFirst();
483        while(NULL != tempR) {
484            pWrite(tempR->getRuleTerm());
485            Print("%d\n\n",tempR->getRuleIndex());
486            tempR   =   tempR->getNext();
487        }
488        //Print("TESTED ELEMENT: ");
489        //pWrite(l->getPoly());
490        //pWrite(l->getTerm());
491        //pWrite(ppMult_qq(t,l->getTerm()));
492        //Print("%d\n\n",l->getIndex());
493    */
494// start at the previously added element to gPrev, as all other elements will have the same index for sure
495        RNode* testNode =   rules->getFirst();
496    // save the monom t1*label_term(l) as it is tested various times in the following
497    poly u1 = ppMult_qq(t,l->getTerm());
498        // first element added to rTag was NULL, check for this
499        while(NULL != testNode && testNode->getRule() != testedRule) {
500        //pWrite(testNode->getRuleTerm());
501        if(pLmDivisibleByNoComp(testNode->getRuleTerm(),u1)) {
502            //Print("--------------------------Criterion 2 NOT passed!------------------------------\n");
503            //Print("INDEX: %d\n",l->getIndex());
504            pDelete(&u1);
505    //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
506            return true;
507        }
508                testNode    =   testNode->getNext();
509    }
510    pDelete(&u1);
511    //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
512    return false;
513}
514
515
516
517/*
518==================================
519Computation of S-Polynomials in F5
520==================================
521*/
522void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) { 
523    CNode* temp         =   first;
524    poly sp     =   pInit();
525    number sign =   nInit(-1);   
526    //Print("###############################IN SPOLS##############################\n");
527    //first->print();
528
529    while(NULL != temp) {
530        //Print("JA\n");
531        // only if a new rule was added since the last test in subalgorithm criticalPair()
532        //if(rules->getFirst() != rTag->getFirst()) {
533        if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRule())) {
534                // the second component is tested only when it has the actual index, otherwise there is
535                // no new rule to test since the last test in subalgorithm criticalPair()
536                if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) { 
537                    highestDegree   = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()));
538                    //pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
539                }   
540                if(temp->getLp2Index() == temp->getLp1Index()) {
541                    if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRule())) {
542                        // computation of S-polynomial
543                        //poly p1 =   temp->getLp1Poly();
544                        //poly p2 =   temp->getLp2Poly();
545                        //pIter(p1);
546                        //pIter(p2);
547                        //sp  =   pAdd(ppMult_qq(temp->getT1(),p1),pMult_nn(ppMult_qq(temp->getT2(),p2),sign)); 
548                        sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
549                                         ppMult_qq(temp->getT2(),temp->getLp2Poly()));
550                        //Print("BEGIN SPOLY1\n====================\n");
551                        pNorm(sp);
552                        //pWrite(sp);
553                        //Print("END SPOLY1\n====================\n");
554                        if(NULL == sp) {
555                            // as rules consist only of pointers we need to save the labeled
556                            // S-polynomial also of a zero S-polynomial
557                            //zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
558                            // origin of rule can be set NULL as the labeled polynomial
559                            // will never be used again as it is zero => no problems with
560                            // further criterion2() tests and termination conditions
561                            //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
562                                                        reductionsToZero++;
563                        //Print("IN SPOLS 1\n");
564                            //Rule* rNew  =  new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
565                            //rules->insertOrdered(rNew);
566                            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
567                            numberOfRules++;
568                            //Print("RULE ADDED: \n");
569                            //pWrite(rules->getFirst()->getRuleTerm());
570                            //rules->print();
571                            // as sp = NULL, delete it
572                            pDelete(&sp);
573                            //Print("HIER\n");
574                        }
575                        else {
576                        //Print("IN SPOLS 2\n");
577                            //Rule* rNew  =  new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
578                            //rules->insertOrdered(rNew);
579                            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
580                            numberOfRules++;
581                            //Print("RULE ADDED: \n");
582                            //pWrite(rules->getFirst()->getRuleTerm()); 
583                            //rules->print();
584                            sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
585                            //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rNew);
586                        }
587                        // data is saved in sPolyList or zero => delete sp
588                    }
589                }
590                else { // temp->getLp2Index() < temp->getLp1Index()
591                    // computation of S-polynomial
592                        //poly p1 =   temp->getLp1Poly();
593                        //poly p2 =   temp->getLp2Poly();
594                        //pIter(p1);
595                        //pIter(p2);
596                        //sp  =   pAdd(ppMult_qq(temp->getT1(),p1),pMult_nn(ppMult_qq(temp->getT2(),p2),sign)); 
597                    sp      =   ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
598                                     ppMult_qq(temp->getT2(),temp->getLp2Poly()));
599                    //Print("BEGIN SPOLY2\n====================\n");
600                    pNorm(sp);
601                    //pWrite(sp);
602                    //Print("END SPOLY2\n====================\n");
603                    if(NULL == sp) {
604                        // zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
605                        // origin of rule can be set NULL as the labeled polynomial
606                        // will never be used again as it is zero => no problems with
607                        // further criterion2() tests and termination conditions
608                            //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
609                        reductionsToZero++;
610                        //Print("IN SPOLS 3\n");
611                        rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
612                        numberOfRules++;
613                        //Print("RULE ADDED: \n");
614                        //pWrite(rules->getFirst()->getRuleTerm());
615                        //rules->print();
616                        // as sp = NULL, delete it
617                        pDelete(&sp);
618                    }
619                    else {
620                        //Print("IN SPOLS 4\n");
621                       
622                        //////////////////////////////////////////////////////////
623                        //////////////////////////////////////////////////////////
624                        // TODO: Rules inserted ordered by their label monomial!//
625                        //////////////////////////////////////////////////////////
626                        //////////////////////////////////////////////////////////
627
628                        //Rule* rNew      =   new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
629                        //RNode* rNodeNew =   new RNode(rNew);
630                        //rules->insertOrdered(rNew);
631                        rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
632                        numberOfRules++;
633                        //Print("RULE ADDED: \n");
634                        //pWrite(rules->getFirst()->getRuleTerm());
635                        //rules->print();
636                        //Print("%d\n",rules->getFirst()->getRuleIndex());
637                        //Print("%p\n",sPolyList->getFirst());
638                        sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
639                        //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rNew);
640                    }
641                }
642            }
643        //}
644        //Print("%p\n",temp);
645        temp    =   temp->getNext();
646        //Print("%p\n",temp);
647        //Print("%p\n",temp->getData());
648        //pWrite(temp->getLp1Poly());
649    }
650    // these critical pairs can be deleted now as they are either useless for further computations or
651    // already saved as an S-polynomial to be reduced in the following
652    delete first;   
653}
654
655
656
657/*
658========================================================================
659reduction including subalgorithm topReduction() using Faugere's criteria
660========================================================================
661*/
662void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, 
663                 ideal gbPrev) { 
664    //Print("##########################################In REDUCTION!########################################\n");
665    // check if sPolyList has any elements
666    // NOTE: due to initialization sPolyList always has a default NULL element
667    LNode* temp = sPolyList->getFirst();
668    while(NULL != temp) {
669        // temp is the first element in the sPolyList which should be reduced
670        // due to earlier sorting this is the element of minimal degree AND
671        // minimal label
672        // delete the above first element from sPolyList, temp will be either reduced to
673        // zero or added to gPrev, but never come back to sPolyList
674        //pWrite(sPolyList->getFirst()->getPoly());
675        //Print("LIST OF SPOLYNOMIALS!\n");
676        //sPolyList->print();
677        sPolyList->setFirst(temp->getNext());
678        poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
679        if(NULL != tempNF) {
680            pNorm(tempNF);
681            temp->setPoly(tempNF);
682            // try further reductions of temp with polynomials in gPrev
683            // with label index = current label index: this is done such that there
684            // is no label corruption during the reduction process
685            //Print("lower label reduction:  ");
686            //pWrite(tempNF);
687            topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev);
688       
689        }
690        else {
691            reductionsToZero++;
692            delete temp;
693        }
694        //if(NULL != temp->getPoly()) {
695        //    criticalPair(gPrev,critPairs,lTag,rTag,rules);
696        //}
697        temp =   sPolyList->getFirst();
698    }
699    //sPolyList->print();
700    //delete sPolyList;
701}   
702
703/*
704========================================================================
705reduction including subalgorithm topReduction() using Faugere's criteria
706========================================================================
707*/
708void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, 
709                 ideal gbPrev, int termination) { 
710    //Print("##########################################In REDUCTION!########################################\n");
711    // check if sPolyList has any elements
712    // NOTE: due to initialization sPolyList always has a default NULL element
713    //Print("--1--\n");
714    LNode* temp = sPolyList->getFirst();
715    while(NULL != temp) {
716        // temp is the first element in the sPolyList which should be reduced
717        // due to earlier sorting this is the element of minimal degree AND
718        // minimal label
719        // delete the above first element from sPolyList, temp will be either reduced to
720        // zero or added to gPrev, but never come back to sPolyList
721        //Print("LIST OF SPOLYNOMIALS!\n");
722        //sPolyList->print();
723        //pWrite(sPolyList->getFirst()->getPoly());
724        sPolyList->setFirst(temp->getNext());
725        //pWrite(temp->getPoly());
726        //poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
727        //Print("!!!\n");
728        //if(NULL != tempNF) {
729            //pNorm(tempNF);
730            //temp->setPoly(tempNF);
731            //Print("lower label reduction:  ");
732            //pWrite(tempNF);
733            // try further reductions of temp with polynomials in gPrev
734            // with label index = current label index: this is done such that there
735            // is no label corruption during the reduction process
736            findReducers(temp,sPolyList,gbPrev,gPrev,critPairs,rules,lTag,rTag, termination); 
737        //}
738        //else {
739        //    reductionsToZero++;
740        //    delete temp;
741        //}
742        //if(NULL != temp->getPoly()) {
743        //    criticalPair(gPrev,critPairs,lTag,rTag,rules);
744        //}
745        //Print("HIER AUCH ?\n");
746        //Print("--2--\n");
747        //sPolyList->print();
748        //critPairs->print();
749        temp =   sPolyList->getFirst();
750        //Print("%p\n",temp);
751    }
752    //sPolyList->print();
753    //delete sPolyList;
754    //Print("REDUCTION FERTIG\n");
755}     
756
757
758/*!
759 * ================================================================================
760 * searches for reducers of temp similar to the symbolic preprocessing of F4  and
761 * divides them into a "good" and "bad" part:
762 *
763 * the "good" ones are the reducers which do not corrupt the label of temp, with
764 * these the normal form of temp is computed
765 *
766 * the "bad" ones are the reducers which corrupt the label of temp, they are tested
767 * later on for possible new rules and S-polynomials to be added to the algorithm
768 * ================================================================================
769*/
770void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination) {
771    int canonicalize    =   0;
772    //int timerRed        =   0;
773    bool addToG         =   1;
774    number sign         =   nInit(-1);
775    LList* good         =   new LList();
776    LList* bad          =   new LList();
777    LList* monomials    =   new LList(l->getLPoly());
778    poly u              =   pOne();
779    number nOne         =   nInit(1);
780    LNode* tempRed      =   lTag->getFirstCurrentIdx();
781    LNode* tempMon      =   monomials->getFirst();
782    poly tempPoly       =   pInit();
783    poly redPoly        =   NULL;
784    int idx             =   l->getIndex();
785    //Print("IN FIND REDUCERS:  ");
786    //pWrite(l->getPoly());
787    tempPoly    =   pCopy(l->getPoly());
788    //tempMon->setPoly(tempPoly);
789    //while(NULL != tempMon) {
790        // iteration over all monomials in tempMon
791        kBucket* bucket  =   kBucketCreate();
792        kBucketInit(bucket,tempPoly,0);
793        tempPoly    =   kBucketGetLm(bucket);
794        //Print("\n\n\nTO BE REDUCED:  ");
795        //pWrite(l->getPoly());
796        //pWrite(tempPoly);
797        while(NULL != tempPoly) {
798            // iteration of all elements in gPrev of the current index
799            tempRed =   gPrev->getFirst();
800            while(NULL != tempRed) {
801                //Print("TEMPREDPOLY:  ");
802                //pWrite(tempRed->getPoly());
803                if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
804                    u   =   pDivideM(pHead(tempPoly),pHead(tempRed->getPoly()));
805                    //Print("U:  ");
806                    //pWrite(u);
807                    if(tempRed->getIndex() != idx) {
808                            // passing criterion1 ?
809                            if(!criterion1(gPrev,u,tempRed,lTag)) {
810                                    poly tempRedPoly    =   tempRed->getPoly();
811                                    //Print("REDUCER: ");
812                                    //pWrite(ppMult_qq(u,tempRedPoly));
813                                    pIter(tempRedPoly);
814                                    int lTempRedPoly    =   pLength(tempRedPoly);
815                                    kBucketExtractLm(bucket);
816                                    kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
817                                    canonicalize++;
818                                    //Print("Reduction\n");
819                                    if(!(canonicalize % 50)) {
820                                        kBucketCanonicalize(bucket);
821                                    }
822                                    tempPoly    =   kBucketGetLm(bucket);
823                                    //Print("TEMPPOLY:  ");
824                                    //pWrite(tempPoly);
825                                    if(NULL != tempPoly) {
826                                        tempRed     =   gPrev->getFirst();
827                                        continue;
828                                    }
829                                    else {
830                                        break;
831                                    }
832                             }   
833                   
834                    }
835                    else {
836                        if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) {
837                         Print("NOT ALLOWED REDUCER:\n");
838                                      pWrite(u);
839                                      pWrite(tempRed->getTerm());
840                                      pWrite(tempRed->getPoly()); 
841                                      addToG  = 0;
842                        }
843                        if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) {
844                            // passing criterion2 ?
845                            if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) {
846                                // passing criterion1 ?
847                                if(!criterion1(gPrev,u,tempRed,lTag)) {
848                                    if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
849                                        if(NULL == redPoly) {
850                                            bad->insert(tempRed->getLPoly());
851                                            addToG  = 1;
852                                            //poly tempRedPoly    =   tempRed->getPoly();
853                                            //break;
854                                        }
855                                    }
856                                    else {
857                                        poly tempRedPoly    =   tempRed->getPoly();
858                                        //Print("REDUCER: ");
859                                        //pWrite(ppMult_qq(u,tempRedPoly));
860                                        pIter(tempRedPoly);
861                                        int lTempRedPoly    =   pLength(tempRedPoly);
862                                        //Print("HEAD MONOMIAL KBUCKET: ");
863                                        //pWrite(kBucketGetLm(bucket));
864                                        kBucketExtractLm(bucket);
865                                        kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly);
866                                        canonicalize++;
867                                        //Print("REDUCTION\n");
868                                        addToG  = 1;
869                                        if(!(canonicalize % 50)) {
870                                            kBucketCanonicalize(bucket);
871                                        }
872                                        //Print("HEAD MONOMIAL KBUCKET: ");
873                                        //pWrite(kBucketGetLm(bucket));
874                                        tempPoly    =   kBucketGetLm(bucket);
875                                        //Print("TEMPPOLY:  ");
876                                        //pWrite(tempPoly);
877                                        if(NULL != tempPoly) {
878                                            tempRed     =   gPrev->getFirst();
879                                            continue;
880                                        }
881                                        else {
882                                            break;
883                                        }
884                                    }
885                                }   
886                            }
887                            else {
888                              Print("CRIT 1  ");
889                                   
890                                      if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) {
891                                      Print("NOT ALLOWED REDUCER:\n");
892                                      pWrite(u);
893                                      pWrite(tempRed->getTerm());
894                                      pWrite(tempRed->getPoly());
895                                      addToG  = 0;
896                                    }
897                            }
898                        }
899                        else {
900                          Print("CRIT 2  ");
901                                    if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
902                                      Print("NOT ALLOWED REDUCER:\n");
903                                      pWrite(u);
904                                      pWrite(tempRed->getTerm());
905                                      pWrite(tempRed->getPoly());
906                                      addToG  = 0;
907                                    }
908                        }
909                    }
910                   
911                }
912                tempRed =   tempRed->getNext();
913            }
914            if(NULL != tempPoly) {
915                if(NULL == redPoly) {
916                    redPoly =   kBucketExtractLm(bucket);
917                }
918                else {
919                    redPoly     =   p_Merge_q(redPoly,kBucketExtractLm(bucket),currRing);
920                }
921               // for top-reduction only
922               redPoly  = p_Merge_q(redPoly,kBucketClear(bucket),currRing);
923               break;
924               // end for top-reduction only
925               tempPoly    =   kBucketGetLm(bucket);
926               
927            }
928        }
929        if(NULL == redPoly) {
930            reductionsToZero++;
931            //pDelete(&redPoly);
932        }
933        else {
934            Print("\nELEMENT ADDED TO GPREV: ");
935            pNorm(redPoly);
936            pWrite(pHead(redPoly));
937            pWrite(l->getTerm());
938            //Print("%d\n",canonicalize);
939            l->setPoly(redPoly);
940            gPrev->insert(l->getLPoly());
941            //Print("%d\n\n",termination);
942            if(termination == 1) {
943            if(addToG) {
944              //Print("----------------HERE?-----------------\n");
945              criticalPair(gPrev,critPairs,lTag,rTag,rules);
946            }
947            else {
948              notInG++;
949              Print("\nNONONO");
950              pWrite(pHead(l->getPoly()));
951              pWrite(l->getTerm());
952            }
953            }
954            else {
955              criticalPair(gPrev,critPairs,lTag,rTag,rules);
956            }
957        }
958   
959    // if there are "bad" reducers than try to compute new S-polynomials and rules
960   
961    if(NULL != bad->getFirst()) {
962        //Print("BAD STUFF LIST:\n");
963        //bad->print();
964        LNode* tempBad  =   bad->getFirst();
965        //pWrite(l->getPoly());
966        while(NULL != tempBad) {
967            if(pDivisibleBy(tempBad->getPoly(),l->getPoly())) {
968                //Print("BAD STUFF\n");
969                //pWrite(l->getPoly());
970                //pWrite(tempBad->getPoly());
971                u   =   pDivide(pHead(l->getPoly()),pHead(tempBad->getPoly()));
972                //Print("MULTIPLIER:  ");
973                //pWrite(u);
974                pSetCoeff(u,nOne);
975                if(pLmCmp(ppMult_qq(u,tempBad->getTerm()),l->getTerm()) != 0) {
976                    // passing criterion2 ?
977                    if(!criterion2(gPrev->getFirst()->getIndex(), u,tempBad,rules,rTag)) {
978                        // passing criterion1 ?
979                        if(!criterion1(gPrev,u,tempBad,lTag)) {
980                            //Print("HIERHIERHIERHIERHIERHIER\n");
981                            rules->insert(tempBad->getIndex(),ppMult_qq(u,tempBad->getTerm()));
982                            numberOfRules++;
983                            //gPrev->print();
984                            //pWrite(l->getPoly());
985                            poly temp   =   ksOldSpolyRedNew(ppMult_qq(u,tempBad->getPoly()),l->getPoly());
986                            //pWrite(l->getPoly());
987                            //Print("%p\n",temp);
988                            //gPrev->print();
989                            if(NULL != temp) {
990                                pNorm(temp);
991                                LNode* tempBadNew   =   new LNode(ppMult_qq(u,tempBad->getTerm()),tempBad->getIndex(),temp,rules->getFirst()->getRule());
992                                //pWrite(temp);
993                                //pWrite(tempBadNew->getPoly());
994                                //pWrite(tempBadNew->getTerm());
995                                //pWrite(pHead(tempBadNew->getPoly()));
996                                //Print("%p\n",tempBadNew->getPoly());
997                                //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
998                                tempBadNew->setDel(1);
999                           
1000                                sPolyList->insertByLabel(tempBadNew);
1001                                //Print("BAD SPOLYLIST: \n");
1002                                //sPolyList->print();
1003                            }
1004                        }
1005                    }
1006                }
1007            }
1008        //Print("HIER\n");
1009            tempBad =   tempBad->getNext();
1010            //Print("%p\n",tempBad);
1011        }
1012       // Print("-------------------BAD STUFF LIST-----------------------------\n");
1013    }
1014        //Print("HIER AUCH\n");
1015        //Print("SPOLYLIST IN BAD: \n");
1016        //sPolyList->print();
1017    //Print("END FIND REDUCERS\n");
1018}
1019
1020/*
1021=======================================================================================
1022merging 2 polynomials p & q without requiring that all monomials of p & q are different
1023if there are equal monomials in p & q only one of these monomials (always that of p!)
1024is taken into account
1025=======================================================================================
1026
1027poly p_MergeEq_q(poly p, poly q, const ring r) {
1028  assume(p != NULL && q != NULL);
1029  p_Test(p, r);
1030  p_Test(q, r);
1031#if PDEBUG > 0
1032  int l = pLength(p) + pLength(q);
1033#endif
1034
1035  spolyrec rp;
1036  poly a = &rp;
1037  DECLARE_LENGTH(const unsigned long length = r->CmpL_Size);
1038  DECLARE_ORDSGN(const long* ordsgn = r->ordsgn);
1039
1040  Top:     // compare p and q w.r.t. monomial ordering
1041  p_MemCmp(p->exp, q->exp, length, ordsgn, goto Equal, goto Greater , goto Smaller);
1042
1043  Equal:
1044  a =   pNext(a)    =   p;
1045  pIter(p);
1046  pIter(q);
1047  if(NULL == p) {
1048      if(NULL == q) {
1049          goto Finish;
1050      }
1051      else {
1052          pNext(a)  =   q;
1053          goto Finish;
1054      }
1055  }
1056  goto Top;
1057
1058  Greater:
1059  a = pNext(a) = p;
1060  pIter(p);
1061  if (p==NULL) { pNext(a) = q; goto Finish;}
1062  goto Top;
1063
1064  Smaller:
1065  a = pNext(a) = q;
1066  pIter(q);
1067  if (q==NULL) { pNext(a) = p; goto Finish;}
1068  goto Top;
1069
1070  Finish:
1071
1072  p_Test(pNext(&rp), r);
1073#if PDEBUG > 0
1074  pAssume1(l - pLength(pNext(&rp)) == 0);
1075#endif
1076  return pNext(&rp);
1077}
1078*/
1079
1080/*
1081=====================================================================================
1082top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
1083the same index whereas the labels are taken into account
1084=====================================================================================
1085*/
1086void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs,  RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev) {
1087    //Print("##########################################In topREDUCTION!########################################\n");
1088    // try l as long as there are reductors found by findReductor()
1089    LNode* gPrevRedCheck    =   lTag->getFirstCurrentIdx();
1090    LNode* tempRed;
1091    poly pOne               =   pOne();
1092    do {
1093        //int timer5  =   initTimer();
1094        //startTimer();
1095        //Print("TOP REDUCTION:  ");
1096        //pWrite(l->getPoly());
1097        tempRed  =   findReductor(l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag);
1098        //timer5  =   getTimer();
1099        //reductionTime   =   reductionTime   +   timer5;
1100        // if a reductor for l is found and saved in tempRed
1101        if(NULL != tempRed) {
1102            // if label of reductor is greater than the label of l we have to built a new element
1103            // and add it to sPolyList
1104           
1105            if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
1106                // needed sinc pSub destroys the arguments!
1107                //poly temp_poly_l    =   pInit();
1108                //temp_poly_l         =   pCopy(l->getPoly());
1109                //Print("VORHER: ");
1110                //pWrite(tempRed->getPoly());
1111                //poly temp           =   pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1112                poly temp   =   ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1113                rules->insert(tempRed->getIndex(),tempRed->getTerm());
1114                //Print("NACHHER: ");
1115                //pWrite(tempRed->getPoly());
1116                //Print("TEMP: ");
1117                //pWrite(temp);
1118                if(NULL != temp) {
1119                    pNorm(temp);
1120                    //tempRed->setPoly(temp);
1121                    //tempRed->setDel(1);
1122                    //rules->insert(tempRed->getIndex(),tempRed->getTerm());
1123                    LNode* tempRedNew   =   new LNode(tempRed->getTerm(),tempRed->getIndex(),temp,rules->getFirst()->getRule());
1124                    //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
1125                    tempRedNew->setDel(1);
1126                    sPolyList->insertByLabel(tempRedNew);
1127                }
1128                else {
1129                    pDelete(&temp);
1130                    reductionsToZero++;
1131                    //delete tempRed;
1132                }
1133            }
1134           
1135            // label of reductor is smaller than the label of l, subtract reductor from l and delete the
1136            // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
1137            // after subtraction
1138            else {
1139               
1140                //poly temp_poly_l    =   pInit();
1141                //temp_poly_l         =   pCopy(l->getPoly());
1142                //poly temp   =   pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
1143                //Print("REDUCER: ");
1144                //pWrite(tempRed->getPoly());
1145                //pWrite(tempRed->getTerm());
1146                poly temp   =   ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
1147                //Print("REDUCED ELEMENT:  ");
1148                if(NULL != temp) {
1149                    pNorm(temp);
1150                    //pWrite(temp);
1151                    poly tempNF =   kNF(gbPrev,currQuotient,temp); 
1152                    pNorm(tempNF);
1153                    if(NULL == tempNF) {
1154                        reductionsToZero++;
1155                        pDelete(&tempNF);
1156                        l->setPoly(NULL);
1157                        break;
1158                    }
1159                    l->setPoly(tempNF);
1160                   
1161                    gPrevRedCheck   =   lTag->getFirstCurrentIdx();
1162                }
1163                else {
1164                    reductionsToZero++;
1165                    pDelete(&temp);
1166                    l->setPoly(NULL);
1167                    break;
1168                }
1169            }   
1170        }
1171        else {
1172            if(NULL != l->getPoly()) {
1173                pNorm(l->getPoly());
1174                //Print("ELEMENT ADDED TO GPREV: ");
1175                //pWrite(l->getPoly());
1176                gPrev->insert(l->getLPoly());
1177                //Print("TEMP RED == 0  ");
1178                //pWrite(l->getPoly());
1179                //pWrite(l->getTerm());
1180                //rules->print();
1181                criticalPair(gPrev,critPairs,lTag,rTag,rules);
1182                //Print("LIST OF CRITICAL PAIRS:    \n");
1183                //critPairs->print();
1184            }
1185            break;
1186        }
1187    } while(1);
1188}
1189
1190
1191/*
1192=====================================================================
1193subalgorithm to find a possible reductor for the labeled polynomial l
1194=====================================================================
1195*/
1196LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag) {
1197    // allociation of memory for the possible reductor
1198    //Print("LPOLY:  ");
1199    //pWrite(l->getPoly());
1200    poly u      =   pOne();
1201    poly red;
1202    number nOne =   nInit(1);
1203    LNode* temp;
1204    // head term of actual element such that we do not have to call pHead at each new reductor test
1205    poly t      =   pHead(l->getPoly());
1206    // if l was already checked use the information in gPrevRedCheck such
1207    // that we can start searching for new reducers from this point and
1208    // not from the first element of gPrev with the current index
1209    temp    =   gPrevRedCheck;
1210    // search for reductors until we are at the end of gPrev resp. at the
1211    // end of the elements of the current index
1212    while(NULL != temp && temp->getIndex() == l->getIndex()) {
1213        // does the head of the element of gPrev divides the head of
1214        // the to be reduced element?
1215        if(pLmDivisibleByNoComp(pHead(temp->getPoly()),t)) {
1216            // get all the information needed for the following tests
1217            // of the criteria
1218            u   =   pDivide(t,pHead(temp->getPoly()));
1219            pSetCoeff(u,nOne);
1220            red =   ppMult_qq(u,temp->getPoly());
1221            pNorm(red);
1222            // check if both have the same label
1223            if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) != 0) {
1224                // passing criterion2 ?
1225                if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) {
1226                    // passing criterion1 ?
1227                    if(!criterion1(gPrev,u,temp,lTag)) {
1228                            gPrevRedCheck   =   temp->getNext();
1229                            LNode* redNode  =   new LNode(ppMult_qq(u,temp->getTerm()),temp->getIndex(),red,NULL,NULL);
1230                            return redNode;
1231                    }
1232                }
1233            }
1234            if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) == 1) {
1235                // passing criterion2 ?
1236                if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) {
1237                    // passing criterion1 ?
1238                    if(!criterion1(gPrev,u,temp,lTag)) {
1239                        poly tempSpoly  =   ksOldSpolyRedNew(red,l->getPoly());
1240                        rules->insert(temp->getIndex(),ppMult_qq(u,temp->getTerm()));
1241                        gPrevRedCheck   =   temp->getNext();
1242                        if(NULL != tempSpoly) {
1243                            pNorm(tempSpoly);
1244                            sPolyList->insertByLabel(ppMult_qq(u,temp->getTerm()),temp->getIndex(),tempSpoly,rules->getFirst()->getRule());
1245                    //Print("NEW ONE: ");
1246                    //pWrite(tempSpoly);
1247                    //Print("HIER\n");
1248                            //sPolyList->print();
1249                            //sleep(5);
1250                        }
1251                    }
1252                }
1253            }
1254        }
1255        //Print("AUCH HIER\n");
1256        temp = temp->getNext();
1257    }
1258   
1259//    delete temp;
1260 return NULL;
1261}
1262
1263
1264
1265/*
1266==========================================================================
1267MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
1268OPTIONS: INTEGER "opt" is to be set "0" for F5, "1" for F5R, "2" for F5C
1269==========================================================================
1270*/
1271ideal F5main(ideal id, ring r, int opt, int termination) {
1272  switch(opt) { 
1273    case 0:
1274      Print("\nComputations are done by the standard F5 Algorithm");
1275      break;
1276    case 1:
1277      Print("\nComputations are done by the variant F5R of the F5 Algorithm");
1278      break;
1279    case 2:
1280      Print("\nComputations are done by the variant F5C of the F5 Algorithm");
1281      break;
1282    default:
1283      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");
1284      return id;
1285  }
1286    int timer   =   initTimer();
1287    startTimer();
1288    int i,j,k,l;
1289    int gbLength;
1290    // 1 polynomial for defining initial labels & further tests
1291    poly ONE = pOne();
1292    poly pOne   =   pOne();
1293    number nOne =   nInit(1);
1294    // tag the first element of index i-1 for criterion 1
1295    //Print("LTAG BEGINNING: %p\n",lTag);
1296   
1297    // DEBUGGING STUFF START
1298    //Print("NUMBER: %d\n",r->N);
1299    /*
1300    int* ev = new int[r->N +1];
1301    for(i=0;i<IDELEMS(id);i++) {
1302        pGetExpV(id->m[i],ev);
1303        //ev2  =   pGetExp(id->m[i],1);
1304        pWrite(id->m[i]);
1305        Print("EXP1: %d\n",ev[1]);
1306        Print("EXP2: %d\n",ev[2]);
1307        Print("EXP3: %d\n\n",ev[3]);
1308        Print("SUM: %ld\n\n\n",sumVector(ev,r->N));
1309    }
1310    delete ev;
1311    */
1312    /*DEBUGGING STUFF END */
1313   
1314    // first element in rTag is first element of rules which is NULL RNode,
1315    // this must be done due to possible later improvements
1316    RList* rules    =   new RList();
1317    //Print("RULES FIRST: %p\n",rules->getFirst());
1318    //Print("RULES FIRST DATA: %p\n",rules->getFirst()->getRule());
1319    //RTagList* rTag  =   new RTagList(rules->getFirst());
1320    RTagList* rTag  =   NULL;
1321    i = 1;
1322    /*for(j=0; j<IDELEMS(id); j++) {
1323        if(NULL != id->m[j]) {
1324            if(pComparePolys(id->m[j],ONE)) {
1325                Print("One Polynomial in Input => Computations stopped\n");
1326                ideal idNew = idInit(1,1);
1327                idNew->m[0] = ONE;
1328                return(idNew);
1329            }   
1330        }
1331    }*/ 
1332    ideal idNew     =   kInterRed(id); 
1333    id              =   idNew;
1334    //qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
1335    //idShow(id);
1336    LList* gPrev    =   new LList(ONE, i, id->m[0]);
1337    //idShow(id);
1338    //Print("%p\n",id->m[0]);
1339    //pWrite(id->m[0]);
1340    //Print("%p\n",gPrev->getFirst()->getPoly());
1341    //pWrite(gPrev->getFirst()->getPoly());
1342
1343    LTagList* lTag  =   new LTagList(gPrev->getFirst());
1344    //lTag->insert(gPrev->getFirst());
1345    lTag->setFirstCurrentIdx(gPrev->getFirst());
1346    // computing the groebner basis of the elements of index < actual index
1347    gbLength    =   gPrev->getLength();
1348    //Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
1349    ideal gbPrev    =   idInit(gbLength,1);
1350    // initializing the groebner basis of elements of index < actual index
1351    gbPrev->m[0]    =   gPrev->getFirst()->getPoly();
1352    //idShow(gbPrev);
1353    //idShow(currQuotient);
1354    for(i=2; i<=IDELEMS(id); i++) {
1355        LNode* gPrevTag =   gPrev->getLast();
1356        //Print("Last POlynomial in GPREV: ");
1357        //Print("%p\n",gPrevTag);   
1358        //pWrite(gPrevTag->getPoly());
1359        gPrev   =   F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag, termination);
1360        //Print("%d\n",gPrev->count(gPrevTag->getNext()));
1361        //Print("%d\n",gPrev->getLength());
1362        //Print("____________________________________ITERATION STEP DONE________________________________________\n");
1363       
1364        // DEBUGGING STUFF
1365        LNode* temp    =   gPrev->getFirst();
1366   
1367
1368        /////////////////////////////////////////////////////////////////////////////////
1369        //                                                                             //
1370        // one needs to choose one of the following 3 implementations of the algorithm //
1371        // F5,F5R or F5C                                                               //
1372        //                                                                             //
1373        /////////////////////////////////////////////////////////////////////////////////                                                                           
1374       
1375       
1376        //   
1377        // standard "F5"
1378        //
1379        if(0 == opt) { 
1380          if(gPrev->getLength() > gbLength) {
1381            if(i < IDELEMS(id)) {
1382                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
1383                LNode*  temp =   gPrevTag;
1384                int counter =   0;
1385                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
1386                    temp        =   temp->getNext();
1387                    if(0 == temp->getDel()) {
1388                        counter++;
1389                        gbAdd->m[j] =   temp->getPoly();
1390                    }
1391                }
1392                    gbPrev          =   idAdd(gbPrev,gbAdd);
1393            }
1394            else {
1395                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
1396                LNode*  temp =   gPrevTag;
1397                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
1398                    temp        =   temp->getNext();
1399                    gbAdd->m[j] =   temp->getPoly();
1400                }
1401                gbPrev          =   idAdd(gbPrev,gbAdd);
1402            }
1403            if(i == IDELEMS(id)) {
1404                ideal tempId        =   kInterRed(gbPrev);
1405                gbPrev              =   tempId;
1406            }
1407        }
1408        gbLength    =   gPrev->getLength();
1409        }
1410       
1411
1412        //
1413        //  "F5R"
1414        //
1415        if(1 == opt) {
1416        if(gPrev->getLength() > gbLength) {
1417            if(i < IDELEMS(id)) {
1418                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
1419                LNode*  temp =   gPrevTag;
1420                int counter =   0;
1421                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
1422                    temp        =   temp->getNext();
1423                    if(0 == temp->getDel()) {
1424                        counter++;
1425                        gbAdd->m[j] =   temp->getPoly();
1426                    }
1427                }
1428                    gbPrev          =   idAdd(gbPrev,gbAdd);
1429            }
1430            else {
1431                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
1432                LNode*  temp =   gPrevTag;
1433                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
1434                    temp        =   temp->getNext();
1435                    gbAdd->m[j] =   temp->getPoly();
1436                }
1437                gbPrev          =   idAdd(gbPrev,gbAdd);
1438            }
1439            // interreduction stuff
1440            // comment this out if you want F5 instead of F5R
1441            //if(i<IDELEMS(id)) {
1442                ideal tempId    =   kInterRed(gbPrev);
1443                gbPrev          =   tempId;
1444            //}
1445        }
1446        gbLength    =   gPrev->getLength();
1447        }
1448       
1449
1450        //
1451        // "F5C"
1452        //
1453        if(2 == opt) { 
1454        if(gPrev->getLength() > gbLength) {
1455            if(i < IDELEMS(id)) {
1456                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
1457                LNode*  temp =   gPrevTag;
1458                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
1459                    temp        =   temp->getNext();
1460                        gbAdd->m[j] =   temp->getPoly();
1461                }
1462                    gbPrev          =   idAdd(gbPrev,gbAdd);
1463            }
1464            else {
1465                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
1466                LNode*  temp =   gPrevTag;
1467                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
1468                    temp        =   temp->getNext();
1469                    gbAdd->m[j] =   temp->getPoly();
1470                }
1471                gbPrev          =   idAdd(gbPrev,gbAdd);
1472            }
1473            if(i<IDELEMS(id)) {
1474                ideal tempId    =   kInterRed(gbPrev);
1475                gbPrev          =   tempId;
1476                delete gPrev;
1477                delete rules;
1478                gPrev    =   new LList(pOne,1,gbPrev->m[0]);
1479                gPrev->insert(pOne,1,gbPrev->m[1]);
1480                rules    =   new RList();
1481                //rTag     =   new RTagList(rules->getFirst());
1482                for(k=2; k<IDELEMS(gbPrev); k++) {
1483                    gPrev->insert(pOne,k+1,gbPrev->m[k]);
1484                    /*
1485                    for(l=0; l<k; l++) {
1486                    }
1487                    rTag->insert(rules->getFirst());
1488                    */
1489                }
1490            }
1491            gbLength    =   gPrev->getLength(); 
1492        } 
1493        }
1494
1495
1496    }
1497    timer   =   getTimer();
1498    //Print("\n\nADDING TIME IN REDUCTION: %d\n\n",reductionTime);
1499    Print("\n\nNumber of zero-reductions:           %d\n",reductionsToZero);
1500    Print("Number of rules:                     %d\n",numberOfRules); 
1501    Print("Elements not added to G:             %d\n",notInG); 
1502    Print("Highest Degree during computations:  %d\n",highestDegree);
1503    Print("Time for computations:               %d/1000 seconds\n",timer);
1504    Print("Number of elements in gb:            %d\n",IDELEMS(gbPrev));
1505    //LNode* temp    =   gPrev->getFirst();
1506    //while(NULL != temp) {
1507    //    pWrite(temp->getPoly());
1508    //    temp    =   temp->getNext();
1509    // }
1510    //gPrev->print();
1511    //delete lTag;
1512    delete rTag;
1513    delete gPrev;
1514    notInG              =   0;
1515    numberOfRules       =   0;
1516    reductionsToZero    =   0;
1517    highestDegree       =   0;
1518    reductionTime       =   0;
1519    spolsTime           =   0;
1520    return(gbPrev);
1521
1522
1523}
1524
1525#endif
Note: See TracBrowser for help on using the repository browser.