source: git/kernel/f5gb.cc @ fe88079

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