# source:git/kernel/f5gb.cc@c9193a

spielwiese
Last change on this file since c9193a was c9193a, checked in by Christian Eder, 15 years ago
fixed bug: zero reduction after top reduction git-svn-id: file:///usr/local/Singular/svn/trunk@11501 2c84dea3-7e68-4137-9b89-c4e89433aadc
• Property mode set to `100644`
File size: 38.0 KB
Line
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* \$Id: f5gb.cc,v 1.36 2009-02-28 21:14:06 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================================================================
232computes a list of critical pairs for the next reduction process
233first element in gPrev is always the newest element which must
234build critical pairs with all other elements in gPrev
235this is a special version for reduction() in which the first
236generator of the critical pair is not tested by criterion2()
237as there are no rules added until then to test for
238================================================================
239*/
240void criticalPairRed(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
241    // initialization for usage in pLcm()
242    number nOne         =   nInit(1);
243    LNode* newElement   =   gPrev->getLast();
244    LNode* temp         =   gPrev->getFirst();
245    poly u1             =   pOne();
246    poly u2             =   pOne();
247    poly lcm            =   pOne();
249    Rule* testedRule    =   rules->getFirst()->getRule();
250    // computation of critical pairs
251    while( gPrev->getLast() != temp) {
252        //pWrite( *(gPrev->getFirst()->getPoly()) );
253       // pWrite( *(l->getPoly()) );
254        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
255        pSetCoeff(lcm,nOne);
256        // computing factors u2 for new labels
257        u1 = pDivide(lcm,t);
258        pSetCoeff(u1,nOne);
260        pSetCoeff(u2,nOne);
261        //if(gPrev->getLast()->getIndex()==5) {
262            //Print("IN CRITPAIRS\n");
263        //    pWrite(u1);
264        //    Print("1st ELEMENT: ");
265        //    pWrite(newElement->getPoly());
266        //    Print("2nd ELEMENT: ");
267        //    pWrite(temp->getPoly());
268        //}
269        // testing both new labels by the F5 Criterion
270        if(!criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag) &&
271           !criterion2(u2, temp, rules, rTag)) {
272            // if they pass the test, add them to CList critPairs, having the LPoly with greater
273            // label as first element in the CPair
274            if(newElement->getIndex() == temp->getIndex() &&
275            -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) {
276                //Print("zweites groesser\n");
277                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2,
278                                temp->getLPoly(), u1, newElement->getLPoly(), testedRule);
279                critPairs->insert(cp);
280            }
281            else {
282                //Print("erstes groesser\n");
283                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1,
284                                newElement->getLPoly(), u2, temp->getLPoly(), testedRule);
285                critPairs->insert(cp);
286            }
287        }
288        else {
289        }
290
291        //Print("\n\n");
292        temp    =   temp->getNext();
293    }
294    // for debugging
295    //if(NULL != critPairs) {
296        //critPairs->print();
297        //sleep(5);
298    //}
299}
300
301
302
303
304/*
305========================================
306Criterion 1, i.e. Faugere's F5 Criterion
307========================================
308*/
309bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) {
310    // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
311        int idx =   l->getIndex();
312    if(idx == 1) {
313        return false;
314    }
315    else {
316        LNode* testNode =   gPrev->getFirst();
317        // save the monom t1*label_term(l) as it is tested various times in the following
318        poly u1 = ppMult_qq(t,l->getTerm());
319        //Print("------------------------------IN CRITERION 1-----------------------------------------\n");
320        //Print("TESTED ELEMENT: ");
321        //pWrite(l->getPoly());
322        //pWrite(l->getTerm());
323        //pWrite(ppMult_qq(t,l->getTerm()));
324        //Print("%d\n\n",l->getIndex());
325        while(testNode->getIndex() < idx && NULL != testNode->getLPoly()) {
326            //pWrite(testNode->getPoly());
327            //Print("%d\n",testNode->getIndex());
328            if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
329                //Print("Criterion 1 NOT passed!\n");
330                return true;
331            }
332            //pWrite(testNode->getNext()->getPoly());
333            testNode    =   testNode->getNext();
334        }
335        return false;
336    }
337}
338
339
340
341/*
342=====================================
343Criterion 2, i.e. Rewritten Criterion
344=====================================
345*/
346bool criterion2(poly t, LNode* l, RList* rules, RTagList* rTag) {
347    //Print("------------------------------IN CRITERION 2-----------------------------------------\n");
348        //Print("RULES: \n");
349        RNode* tempR    =   rules->getFirst();
350        while(NULL != tempR->getRule()) {
352            //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 =   new RNode();
364    if(NULL == rTag->getFirst()->getRule()) {
365        testNode    =   rules->getFirst();
366    }
367    else {
368        if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
369            testNode    =   rules->getFirst();
370        }
371        else {
372        //Print("DEBUG\n");
373        //Print("L INDEX: %d\n",l->getIndex());
374            testNode    =   rTag->get(l->getIndex());
376        }
377    }
378        // save the monom t1*label_term(l) as it is tested various times in the following
379    poly u1 = ppMult_qq(t,l->getTerm());
380    // first element added to rTag was NULL, check for this
381    //Print("%p\n",testNode->getRule());
382    // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
383    if(NULL != testNode && NULL != testNode->getRule()) {
384        //pWrite(testNode->getRuleTerm());
385    }
386    if(NULL != testNode) {
387        if(testNode->getRule() == l->getRule()) {
388            //Print("%p\n%p\n",testNode->getRule(),l->getRule());
389            //Print("EQUAL\n");
390        }
391        else {
392            //Print("NOT EQUAL\n");
393        }
394    }
395    while(NULL != testNode && NULL != testNode->getRule() && testNode->getRule() != l->getRule()
396          && l->getIndex() == testNode->getRuleIndex()) {
397        //pWrite(testNode->getRuleTerm());
398                //pWrite(testNode->getRuleTerm());
399        //pWrite(t);
400        //pWrite(l->getTerm());
401        //pWrite(u1);
402        //Print("%d\n",testNode->getRuleIndex());
403        if(pLmDivisibleBy(testNode->getRuleTerm(),u1)) {
404            //Print("Criterion 2 NOT passed!\n");
405            pDelete(&u1);
406            return true;
407        }
408                testNode    =   testNode->getNext();
409    }
410    pDelete(&u1);
411    return false;
412}
413
414
415
416/*
417=================================================================================================================
418Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter
419=================================================================================================================
420*/
421bool criterion2(poly t, LPoly* l, RList* rules, Rule* testedRule) {
422    //Print("------------------------------IN CRITERION 2-----------------------------------------\n");
423    //Print("LAST RULE TESTED: %p",testedRule);
424    //Print("RULES: \n");
425        RNode* tempR    =   rules->getFirst();
426        //while(NULL != tempR->getRule()) {
427            //pWrite(tempR->getRuleTerm());
428            //Print("%d\n\n",tempR->getRuleIndex());
429            //tempR   =   tempR->getNext();
430        //}
431        //Print("TESTED ELEMENT: ");
432        //pWrite(l->getPoly());
433        //pWrite(l->getTerm());
434        //pWrite(ppMult_qq(t,l->getTerm()));
435        //Print("%d\n\n",l->getIndex());
436// start at the previously added element to gPrev, as all other elements will have the same index for sure
437        RNode* testNode =   rules->getFirst();
438    // save the monom t1*label_term(l) as it is tested various times in the following
439    poly u1 = ppMult_qq(t,l->getTerm());
440        // first element added to rTag was NULL, check for this
441        while(NULL != testNode->getRule() && testNode->getRule() != testedRule) {
442        //pWrite(testNode->getRuleTerm());
443        if(pLmDivisibleBy(testNode->getRuleTerm(),u1)) {
444            //Print("Criterion 2 NOT passed!\n");
445            pDelete(&u1);
446            return true;
447        }
448                testNode    =   testNode->getNext();
449    }
450    pDelete(&u1);
451    return false;
452}
453
454
455
456/*
457==================================
458Computation of S-Polynomials in F5
459==================================
460*/
461void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) {
462    CNode* temp         =   first;
463    poly sp      =   pInit();
464    //Print("###############################IN SPOLS##############################\n");
465    while(NULL != temp->getData()) {
466        // only if a new rule was added since the last test in subalgorithm criticalPair()
467        //if(rules->getFirst() != rTag->getFirst()) {
469                // the second component is tested only when it has the actual index, otherwise there is
470                // no new rule to test since the last test in subalgorithm criticalPair()
471                if(temp->getLp2Index() == temp->getLp1Index()) {
473                        // computation of S-polynomial
474                        sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
475                                         ppMult_qq(temp->getT2(),temp->getLp2Poly()));
476                        //Print("BEGIN SPOLY1\n====================\n");
477                        pNorm(sp);
478                        //pWrite(sp);
479                        //Print("END SPOLY1\n====================\n");
480                        if(NULL == sp) {
481                            // as rules consist only of pointers we need to save the labeled
482                            // S-polynomial also of a zero S-polynomial
484                            // origin of rule can be set NULL as the labeled polynomial
485                            // will never be used again as it is zero => no problems with
486                            // further criterion2() tests and termination conditions
487                            //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
488                                                        reductionsToZero++;
489                            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
491                            //pWrite(rules->getFirst()->getRuleTerm());
492                            // as sp = NULL, delete it
493                            pDelete(&sp);
494                            //Print("HIER\n");
495                        }
496                        else {
497                            rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
499                            //pWrite(rules->getFirst()->getRuleTerm());
500                            sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
501                        }
502                        // data is saved in sPolyList or zero => delete sp
503                    }
504                }
505                else { // temp->getLp2Index() < temp->getLp1Index()
506                    // computation of S-polynomial
507                    sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
508                                     ppMult_qq(temp->getT2(),temp->getLp2Poly()));
509                    //Print("BEGIN SPOLY2\n====================\n");
510                    pNorm(sp);
511                    //pWrite(sp);
512                    //Print("END SPOLY2\n====================\n");
513                    if(NULL == sp) {
515                        // origin of rule can be set NULL as the labeled polynomial
516                        // will never be used again as it is zero => no problems with
517                        // further criterion2() tests and termination conditions
518                            //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
519                        reductionsToZero++;
520                        rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
522                        //pWrite(rules->getFirst()->getRuleTerm());
523                        // as sp = NULL, delete it
524                        pDelete(&sp);
525                    }
526                    else {
527                        rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
529                        //pWrite(rules->getFirst()->getRuleTerm());
530                        //Print("%d\n",rules->getFirst()->getRuleIndex());
531                        //Print("%p\n",sPolyList->getFirst());
532                        sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
533                    }
534                    // data is saved in sPolyList or zero => delete sp
535                }
536            }
537        //}
538        temp    =   temp->getNext();
539    }
540    // these critical pairs can be deleted now as they are either useless for further computations or
541    // already saved as an S-polynomial to be reduced in the following
542    delete first;
543}
544
545
546
547/*
548========================================================================
549reduction including subalgorithm topReduction() using Faugere's criteria
550========================================================================
551*/
552void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
553                 ideal gbPrev) {
554    //Print("##########################################In REDUCTION!########################################\n");
555    // check if sPolyList has any elements
556    // NOTE: due to initialization sPolyList always has a default NULL element
557    while(sPolyList->getLength() > 0) {
558        //Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
559        if(sPolyList->getLength() > 1) {
560        //Print("%p\n",sPolyList->getFirst());
561        //Print("%p\n",sPolyList->getFirst()->getLPoly());
562        //Print("%p\n",sPolyList->getFirst()->getNext());
563        //Print("%p\n",sPolyList->getFirst()->getNext()->getLPoly());
564        //Print("%p\n",sPolyList->getFirst());
565        }
566        //if(gPrev->getLast()->getIndex() == 5) {
567            //sPolyList->print();
568            //sleep(5);
569        //}
570
571        // temp is the first element in the sPolyList which should be reduced
572        // due to earlier sorting this is the element of minimal degree AND
573        // minimal label
574        LNode* temp =   sPolyList->getFirst();
575        //pWrite(temp->getPoly());
576        // delete the above first element from sPolyList, temp will be either reduced to
577        // zero or added to gPrev, but never come back to sPolyList
578        if(NULL != temp && NULL != temp->getLPoly()) {
579            sPolyList->setFirst(temp->getNext());
580        //Print("HIER\n");
581        }
582        else {
583            break;
584        }
585        //Print("HALLO %p\n",temp->getPoly());
586        //Print("%p\n",temp->getPoly());
587        //pWrite(temp->getPoly());
588        //idShow(gbPrev);
589        poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
590        //Print("LENGTH: %d\n",sPolyList->getLength());
591        //pWrite(tempNF);
592        //pWrite(temp->getPoly());
593        if(NULL != tempNF) {
594            pNorm(tempNF);
595            // write the reduced polynomial in temp
596            temp->setPoly(tempNF);
597            // try further reductions of temp with polynomials in gPrev
598            // with label index = current label index: this is done such that there
599            // is no label corruption during the reduction process
600            topReduction(temp,sPolyList,gPrev,rules,lTag,rTag,gbPrev);
601
602        }
603        if(NULL != temp->getPoly()) {
604            //CList* newCritPairs = new CList;
605            //Print("##################IN CRITPAIRS IN REDUCTION#####################\n");
606            criticalPairRed(gPrev,critPairs,lTag,rTag,rules);
607            //Print("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++H I E R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
608        }
609        else {
610            //delete temp;
611            LNode* tempLoop = gPrev->getFirst();
612            //Print("AUSGABE IN REDUCTION:\n");
613            //while(NULL != tempLoop) {
614                //pWrite(tempLoop->getPoly());
615                //tempLoop = tempLoop->getNext();
616            //}
617            //sleep(10);
618        }
619    }
620}
621
622
623
624/*
625=====================================================================================
626top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
627the same index whereas the labels are taken into account
628=====================================================================================
629*/
630void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev) {
631    //Print("##########################################In topREDUCTION!########################################\n");
632    // try l as long as there are reductors found by findReductor()
633    do {
634        LNode* tempRed  =   new LNode();
635        //Print("TESTED POLYNOMIAL IN THE FOLLOWING: ");
636        //pWrite(l->getPoly());
637        //Print("HIER\n");
638        tempRed  =   findReductor(l,gPrev,rules,lTag,rTag);
639        //Print("--------------------------------HIER DEBUG 2----------------------------------\n");
640        // if a reductor for l is found and saved in tempRed
641        if(NULL != tempRed) {
642            // if label of reductor is greater than the label of l we have to built a new element
643            // and add it to sPolyList
644            //Print("REDUCTOR POLYNOMIAL: ");
645            //pWrite(tempRed->getPoly());
646            //Print("TERM: ");
647            //pWrite(tempRed->getTerm());
648            if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
649                // needed sinc pSub destroys the arguments!
650                //Print("H----------I------------E--------------R\n");
651                poly temp_poly_l    =   pInit();
652                temp_poly_l         =   pCopy(l->getPoly());
653                //Print("POLYNOMIAL L: ");
654                //pWrite(l->getPoly());
655                //pWrite(temp_poly_l);
656                poly temp           =   pSub(tempRed->getPoly(),temp_poly_l);
657                //Print("POLYNOMIAL L: ");
658                //pWrite(l->getPoly());
659                //pWrite(temp_poly_l);
660                //Print("AFTER REDUCTION STEP: ");
661                //pWrite(temp);
662                //sleep(20);
663                //pWrite(temp);
664                if(NULL != temp) {
665                    pNorm(temp);
666                    tempRed->setPoly(temp);
667                    //pWrite(tempRed->getPoly());
668                    // for debugging
669                    //pWrite(tempRed->getPoly());
671                    rules->insert(tempRed->getIndex(),tempRed->getTerm());
672                    tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
673                    //Print("%p\n",sPolyList->getFirst());
674                    //Print("%p\n",sPolyList->getFirst()->getLPoly());
675                    //Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
676                    //sPolyList->print();
677
678                    sPolyList->insertByLabel(tempRed);
679                    //sPolyList->print();
680                    //Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
681                    //Print("OH JE\n");
682                }
683                else {
684                    pDelete(&temp);
685                    reductionsToZero++;
687        //Print("wieder hier2\n");
688                    rules->insert(tempRed->getIndex(),tempRed->getTerm());
689                    delete tempRed;
690                }
691            }
692            // label of reductor is smaller than the label of l, subtract reductor from l and delete the
693            // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes
694            // after subtraction
695            else {
696                poly temp_poly_l    =   pInit();
697                temp_poly_l         =   pCopy(l->getPoly());
698                poly temp   =   pSub(temp_poly_l,tempRed->getPoly());
699                //Print("AFTER REDUCTION STEP: ");
700                //pWrite(temp);
701                if(NULL != temp) {
702                    pNorm(temp);
703                    poly tempNF =   kNF(gbPrev,currQuotient,temp);
704                    pNorm(tempNF);
705                    //pWrite(tempNF);
706                    if(NULL == tempNF) {
707                        reductionsToZero++;
708                        pDelete(&tempNF);
709                        l->setPoly(NULL);
710                        break;
711                    }
712                    l->setPoly(tempNF);
713
714                    //pWrite(l->getPoly());
715                    l->setGPrevRedCheck(NULL);
716                }
717                else {
718                    //Print("ZERO REDUCTION!\n");
719                    reductionsToZero++;
720                    pDelete(&temp);
721                    l->setPoly(NULL);
722                    //pWrite(gPrev->getLast()->getPoly());
723                    break;
724                }
725            }
726        }
727        else {
728            if(NULL != l->getPoly()) {
729                pNorm(l->getPoly());
730                //Print("----------------------------------ADDED TO GPREV IN TOPREDUCTION:-------------------------------------- ");
731                //pWrite(l->getPoly());
732                //pWrite(l->getTerm());
733                //Print("INDEX: %d\n\n\n", l->getIndex());
734                //sleep(20);
735                gPrev->insert(l->getLPoly());
736                //Print("GPREV: \n");
737                LNode* tempLoop = gPrev->getFirst();
738                //while(NULL != tempLoop) {
739                    //Print("HERE\n");
740                    //pWrite(tempLoop->getPoly());
741                    //tempLoop = tempLoop->getNext();
742                //}
743            }
744            break;
745        }
746    } while(1);
747}
748
749
750/*
751=====================================================================
752subalgorithm to find a possible reductor for the labeled polynomial l
753=====================================================================
754*/
755LNode* findReductor(LNode* l, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag) {
756    // allociation of memory for the possible reductor
757    //Print("IN FIND REDUCTOR\n");
758    poly u      =   pOne();
759    poly red    =   pOne();
760    number nOne =   nInit(1);
761    LNode* temp =   new LNode();
762    // head term of actual element such that we do not have to call pHead at each new reductor test
764    // if l was already checked use the information in gPrevRedCheck such
765    // that we can start searching for new reducers from this point and
766    // not from the first element of gPrev with the current index
767    if(NULL != l->getGPrevRedCheck()) {
768        temp    =   l->getGPrevRedCheck()->getNext();
769    }
770    // no reductors were searched for l before, thus start at the first
771    // element of gPrev with the current index, tagged by lTag
772    else {
773        temp    =   lTag->getFirstCurrentIdx();
774    }
775    // search for reductors until we are at the end of gPrev resp. at the
776    // end of the elements of the current index
777    while(NULL != temp && temp->getIndex() == l->getIndex()) {
778        // does the head of the element of gPrev divides the head of
779        // the to be reduced element?
780        //Print("-------------FOUND REDUCTORS----------------------\n");
781        //Print("\n");
782        //pWrite(temp->getPoly());
783        //pWrite(temp->getTerm());
784        //pWrite(t);
785        //pWrite(l->getPoly());
786        //Print("HALLO\n");
787        if(pLmDivisibleByNoComp(temp->getPoly(),t)) {
788        //Print("HALLO\n");
789            // get all the information needed for the following tests
790            // of the criteria
792            pSetCoeff(u,nOne);
793            //Print("HIER FINDRED\n");
794            //pWrite(u);
795            //Print("\n");
796            red =   ppMult_qq(u,temp->getPoly());
797            pNorm(red);
798            //u   =   ppMult_qq(u,temp->getTerm());
799            //pSetCoeff(u,nOne);
800            // check if both have the same label
801        //Print("HALLO\n");
802            if(pLmCmp(u,l->getTerm()) != 0) {
803        //Print("HALLO\n");
804                // passing criterion2 ?
805                if(!criterion2(u,temp,rules,rTag)) {
806                    // passing criterion1 ?
807                    if(!criterion1(gPrev,u,temp,lTag)) {
808                            //Print("HIER DEBUG\n");
809                            l->setGPrevRedCheck(temp);
810                            LNode* redNode  =   new LNode(ppMult_qq(u,temp->getTerm()),temp->getIndex(),red,NULL,NULL);
811                            return redNode;
812                    }
813                }
814            }
815        }
816        //Print("%p\n",temp->getNext());
817        //pWrite(temp->getPoly());
818        //Print("HALLO\n");
819        temp = temp->getNext();
820    }
821
822//    delete temp;
823   //Print("1st gPrev: ");
824    //pWrite(gPrev->getFirst()->getPoly());
825    //Print("2nd gPrev: ");
826    //pWrite(gPrev->getFirst()->getNext()->getPoly());
827 return NULL;
828}
829
830
831
832/*
833==========================================================================
834MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
835==========================================================================
836*/
837ideal F5main(ideal id, ring r) {
838    int i,j;
839    int gbLength;
840    // 1 polynomial for defining initial labels & further tests
841    poly ONE = pOne();
842    // tag the first element of index i-1 for criterion 1
843    LTagList* lTag  =   new LTagList();
844    //Print("LTAG BEGINNING: %p\n",lTag->getFirst());
845
846    // first element in rTag is first element of rules which is NULL RNode,
847    // this must be done due to possible later improvements
848    RList* rules    =   new RList();
849    RTagList* rTag  =   new RTagList(rules->getFirst());
850    i = 1;
851    for(j=0; j<IDELEMS(id); j++) {
852        if(NULL != id->m[j]) {
853            if(pComparePolys(id->m[j],ONE)) {
854                Print("One Polynomial in Input => Computations stopped\n");
855                ideal idNew = idInit(1,1);
856                idNew->m[0] = ONE;
857                return(idNew);
858            }
859        }
860    }
861    ideal idNew     =   kInterRed(id);
862    idDelete(&id);
863    id              =   idNew;
864    qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
865    LList* gPrev    =   new LList(ONE, i, id->m[0]);
866    //idShow(id);
867    //Print("%p\n",id->m[0]);
868    //pWrite(id->m[0]);
869    //Print("%p\n",gPrev->getFirst()->getPoly());
870    //pWrite(gPrev->getFirst()->getPoly());
871
872    lTag->insert(gPrev->getFirst());
873    lTag->setFirstCurrentIdx(gPrev->getFirst());
874    // computing the groebner basis of the elements of index < actual index
875    gbLength    =   gPrev->getLength();
876    //Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
877    ideal gbPrev    =   idInit(gbLength,1);
878    // initializing the groebner basis of elements of index < actual index
879    gbPrev->m[0]    =   gPrev->getFirst()->getPoly();
880    //idShow(gbPrev);
881    //idShow(currQuotient);
882
883    for(i=2; i<=IDELEMS(id); i++) {
884        LNode* gPrevTag =   gPrev->getLast();
885        //Print("Last POlynomial in GPREV: ");
886        //Print("%p\n",gPrevTag);
887        //pWrite(gPrevTag->getPoly());
888        gPrev   =   F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag);
889        // DEBUGGING STUFF
890        LNode* temp    =   gPrev->getFirst();
891    // computing new groebner basis gbPrev
892        if(gPrev->getLength() > gbLength) {
894        LNode*  temp    =   gPrevTag;
895        //Print("%p\n",gPrevTag);
896        //Print("%p\n",gPrev->getLast());
897        //pWrite(temp->getPoly());
898        //Print("LENGTH OF GPREV LIST: %d\n",gPrev->getLength());
899        //Print("%d\n",gbLength);
900        for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
901            //Print("YES\n");
902            temp        =   temp->getNext();
904            //pWrite(temp->getPoly());
905        }
906        gbLength    =   gPrev->getLength();
908        }
909        int anzahl  =   1;
910        //while(NULL != temp) {
911        //    Print("%d. Element: ",anzahl);
912        //    pWrite(temp->getPoly());
913        //    Print("\n");
914        //    temp    =   temp->getNext();
915        //    anzahl++;
916        //}
917        //sleep(5);
918        //Print("GROEBNER BASIS:\n====================================================\n");
919        //idShow(gbPrev);
920        //Print("===================================================\n");
921        //Print("JA\n");
922    }
923    Print("\n\nNumber of zero-reductions:  %d\n",reductionsToZero);
924    //LNode* temp    =   gPrev->getFirst();
925    //while(NULL != temp) {
926    //    pWrite(temp->getPoly());
927    //    temp    =   temp->getNext();
928    // }
929    delete(gPrev);
930    return(gbPrev);
931
932
933}
934
935#endif
Note: See TracBrowser for help on using the repository browser.