Changeset d51339 in git

Timestamp:

Feb 18, 2009, 9:43:05 PM (14 years ago)

Author:

Christian Eder

Branches:

(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')

Children:

eab144e3329d02244a62975d1bb6e77d4754f131

Parents:

93a7f7b1c20c3c886dd4dff521c518039f3824e7

Message:

new written reduction process, still problems getting the right rules in criterion2()
->lastRuleTested shouldnt be part of the CPair as it is a characteristic of an LPoly


git-svn-id: file:///usr/local/Singular/svn/trunk@11406 2c84dea3-7e68-4137-9b89-c4e89433aadc

Location:

kernel

Files:

• f5data.cc (modified) (2 diffs)
• f5data.h (modified) (2 diffs)
• f5gb.cc (modified) (26 diffs)
• f5gb.h (modified) (8 diffs)
• f5lists.cc (modified) (12 diffs)
• f5lists.h (modified) (8 diffs)

kernel/f5data.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5data.cc,v 1.6 2009-02-15 20:33:56 ederc Exp $ */
+/* $Id: f5data.cc,v 1.7 2009-02-18 20:43:05 ederc Exp $ */
 /*
 * ABSTRACT: lpolynomial definition 
@@ -150 +150 @@
 }
 
+void CPair::setLastRuleTested(Rule* r) {
+    lastRuleTested   =   r;
+}
+
 /*
 ===================================

kernel/f5data.h

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5data.h,v 1.5 2009-02-11 21:24:07 ederc Exp $ */
+/* $Id: f5data.h,v 1.6 2009-02-18 20:43:05 ederc Exp $ */
 /*
 * ABSTRACT: labeled polynomial interface
@@ -75 +75 @@
         int     getLp2Index();
         Rule*   getLastRuleTested();
+        void    setLastRuleTested(Rule* r);
 };
 

kernel/f5gb.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5gb.cc,v 1.29 2009-02-16 14:23:42 ederc Exp $ */
+/* $Id: f5gb.cc,v 1.30 2009-02-18 20:43:05 ederc Exp $ */
 /*
 * ABSTRACT: f5gb interface
@@ -74 +74 @@
     pWrite(gPrev->getFirst()->getPoly());
     gPrev->insert(ONE,i,f_i);
+    // tag the first element in gPrev of the current index for findReductor()
+    lTag->setFirstCurrentIdx(gPrev->getFirst());
     Print("1st gPrev: ");
     pWrite(gPrev->getFirst()->getPoly());
@@ -81 +83 @@
     CList* critPairs        =   new CList();
     CNode* critPairsMinDeg  =   new CNode();   
-    // computation of critical pairs with checking of criterion 1 and criterion 2
-    critPairs               =   criticalPair(gPrev, critPairs, lTag, rTag, rules);
+    // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them
+    // in the list critPairs
+    criticalPair(gPrev, critPairs, lTag, rTag, rules);
     static LList* sPolyList        =   new LList();
     // labeled polynomials which have passed reduction() and have to be added to list gPrev
     static LList* completed        =   new LList();
-    Print("_____________________________________________________________________________%p\n",completed->getFirst()->getLPoly());
     // the reduced labeled polynomials which are returned from subalgorithm reduction()
     static LList* reducedLPolys     =   new LList();
@@ -93 +95 @@
         // critPairs->getMinDeg() deletes the first elements of minimal degree from
         // critPairs, thus the while loop is not infinite.
-        critPairs->print();
         critPairsMinDeg =   critPairs->getMinDeg();
         // adds all to be reduced S-polynomials in the list sPolyList and adds 
@@ -108 +109 @@
             temp    =   temp->getNext();
         } 
-        //while(NULL != sPolyList->getFirst()->getLPoly()) {
-            reduction(sPolyList, completed, gPrev, rules, lTag, rTag, gbPrev);
-        //}
-    }
-    Print("HIER123\n");
+        // reduction process of new S-polynomials and also adds new critical pairs to critPairs
+        reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev);
+    }
+    Print("REDUCTION DONE\n");
     Print("%p\n",rules->getFirst());
     Print("%p\n",rTag->getFirst());
@@ -122 +122 @@
         Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
     }
-    lTag->insert(gPrev->getFirst());
+    lTag->insert(lTag->getFirstCurrentIdx());
+    Print("LTAG LIST: \n");
+    LNode* tempTag = lTag->getFirst();
+    Print("INDEX: %d\n",tempTag->getIndex());
+    pWrite(tempTag->getPoly());
     Print("COMPLETED FIRST IN F5INC: \n");
+    Print("1st gPrev: ");
+    pWrite(gPrev->getFirst()->getPoly());
+    Print("2nd gPrev: ");
+    pWrite(gPrev->getFirst()->getNext()->getPoly());
+    Print("3rd gPrev: ");
+    pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly());
+ 
+ 
     return gPrev;
 }
@@ -136 +148 @@
 ================================================================
 */
-CList* criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
+void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
     // initialization for usage in pLcm()
     number nOne         =   nInit(1);
-    LNode* first        =   gPrev->getFirst();
-    LNode* l            =   first->getNext();
-    poly* u1            =   new poly(pInit());
-    poly* u2            =   new poly(pInit());
-    poly* lcm           =   new poly(pInit());
-    poly t              =   pHead(first->getPoly());
+    LNode* newElement   =   gPrev->getLast();
+    LNode* temp         =   gPrev->getFirst();
+    poly u1             =   pOne();
+    poly u2             =   pOne();
+    poly lcm            =   pOne();
+    poly t              =   pHead(newElement->getPoly());
     // computation of critical pairs
-    while( NULL != l) {
+    while( gPrev->getLast() != temp) {
         //pWrite( *(gPrev->getFirst()->getPoly()) );
         //pWrite( *(l->getPoly()) );
-        pLcm(first->getPoly(), l->getPoly(), *lcm);
-        pSetCoeff(*lcm,nOne);
+        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
+        pSetCoeff(lcm,nOne);
         // computing factors u2 for new labels
-        pWrite(t);
-        *u1 = pDivide(*lcm,t);
-        pWrite(*u1);
-        pSetCoeff(*u1,nOne);
-        pWrite(pHead(l->getPoly()));
-        *u2 = pDivide(*lcm, pHead(l->getPoly()));
-        pSetCoeff(*u2,nOne);
+        u1 = pDivide(lcm,t);
+        pSetCoeff(u1,nOne);
+        u2 = pDivide(lcm, pHead(temp->getPoly()));
+        pSetCoeff(u2,nOne);
         Print("IN CRITPAIRS\n");
-        pWrite(*u2);
+        pWrite(u1);
+        Print("1st ELEMENT: ");
+        pWrite(newElement->getPoly());
+        Print("2nd ELEMENT: ");
+        pWrite(temp->getPoly());
         // testing both new labels by the F5 Criterion
-        if(!criterion1(u1, first, lTag) && !criterion1(u2, l, lTag) && 
-           !criterion2(u1, first, rules, rTag) && !criterion2(u2, l, rules, rTag)) {
+        if(!criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag) && 
+           !criterion2(u1, newElement, rules, rTag) && !criterion2(u2, temp, rules, rTag)) {
             // if they pass the test, add them to CList critPairs, having the LPoly with greater
             // label as first element in the CPair
-            if(first->getIndex() == l->getIndex() && 
-            pMult(*u1, first->getTerm()) < pMult(*u2, l->getTerm())) {
-                CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u2, 
-                                l->getLPoly(), *u1, first->getLPoly());                   
-                    critPairs->insert(cp);
+            if(newElement->getIndex() == temp->getIndex() && 
+            ppMult_qq(u1, newElement->getTerm()) < ppMult_qq(u2, temp->getTerm())) {
+                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, 
+                                temp->getLPoly(), u1, newElement->getLPoly());                   
+                critPairs->insert(cp);
             }
             else {
-                CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u1, 
-                                first->getLPoly(), *u2, l->getLPoly());                   
-                    critPairs->insert(cp);
+                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, 
+                                newElement->getLPoly(), u2, temp->getLPoly());                   
+                critPairs->insert(cp);
             }
         }
@@ -181 +194 @@
         }
         
-        // for debugging
-        if(NULL != critPairs) {
-            critPairs->print(); 
-        }
-        l   =   l->getNext();
-    }
-    return critPairs;
+        Print("\n\n");
+        temp    =   temp->getNext();
+    }
+    // for debugging
+    if(NULL != critPairs) {
+        critPairs->print(); 
+    }
+}
+
+
+
+/*
+================================================================
+computes a list of critical pairs for the next reduction process
+first element in gPrev is always the newest element which must
+build critical pairs with all other elements in gPrev
+NOTE: this is a special version for the call inside reduction()
+      which adds to the already existing critical pairs new ones
+================================================================
+*/
+void criticalPairRed(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
+    // initialization for usage in pLcm()
+    number nOne         =   nInit(1);
+    LNode* newElement   =   gPrev->getLast();
+    LNode* temp         =   gPrev->getFirst();
+    poly u1             =   pOne();
+    poly u2             =   pOne();
+    poly lcm            =   pOne();
+    poly t              =   pHead(newElement->getPoly());
+    // computation of critical pairs
+    while( gPrev->getLast() != temp) {
+        //pWrite( *(gPrev->getFirst()->getPoly()) );
+        //pWrite( *(l->getPoly()) );
+        pLcm(newElement->getPoly(), temp->getPoly(), lcm);
+        pSetCoeff(lcm,nOne);
+        // computing factors u2 for new labels
+        u1 = pDivide(lcm,t);
+        pSetCoeff(u1,nOne);
+        u2 = pDivide(lcm, pHead(temp->getPoly()));
+        pSetCoeff(u2,nOne);
+        Print("IN CRITPAIRS\n");
+        // testing both new labels by the F5 Criterion
+        if(!criterion1(gPrev,u1, newElement, lTag) && !criterion1(gPrev,u2, temp, lTag) && 
+           !criterion2(u1, newElement, rules, rTag) && !criterion2(u2, temp, rules, rTag)) {
+            // if they pass the test, add them to CList critPairs, having the LPoly with greater
+            // label as first element in the CPair
+            if(newElement->getIndex() == temp->getIndex() && 
+            pMult(u1, newElement->getTerm()) < pMult(u2, temp->getTerm())) {
+                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, 
+                                temp->getLPoly(), u1, newElement->getLPoly());                   
+                critPairs->insert(cp);
+            }
+            else {
+                CPair* cp   =   new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, 
+                                newElement->getLPoly(), u2, temp->getLPoly());                   
+                critPairs->insert(cp);
+            }
+        }
+        else {
+        }
+        
+        
+        temp    =   temp->getNext();
+    }
+    // for debugging
+    if(NULL != critPairs) {
+        critPairs->print(); 
+    }
 }
 
@@ -197 +271 @@
 ========================================
 */
-bool criterion1(poly* t, LNode* l, LTagList* lTag) {
+bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) {
     // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
-        LNode* testNode =   lTag->get(l->getIndex());
-        // save the monom t1*label_term(l) as it is tested various times in the following
-    poly u1 = ppMult_qq(*t,l->getTerm());
-    while(NULL != testNode && NULL != testNode->getLPoly()) {
-        if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
-            Print("Criterion 1 NOT passed!\n");
-            return true;
-        }
-        //pWrite(testNode->getNext()->getPoly());
-                testNode    =   testNode->getNext();
-        Print("ADDRESS OF TEST NODE: %p\n",testNode);
-    Print("Hier\n");
-    }
-    Print("HIER DRIN CRITERION 1\n");
-        
-    return false;
+        int idx =   l->getIndex();
+    if(idx == 1) {
+        return false;
+    }
+    else {
+        LNode* testNode =   gPrev->getFirst();
+        // save the monom t1*label_term(l) as it is tested various times in the following
+        poly u1 = ppMult_qq(t,l->getTerm());
+        Print("------------------------------IN CRITERION 1-----------------------------------------\n");
+        Print("TESTED ELEMENT: ");
+        pWrite(l->getPoly());
+        pWrite(ppMult_qq(t,l->getTerm()));
+        Print("%d\n\n",l->getIndex());
+        while(testNode->getIndex() < idx && NULL != testNode->getLPoly()) {
+            pWrite(testNode->getPoly());
+            Print("%d\n",testNode->getIndex());
+            if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
+                Print("Criterion 1 NOT passed!\n");
+                return true;
+            }
+            //pWrite(testNode->getNext()->getPoly());
+            testNode    =   testNode->getNext();
+        }
+        return false;
+    }
 }
 
@@ -224 +307 @@
 =====================================
 */
-bool criterion2(poly* t, LNode* l, RList* rules, RTagList* rTag) {
-        Print("HIER DRIN CRITERION 2:=========================\n");
-    // start at the previously added element to gPrev, as all other elements will have the same index for sure
-        Print("%d\n",l->getIndex());
+bool criterion2(poly t, LNode* l, RList* rules, RTagList* rTag) {
+    Print("------------------------------IN CRITERION 2-----------------------------------------\n");
+        Print("RULES: \n");
+        RNode* tempR    =   rules->getFirst();
+        while(NULL != tempR->getRule()) {
+            pWrite(tempR->getRuleTerm());
+            Print("%d\n\n",tempR->getRuleIndex());
+            tempR   =   tempR->getNext();
+        }
+Print("TESTED ELEMENT: ");
+        pWrite(l->getPoly());
+        pWrite(ppMult_qq(t,l->getTerm()));
+        Print("%d\n\n",l->getIndex());
+// start at the previously added element to gPrev, as all other elements will have the same index for sure
     RNode* testNode =   new RNode();
     if(NULL == rTag->getFirst()->getRule()) {
@@ -233 +326 @@
     }
     else {
-        Print("%d\n",l->getIndex());
-        Print("%d\n",rTag->getFirst()->getRuleIndex());
-pWrite(rTag->getFirst()->getRuleTerm());
         if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
             testNode    =   rules->getFirst();
-            Print("TEST NODE: %p\n",testNode);
         }
         else {
@@ -245 +334 @@
     }
         // save the monom t1*label_term(l) as it is tested various times in the following
-    poly u1 = ppMult_qq(*t,l->getTerm());
-        pWrite(u1);
+    poly u1 = ppMult_qq(t,l->getTerm());
     // first element added to rTag was NULL, check for this
-    pWrite(l->getPoly());
     //Print("%p\n",testNode->getRule());
-    Print("HIER !!!!\n");
     // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
     while(NULL != testNode && NULL != testNode->getRule() && testNode->getRule() != l->getRule() 
           && l->getIndex() == testNode->getRuleIndex()) {
-                pWrite(ppMult_qq(*t,l->getTerm()));
-                pWrite(testNode->getRuleTerm());
-                if(pLmDivisibleBy(ppMult_qq(*t,l->getTerm()),testNode->getRuleTerm())) {
+        pWrite(testNode->getRuleTerm());
+                if(pLmDivisibleBy(ppMult_qq(t,l->getTerm()),testNode->getRuleTerm())) {
             Print("Criterion 2 NOT passed!\n");
             return true;
@@ -272 +357 @@
 =================================================================================================================
 */
-bool criterion2(poly* t, LPoly* l, RList* rules, Rule* lastRuleTested) {
-    // start at the previously added element to gPrev, as all other elements will have the same index for sure
+bool criterion2(poly t, LPoly* l, RList* rules, Rule* lastRuleTested) {
+    Print("------------------------------IN CRITERION 2-----------------------------------------\n");
+    Print("LAST RULE TESTED: %p",lastRuleTested);
+    Print("RULES: \n");
+        RNode* tempR    =   rules->getFirst();
+        while(NULL != tempR->getRule()) {
+            pWrite(tempR->getRuleTerm());
+            Print("%d\n\n",tempR->getRuleIndex());
+            tempR   =   tempR->getNext();
+        }
+        Print("TESTED ELEMENT: ");
+        pWrite(l->getPoly());
+        pWrite(ppMult_qq(t,l->getTerm()));
+        Print("%d\n\n",l->getIndex());
+// start at the previously added element to gPrev, as all other elements will have the same index for sure
         RNode* testNode =   rules->getFirst();
     // save the monom t1*label_term(l) as it is tested various times in the following
-    poly u1 = ppMult_qq(*t,l->getTerm());
+    poly u1 = ppMult_qq(t,l->getTerm());
         // first element added to rTag was NULL, check for this
-        while(NULL != testNode->getRule() && l->getRule() != lastRuleTested) {
-        if(pLmDivisibleBy(testNode->getRuleTerm(),ppMult_qq(*t,l->getTerm()))) {
+        while(NULL != testNode->getRule() && testNode->getRule() != lastRuleTested) {
+        pWrite(testNode->getRuleTerm());
+        if(pLmDivisibleBy(testNode->getRuleTerm(),ppMult_qq(t,l->getTerm()))) {
             Print("Criterion 2 NOT passed!\n");
             return true;
@@ -285 +384 @@
                 testNode    =   testNode->getNext();
     }
+    lastRuleTested = testNode->getRule();
     return false;
 }
@@ -302 +402 @@
         // only if a new rule was added since the last test in subalgorithm criticalPair()
         //if(rules->getFirst() != rTag->getFirst()) {
-            Print("IN SPOLS => NEW RULES AVAILABLE\n");
-            if(!criterion2(temp->getAdT1(),temp->getAdLp1(),rules,temp->getLastRuleTested())) {
+            if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getLastRuleTested())) {
                 // the second component is tested only when it has the actual index, otherwise there is
                 // no new rule to test since the last test in subalgorithm criticalPair()
                 if(temp->getLp2Index() == temp->getLp1Index()) {
-                    if(!criterion2(temp->getAdT2(),temp->getAdLp2(),rules,temp->getLastRuleTested())) {
+                    if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getLastRuleTested())) {
                         // computation of S-polynomial
                         sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
@@ -324 +423 @@
                                                         reductionsToZero++;
                             rules->insert(temp->getLp1Index(),temp->getT1());
+                            Print("RULE ADDED: \n");
+                            pWrite(rules->getFirst()->getRuleTerm());
                             // as sp = NULL, delete it
                             delete(&sp);
@@ -329 +430 @@
                         else {
                             rules->insert(temp->getLp1Index(),temp->getT1());
-                            sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
+                            Print("RULE ADDED: \n");
+                            pWrite(rules->getFirst()->getRuleTerm());  
+                            sPolyList->insertSP(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
                         }
                         // data is saved in sPolyList or zero => delete sp
@@ -339 +442 @@
                                      ppMult_qq(temp->getT2(),temp->getLp2Poly()));
                     Print("BEGIN SPOLY2\n====================\n");
+                    pNorm(sp);
                     pWrite(sp);
                     Print("END SPOLY2\n====================\n");
@@ -349 +453 @@
                         reductionsToZero++;
                         rules->insert(temp->getLp1Index(),temp->getT1());
+                        Print("RULE ADDED: \n");
+                        pWrite(rules->getFirst()->getRuleTerm()); 
                         // as sp = NULL, delete it
                         delete(&sp);
@@ -354 +460 @@
                     else {
                         rules->insert(temp->getLp1Index(),temp->getT1());
-                        sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
+                        Print("RULE ADDED: \n");
+                        pWrite(rules->getFirst()->getRuleTerm()); 
+                        Print("%p\n",sPolyList->getFirst());
+                        sPolyList->insertSP(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
                     }
                     // data is saved in sPolyList or zero => delete sp
@@ -375 +484 @@
 ========================================================================
 */
-void reduction(LList* sPolyList, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, 
+void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, 
                  ideal gbPrev) { 
     Print("##########################################In REDUCTION!########################################\n");
-     // LNode* saving the last element in gPrev before the completed elements from the reduction process are added
-    // this is needed to get the new critical pairs computed
-    LNode* gPrevTag = gPrev->getLast();
-    //for debugging
-    pWrite(gPrevTag->getPoly());
     // check if sPolyList has any elements
     // NOTE: due to initialization sPolyList always has a default NULL element
-    while(sPolyList->getLength() > 1) {
+    while(sPolyList->getLength() > 0) {
+        Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength());
+        sPolyList->print();
         // temp is the first element in the sPolyList which should be reduced
         // due to earlier sorting this is the element of minimal degree AND 
         // minimal label
         LNode* temp =   sPolyList->getFirst();
+        pWrite(temp->getPoly());
         // delete the above first element from sPolyList, temp will be either reduced to
         // zero or added to gPrev, but never come back to sPolyList
         sPolyList->setFirst(temp->getNext());
+        Print("HALLO %p\n",temp->getPoly());
+        Print("%p\n",temp->getPoly());
         pWrite(temp->getPoly());
         poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly());
@@ -404 +513 @@
             // with label index = current label index: this is done such that there 
             // is no label corruption during the reduction process
-            topReduction(temp,completed,gPrev,rules,lTag,rTag);
+            topReduction(temp,sPolyList,gPrev,rules,lTag,rTag);
+        LNode* tempLoop = gPrev->getFirst();
+                while(NULL != tempLoop) {
+                    pWrite(tempLoop->getPoly());
+                    tempLoop = tempLoop->getNext();
+                    }
+        }
+        if(NULL != temp->getPoly()) {
+            //CList* newCritPairs = new CList;
+            criticalPair(gPrev,critPairs,lTag,rTag,rules);
+        }
+        else {
+            delete temp;
         }
     }
@@ -417 +538 @@
 =====================================================================================
 */
-void topReduction(LNode* l, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag) {
+void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag) {
     Print("##########################################In topREDUCTION!########################################\n");
-
+    // try l as long as there are reductors found by findReductor()
+    do {
+        LNode* tempRed  =   new LNode();
+        tempRed  =   findReductor(l,gPrev,rules,lTag,rTag);
+        // if a reductor for l is found and saved in tempRed
+        if(NULL != tempRed) {
+            // if label of reductor is greater than the label of l we have to built a new element
+            // and add it to sPolyList
+            if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) {
+                poly temp   =   pSub(tempRed->getPoly(),l->getPoly());
+                pWrite(temp);
+                if(NULL != temp) {
+                    tempRed->setPoly(temp);
+                    // for debugging
+                    pWrite(tempRed->getPoly());
+                    Print("RULE ADDED\n");
+                    rules->insert(tempRed->getIndex(),tempRed->getTerm());
+                    
+                    tempRed->getLPoly()->setRule(rules->getFirst()->getRule());
+                    sPolyList->insertByLabel(tempRed);
+                }
+                else {
+                    pDelete(&temp);
+                    reductionsToZero++;
+                    Print("RULE ADDED\n");
+                    rules->insert(tempRed->getIndex(),tempRed->getTerm());
+                    delete tempRed;
+                }
+            }
+            // label of reductor is smaller than the label of l, subtract reductor from l and delete the 
+            // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes 
+            // after subtraction 
+            else {
+                poly temp   =   pSub(l->getPoly(),tempRed->getPoly());
+                pWrite(temp);
+                if(NULL != temp) {
+                    l->setPoly(temp);
+                    l->setGPrevRedCheck(NULL);
+                }
+                else {
+                    pDelete(&temp);
+                    l->setPoly(NULL);
+                }
+            }    
+        }
+        else {
+            if(NULL != l->getPoly()) {
+                Print("ADDED TO GPREV IN TOPREDUCTION: ");
+                pWrite(l->getPoly());
+                gPrev->insert(l->getLPoly());
+                Print("GPREV: \n");
+                LNode* tempLoop = gPrev->getFirst();
+                while(NULL != tempLoop) {
+                    pWrite(tempLoop->getPoly());
+                    tempLoop = tempLoop->getNext();
+                }
+            }
+            break;
+        }
+    } while(1);
 }
 
@@ -428 +608 @@
 =====================================================================
 */
-LNode* findReductor(LNode* l,LList* completed,LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag,
-                    LNode* gPrevRedCheck) {
-   Print("HIER DU NULL!\n");
-    return NULL;
+LNode* findReductor(LNode* l, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag) {
+    // allociation of memory for the possible reductor
+    poly u      =   pOne();
+    poly red    =   pOne();
+    number nOne =   nInit(1);
+    LNode* temp =   new LNode();
+    // head term of actual element such that we do not have to call pHead at each new reductor test
+    poly t      =   pHead(l->getPoly());
+    // if l was already checked use the information in gPrevRedCheck such
+    // that we can start searching for new reducers from this point and 
+    // not from the first element of gPrev with the current index
+    if(NULL != l->getGPrevRedCheck()) {
+        temp    =   l->getGPrevRedCheck()->getNext();
+    }
+    // no reductors were searched for l before, thus start at the first
+    // element of gPrev with the current index, tagged by lTag
+    else {
+        temp    =   lTag->getFirstCurrentIdx();
+    }
+    // search for reductors until we are at the end of gPrev resp. at the
+    // end of the elements of the current index
+    while(NULL != temp && temp->getIndex() == l->getIndex()) {
+        // does the head of the element of gPrev divides the head of
+        // the to be reduced element?
+        if(pLmDivisibleByNoComp(temp->getPoly(),t)) {
+            // get all the information needed for the following tests
+            // of the criteria
+            u   =   pDivide(t,pHead(temp->getPoly()));
+            pSetCoeff(u,nOne);
+            red =   ppMult_qq(u,temp->getPoly());
+            pNorm(red);
+            u   =   ppMult_qq(u,temp->getTerm());
+            pSetCoeff(u,nOne);
+            // check if both have the same label
+            if(pLmCmp(u,l->getTerm()) != 0) {
+                // passing criterion2 ?
+                if(!criterion2(u,temp,rules,rTag)) {
+                    // passing criterion1 ?
+                    if(!criterion1(gPrev,u,temp,lTag)) {
+                            l->setGPrevRedCheck(temp);
+                            LNode* redNode  =   new LNode(u,temp->getIndex(),red,NULL,NULL);
+                            return redNode;
+                    }
+                }
+            }
+        }
+        temp = temp->getNext();
+    }
+    
+//    delete temp;
+   Print("1st gPrev: ");
+    pWrite(gPrev->getFirst()->getPoly());
+    Print("2nd gPrev: ");
+    pWrite(gPrev->getFirst()->getNext()->getPoly());
+ return NULL;
 }
 
@@ -472 +703 @@
 
     lTag->insert(gPrev->getFirst());
+    lTag->setFirstCurrentIdx(gPrev->getFirst());
     // computing the groebner basis of the elements of index < actual index
     gbLength    =   gPrev->getLength();
@@ -482 +714 @@
 
     for(i=2; i<=IDELEMS(id); i++) {
+        LNode* gPrevTag =   gPrev->getLast();
+        Print("Last POlynomial in GPREV: ");
+        Print("%p\n",gPrevTag);    
+        pWrite(gPrevTag->getPoly());
         gPrev   =   F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag);
         // comuting new groebner basis gbPrev
-        ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
-        LNode*  temp    =   gPrev->getFirst();
+        if(gPrev->getLength() > gbLength) {
+            ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);
+        LNode*  temp    =   gPrevTag;
+        Print("%p\n",gPrevTag);    
+        Print("%p\n",gPrev->getLast());    
+        pWrite(temp->getPoly());
+        Print("LENGTH OF GPREV LIST: %d\n",gPrev->getLength());
+        Print("%d\n",gbLength);
         for(j=0;j<=gPrev->getLength()-gbLength-1;j++) {
+            Print("YES\n");
             gbAdd->m[j] =   temp->getPoly();
+            pWrite(temp->getPoly());
             temp        =   temp->getNext();
         }
+        gbLength    =   gPrev->getLength(); 
         gbPrev  =   idAdd(gbPrev,gbAdd);
+        }
         Print("GROEBNER BASIS:\n====================================================\n");
         idShow(gbPrev);

kernel/f5gb.h

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5gb.h,v 1.26 2009-02-16 14:23:42 ederc Exp $ */
+/* $Id: f5gb.h,v 1.27 2009-02-18 20:43:05 ederc Exp $ */
 /*
 * ABSTRACT: f5gb interface
@@ -44 +44 @@
 ================================================================
 */
-CList* criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
+void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
+
+/*
+================================================================
+computes a list of critical pairs for the next reduction process
+first element in gPrev is always the newest element which must
+build critical pairs with all other elements in gPrev
+NOTE: this is a special version for the call inside reduction()
+      which adds to the already existing critical pairs new ones
+================================================================
+*/
+void criticalPairRed(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
 
 /*
@@ -51 +62 @@
 ========================================
 */
-bool criterion1(poly* t, LNode* l, LTagList* lTag);
+bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
 
 /*
@@ -58 +69 @@
 =====================================
 */
-bool criterion2(poly* t, LNode* l, RList* rules, RTagList* rTag);
+bool criterion2(poly t, LNode* l, RList* rules, RTagList* rTag);
 
 /*
@@ -65 +76 @@
 ==========================================================================================================
 */
-bool criterion2(poly* t, LPoly* l, RList* rules, Rule* lastRuleTested);
+bool criterion2(poly t, LPoly* l, RList* rules, Rule* lastRuleTested);
 
 /*
@@ -79 +90 @@
 ========================================================================
 */
-void reduction(LList* sPolyList, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
+void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
                  ideal gbPrev);
 
@@ -88 +99 @@
 =====================================================================================
 */
-void topReduction(LNode* l, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag); 
+void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag); 
 
 /*
@@ -95 +106 @@
 =====================================================================
 */
-LNode* findReductor(LNode* l,LList* completed,LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag,
-                    LNode* gPrevRedCheck);
+LNode* findReductor(LNode* l, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag);
 
 /*

kernel/f5lists.cc

@@ -70 +70 @@
 }
        
-// insert new elements to the list always in front (labeled / classical polynomial view)
+// insert new elements to the list always at the end (labeled / classical polynomial view)
+// needed for list gPrev
 LNode* LNode::insert(LPoly* lp) {
-    Print("HIER\n");
-    LNode* newElement = new LNode(lp, this);
+    Print("INSERTION: \n");
+    Print("LAST GPREV: ");
+    pWrite(this->getPoly());
+LNode* newElement   =   new LNode(lp, NULL);
+    this->next          =   newElement;
     return newElement;
 }
         
 LNode* LNode::insert(poly t, int i, poly p, Rule* r) {
-    LNode* newElement = new LNode(t, i, p, r, NULL, this);
+    LNode* newElement   =   new LNode(t, i, p, r, NULL, NULL);
+    this->next          =   newElement;
     return newElement;
 }
 
-LNode* LNode::append(poly t, int i, poly p, Rule* r) {
-    LNode* newElement   =   new LNode(t,i,p,r,NULL);
-    this->next          =   newElement;
-}
-
+// insert new elements to the list always in front (labeled / classical polynomial view)
+// needed for sPolyList
+LNode* LNode::insertSP(LPoly* lp) {
+    LNode* newElement   =   new LNode(lp, this);
+    return newElement;
+}
+        
+LNode* LNode::insertSP(poly t, int i, poly p, Rule* r) {
+    LNode* newElement   =   new LNode(t, i, p, r, NULL, this);
+    return newElement;
+}
 // insert new elemets to the list w.r.t. increasing labels
 // only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
@@ -122 +133 @@
     return next;
 }
-        
+
 // get the LPoly* out of LNode*
 LPoly* LNode::getLPoly() {
@@ -182 +193 @@
 }
 
+// for debugging
+void LNode::print() {
+    LNode* temp = this;
+    Print("___________________List of S-polynomials______________________:\n");
+    while(NULL != temp->data) {
+        Print("Index: %d\n",temp->getIndex());
+        Print("Term: ");
+        pWrite(temp->getTerm());
+        Print("Poly: ");
+        pWrite(temp->getPoly());
+        Print("\n");
+        temp = temp->next;
+    }
+}
+
+
 /*
 ====================================
@@ -210 +237 @@
 }
 
-// insertion in front of the list
+// insertion at the end of the list, needed for gPrev
 void LList::insert(LPoly* lp) {
-    first = first->insert(lp);
+    last = last->insert(lp);
+    Print("NEW LAST GPREV: ");
+    pWrite(last->getPoly());
     length++;
+    Print("LENGTH %d\n",length);
 }
 
 void LList::insert(poly t,int i, poly p, Rule* r) {
-    first = first->insert(t,i,p,r);
+    last = last->insert(t,i,p,r);
     length++;
-}
-
-void LList::append(poly t, int i, poly p, Rule* r) {
-    last    =   last->append(t,i,p,r);
+    Print("LENGTH %d\n",length);
+}
+
+// insertion in front of the list, needed for sPolyList
+void LList::insertSP(LPoly* lp) {
+    first = first->insertSP(lp);
     length++;
-}
+    Print("LENGTH %d\n",length);
+}
+
+void LList::insertSP(poly t,int i, poly p, Rule* r) {
+    first = first->insertSP(t,i,p,r);
+    length++;
+    Print("LENGTH %d\n",length);
+}
+
 
 void LList::insertByLabel(poly t, int i, poly p, Rule* r) {
     first = first->insertByLabel(t,i,p,r);
     length++;
+    Print("LENGTH %d\n",length);
 }
 
@@ -234 +275 @@
     first = first->insertByLabel(l->getTerm(),l->getIndex(),l->getPoly(),l->getRule());
     length++;
+    Print("LENGTH %d\n",length);
 }
 
@@ -252 +294 @@
 }
 
-LNode* LList::getNext(LNode* l) {
-    return l->getNext();
-}
-
 int LList::getLength() {
     return length;
@@ -261 +299 @@
 
 void LList::setFirst(LNode* l) {
-    LNode* temp =   first;
     first       =   l;
-    delete(temp);
     length--;
 }
 
-
+void LList::print() {
+    first->print();
+}
 
 /*
@@ -302 +340 @@
 LNode* LTagNode::getLNode() {
     return this->data;
+}
+
+LTagNode* LTagNode::getNext() {
+    return next;
 }
 
@@ -329 +371 @@
 LTagList::LTagList() {
     LTagNode* first =   new LTagNode();
+    
     length          =   0;
 }
@@ -343 +386 @@
 }
 
+void LTagList::setFirstCurrentIdx(LNode* l) {
+    firstCurrentIdx =   l;
+}
+
 LNode* LTagList::get(int idx) {
     return first->get(idx, length);
@@ -351 +398 @@
 }
 
+LNode* LTagList::getFirstCurrentIdx() {
+    return firstCurrentIdx;
+}
 
 /*
@@ -579 +629 @@
 void CNode::print() {
     CNode* temp = this;
-    Print("List of critical pairs:\n");
+    Print("___________________List of critical pairs______________________:\n");
     while(NULL != temp->data) {
-        Print("Index: %d\n",temp->getLp1Index());
+        Print("LP1 Index: %d\n",temp->getLp1Index());
         Print("T1: ");
         pWrite(temp->getT1());
-        Print("Lp1 Term: ");
+        Print("LP1 Term: ");
         pWrite(temp->getLp1Term());
-        Print("%d\n",temp->getLp2Index());
+        Print("LP1 Poly: ");
+        pWrite(temp->getLp1Poly());
+        Print("LP2 Index: %d\n",temp->getLp2Index());
+        Print("T2: ");
         pWrite(temp->getT2());
+        Print("LP2 Term: ");
         pWrite(temp->getLp2Term());
+        Print("LP2 Poly: ");
+        pWrite(temp->getLp2Poly());
         Print("\n");
         temp = temp->next;
     }
+}
+
+void CNode::setLastRuleTested(Rule* r) {
+    data->setLastRuleTested(r);
 }
 

kernel/f5lists.h

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5lists.h,v 1.9 2009-02-16 14:23:42 ederc Exp $ */
+/* $Id: f5lists.h,v 1.10 2009-02-18 20:43:05 ederc Exp $ */
 /*
 * ABSTRACT: list interface
@@ -49 +49 @@
                 LNode(LNode* ln);
                 ~LNode();
-        // insert new elements to the list in first place from the labeled / classical polynomial view
+        // insert new elements to the list at the end from the labeled / classical polynomial view
+        // needed for gPrev
         LNode*  insert(LPoly* lp);
         LNode*  insert(poly t, int i, poly p, Rule* r);
-        //appends elements to the end of the list, done in reduction() in f5gb.cc
-        LNode*  append(poly t, int i, poly p, Rule* r);
+        // insert new elements to the list in front from the labeled / classical polynomial view
+        // needed for sPolyList
+        LNode*  insertSP(LPoly* lp);
+        LNode*  insertSP(poly t, int i, poly p, Rule* r);
         // insert new elements to the list with resp. to increasing labels
         // only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
         LNode*  insertByLabel(poly t, int i, poly p, Rule* r);
         // deletes the first elements of the list with the same degree
-        // get next from current LNode
+        // get next & prev from current LNode
         LNode*  getNext();
+        LNode*  getPrev();
         // only used for the S-polys, which are already sorted by increasing degree by CList
         LNode*  deleteByDeg();
@@ -78 +82 @@
         bool    polyTest(poly* p);
         LNode*  getNext(LNode* l);
+        void    print();
 };
 
@@ -96 +101 @@
                 LList(poly t,int i,poly p, Rule* r = NULL);
                 ~LList();
+        // insertion at the end of the list
+        // needed for gPrev
         void    insert(LPoly* lp);
-        // insertion in front of the list
         void    insert(poly t,int i, poly p, Rule* r = NULL);
+         // insertion in front of the list
+        // needed for sPolyList
+        void    insertSP(LPoly* lp);
+        void    insertSP(poly t,int i, poly p, Rule* r = NULL);
         void    insertByLabel(poly t, int i, poly p, Rule* r = NULL);
         void    insertByLabel(LNode* l);
-        void    append(poly t, int i, poly p, Rule* r=NULL);
         void    deleteByDeg();
         bool    polyTest(poly* p);
         LNode*  getFirst();
         LNode*  getLast();
-        LNode*  getNext(LNode* l);
         int     getLength();
         void    setFirst(LNode* l);
+        void    print();
 };
 
@@ -130 +139 @@
         LTagNode*   insert(LNode* l);
         LNode*      getLNode();
+        LTagNode*   getNext();
         LNode*      get(int i, int length);
 };
@@ -142 +152 @@
     private:
         LTagNode*   first;
+        LNode*      firstCurrentIdx;
         int         length;
     public:
@@ -149 +160 @@
         // declaration with first as parameter in LTagNode due to sorting of LTagList
         void    insert(LNode* l);
+        void    setFirstCurrentIdx(LNode* l);
         LNode*  get(int idx);
         LNode*  getFirst();
+        LNode*  getFirstCurrentIdx();
 };
 
@@ -207 +220 @@
         Rule*   getLastRuleTested();
         void    print();
+        void    setLastRuleTested(Rule* r);
 };