source: git/kernel/f5gb.cc @ 5cd07b

spielwiese
Last change on this file since 5cd07b was c4a041, checked in by Christian Eder, 15 years ago
memory optimized in reduction() git-svn-id: file:///usr/local/Singular/svn/trunk@11614 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 40.3 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 "ideals.h"
17#include "febase.h"
18#include "kstd1.h"
19#include "khstd.h"
20#include "kbuckets.h"
21#include "weight.h"
22#include "intvec.h"
23#include "pInline1.h"
24#include "f5gb.h"
25#include "f5data.h"
26#include "f5lists.h"
27#include "timer.h"
28int reductionsToZero    =   0;
29int reductionTime       =   0;
30int spolsTime           =   0;
31int highestDegree       =   0;
32/*
33====================================================================
34sorting ideals by decreasing total degree "left" and "right" are the
35pointer of the first and last polynomial in the considered ideal
36====================================================================
37*/
38void qsortDegree(poly* left, poly* right) {
39    poly* ptr1 = left;
40    poly* ptr2 = right;
41    poly p1,p2;
42    p2 = *(left + (right - left >> 1));
43    do {
44            while(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)) {
45                    ptr1++;
46            } 
47            while(pTotaldegree(*ptr2, currRing) > pTotaldegree(p2,currRing)) {
48                    ptr2--;
49            }
50            if(ptr1 > ptr2) {
51                    break;
52            }
53            p1    = *ptr1;
54            *ptr1 = *ptr2;
55            *ptr2 = p1;
56    } while(++ptr1 <= --ptr2);
57
58    if(left < ptr2) {
59            qsortDegree(left,ptr2);
60    }
61    if(ptr1 < right) {
62            qsortDegree(ptr1,right);
63    }
64}
65
66
67
68/*
69==================================================
70computes incrementally gbs of subsets of the input
71gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
72==================================================
73*/
74LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag) {
75    Print("in f5inc\n");           
76    //pWrite(rules->getFirst()->getRuleTerm());
77    int j;
78    //Print("%p\n",gPrev->getFirst());
79    //pWrite(gPrev->getFirst()->getPoly());
80    poly tempNF =   kNF(gbPrev,currQuotient,f_i);
81    f_i         =   tempNF;
82    //gPrev->insert(ONE,i,f_i);
83    gPrev->insert(ONE,gPrev->getLength()+1,f_i);
84    // tag the first element in gPrev of the current index for findReductor()
85    lTag->setFirstCurrentIdx(gPrev->getLast());
86    //Print("1st gPrev: ");
87    //pWrite(gPrev->getFirst()->getPoly());
88    //Print("2nd gPrev: ");
89    //pWrite(gPrev->getFirst()->getNext()->getPoly());
90    //pWrite(gPrev->getFirst()->getNext()->getPoly());   
91    CList* critPairs        =   new CList();
92    CNode* critPairsMinDeg  =   new CNode();   
93    // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
94    // in the list critPairs
95    criticalPair(gPrev, critPairs, lTag, rTag, rules);
96    static LList* sPolyList        =   new LList();
97    //sPolyList->print();
98    // labeled polynomials which have passed reduction() and have to be added to list gPrev
99    static LList* completed        =   new LList();
100    // the reduced labeled polynomials which are returned from subalgorithm reduction()
101    static LList* reducedLPolys     =   new LList();
102    // while there are critical pairs to be further checked and deleted/computed
103    while(NULL != critPairs->getFirst()) { 
104        // critPairs->getMinDeg() deletes the first elements of minimal degree from
105        // critPairs, thus the while loop is not infinite.
106        critPairsMinDeg =   critPairs->getMinDeg();
107        // adds all to be reduced S-polynomials in the list sPolyList and adds
108        // the corresponding rules to the list rules
109        // NOTE: inside there is a second check of criterion 2 if new rules are
110        // added
111        //int timer4  =   initTimer();
112        //startTimer();
113        computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
114        //timer4  =   getTimer();
115        //Print("SPOLS TIMER: %d\n",timer4);
116        //spolsTime  =   spolsTime  +   timer4;
117        // DEBUG STUFF FOR SPOLYLIST
118        LNode* temp     =   sPolyList->getFirst();
119        //while(NULL != temp && NULL != temp->getLPoly()) {
120            //Print("Spolylist element: ");
121            //pWrite(temp->getPoly());
122            //temp    =   temp->getNext();
123        //}
124        // reduction process of new S-polynomials and also adds new critical pairs to critPairs
125        //int timer3  =   initTimer();
126        //startTimer();
127        reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
128        //timer3      =  getTimer();
129        //reductionTime = reductionTime + timer3;
130        //Print("REDUCTION TIMER: %d\n",timer3);
131        // DEBUG STUFF FOR GPREV
132        //temp    =   gPrev->getFirst();
133        //int number  =   1;
134        //Print("\n\n");
135        //while(NULL != temp) {
136        //    Print("%d.  ",number);
137        //    pWrite(temp->getPoly());
138        //    temp    =   temp->getNext();
139        //    number++;
140        //    Print("\n");
141        //}
142        //sleep(5);
143   
144    }
145    //Print("REDUCTION DONE\n");
146    //Print("%p\n",rules->getFirst());
147    //Print("%p\n",rTag->getFirst());
148    //if(rules->getFirst() != rTag->getFirst()) {
149        //Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n");
150        //rTag->insert(rules->getFirst());
151    //}
152    //else {
153        //Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
154    //}
155    lTag->insert(lTag->getFirstCurrentIdx());
156    //Print("INDEX: %d\n",tempTag->getIndex());
157    //pWrite(tempTag->getPoly());
158    //Print("COMPLETED FIRST IN F5INC: \n");
159    //Print("1st gPrev: ");
160    //pWrite(gPrev->getFirst()->getPoly());
161    //Print("2nd gPrev: ");
162    //pWrite(gPrev->getFirst()->getNext()->getPoly());
163    //Print("3rd gPrev: ");
164    //pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly());
165    //delete sPolyList;
166    //critPairs->print();
167    delete critPairs;
168    //Print("IN F5INC\n");
169    /*
170    Print("\n\n\nRULES: \n");
171        RNode* tempR    =   rules->getFirst();
172        Print("%p\n",tempR);
173        int t   = 1;
174        while(NULL != tempR) {
175            Print("ADDRESS OF %d RNODE: %p\n",t,tempR);
176            Print("ADDRESS OF RULE: %p\n",tempR->getRule());
177            pWrite(tempR->getRuleTerm());
178            Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
179            Print("%d\n\n",tempR->getRuleIndex());
180            tempR   =   tempR->getNext();
181            t++;
182        }
183    */
184    //gPrev->print();
185    Print("COMPLETE REDUCTION TIME UNTIL NOW: %d\n",reductionTime);
186    Print("COMPLETE SPOLS TIME UNTIL NOW:     %d\n",spolsTime);
187    return gPrev;
188}
189
190
191
192/*
193================================================================
194computes a list of critical pairs for the next reduction process
195first element in gPrev is always the newest element which must
196build critical pairs with all other elements in gPrev
197================================================================
198*/
199inline void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
200    //Print("IN CRITPAIRS\n");
201    // initialization for usage in pLcm()
202    number nOne         =   nInit(1);
203    LNode* newElement   =   gPrev->getLast();
204    LNode* temp         =   gPrev->getFirst();
205    poly u1             =   pOne();
206    poly u2             =   pOne();
207    poly lcm            =   pOne();
208    poly t              =   pHead(newElement->getPoly());
209    Rule* testedRule    =   NULL;
210    if(NULL != rules->getFirst()) {
211        testedRule  =   rules->getFirst()->getRule();
212    }
213    // computation of critical pairs
214    //critPairs->print();
215    while( gPrev->getLast() != temp) {
216        //pWrite( *(gPrev->getFirst()->getPoly()) );
217       // pWrite( *(l->getPoly()) );
218       //pWrite(newElement->getPoly());
219        //pWrite(temp->getPoly());
220        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
221        pSetCoeff(lcm,nOne);
222        // computing factors u2 for new labels
223        //pExpVectorDiff(u1,lcm,t);
224        //Print("U1: ");
225        //pWrite(u1);
226        u1 = pDivide(lcm,t);
227        //pWrite(u1);
228        pSetCoeff(u1,nOne);
229        //Print("%p\n",u1);
230        //critPairs->print();
231        //pExpVectorDiff(u2,lcm,temp->getPoly());
232        //Print("U2: ");
233        //pWrite(u2);
234        u2 = pDivide(lcm, pHead(temp->getPoly()));
235        //pWrite(u2);
236        //Print("%p\n",u2);
237        pSetCoeff(u2,nOne);
238        //if(gPrev->getLast()->getIndex()==5) {
239            //Print("IN CRITPAIRS\n");
240        //    pWrite(u1);
241        //    Print("1st ELEMENT: ");
242        //    pWrite(newElement->getPoly());
243        //    Print("2nd ELEMENT: ");
244        //    pWrite(temp->getPoly());
245        //}
246        // testing both new labels by the F5 Criterion
247        //critPairs->print();
248        if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag)
249           && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag) 
250           && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) {
251            // if they pass the test, add them to CList critPairs, having the LPoly with greater
252            // label as first element in the CPair
253            if(newElement->getIndex() == temp->getIndex() && 
254            -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
255                //Print("zweites groesser\n");
256               
257                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, 
258                                temp->getLPoly(), u1, newElement->getLPoly(), testedRule);                   
259               
260                critPairs->insert(cp);
261                //Print("LALA %p\n",critPairs->getFirst());
262                //sleep(5);
263            }
264            else {
265                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, 
266                                newElement->getLPoly(), u2, temp->getLPoly(), testedRule);                   
267                //Print("erstes groesser\n");
268                critPairs->insert(cp);
269                //Print("LALA %p\n",critPairs->getFirst());
270                //sleep(5);
271            }
272        }
273        else {
274        }
275       
276        //Print("\n\n");
277        temp    =   temp->getNext();
278    }
279    // for debugging
280    //if(NULL != critPairs) {
281        //critPairs->print();
282        //sleep(5);
283    //}
284    //Print("END CRITPAIRS\n");
285}
286
287
288
289
290
291
292
293/*
294========================================
295Criterion 1, i.e. Faugere's F5 Criterion
296========================================
297*/
298inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) {
299    // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
300        int idx =   l->getIndex();
301    int i;
302    if(idx == 1) {
303        //Print("HIER\n");
304        return false;
305    }
306    else {
307        LNode* testNode =   gPrev->getFirst();
308        // save the monom t1*label_term(l) as it is tested various times in the following
309        poly u1 = ppMult_qq(t,l->getTerm());
310        //Print("------------------------------IN CRITERION 1-----------------------------------------\n");
311        //Print("TESTED ELEMENT: ");
312        //pWrite(l->getPoly());
313        //pWrite(l->getTerm());
314        //pWrite(ppMult_qq(t,l->getTerm()));
315        //Print("%d\n\n",l->getIndex());
316        while(testNode->getIndex() < idx) { // && NULL != testNode->getLPoly()) {
317            //pWrite(testNode->getPoly());
318            //Print("%d\n",testNode->getIndex());
319            if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
320                //Print("Criterion 1 NOT passed!\n");
321                return true;
322            }
323            //pWrite(testNode->getNext()->getPoly());
324            testNode    =   testNode->getNext();
325        }
326        /*
327        ideal testId    =   idInit(idx-1,1);
328        for(i=0;i<idx-1;i++) {
329            testId->m[i]  =   pHead(testNode->getPoly());
330            testNode        =   testNode->getNext();
331        }
332        poly temp   =   kNF(testId,currQuotient,u1);
333        //pWrite(temp);
334        for(i=0;i<IDELEMS(testId);i++) {
335            testId->m[i]    =   NULL;
336        }
337        idDelete(&testId);
338        if(NULL == temp) {
339            //if(l->getIndex() != gPrev->getFirst()->getIndex()) {
340            //    Print("----------------------------Criterion1 not passed----------------------------------\n");
341            //}
342            return true;
343        }
344        */
345        return false;
346    }
347}
348
349
350
351/*
352=====================================
353Criterion 2, i.e. Rewritten Criterion
354=====================================
355*/
356inline bool criterion2(int idx, poly t, LNode* l, RList* rules, RTagList* rTag) {
357    //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n");
358    /* 
359    Print("RULES: \n");
360        RNode* tempR    =   rules->getFirst();
361        Print("%p\n",tempR);
362        int i   = 1;
363        while(NULL != tempR) {
364            Print("ADDRESS OF %d RNODE: %p\n",i,tempR);
365            Print("ADDRESS OF RULE: %p\n",tempR->getRule());
366            pWrite(tempR->getRuleTerm());
367            Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm());
368            Print("%d\n\n",tempR->getRuleIndex());
369            tempR   =   tempR->getNext();
370            i++;
371        }
372        //Print("TESTED ELEMENT: ");
373        //pWrite(l->getPoly());
374        //pWrite(l->getTerm());
375        //pWrite(ppMult_qq(t,l->getTerm()));
376        //Print("%d\n\n",l->getIndex());
377      */
378// start at the previously added element to gPrev, as all other elements will have the same index for sure
379    if(idx > l->getIndex()) {
380        return false;
381    }
382   
383    RNode* testNode; // =   new RNode();
384   
385
386    if(NULL == rTag->getFirst()) {
387        if(NULL != rules->getFirst()) {
388            testNode    =   rules->getFirst();
389        }
390        else {
391            return false;
392        }
393    }
394    else {
395
396        if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
397            testNode    =   rules->getFirst();
398        }
399        else {
400       //Print("HIER\n");
401            //Print("DEBUG\n");
402        //Print("L INDEX: %d\n",l->getIndex());
403            /*-------------------------------------
404             * TODO: WHEN INTERREDUCING THE GB THE
405             *       INDEX OF THE PREVIOUS ELEMENTS
406             *       GETS HIGHER!
407             *-----------------------------------*/
408            //testNode    =   rules->getFirst();
409            testNode    =   rTag->get(l->getIndex());
410            if(NULL == testNode) {
411                testNode    =   rules->getFirst();
412            }
413            //Print("TESTNODE ADDRESS: %p\n",testNode);
414        }
415    }
416    //testNode    =   rules->getFirst();
417        // save the monom t1*label_term(l) as it is tested various times in the following
418    poly u1 = ppMult_qq(t,l->getTerm());
419    // first element added to rTag was NULL, check for this
420    //Print("%p\n",testNode->getRule());
421    // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
422    //Print("TESTNODE: %p\n",testNode);
423    //pWrite(testNode->getRuleTerm());
424    if(NULL != testNode ) {   
425        //pWrite(testNode->getRuleTerm());
426    }
427    if(NULL != testNode) {
428        if(testNode->getRule() == l->getRule()) {
429            //Print("%p\n%p\n",testNode->getRule(),l->getRule());
430            //Print("EQUAL\n");
431        }
432        else {
433            //Print("NOT EQUAL\n");
434        }
435    }
436    while(NULL != testNode && testNode->getRule() != l->getRule() 
437          && l->getIndex() == testNode->getRuleIndex()) {
438        //Print("%p\n",testNode);
439        //pWrite(testNode->getRuleTerm());
440        //pWrite(t);
441        //pWrite(l->getTerm());
442        //pWrite(u1);
443        //Print("%d\n",testNode->getRuleIndex());
444        if(pLmDivisibleByNoComp(testNode->getRuleTerm(),u1)) {
445            //Print("-----------------Criterion 2 NOT passed!-----------------------------------\n");
446            //Print("INDEX: %d\n",l->getIndex());
447            pDelete(&u1);
448    //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
449            return true;
450        }
451                testNode    =   testNode->getNext();
452    }
453    //delete testNode;
454    pDelete(&u1);
455    //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n");
456    return false;
457}
458
459
460
461/*
462=================================================================================================================
463Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter
464=================================================================================================================
465*/
466inline bool criterion2(poly t, LPoly* l, RList* rules, Rule* testedRule) {
467    //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n");
468    //Print("LAST RULE TESTED: %p",testedRule);
469    /*
470    Print("RULES: \n");
471        RNode* tempR    =   rules->getFirst();
472        while(NULL != tempR) {
473            pWrite(tempR->getRuleTerm());
474            Print("%d\n\n",tempR->getRuleIndex());
475            tempR   =   tempR->getNext();
476        }
477        //Print("TESTED ELEMENT: ");
478        //pWrite(l->getPoly());
479        //pWrite(l->getTerm());
480        //pWrite(ppMult_qq(t,l->getTerm()));
481        //Print("%d\n\n",l->getIndex());
482    */
483// start at the previously added element to gPrev, as all other elements will have the same index for sure
484        RNode* testNode =   rules->getFirst();
485    // save the monom t1*label_term(l) as it is tested various times in the following
486    poly u1 = ppMult_qq(t,l->getTerm());
487        // first element added to rTag was NULL, check for this
488        while(NULL != testNode && testNode->getRule() != testedRule) {
489        //pWrite(testNode->getRuleTerm());
490        if(pLmDivisibleByNoComp(testNode->getRuleTerm(),u1)) {
491            //Print("--------------------------Criterion 2 NOT passed!------------------------------\n");
492            //Print("INDEX: %d\n",l->getIndex());
493            pDelete(&u1);
494    //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
495            return true;
496        }
497                testNode    =   testNode->getNext();
498    }
499    pDelete(&u1);
500    //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n");
501    return false;
502}
503
504
505
506/*
507==================================
508Computation of S-Polynomials in F5
509==================================
510*/
511void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) { 
512    CNode* temp         =   first;
513    poly sp      =   pInit();
514    //Print("###############################IN SPOLS##############################\n");
515    //first->print();
516
517    while(NULL != temp) {
518        //Print("JA\n");
519        // only if a new rule was added since the last test in subalgorithm criticalPair()
520        //if(rules->getFirst() != rTag->getFirst()) {
521        if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRule())) {
522                // the second component is tested only when it has the actual index, otherwise there is
523                // no new rule to test since the last test in subalgorithm criticalPair()
524                if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) { 
525                    highestDegree   = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()));
526                    //pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
527                }   
528                if(temp->getLp2Index() == temp->getLp1Index()) {
529                    if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRule())) {
530                        // computation of S-polynomial
531                        sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
532                                         ppMult_qq(temp->getT2(),temp->getLp2Poly()));
533                        //Print("BEGIN SPOLY1\n====================\n");
534                        pNorm(sp);
535                        //pWrite(sp);
536                        //Print("END SPOLY1\n====================\n");
537                        if(NULL == sp) {
538                            // as rules consist only of pointers we need to save the labeled
539                            // S-polynomial also of a zero S-polynomial
540                            //zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
541                            // origin of rule can be set NULL as the labeled polynomial
542                            // will never be used again as it is zero => no problems with
543                            // further criterion2() tests and termination conditions
544                            //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
545                                                        reductionsToZero++;
546                        //Print("IN SPOLS 1\n");
547                            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
548                            //Print("RULE ADDED: \n");
549                            //pWrite(rules->getFirst()->getRuleTerm());
550                            // as sp = NULL, delete it
551                            pDelete(&sp);
552                            //Print("HIER\n");
553                        }
554                        else {
555                        //Print("IN SPOLS 2\n");
556                            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
557                            //Print("RULE ADDED: \n");
558                            //pWrite(rules->getFirst()->getRuleTerm()); 
559                            sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
560                        }
561                        // data is saved in sPolyList or zero => delete sp
562                    }
563                }
564                else { // temp->getLp2Index() < temp->getLp1Index()
565                    // computation of S-polynomial
566                    sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
567                                     ppMult_qq(temp->getT2(),temp->getLp2Poly()));
568                    //Print("BEGIN SPOLY2\n====================\n");
569                    pNorm(sp);
570                    //pWrite(sp);
571                    //Print("END SPOLY2\n====================\n");
572                    if(NULL == sp) {
573                        // zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
574                        // origin of rule can be set NULL as the labeled polynomial
575                        // will never be used again as it is zero => no problems with
576                        // further criterion2() tests and termination conditions
577                            //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
578                        reductionsToZero++;
579                        //Print("IN SPOLS 3\n");
580                        rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
581                        //Print("RULE ADDED: \n");
582                        //pWrite(rules->getFirst()->getRuleTerm());
583                        // as sp = NULL, delete it
584                        pDelete(&sp);
585                    }
586                    else {
587                        //Print("IN SPOLS 4\n");
588                        rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
589                        //Print("RULE ADDED: \n");
590                        //pWrite(rules->getFirst()->getRuleTerm());
591                        //Print("%d\n",rules->getFirst()->getRuleIndex());
592                        //Print("%p\n",sPolyList->getFirst());
593                        sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
594                    }
595                }
596            }
597        //}
598        //Print("%p\n",temp);
599        temp    =   temp->getNext();
600        //Print("%p\n",temp);
601        //Print("%p\n",temp->getData());
602        //pWrite(temp->getLp1Poly());
603    }
604    // these critical pairs can be deleted now as they are either useless for further computations or
605    // already saved as an S-polynomial to be reduced in the following
606    delete first;   
607}
608
609
610
611/*
612========================================================================
613reduction including subalgorithm topReduction() using Faugere's criteria
614========================================================================
615*/
616void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, 
617                 ideal gbPrev) { 
618    //Print("##########################################In REDUCTION!########################################\n");
619    // check if sPolyList has any elements
620    // NOTE: due to initialization sPolyList always has a default NULL element
621    LNode* temp = sPolyList->getFirst();
622    while(NULL != temp) {
623        // temp is the first element in the sPolyList which should be reduced
624        // due to earlier sorting this is the element of minimal degree AND
625        // minimal label
626        // delete the above first element from sPolyList, temp will be either reduced to
627        // zero or added to gPrev, but never come back to sPolyList
628        sPolyList->setFirst(temp->getNext());
629        poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
630        if(NULL != tempNF) {
631            pNorm(tempNF);
632            temp->setPoly(tempNF);
633            // try further reductions of temp with polynomials in gPrev
634            // with label index = current label index: this is done such that there
635            // is no label corruption during the reduction process
636            topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev);
637       
638        }
639        else {
640            reductionsToZero++;
641            delete temp;
642        }
643        //if(NULL != temp->getPoly()) {
644        //    criticalPair(gPrev,critPairs,lTag,rTag,rules);
645        //}
646        temp =   sPolyList->getFirst();
647    }
648    //sPolyList->print();
649    //delete sPolyList;
650}   
651
652
653
654/*
655=====================================================================================
656top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
657the same index whereas the labels are taken into account
658=====================================================================================
659*/
660void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CList* critPairs,  RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev) {
661    //Print("##########################################In topREDUCTION!########################################\n");
662    // try l as long as there are reductors found by findReductor()
663    LNode* gPrevRedCheck    =   lTag->getFirstCurrentIdx();
664    LNode* tempRed;
665    poly pOne               =   pOne();
666    do {
667        int timer5  =   initTimer();
668        startTimer();
669        tempRed  =   findReductor(l,gPrevRedCheck,gPrev,rules,lTag,rTag);
670        timer5  =   getTimer();
671        reductionTime   =   reductionTime   +   timer5;
672        // if a reductor for l is found and saved in tempRed
673        if(NULL != tempRed) {
674            // if label of reductor is greater than the label of l we have to built a new element
675            // and add it to sPolyList
676            if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
677                // needed sinc pSub destroys the arguments!
678                //poly temp_poly_l    =   pInit();
679                //temp_poly_l         =   pCopy(l->getPoly());
680                //Print("VORHER: ");
681                //pWrite(tempRed->getPoly());
682                poly temp           =   pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
683                //poly temp   =   ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
684                //Print("NACHHER: ");
685                //pWrite(tempRed->getPoly());
686                //Print("TEMP: ");
687                //pWrite(temp);
688                if(NULL != temp) {
689                    pNorm(temp);
690                    //tempRed->setPoly(temp);
691                    //tempRed->setDel(1);
692                    rules->insert(tempRed->getIndex(),tempRed->getTerm());
693                    LNode* tempRedNew   =   new LNode(tempRed->getTerm(),tempRed->getIndex(),temp,rules->getFirst()->getRule());
694                    //tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
695                    tempRedNew->setDel(1);
696                    sPolyList->insertByLabel(tempRedNew);
697                }
698                else {
699                    pDelete(&temp);
700                    reductionsToZero++;
701                    //delete tempRed;
702                }
703            }
704            // label of reductor is smaller than the label of l, subtract reductor from l and delete the
705            // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
706            // after subtraction
707            else {
708               
709                //poly temp_poly_l    =   pInit();
710                //temp_poly_l         =   pCopy(l->getPoly());
711                poly temp   =   pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly());
712                //poly temp   =   ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly());
713                if(NULL != temp) {
714                    pNorm(temp);
715                    poly tempNF =   kNF(gbPrev,currQuotient,temp); 
716                    pNorm(tempNF);
717                    if(NULL == tempNF) {
718                        reductionsToZero++;
719                        pDelete(&tempNF);
720                        l->setPoly(NULL);
721                        break;
722                    }
723                    l->setPoly(tempNF);
724                   
725                    gPrevRedCheck   =   lTag->getFirstCurrentIdx();
726                }
727                else {
728                    reductionsToZero++;
729                    pDelete(&temp);
730                    l->setPoly(NULL);
731                    break;
732                }
733            }   
734        }
735        else {
736            if(NULL != l->getPoly()) {
737                pNorm(l->getPoly());
738                gPrev->insert(l->getLPoly());
739                criticalPair(gPrev,critPairs,lTag,rTag,rules);
740            }
741            break;
742        }
743    } while(1);
744}
745
746
747/*
748=====================================================================
749subalgorithm to find a possible reductor for the labeled polynomial l
750=====================================================================
751*/
752LNode* findReductor(LNode* l, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag) {
753    // allociation of memory for the possible reductor
754    poly u      =   pOne();
755    poly red;
756    number nOne =   nInit(1);
757    LNode* temp;
758    // head term of actual element such that we do not have to call pHead at each new reductor test
759    poly t      =   pHead(l->getPoly());
760    // if l was already checked use the information in gPrevRedCheck such
761    // that we can start searching for new reducers from this point and
762    // not from the first element of gPrev with the current index
763    temp    =   gPrevRedCheck;
764    // search for reductors until we are at the end of gPrev resp. at the
765    // end of the elements of the current index
766    while(NULL != temp && temp->getIndex() == l->getIndex()) {
767        // does the head of the element of gPrev divides the head of
768        // the to be reduced element?
769        if(pLmDivisibleByNoComp(pHead(temp->getPoly()),t)) {
770            // get all the information needed for the following tests
771            // of the criteria
772            u   =   pDivide(t,pHead(temp->getPoly()));
773            pSetCoeff(u,nOne);
774            red =   ppMult_qq(u,temp->getPoly());
775            pNorm(red);
776            // check if both have the same label
777            if(pLmCmp(u,l->getTerm()) != 0) {
778                // passing criterion2 ?
779                if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) {
780                    // passing criterion1 ?
781                    if(!criterion1(gPrev,u,temp,lTag)) {
782                            gPrevRedCheck   =   temp->getNext();
783                            LNode* redNode  =   new LNode(ppMult_qq(u,temp->getTerm()),temp->getIndex(),red,NULL,NULL);
784                            return redNode;
785                    }
786                }
787            }
788        }
789        temp = temp->getNext();
790    }
791   
792//    delete temp;
793 return NULL;
794}
795
796
797
798/*
799==========================================================================
800MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
801==========================================================================
802*/
803ideal F5main(ideal id, ring r) {
804    int timer   =   initTimer();
805    startTimer();
806    int i,j,k,l;
807    int gbLength;
808    // 1 polynomial for defining initial labels & further tests
809    poly ONE = pOne();
810    poly pOne   =   pOne();
811    number nOne =   nInit(1);
812    // tag the first element of index i-1 for criterion 1
813    LTagList* lTag  =   new LTagList();
814    //Print("LTAG BEGINNING: %p\n",lTag);
815   
816    // DEBUGGING STUFF START
817    //Print("NUMBER: %d\n",r->N);
818   
819    int* ev = new int[r->N +1];
820    int  ev2;
821    for(i=0;i<IDELEMS(id);i++) {
822        pGetExpV(id->m[i],ev);
823        //ev2  =   pGetExp(id->m[i],1);
824        pWrite(id->m[i]);
825        Print("%d\n",ev2);
826        Print("EXP1: %d\n",ev[1]);
827        Print("EXP2: %d\n",ev[2]);
828        Print("EXP3: %d\n\n",ev[3]);
829    }
830    delete ev;
831   
832    /*DEBUGGING STUFF END */
833   
834    // first element in rTag is first element of rules which is NULL RNode,
835    // this must be done due to possible later improvements
836    RList* rules    =   new RList();
837    //Print("RULES FIRST: %p\n",rules->getFirst());
838    //Print("RULES FIRST DATA: %p\n",rules->getFirst()->getRule());
839    RTagList* rTag  =   new RTagList(rules->getFirst());
840    i = 1;
841    /*for(j=0; j<IDELEMS(id); j++) {
842        if(NULL != id->m[j]) {
843            if(pComparePolys(id->m[j],ONE)) {
844                Print("One Polynomial in Input => Computations stopped\n");
845                ideal idNew = idInit(1,1);
846                idNew->m[0] = ONE;
847                return(idNew);
848            }   
849        }
850    }*/ 
851    ideal idNew     =   kInterRed(id); 
852    id              =   idNew;
853    //qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
854    idShow(id);
855    LList* gPrev    =   new LList(ONE, i, id->m[0]);
856    //idShow(id);
857    //Print("%p\n",id->m[0]);
858    //pWrite(id->m[0]);
859    //Print("%p\n",gPrev->getFirst()->getPoly());
860    //pWrite(gPrev->getFirst()->getPoly());
861
862    lTag->insert(gPrev->getFirst());
863    lTag->setFirstCurrentIdx(gPrev->getFirst());
864    // computing the groebner basis of the elements of index < actual index
865    gbLength    =   gPrev->getLength();
866    //Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
867    ideal gbPrev    =   idInit(gbLength,1);
868    // initializing the groebner basis of elements of index < actual index
869    gbPrev->m[0]    =   gPrev->getFirst()->getPoly();
870    //idShow(gbPrev);
871    //idShow(currQuotient);
872    for(i=2; i<=IDELEMS(id); i++) {
873        LNode* gPrevTag =   gPrev->getLast();
874        //Print("Last POlynomial in GPREV: ");
875        //Print("%p\n",gPrevTag);   
876        //pWrite(gPrevTag->getPoly());
877        gPrev   =   F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag);
878        Print("%d\n",gPrev->count(gPrevTag->getNext()));
879        Print("%d\n",gPrev->getLength());
880        //Print("____________________________________ITERATION STEP DONE________________________________________\n");
881       
882        // DEBUGGING STUFF
883        LNode* temp    =   gPrev->getFirst();
884    // computing new groebner basis gbPrev
885        if(gPrev->getLength() > gbLength) {
886            if(i < IDELEMS(id)) {
887                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
888                LNode*  temp =   gPrevTag;
889                int counter =   0;
890                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
891                    temp        =   temp->getNext();
892                    if(0 == temp->getDel()) {
893                        counter++;
894                        gbAdd->m[j] =   temp->getPoly();
895                    }
896                        //if(1 == temp->getDel()) {
897                        //    pWrite(temp->getPoly());
898                        //}
899                }
900                if(counter != gPrev->count(gPrevTag->getNext())) {
901                    Print("----------------------------------WRONG COUNTING---------------------------\n");
902                }
903                    gbPrev          =   idAdd(gbPrev,gbAdd);
904                    //idShow(gbPrev);
905            }
906            else {
907                ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
908                LNode*  temp =   gPrevTag;
909                for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
910                    temp        =   temp->getNext();
911                    gbAdd->m[j] =   temp->getPoly();
912                }
913                gbPrev          =   idAdd(gbPrev,gbAdd);
914            }
915            // interreduction stuff
916            if(i<IDELEMS(id)) {
917                int timer2  =   initTimer();
918                startTimer();
919                ideal tempId    =   kInterRed(gbPrev);
920               
921                //idShow(tempId);
922                gbPrev          =   tempId;
923                timer2  =   getTimer();
924                Print("Timer INTERREDUCTION: %d\n",timer2);
925                //idShow(gbPrev);
926                //qsortDegree(&gbPrev->m[0],&gbPrev->m[IDELEMS(gbPrev)-1]);
927                delete gPrev;
928                //sleep(5);
929                //Print("RULES FIRST NOW1: %p\n",rules->getFirst());
930                //Print("HIER\n");
931                delete rules;
932                //delete rTag;
933                //Print("HIER AUCH\n");
934                //Print("%p\n",rules->getFirst());
935                gPrev    =   new LList(pOne,1,gbPrev->m[0]);
936                gPrev->insert(pOne,1,gbPrev->m[1]);
937                //poly tempPoly = pInit();
938                //pLcm(pHead(gbPrev->m[0]),pHead(gbPrev->m[1]),tempPoly);
939                //tempPoly    =   pDivide(tempPoly,pOne());
940                //pSetCoeff(tempPoly,nOne);
941                rules    =   new RList();
942                rTag     =   new RTagList(rules->getFirst());
943               
944                //Print("%p\n",rules->getFirst());
945                //pWrite(tempPoly);
946                //rules->insert(2,tempPoly);
947                //rTag->insert(rules->getFirst());
948                //Print("%p\n",rules->getFirst());
949                //Print("%p\n",rTag->getFirst());
950                //Print("%p\n",rules->getFirst());
951                //Print("%p\n",rules->getFirst()->getNext()->getNext());
952                //Print("HIERLALA\n");
953            //pWrite(rules->getFirst()->getRuleTerm());
954           // Print("RULES FIRST NOW2: %p\n",rules->getFirst());
955                for(k=2; k<IDELEMS(gbPrev); k++) {
956                    gPrev->insert(pOne,k+1,gbPrev->m[k]);
957                    for(l=0; l<k; l++) {
958                        //pWrite(gbPrev->m[k]);
959                        //pWrite(gbPrev->m[l]);
960                        //poly tempPoly2  =   pOne();
961                        //pLcm(pHead(gbPrev->m[k]),pHead(gbPrev->m[l]),tempPoly2);
962                        //tempPoly2   =   pDivide(tempPoly2,pOne());
963                        //pSetCoeff(tempPoly2,nOne);
964                        //pWrite(tempPoly2);
965                        //rules->insert(k+1,tempPoly2);
966                    }
967                    //rTag->insert(rules->getFirst());
968                }
969            }
970            gbLength    =   gPrev->getLength(); 
971            //Print("HIER\n");
972        }
973        //gPrev->print();
974        //int anzahl  =   1;
975        //while(NULL != temp) {
976        //    Print("%d. Element: ",anzahl);
977        //    pWrite(temp->getPoly());
978        //    Print("\n");
979        //    temp    =   temp->getNext();
980        //    anzahl++;
981        //}
982        //sleep(5);
983        //Print("GROEBNER BASIS:\n====================================================\n");
984        //idShow(gbPrev);
985        //Print("===================================================\n");
986        //Print("JA\n");
987        Print("LENGTH OF GPREV: %d\n",gPrev->getLength());
988    } 
989        //idShow(gbPrev);
990    Print("\n\nNumber of zero-reductions:  %d\n",reductionsToZero);
991    timer   =   getTimer();
992    Print("Highest Degree during computations: %d\n",highestDegree);
993    Print("Time for computations: %d/10000 seconds\n",timer);
994    //LNode* temp    =   gPrev->getFirst();
995    //while(NULL != temp) {
996    //    pWrite(temp->getPoly());
997    //    temp    =   temp->getNext();
998    // }
999    //gPrev->print();
1000    //delete lTag;
1001    //delete rTag;
1002    //delete gPrev;
1003    reductionTime   =   0;
1004    spolsTime       =   0;
1005    return(gbPrev);
1006
1007
1008}
1009
1010#endif
Note: See TracBrowser for help on using the repository browser.