source: git/kernel/f5gb.cc @ 47b2b2d

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