# source:git/kernel/f5gb.cc@70c15e

spielwiese
Last change on this file since 70c15e was 70c15e, checked in by Christian Eder, 15 years ago
problem in cyclic_n(4) solved git-svn-id: file:///usr/local/Singular/svn/trunk@11441 2c84dea3-7e68-4137-9b89-c4e89433aadc
• Property mode set to `100644`
File size: 31.0 KB
Line
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* \$Id: f5gb.cc,v 1.32 2009-02-22 18:58:36 ederc Exp \$ */
5/*
6* ABSTRACT: f5gb interface
7*/
8#include "mod2.h"
9#ifdef HAVE_F5
10#include "kutil.h"
11#include "structs.h"
12#include "omalloc.h"
13#include "polys.h"
14#include "p_polys.h"
15#include "ideals.h"
16#include "febase.h"
17#include "kstd1.h"
18#include "khstd.h"
19#include "kbuckets.h"
20#include "weight.h"
21#include "intvec.h"
22#include "pInline1.h"
23#include "f5gb.h"
24#include "f5data.h"
25#include "f5lists.h"
26
27int reductionsToZero   =  0;
28
29/*
30====================================================================
31sorting ideals by decreasing total degree "left" and "right" are the
32pointer of the first and last polynomial in the considered ideal
33====================================================================
34*/
35void qsortDegree(poly* left, poly* right) {
36    poly* ptr1 = left;
37    poly* ptr2 = right;
38    poly p1,p2;
39    p2 = *(left + (right - left >> 1));
40    do {
41            while(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)) {
42                    ptr1++;
43            }
44            while(pTotaldegree(*ptr2, currRing) > pTotaldegree(p2,currRing)) {
45                    ptr2--;
46            }
47            if(ptr1 > ptr2) {
48                    break;
49            }
50            p1    = *ptr1;
51            *ptr1 = *ptr2;
52            *ptr2 = p1;
53    } while(++ptr1 <= --ptr2);
54
55    if(left < ptr2) {
56            qsortDegree(left,ptr2);
57    }
58    if(ptr1 < right) {
59            qsortDegree(ptr1,right);
60    }
61}
62
63
64
65/*
66==================================================
67computes incrementally gbs of subsets of the input
68gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
69==================================================
70*/
71LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag) {
72    int j;
73    //Print("%p\n",gPrev->getFirst());
74    //pWrite(gPrev->getFirst()->getPoly());
75    gPrev->insert(ONE,i,f_i);
76    // tag the first element in gPrev of the current index for findReductor()
77    lTag->setFirstCurrentIdx(gPrev->getLast());
78    //Print("1st gPrev: ");
79    //pWrite(gPrev->getFirst()->getPoly());
80    //Print("2nd gPrev: ");
81    //pWrite(gPrev->getFirst()->getNext()->getPoly());
82    //pWrite(gPrev->getFirst()->getNext()->getPoly());
83    CList* critPairs        =   new CList();
84    CNode* critPairsMinDeg  =   new CNode();
85    // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
86    // in the list critPairs
87    criticalPair(gPrev, critPairs, lTag, rTag, rules);
88    static LList* sPolyList        =   new LList();
89    // labeled polynomials which have passed reduction() and have to be added to list gPrev
90    static LList* completed        =   new LList();
91    // the reduced labeled polynomials which are returned from subalgorithm reduction()
92    static LList* reducedLPolys     =   new LList();
93    // while there are critical pairs to be further checked and deleted/computed
94    while(NULL != critPairs->getFirst()->getData()) {
95        // critPairs->getMinDeg() deletes the first elements of minimal degree from
96        // critPairs, thus the while loop is not infinite.
97        critPairsMinDeg =   critPairs->getMinDeg();
98        // adds all to be reduced S-polynomials in the list sPolyList and adds
99        // the corresponding rules to the list rules
100        // NOTE: inside there is a second check of criterion 2 if new rules are
102        computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
103
104        // DEBUG STUFF FOR SPOLYLIST
105        LNode* temp     =   sPolyList->getFirst();
106        while(NULL != temp && NULL != temp->getLPoly()) {
107            Print("Spolylist element: ");
108            pWrite(temp->getPoly());
109            temp    =   temp->getNext();
110        }
111        // reduction process of new S-polynomials and also adds new critical pairs to critPairs
112        reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
113
114        // DEBUG STUFF FOR GPREV
115        temp    =   gPrev->getFirst();
116        Print("\n\n");
117        while(NULL != temp) {
118            pWrite(temp->getPoly());
119            temp    =   temp->getNext();
120        }
121        //sleep(10);
122
123    }
124    Print("REDUCTION DONE\n");
125    Print("%p\n",rules->getFirst());
126    Print("%p\n",rTag->getFirst());
127    if(rules->getFirst() != rTag->getFirst()) {
128        Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n");
129        rTag->insert(rules->getFirst());
130    }
131    else {
132        Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
133    }
134    lTag->insert(lTag->getFirstCurrentIdx());
135    Print("LTAG LIST: \n");
136    LNode* tempTag = lTag->getFirst();
137    Print("INDEX: %d\n",tempTag->getIndex());
138    pWrite(tempTag->getPoly());
139    Print("COMPLETED FIRST IN F5INC: \n");
140    //Print("1st gPrev: ");
141    //pWrite(gPrev->getFirst()->getPoly());
142    //Print("2nd gPrev: ");
143    //pWrite(gPrev->getFirst()->getNext()->getPoly());
144    //Print("3rd gPrev: ");
145    //pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly());
146
147
148    return gPrev;
149}
150
151
152
153/*
154================================================================
155computes a list of critical pairs for the next reduction process
156first element in gPrev is always the newest element which must
157build critical pairs with all other elements in gPrev
158================================================================
159*/
160void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
161    // initialization for usage in pLcm()
162    number nOne         =   nInit(1);
163    LNode* newElement   =   gPrev->getLast();
164    LNode* temp         =   gPrev->getFirst();
165    poly u1             =   pOne();
166    poly u2             =   pOne();
167    poly lcm            =   pOne();
169    Rule* testedRule    =   rules->getFirst()->getRule();
170    // computation of critical pairs
171    while( gPrev->getLast() != temp) {
172        //pWrite( *(gPrev->getFirst()->getPoly()) );
173       // pWrite( *(l->getPoly()) );
174        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
175        pSetCoeff(lcm,nOne);
176        // computing factors u2 for new labels
177        u1 = pDivide(lcm,t);
178        pSetCoeff(u1,nOne);
180        pSetCoeff(u2,nOne);
181        Print("IN CRITPAIRS\n");
182        pWrite(u1);
183        Print("1st ELEMENT: ");
184        pWrite(newElement->getPoly());
185        Print("2nd ELEMENT: ");
186        pWrite(temp->getPoly());
187        // testing both new labels by the F5 Criterion
188        if(!criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag) &&
189           !criterion2(u1, newElement, rules, rTag) && !criterion2(u2, temp, rules, rTag)) {
190            // if they pass the test, add them to CList critPairs, having the LPoly with greater
191            // label as first element in the CPair
192            if(newElement->getIndex() == temp->getIndex() &&
193            -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
194                Print("zweites groesser\n");
195                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
196                                temp->getLPoly(), u1, newElement->getLPoly(), testedRule);
197                critPairs->insert(cp);
198            }
199            else {
200                Print("erstes groesser\n");
201                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
202                                newElement->getLPoly(), u2, temp->getLPoly(), testedRule);
203                critPairs->insert(cp);
204            }
205        }
206        else {
207        }
208
209        Print("\n\n");
210        temp    =   temp->getNext();
211    }
212    // for debugging
213    if(NULL != critPairs) {
214        critPairs->print();
215    }
216}
217
218
219
220
221/*
222========================================
223Criterion 1, i.e. Faugere's F5 Criterion
224========================================
225*/
226bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) {
227    // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
228        int idx =   l->getIndex();
229    if(idx == 1) {
230        return false;
231    }
232    else {
233        LNode* testNode =   gPrev->getFirst();
234        // save the monom t1*label_term(l) as it is tested various times in the following
235        poly u1 = ppMult_qq(t,l->getTerm());
236        Print("------------------------------IN CRITERION 1-----------------------------------------\n");
237        Print("TESTED ELEMENT: ");
238        pWrite(l->getPoly());
239        pWrite(ppMult_qq(t,l->getTerm()));
240        Print("%d\n\n",l->getIndex());
241        while(testNode->getIndex() < idx && NULL != testNode->getLPoly()) {
242            pWrite(testNode->getPoly());
243            Print("%d\n",testNode->getIndex());
244            if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
245                Print("Criterion 1 NOT passed!\n");
246                return true;
247            }
248            pWrite(testNode->getNext()->getPoly());
249            testNode    =   testNode->getNext();
250        }
251        return false;
252    }
253}
254
255
256
257/*
258=====================================
259Criterion 2, i.e. Rewritten Criterion
260=====================================
261*/
262bool criterion2(poly t, LNode* l, RList* rules, RTagList* rTag) {
263    Print("------------------------------IN CRITERION 2-----------------------------------------\n");
264        Print("RULES: \n");
265        RNode* tempR    =   rules->getFirst();
266        while(NULL != tempR->getRule()) {
268            pWrite(tempR->getRuleTerm());
270            Print("%d\n\n",tempR->getRuleIndex());
271            tempR   =   tempR->getNext();
272        }
273Print("TESTED ELEMENT: ");
274        pWrite(l->getPoly());
275        pWrite(ppMult_qq(t,l->getTerm()));
276        Print("%d\n\n",l->getIndex());
277// start at the previously added element to gPrev, as all other elements will have the same index for sure
278    RNode* testNode =   new RNode();
279    if(NULL == rTag->getFirst()->getRule()) {
280        testNode    =   rules->getFirst();
281    }
282    else {
283        if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
284            testNode    =   rules->getFirst();
285        }
286        else {
287        Print("DEBUG\n");
288        Print("L INDEX: %d\n",l->getIndex());
289            testNode    =   rTag->get(l->getIndex());
291        }
292    }
293        // save the monom t1*label_term(l) as it is tested various times in the following
294    poly u1 = ppMult_qq(t,l->getTerm());
295    // first element added to rTag was NULL, check for this
296    //Print("%p\n",testNode->getRule());
297    // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
298    if(NULL != testNode && NULL != testNode->getRule()) {
299        pWrite(testNode->getRuleTerm());
300    }
301    if(NULL != testNode) {
302        if(testNode->getRule() == l->getRule()) {
303            Print("%p\n%p\n",testNode->getRule(),l->getRule());
304            Print("EQUAL\n");
305        }
306        else {
307            Print("NOT EQUAL\n");
308        }
309    }
310    while(NULL != testNode && NULL != testNode->getRule() && testNode->getRule() != l->getRule()
311          && l->getIndex() == testNode->getRuleIndex()) {
312        pWrite(testNode->getRuleTerm());
313                if(pLmDivisibleBy(testNode->getRuleTerm(),u1)) {
314            Print("Criterion 2 NOT passed!\n");
315            pDelete(&u1);
316            return true;
317        }
318                testNode    =   testNode->getNext();
319    }
320    pDelete(&u1);
321    return false;
322}
323
324
325
326/*
327=================================================================================================================
328Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter
329=================================================================================================================
330*/
331bool criterion2(poly t, LPoly* l, RList* rules, Rule* testedRule) {
332    Print("------------------------------IN CRITERION 2-----------------------------------------\n");
333    Print("LAST RULE TESTED: %p",testedRule);
334    Print("RULES: \n");
335        RNode* tempR    =   rules->getFirst();
336        while(NULL != tempR->getRule()) {
337            pWrite(tempR->getRuleTerm());
338            Print("%d\n\n",tempR->getRuleIndex());
339            tempR   =   tempR->getNext();
340        }
341        Print("TESTED ELEMENT: ");
342        pWrite(l->getPoly());
343        pWrite(ppMult_qq(t,l->getTerm()));
344        Print("%d\n\n",l->getIndex());
345// start at the previously added element to gPrev, as all other elements will have the same index for sure
346        RNode* testNode =   rules->getFirst();
347    // save the monom t1*label_term(l) as it is tested various times in the following
348    poly u1 = ppMult_qq(t,l->getTerm());
349        // first element added to rTag was NULL, check for this
350        while(NULL != testNode->getRule() && testNode->getRule() != testedRule) {
351        pWrite(testNode->getRuleTerm());
352        if(pLmDivisibleBy(testNode->getRuleTerm(),u1)) {
353            Print("Criterion 2 NOT passed!\n");
354            pDelete(&u1);
355            return true;
356        }
357                testNode    =   testNode->getNext();
358    }
359    pDelete(&u1);
360    return false;
361}
362
363
364
365/*
366==================================
367Computation of S-Polynomials in F5
368==================================
369*/
370void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) {
371    CNode* temp         =   first;
372    poly sp      =   pInit();
373    //Print("###############################IN SPOLS##############################\n");
374    while(NULL != temp->getData()) {
375        // only if a new rule was added since the last test in subalgorithm criticalPair()
376        //if(rules->getFirst() != rTag->getFirst()) {
378                // the second component is tested only when it has the actual index, otherwise there is
379                // no new rule to test since the last test in subalgorithm criticalPair()
380                if(temp->getLp2Index() == temp->getLp1Index()) {
382                        // computation of S-polynomial
383                        sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
384                                         ppMult_qq(temp->getT2(),temp->getLp2Poly()));
385                        Print("BEGIN SPOLY1\n====================\n");
386                        pNorm(sp);
387                        pWrite(sp);
388                        Print("END SPOLY1\n====================\n");
389                        if(NULL == sp) {
390                            // as rules consist only of pointers we need to save the labeled
391                            // S-polynomial also of a zero S-polynomial
393                            // origin of rule can be set NULL as the labeled polynomial
394                            // will never be used again as it is zero => no problems with
395                            // further criterion2() tests and termination conditions
396                            Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
397                                                        reductionsToZero++;
398                            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
400                            pWrite(rules->getFirst()->getRuleTerm());
401                            // as sp = NULL, delete it
402                            pDelete(&sp);
403                            Print("HIER\n");
404                        }
405                        else {
406                            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
408                            pWrite(rules->getFirst()->getRuleTerm());
409                            sPolyList->insertSP(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
410                        }
411                        // data is saved in sPolyList or zero => delete sp
412                    }
413                }
414                else { // temp->getLp2Index() < temp->getLp1Index()
415                    // computation of S-polynomial
416                    sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
417                                     ppMult_qq(temp->getT2(),temp->getLp2Poly()));
418                    Print("BEGIN SPOLY2\n====================\n");
419                    pNorm(sp);
420                    pWrite(sp);
421                    Print("END SPOLY2\n====================\n");
422                    if(NULL == sp) {
424                        // origin of rule can be set NULL as the labeled polynomial
425                        // will never be used again as it is zero => no problems with
426                        // further criterion2() tests and termination conditions
427                            Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
428                        reductionsToZero++;
429                        rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
431                        pWrite(rules->getFirst()->getRuleTerm());
432                        // as sp = NULL, delete it
433                        pDelete(&sp);
434                    }
435                    else {
436                        rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
438                        pWrite(rules->getFirst()->getRuleTerm());
439                        Print("%d\n",rules->getFirst()->getRuleIndex());
440                        Print("%p\n",sPolyList->getFirst());
441                        sPolyList->insertSP(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
442                    }
443                    // data is saved in sPolyList or zero => delete sp
444                }
445            }
446        //}
447        temp    =   temp->getNext();
448    }
449    // these critical pairs can be deleted now as they are either useless for further computations or
450    // already saved as an S-polynomial to be reduced in the following
451    delete first;
452}
453
454
455
456/*
457========================================================================
458reduction including subalgorithm topReduction() using Faugere's criteria
459========================================================================
460*/
461void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
462                 ideal gbPrev) {
463    Print("##########################################In REDUCTION!########################################\n");
464    // check if sPolyList has any elements
465    // NOTE: due to initialization sPolyList always has a default NULL element
466    while(sPolyList->getLength() > 0) {
467        Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
468        if(sPolyList->getLength() > 1) {
469        Print("%p\n",sPolyList->getFirst());
470        Print("%p\n",sPolyList->getFirst()->getLPoly());
471        Print("%p\n",sPolyList->getFirst()->getNext());
472        Print("%p\n",sPolyList->getFirst()->getNext()->getLPoly());
473        Print("%p\n",sPolyList->getFirst());
474        }
475        sPolyList->print();
476        // temp is the first element in the sPolyList which should be reduced
477        // due to earlier sorting this is the element of minimal degree AND
478        // minimal label
479        LNode* temp =   sPolyList->getFirst();
480        pWrite(temp->getPoly());
481        // delete the above first element from sPolyList, temp will be either reduced to
482        // zero or added to gPrev, but never come back to sPolyList
483        sPolyList->setFirst(temp->getNext());
484        Print("HALLO %p\n",temp->getPoly());
485        Print("%p\n",temp->getPoly());
486        pWrite(temp->getPoly());
487        idShow(gbPrev);
488        poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
489        pNorm(tempNF);
490        Print("LENGTH: %d\n",sPolyList->getLength());
491        pWrite(tempNF);
492        pWrite(temp->getPoly());
493        if(NULL != tempNF) {
494            // write the reduced polynomial in temp
495            temp->setPoly(tempNF);
496            // try further reductions of temp with polynomials in gPrev
497            // with label index = current label index: this is done such that there
498            // is no label corruption during the reduction process
499            topReduction(temp,sPolyList,gPrev,rules,lTag,rTag);
500
501        }
502        if(NULL != temp->getPoly()) {
503            //CList* newCritPairs = new CList;
504            Print("##################IN CRITPAIRS IN REDUCTION#####################\n");
505            criticalPair(gPrev,critPairs,lTag,rTag,rules);
506        }
507        else {
508            //delete temp;
509            LNode* tempLoop = gPrev->getFirst();
510            Print("AUSGABE IN REDUCTION:\n");
511            while(NULL != tempLoop) {
512                pWrite(tempLoop->getPoly());
513                tempLoop = tempLoop->getNext();
514            }
515            //sleep(10);
516        }
517    }
518}
519
520
521
522/*
523=====================================================================================
524top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
525the same index whereas the labels are taken into account
526=====================================================================================
527*/
528void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag) {
529    Print("##########################################In topREDUCTION!########################################\n");
530    // try l as long as there are reductors found by findReductor()
531    do {
532        LNode* tempRed  =   new LNode();
533        tempRed  =   findReductor(l,gPrev,rules,lTag,rTag);
534        Print("--------------------------------HIER DEBUG 2----------------------------------\n");
535        // if a reductor for l is found and saved in tempRed
536        if(NULL != tempRed) {
537            // if label of reductor is greater than the label of l we have to built a new element
538            // and add it to sPolyList
539            if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
540                poly temp   =   pSub(tempRed->getPoly(),l->getPoly());
541                Print("OH JE\n");
542                pWrite(temp);
543                if(NULL != temp) {
544                    pNorm(temp);
545                    tempRed->setPoly(temp);
546                    // for debugging
547                    pWrite(tempRed->getPoly());
549                    rules->insert(tempRed->getIndex(),tempRed->getTerm());
550
551                    tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
552                    Print("%p\n",sPolyList->getFirst());
553                    Print("%p\n",sPolyList->getFirst()->getLPoly());
554                    Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
555                    sPolyList->insertByLabel(tempRed);
556                }
557                else {
558                    pDelete(&temp);
559                    reductionsToZero++;
561        Print("wieder hier2\n");
562                    rules->insert(tempRed->getIndex(),tempRed->getTerm());
563                    delete tempRed;
564                }
565            }
566            // label of reductor is smaller than the label of l, subtract reductor from l and delete the
567            // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
568            // after subtraction
569            else {
570                poly temp   =   pSub(l->getPoly(),tempRed->getPoly());
571                pWrite(temp);
572                if(NULL != temp) {
573                    pNorm(temp);
574                    l->setPoly(temp);
575                    l->setGPrevRedCheck(NULL);
576                }
577                else {
578                    Print("ZERO REDUCTION!\n");
579                    reductionsToZero++;
580                    pDelete(&temp);
581                    l->setPoly(NULL);
582                    pWrite(gPrev->getLast()->getPoly());
583                    break;
584                }
585            }
586        }
587        else {
588            if(NULL != l->getPoly()) {
589                Print("ADDED TO GPREV IN TOPREDUCTION: ");
590                pWrite(l->getPoly());
591                pWrite(l->getTerm());
592                Print("INDEX: %d\n", l->getIndex());
593                //sleep(10);
594                gPrev->insert(l->getLPoly());
595                Print("GPREV: \n");
596                LNode* tempLoop = gPrev->getFirst();
597                while(NULL != tempLoop) {
598                    Print("HERE\n");
599                    pWrite(tempLoop->getPoly());
600                    tempLoop = tempLoop->getNext();
601                }
602            }
603            break;
604        }
605    } while(1);
606}
607
608
609/*
610=====================================================================
611subalgorithm to find a possible reductor for the labeled polynomial l
612=====================================================================
613*/
614LNode* findReductor(LNode* l, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag) {
615    // allociation of memory for the possible reductor
616    Print("IN FIND REDUCTOR\n");
617    poly u      =   pOne();
618    poly red    =   pOne();
619    number nOne =   nInit(1);
620    LNode* temp =   new LNode();
621    // head term of actual element such that we do not have to call pHead at each new reductor test
623    // if l was already checked use the information in gPrevRedCheck such
624    // that we can start searching for new reducers from this point and
625    // not from the first element of gPrev with the current index
626    if(NULL != l->getGPrevRedCheck()) {
627        temp    =   l->getGPrevRedCheck()->getNext();
628    }
629    // no reductors were searched for l before, thus start at the first
630    // element of gPrev with the current index, tagged by lTag
631    else {
632        temp    =   lTag->getFirstCurrentIdx();
633    }
634    // search for reductors until we are at the end of gPrev resp. at the
635    // end of the elements of the current index
636    while(NULL != temp && temp->getIndex() == l->getIndex()) {
637        // does the head of the element of gPrev divides the head of
638        // the to be reduced element?
639        if(pLmDivisibleByNoComp(temp->getPoly(),t)) {
640            // get all the information needed for the following tests
641            // of the criteria
643            pSetCoeff(u,nOne);
644            red =   ppMult_qq(u,temp->getPoly());
645            pNorm(red);
646            u   =   ppMult_qq(u,temp->getTerm());
647            pSetCoeff(u,nOne);
648            // check if both have the same label
649            if(pLmCmp(u,l->getTerm()) != 0) {
650                // passing criterion2 ?
651                if(!criterion2(u,temp,rules,rTag)) {
652                    // passing criterion1 ?
653                    if(!criterion1(gPrev,u,temp,lTag)) {
654                            Print("HIER DEBUG\n");
655                            l->setGPrevRedCheck(temp);
656                            LNode* redNode  =   new LNode(u,temp->getIndex(),red,NULL,NULL);
657                            return redNode;
658                    }
659                }
660            }
661        }
662        temp = temp->getNext();
663    }
664
665//    delete temp;
666   Print("1st gPrev: ");
667    pWrite(gPrev->getFirst()->getPoly());
668    Print("2nd gPrev: ");
669    pWrite(gPrev->getFirst()->getNext()->getPoly());
670 return NULL;
671}
672
673
674
675/*
676==========================================================================
677MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
678==========================================================================
679*/
680ideal F5main(ideal id, ring r) {
681    int i,j;
682    int gbLength;
683    // 1 polynomial for defining initial labels & further tests
684    poly ONE = pOne();
685    // tag the first element of index i-1 for criterion 1
686    LTagList* lTag  =   new LTagList();
687    Print("LTAG BEGINNING: %p\n",lTag->getFirst());
688
689    // first element in rTag is first element of rules which is NULL RNode,
690    // this must be done due to possible later improvements
691    RList* rules    =   new RList();
692    RTagList* rTag  =   new RTagList(rules->getFirst());
693    i = 1;
694    for(j=0; j<IDELEMS(id); j++) {
695        if(NULL != id->m[j]) {
696            if(pComparePolys(id->m[j],ONE)) {
697                Print("One Polynomial in Input => Computations stopped\n");
698                ideal idNew = idInit(1,1);
699                idNew->m[0] = ONE;
700                return(idNew);
701            }
702        }
703    }
704    LList* gPrev    =   new LList(ONE, i, id->m[0]);
705    Print("%p\n",id->m[0]);
706    pWrite(id->m[0]);
707    Print("%p\n",gPrev->getFirst()->getPoly());
708    pWrite(gPrev->getFirst()->getPoly());
709
710    lTag->insert(gPrev->getFirst());
711    lTag->setFirstCurrentIdx(gPrev->getFirst());
712    // computing the groebner basis of the elements of index < actual index
713    gbLength    =   gPrev->getLength();
714    Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
715    ideal gbPrev    =   idInit(gbLength,1);
716    // initializing the groebner basis of elements of index < actual index
717    gbPrev->m[0]    =   gPrev->getFirst()->getPoly();
718    idShow(gbPrev);
719    idShow(currQuotient);
720
721    for(i=2; i<=IDELEMS(id); i++) {
722        LNode* gPrevTag =   gPrev->getLast();
723        Print("Last POlynomial in GPREV: ");
724        Print("%p\n",gPrevTag);
725        pWrite(gPrevTag->getPoly());
726        gPrev   =   F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag);
727        // DEBUGGING STUFF
728        LNode* temp    =   gPrev->getFirst();
729    while(NULL != temp) {
730        pWrite(temp->getPoly());
731        temp    =   temp->getNext();
732    }// comuting new groebner basis gbPrev
733        if(gPrev->getLength() > gbLength) {
735        LNode*  temp    =   gPrevTag;
736        Print("%p\n",gPrevTag);
737        Print("%p\n",gPrev->getLast());
738        pWrite(temp->getPoly());
739        Print("LENGTH OF GPREV LIST: %d\n",gPrev->getLength());
740        Print("%d\n",gbLength);
741        for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
742            Print("YES\n");
743            temp        =   temp->getNext();
745            pWrite(temp->getPoly());
746        }
747        gbLength    =   gPrev->getLength();
749        }
750        Print("GROEBNER BASIS:\n====================================================\n");
751        idShow(gbPrev);
752        Print("===================================================\n");
753        Print("JA\n");
754    }
755    Print("\n\nNumber of zero-reductions:  %d\n",reductionsToZero);
756    LNode* temp    =   gPrev->getFirst();
757    while(NULL != temp) {
758        pWrite(temp->getPoly());
759        temp    =   temp->getNext();
760    }
761    return(gbPrev);
762
763
764}
765
766#endif
Note: See TracBrowser for help on using the repository browser.