source: git/kernel/f5gb.cc @ 61d32c

spielwiese
Last change on this file since 61d32c was 61d32c, checked in by Christian Eder, 15 years ago
still searching errors in reduction() git-svn-id: file:///usr/local/Singular/svn/trunk@11400 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 26.7 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: f5gb.cc,v 1.28 2009-02-15 20:33:56 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    Print("1st gPrev: ");
77    pWrite(gPrev->getFirst()->getPoly());
78    Print("2nd gPrev: ");
79    pWrite(gPrev->getFirst()->getNext()->getPoly());
80    //pWrite(gPrev->getFirst()->getNext()->getPoly());   
81    CList* critPairs        =   new CList();
82    CNode* critPairsMinDeg  =   new CNode();   
83    LNode* sPolys           =   new LNode();
84    // computation of critical pairs with checking of criterion 1 and criterion 2
85    critPairs               =   criticalPair(gPrev, critPairs, lTag, rTag, rules);
86    static LList* sPolyList        =   new LList();
87    // labeled polynomials which have passed reduction() and have to be added to list gPrev
88    static LList* completed        =   new LList();
89    Print("_____________________________________________________________________________%p\n",completed->getFirst()->getLPoly());
90    // the reduced labeled polynomials which are returned from subalgorithm reduction()
91    static LList* reducedLPolys     =   new LList();
92    // while there are critical pairs to be further checked and deleted/computed
93    while(NULL != critPairs->getFirst()->getData()) { 
94        // critPairs->getMinDeg() deletes the first elements of minimal degree from
95        // critPairs, thus the while loop is not infinite.
96        critPairsMinDeg =   critPairs->getMinDeg();
97        // adds all to be reduced S-polynomials in the list sPolyList and adds
98        // the corresponding rules to the list rules
99        // NOTE: inside there is a second check of criterion 2 if new rules are
100        // added
101        computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
102       
103        // DEBUG STUFF FOR SPOLYLIST
104        LNode* temp     =   sPolyList->getFirst();
105        while(NULL != temp && NULL != temp->getLPoly()) {
106            Print("Spolylist element: ");
107            pWrite(temp->getPoly());
108            temp    =   temp->getNext();
109        } 
110        reducedLPolys   =   reduction(sPolyList, completed, gPrev, rules, lTag, rTag, gbPrev);
111    }
112    Print("HIER123\n");
113    Print("%p\n",rules->getFirst());
114    Print("%p\n",rTag->getFirst());
115    if(rules->getFirst() != rTag->getFirst()) {
116        Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n");
117        rTag->insert(rules->getFirst());
118    }
119    else {
120        Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
121    }
122    lTag->insert(gPrev->getFirst());
123    Print("COMPLETED FIRST IN F5INC: \n");
124    pWrite(completed->getFirst()->getPoly());
125    return gPrev;
126}
127
128
129
130/*
131================================================================
132computes a list of critical pairs for the next reduction process
133first element in gPrev is always the newest element which must
134build critical pairs with all other elements in gPrev
135================================================================
136*/
137CList* criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
138    // initialization for usage in pLcm()
139    number nOne         =   nInit(1);
140    LNode* first        =   gPrev->getFirst();
141    LNode* l            =   first->getNext();
142    poly* u1            =   new poly(pInit());
143    poly* u2            =   new poly(pInit());
144    poly* lcm           =   new poly(pInit());
145    poly t              =   pHead(first->getPoly());
146    // computation of critical pairs
147    while( NULL != l) {
148        //pWrite( *(gPrev->getFirst()->getPoly()) );
149        //pWrite( *(l->getPoly()) );
150        pLcm(first->getPoly(), l->getPoly(), *lcm);
151        pSetCoeff(*lcm,nOne);
152        // computing factors u2 for new labels
153        pWrite(t);
154        *u1 = pDivide(*lcm,t);
155        pWrite(*u1);
156        pSetCoeff(*u1,nOne);
157        pWrite(pHead(l->getPoly()));
158        *u2 = pDivide(*lcm, pHead(l->getPoly()));
159        pSetCoeff(*u2,nOne);
160        Print("IN CRITPAIRS\n");
161        pWrite(*u2);
162        // testing both new labels by the F5 Criterion
163        if(!criterion1(u1, first, lTag) && !criterion1(u2, l, lTag) && 
164           !criterion2(u1, first, rules, rTag) && !criterion2(u2, l, rules, rTag)) {
165            // if they pass the test, add them to CList critPairs, having the LPoly with greater
166            // label as first element in the CPair
167            if(first->getIndex() == l->getIndex() && 
168            pMult(*u1, first->getTerm()) < pMult(*u2, l->getTerm())) {
169                CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u2, 
170                                l->getLPoly(), *u1, first->getLPoly());                   
171                    critPairs->insert(cp);
172            }
173            else {
174                CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u1, 
175                                first->getLPoly(), *u2, l->getLPoly());                   
176                    critPairs->insert(cp);
177            }
178        }
179        else {
180        }
181       
182        // for debugging
183        if(NULL != critPairs) {
184            critPairs->print(); 
185        }
186        l   =   l->getNext();
187    }
188    return critPairs;
189}
190
191
192
193/*
194========================================
195Criterion 1, i.e. Faugere's F5 Criterion
196========================================
197*/
198bool criterion1(poly* t, LNode* l, LTagList* lTag) {
199    // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
200        LNode* testNode =   lTag->get(l->getIndex());
201        // save the monom t1*label_term(l) as it is tested various times in the following
202    poly u1 = ppMult_qq(*t,l->getTerm());
203    while(NULL != testNode && NULL != testNode->getLPoly()) {
204        if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
205            Print("Criterion 1 NOT passed!\n");
206            return true;
207        }
208        //pWrite(testNode->getNext()->getPoly());
209                testNode    =   testNode->getNext();
210        Print("ADDRESS OF TEST NODE: %p\n",testNode);
211    Print("Hier\n");
212    }
213    Print("HIER DRIN CRITERION 1\n");
214       
215    return false;
216}
217
218
219
220/*
221=====================================
222Criterion 2, i.e. Rewritten Criterion
223=====================================
224*/
225bool criterion2(poly* t, LNode* l, RList* rules, RTagList* rTag) {
226        Print("HIER DRIN CRITERION 2:=========================\n");
227    // start at the previously added element to gPrev, as all other elements will have the same index for sure
228        Print("%d\n",l->getIndex());
229    RNode* testNode =   new RNode();
230    if(NULL == rTag->getFirst()->getRule()) {
231        testNode    =   rules->getFirst();
232    }
233    else {
234        Print("%d\n",l->getIndex());
235        Print("%d\n",rTag->getFirst()->getRuleIndex());
236pWrite(rTag->getFirst()->getRuleTerm());
237        if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
238            testNode    =   rules->getFirst();
239            Print("TEST NODE: %p\n",testNode);
240        }
241        else {
242            testNode    =   rTag->get(l->getIndex());
243        }
244    }
245        // save the monom t1*label_term(l) as it is tested various times in the following
246    poly u1 = ppMult_qq(*t,l->getTerm());
247        pWrite(u1);
248    // first element added to rTag was NULL, check for this
249    pWrite(l->getPoly());
250    //Print("%p\n",testNode->getRule());
251    Print("HIER !!!!\n");
252    // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
253    while(NULL != testNode && NULL != testNode->getRule() && testNode->getRule() != l->getRule() 
254          && l->getIndex() == testNode->getRuleIndex()) {
255                pWrite(ppMult_qq(*t,l->getTerm()));
256                pWrite(testNode->getRuleTerm());
257                if(pLmDivisibleBy(ppMult_qq(*t,l->getTerm()),testNode->getRuleTerm())) {
258            Print("Criterion 2 NOT passed!\n");
259            return true;
260        }
261                testNode    =   testNode->getNext();
262    }
263    return false;
264}
265
266
267
268/*
269=================================================================================================================
270Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter
271=================================================================================================================
272*/
273bool criterion2(poly* t, LPoly* l, RList* rules, Rule* lastRuleTested) {
274    // start at the previously added element to gPrev, as all other elements will have the same index for sure
275        RNode* testNode =   rules->getFirst();
276    // save the monom t1*label_term(l) as it is tested various times in the following
277    poly u1 = ppMult_qq(*t,l->getTerm());
278        // first element added to rTag was NULL, check for this
279        while(NULL != testNode->getRule() && l->getRule() != lastRuleTested) {
280        if(pLmDivisibleBy(testNode->getRuleTerm(),ppMult_qq(*t,l->getTerm()))) {
281            Print("Criterion 2 NOT passed!\n");
282            return true;
283        }
284                testNode    =   testNode->getNext();
285    }
286    return false;
287}
288
289
290
291/*
292==================================
293Computation of S-Polynomials in F5
294==================================
295*/
296void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) { 
297    CNode* temp         =   first;
298    poly sp      =   pInit();
299    Print("###############################IN SPOLS##############################\n");
300    while(NULL != temp->getData()) {
301        // only if a new rule was added since the last test in subalgorithm criticalPair()
302        //if(rules->getFirst() != rTag->getFirst()) {
303            Print("IN SPOLS => NEW RULES AVAILABLE\n");
304            if(!criterion2(temp->getAdT1(),temp->getAdLp1(),rules,temp->getLastRuleTested())) {
305                // the second component is tested only when it has the actual index, otherwise there is
306                // no new rule to test since the last test in subalgorithm criticalPair()
307                if(temp->getLp2Index() == temp->getLp1Index()) {
308                    if(!criterion2(temp->getAdT2(),temp->getAdLp2(),rules,temp->getLastRuleTested())) {
309                        // computation of S-polynomial
310                        sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
311                                         ppMult_qq(temp->getT2(),temp->getLp2Poly()));
312                        Print("BEGIN SPOLY1\n====================\n");
313                        pWrite(sp);
314                        Print("END SPOLY1\n====================\n");
315                        if(NULL == sp) {
316                            // as rules consist only of pointers we need to save the labeled
317                            // S-polynomial also of a zero S-polynomial
318                            //zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
319                            // origin of rule can be set NULL as the labeled polynomial
320                            // will never be used again as it is zero => no problems with
321                            // further criterion2() tests and termination conditions
322                            Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
323                                                        reductionsToZero++;
324                            rules->insert(temp->getLp1Index(),temp->getT1());
325                            // as sp = NULL, delete it
326                            delete(&sp);
327                        }
328                        else {
329                            rules->insert(temp->getLp1Index(),temp->getT1());
330                            sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
331                        }
332                        // data is saved in sPolyList or zero => delete sp
333                    }
334                }
335                else { // temp->getLp2Index() < temp->getLp1Index()
336                    // computation of S-polynomial
337                    sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
338                                     ppMult_qq(temp->getT2(),temp->getLp2Poly()));
339                    Print("BEGIN SPOLY2\n====================\n");
340                    pWrite(sp);
341                    Print("END SPOLY2\n====================\n");
342                    if(NULL == sp) {
343                        // zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
344                        // origin of rule can be set NULL as the labeled polynomial
345                        // will never be used again as it is zero => no problems with
346                        // further criterion2() tests and termination conditions
347                            Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
348                        reductionsToZero++;
349                        rules->insert(temp->getLp1Index(),temp->getT1());
350                        // as sp = NULL, delete it
351                        delete(&sp);
352                    }
353                    else {
354                        rules->insert(temp->getLp1Index(),temp->getT1());
355                        sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
356                    }
357                    // data is saved in sPolyList or zero => delete sp
358                }
359            }
360        //}
361        temp    =   temp->getNext();
362    }
363    // these critical pairs can be deleted now as they are either useless for further computations or
364    // already saved as an S-polynomial to be reduced in the following
365    //pDelete(&sp);
366    delete first;   
367}
368
369
370
371/*
372========================================================================
373reduction including subalgorithm topReduction() using Faugere's criteria
374========================================================================
375*/
376LList* reduction(LList* sPolyList, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, 
377                 ideal gbPrev) { 
378    Print("##########################################In REDUCTION!########################################\n");
379    // temporary normal form and zero polynomial for testing
380    static poly tempNF =   pInit();
381    TopRed* ret =   new TopRed();
382    // compute only if there are any S-polynomials to be reduced
383    Print("LENGTH OF SPOLYLIST: %d\n",sPolyList->getLength());
384    if(NULL != sPolyList->getFirst()->getLPoly()) {
385        LNode* temp =   sPolyList->getFirst();
386                Print("SPOLYLIST FIRST START: %p\n",temp);                     
387        while(NULL != temp && NULL != temp->getLPoly()) {
388            if(NULL != completed->getFirst()->getLPoly()) {
389                                Print("BIS HIERHIN UND NICHT WEITER\n");       
390                                Print("%p\n",completed->getFirst());
391                                pWrite(completed->getFirst()->getPoly());
392                Print("ADDRESS OF TERM: %p\n",completed->getFirst()->getTerm());
393                pWrite(completed->getFirst()->getTerm());
394                        }
395                        tempNF = kNF(gbPrev,currQuotient,temp->getPoly()); 
396            temp->setPoly(tempNF);
397            // test if normal form is zero
398            if(NULL == tempNF) {
399                reductionsToZero++;
400                // TODO: sPolyList -> delete first element of list as it is zero and done
401                // TODO: problem is that when deleting the first element, the origin of the
402                // corresponding rule is deleted!
403                Print("LENGTH OF SPOLYLIST: %d\n",sPolyList->getLength());
404                //temp    =   temp->getNext();
405                //sPolyList->setFirst(temp);
406                Print("///////////////////////////////////////////////////////////////////////\n");
407                Print("SPOLYLIST FIRST ELEMENT: %p\n",temp);
408                //Print("%p\n",temp->getLPoly());
409                Print("///////////////////////////////////////////////////////////////////////\n");
410            }
411            else {
412                ret =   topReduction(temp, completed, gPrev, rules, lTag, rTag);
413                // in topReduction() the investigated first element of sPolyList will be deleted after its
414                // reduction has finished => the next to be investigated element is the newly first element
415                // in sPolyList => the while loop is finite
416                // first possible after implementation of topReduction(): temp = sPolyList->getFirst();
417               
418                                completed   =   ret->getCompleted();
419                Print("ZURUECK IN REDUCTION COMPLETED TERM ADDRESS: %p\n",completed->getFirst()->getTerm());
420                pWrite(completed->getFirst()->getTerm());
421                if(NULL != ret->getToDo()) {
422                    sPolyList->insertByLabel(ret->getToDo()->getFirst());
423                }
424            }
425            if(NULL != temp) {
426                sPolyList->setFirst(temp->getNext());
427                temp    =       sPolyList->getFirst();
428            }
429            else {
430                return completed;
431            }
432    Print("ADDRESS OF TERM: %p\n",completed->getFirst()->getTerm());
433
434                        //pWrite(completed->getFirst()->getPoly());
435                        Print("SPOLYLIST FIRST NOW: %p\n",temp);                       
436            //pWrite(temp->getPoly());
437        }
438    }
439    Print("RETURN VALUE OF REDUCTION(): %p\n",completed->getFirst());
440    Print("ADDRESS OF TERM: %p\n",completed->getFirst()->getTerm());
441    Print("ADDRESS OF POLY: %p\n",completed->getFirst()->getPoly());
442    pWrite(completed->getFirst()->getPoly());
443    return completed;
444}   
445
446
447
448/*
449=====================================================================================
450top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
451the same index whereas the labels are taken into account
452=====================================================================================
453*/
454TopRed* topReduction(LNode* l, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag) {
455    Print("##########################################In topREDUCTION!########################################\n");
456                        Print("L BEGIN TOP RED: %p\n",l->getLPoly());
457            pWrite(l->getPoly());
458            pWrite(l->getTerm());
459            Print("ADDRESS OF TERM: %p\n",l->getTerm());
460            //pWrite(completed->getFirst()->getPoly());
461            LNode* red   =   new LNode();
462   
463    do {
464        red  =   findReductor(l, completed, gPrev, rules, lTag, rTag, 
465                              red->getGPrevRedCheck(), red->getCompletedRedCheck());
466        // no reductor found
467        if(NULL == red) {
468            completed->insert(l->getLPoly());
469            Print("AT INSERTION IN COMPLETED ADDRESS OF TERM: %p\n",l->getTerm());
470            Print("AT INSERTION IN COMPLETED ADDRESS OF TERM II: %p\n",completed->getFirst()->getTerm());
471            pWrite(completed->getFirst()->getTerm());
472            TopRed* ret =   new TopRed(completed,NULL);
473            return ret;
474        }
475        // reductor found
476        else {
477            red->setPoly(ppMult_nn(red->getPoly(),pGetCoeff(l->getPoly())));
478        }           
479    } while(NULL != red);
480}
481
482
483
484/*
485=====================================================================
486subalgorithm to find a possible reductor for the labeled polynomial l
487=====================================================================
488*/
489LNode* findReductor(LNode* l,LList* completed,LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag,
490                    LNode* gPrevRedCheck, LNode* completedRedCheck) {
491    Print("HIER FIND REDUCTOR\n");
492        number nOne     =   nInit(1);
493    poly u          =   pOne();
494    poly redPoly    =   pOne();
495    poly t          =   pHead(l->getPoly());
496    LNode* temp     =   new LNode();
497    // setting starting point for search of reductors in gPrev
498    if(NULL != gPrevRedCheck) { 
499        temp =   gPrevRedCheck;
500    }
501    else {
502        temp =   gPrev->getFirst();
503    }
504    // search only for reductors with the same index, as reductions with elements of lower
505    // index were already done in reduction() beforehand
506    while(NULL != temp && NULL != temp->getLPoly() && temp->getIndex() == l->getIndex()) {
507        // divides head term t?
508        if(pLmDivisibleByNoComp(temp->getPoly(),t)) {
509            u       =   pDivide(t,pHead(temp->getPoly()));
510            pSetCoeff(u,nOne);
511            // multiply reductor with factor and normalize it, i.e. LC = 1
512            redPoly =   ppMult_qq(u,temp->getPoly());
513            pNorm(redPoly);
514            u       =   ppMult_qq(u,temp->getTerm());
515            pSetCoeff(u,nOne);
516            Print("IN FIND REDUCTOR:  ");
517            pWrite(u);
518            pWrite(redPoly);
519            // same label? NOTE: also used to
520            if(pLmCmp(u,l->getTerm()) != 0) {
521                // passing criterion 2?
522                if(!criterion2(&u,temp, rules, rTag)) {
523                    // passing criterion 1?
524                    if(!criterion1(&u,temp,lTag)) {
525                        // set tag findRedCheck such that you can start at this point when the
526                        // next time a reductor is searched for in findReductor()
527                        LNode* red      =   new LNode(u,temp->getIndex(),redPoly,NULL,temp->getNext(),completedRedCheck);
528                        return red;
529                    }
530                }
531            }
532        }
533        temp    =   temp->getNext();
534    }
535    if(0 != completed->getLength()) {
536    // do the same as above now for the elements in completed
537    if(NULL != completedRedCheck) {
538        temp    =   completedRedCheck;
539    }
540    else {
541        Print("HIER DRIN\n");
542        temp    =   completed->getFirst();
543        pWrite(temp->getTerm());
544    }
545    // search only for reductors with the same index, as reductions with elements of lower
546    // index where already done in reduction() beforehand
547    while(NULL != temp && NULL != temp->getLPoly() && NULL != temp->getPoly()) {
548        // divides head term t?
549        if(pLmDivisibleByNoComp(temp->getPoly(),t)) {
550            u       =   pDivide(t,pHead(temp->getPoly()));
551            pSetCoeff(u,nOne);
552            pWrite(u);
553            redPoly =   ppMult_qq(u,temp->getPoly());
554            pWrite(temp->getPoly());
555            pWrite(temp->getTerm());
556            u       =   ppMult_qq(u,temp->getTerm());
557            // same label? NOTE: also used to
558        if(pLmCmp(u,l->getTerm()) != 0) {
559                // passing criterion 2?
560                if(!criterion2(&u,temp, rules, rTag)) {
561                    // passing criterion 1?
562                    if(!criterion1(&u,temp,lTag)) {
563                        // set tag findRedCheck such that you can start at this point when the
564                        // next time a reductor is searched for in findReductor()
565                        LNode* red      =   new LNode(u,temp->getIndex(),redPoly,NULL,gPrevRedCheck,temp->getNext());
566                        return red;
567                    }
568                }
569            }
570        }
571        temp    =   temp->getNext();
572    }
573    }
574    // no reductor found
575    Print("HIER DU NULL!\n");
576    return NULL;
577}
578
579
580
581/*
582==========================================================================
583MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
584==========================================================================
585*/
586ideal F5main(ideal id, ring r) {
587    int i,j;
588    int gbLength;
589    // 1 polynomial for defining initial labels & further tests
590    poly ONE = pOne();
591    // tag the first element of index i-1 for criterion 1
592    LTagList* lTag  =   new LTagList();
593    Print("LTAG BEGINNING: %p\n",lTag->getFirst());
594   
595    // first element in rTag is first element of rules which is NULL RNode,
596    // this must be done due to possible later improvements
597    RList* rules    =   new RList();
598    RTagList* rTag  =   new RTagList(rules->getFirst());
599    i = 1;
600    for(j=0; j<IDELEMS(id); j++) {
601        if(NULL != id->m[j]) { 
602            if(pComparePolys(id->m[j],ONE)) {
603                Print("One Polynomial in Input => Computations stopped\n");
604                ideal idNew = idInit(1,1);
605                idNew->m[0] = ONE;
606                return(idNew);
607            }   
608        }
609    } 
610    LList* gPrev    =   new LList(ONE, i, id->m[0]);
611    Print("%p\n",id->m[0]);
612    pWrite(id->m[0]);
613    Print("%p\n",gPrev->getFirst()->getPoly());
614    pWrite(gPrev->getFirst()->getPoly());
615
616    lTag->insert(gPrev->getFirst());
617    // computing the groebner basis of the elements of index < actual index
618    gbLength    =   gPrev->getLength();
619    Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
620    ideal gbPrev    =   idInit(gbLength,1);
621    // initializing the groebner basis of elements of index < actual index
622    gbPrev->m[0]    =   gPrev->getFirst()->getPoly();
623    idShow(gbPrev);
624    idShow(currQuotient);
625
626    for(i=2; i<=IDELEMS(id); i++) {
627        gPrev   =   F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag);
628        // comuting new groebner basis gbPrev
629        ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
630        LNode*  temp    =   gPrev->getFirst();
631        for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
632            gbAdd->m[j] =   temp->getPoly();
633            temp        =   temp->getNext();
634        }
635        gbPrev  =   idAdd(gbPrev,gbAdd);
636        Print("GROEBNER BASIS:\n====================================================\n");
637        idShow(gbPrev);
638        Print("===================================================\n");
639
640        Print("JA\n");
641    } 
642    Print("\n\nNumber of zero-reductions:  %d\n",reductionsToZero);
643    return(gbPrev);
644
645
646}
647
648#endif
Note: See TracBrowser for help on using the repository browser.