source: git/kernel/f5gb.cc @ 9cb4078

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