# source:git/kernel/f5gb.cc@8066e80

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