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

spielwiese
Last change on this file since d738b47 was d738b47, checked in by Christian Eder, 15 years ago
*** empty log message *** git-svn-id: file:///usr/local/Singular/svn/trunk@11558 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.45 2009-03-13 10:36:19 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
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()) {
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()) {
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
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) {
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());
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++;
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");
907
908
909            // interreduction stuff
910
911            if(i<IDELEMS(id)) {
912                ideal tempId    =   kInterRed(gbPrev);
913                idShow(tempId);
914                sleep(5);
915                gbPrev          =   tempId;
916                qsortDegree(&gbPrev->m[0],&gbPrev->m[IDELEMS(gbPrev)-1]);
917                delete gPrev;
918                //Print("RULES FIRST NOW1: %p\n",rules->getFirst());
919                //Print("HIER\n");
920                delete rules;
921                //delete rTag;
922                //Print("HIER AUCH\n");
923                //Print("%p\n",rules->getFirst());
924                gPrev    =   new LList(pOne,1,gbPrev->m[0]);
925                gPrev->insert(pOne,1,gbPrev->m[1]);
926                poly tempPoly = pInit();
927                pSetCoeff(tempPoly,nOne);
929                rules    =   new RList();
930                rTag     =   new RTagList(rules->getFirst());
931
932                //Print("%p\n",rules->getFirst());
933                //pWrite(tempPoly);
934                rules->insert(2,tempPoly);
935                rTag->insert(rules->getFirst());
936                //Print("%p\n",rules->getFirst());
937                //Print("%p\n",rTag->getFirst());
938                //Print("%p\n",rules->getFirst());
939                //Print("%p\n",rules->getFirst()->getNext()->getNext());
940                //Print("HIERLALA\n");
941            //pWrite(rules->getFirst()->getRuleTerm());
942           // Print("RULES FIRST NOW2: %p\n",rules->getFirst());
943                for(k=2; k<IDELEMS(gbPrev); k++) {
944                    gPrev->insert(pOne,k+1,gbPrev->m[k]);
945                    for(l=0; l<k; l++) {
946                        //pWrite(gbPrev->m[k]);
947                        //pWrite(gbPrev->m[l]);
949                        pSetCoeff(tempPoly,nOne);
950                        rules->insert(k+1,tempPoly);
951                    }
952                    rTag->insert(rules->getFirst());
953                }
954            }
955
956            gbLength    =   gPrev->getLength();
957            //Print("HIER\n");
958        }
959        //gPrev->print();
960        //int anzahl  =   1;
961        //while(NULL != temp) {
962        //    Print("%d. Element: ",anzahl);
963        //    pWrite(temp->getPoly());
964        //    Print("\n");
965        //    temp    =   temp->getNext();
966        //    anzahl++;
967        //}
968        //sleep(5);
969        //Print("GROEBNER BASIS:\n====================================================\n");
970        //idShow(gbPrev);
971        //Print("===================================================\n");
972        //Print("JA\n");
973    }
974        //idShow(gbPrev);
975    Print("\n\nNumber of zero-reductions:  %d\n",reductionsToZero);
976    //LNode* temp    =   gPrev->getFirst();
977    //while(NULL != temp) {
978    //    pWrite(temp->getPoly());
979    //    temp    =   temp->getNext();
980    // }
981    //gPrev->print();
982    //delete lTag;
983    //delete rTag;
984    //delete gPrev;
985    return(gbPrev);
986
987
988}
989
990#endif
Note: See TracBrowser for help on using the repository browser.