source: git/kernel/f5gb.cc @ c4158f

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