/**************************************** * Computer Algebra System SINGULAR * ****************************************/ /* * ABSTRACT: f5gb interface */ #include "kernel/mod2.h" #ifdef HAVE_F5 #include #include #include "kernel/structs.h" #include "kernel/GBEngine/kutil.h" #include "kernel/polys.h" #include "polys/monomials/p_polys.h" #include "polys/templates/p_Procs.h" #include "kernel/ideals.h" #include "kernel/GBEngine/kstd1.h" #include "kernel/GBEngine/khstd.h" #include "polys/kbuckets.h" #include "polys/weight.h" #include "misc/intvec.h" #include "kernel/polys.h" #include "kernel/GBEngine/f5gb.h" #include "kernel/GBEngine/f5data.h" #include "kernel/GBEngine/f5lists.h" #include "kernel/oswrapper/timer.h" #define pDeg(A) p_Deg(A,currRing) VAR int notInG = 0; VAR int numberOfRules = 0; VAR int reductionsToZero = 0; VAR int reductionTime = 0; VAR int spolsTime = 0; VAR int highestDegree = 0; VAR int degreeBound = 0; VAR int numberUsefulPairs = 0; VAR int numberUselessPairs = 0; VAR int numberUsefulPairsMinDeg = 0; VAR int highestDegreeGBCriticalPair = 0; VAR int numberRejectedF5CriticalPairs = 0; VAR int numberOfReductions = 0; VAR int numberOfSpolys = 0; /* ==================================================================== sorting ideals by decreasing total degree "left" and "right" are the pointer of the first and last polynomial in the considered ideal ==================================================================== */ void qsortDegree(poly* left, poly* right) { poly* ptr1 = left; poly* ptr2 = right; poly p1,p2; p2 = *(left + (right - left >> 1)); do { while(p_Totaldegree(*ptr1, currRing) < p_Totaldegree(p2, currRing)) { ptr1++; } while(p_Totaldegree(*ptr2, currRing) > p_Totaldegree(p2,currRing)) { ptr2--; } if(ptr1 > ptr2) { break; } p1 = *ptr1; *ptr1 = *ptr2; *ptr2 = p1; } while(++ptr1 <= --ptr2); if(left < ptr2) { qsortDegree(left,ptr2); } if(ptr1 < right) { qsortDegree(ptr1,right); } } /*! * ====================================================================== * builds the sum of the entries of the exponent vectors, i.e. the degree * of the corresponding monomial * ====================================================================== */ long sumVector(int* v, int k) { int i; long sum = 0; for(i=1; i<=k; i++) { Print("%d\n",v[i]); Print("%ld\n",sum); sum = sum + v[i]; } return sum; } /*! ========================================================================== compares monomials, i.e. divisibility tests for criterion 1 and criterion 2 ========================================================================== */ bool compareMonomials(int* m1, int** m2, int numberOfRules, int k) { int i,j; long sumM1 = sumVector(m1,k); //int k = sizeof(m1) / sizeof(int); for(i=0; im2[i][j]) { return true; } } } } return false; } /* ================================================== computes incrementally gbs of subsets of the input gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1} ================================================== */ LList* F5inc(int i, poly f_i, LList* gPrev, LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag, int plus, int termination) { //Print("in f5inc\n"); //pWrite(rules->getFirst()->getRuleTerm()); int iterationstep = i; int j; //Print("%p\n",gPrev->getFirst()); //pWrite(gPrev->getFirst()->getPoly()); poly tempNF = kNF(gbPrev,currRing->qideal,f_i); f_i = tempNF; //gPrev->insert(ONE,i,f_i); gPrev->insert(ONE,gPrev->getLength()+1,f_i); // tag the first element in gPrev of the current index for findReductor() lTag->setFirstCurrentIdx(gPrev->getLast()); //Print("1st gPrev: "); //pWrite(gPrev->getFirst()->getPoly()); //Print("2nd gPrev: "); //pWrite(gPrev->getFirst()->getNext()->getPoly()); //pWrite(gPrev->getFirst()->getNext()->getPoly()); CListOld* critPairs = new CListOld(); CNode* critPairsMinDeg = new CNode(); PList* rejectedGBList = new PList(); // 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, rejectedGBList, plus); STATIC_VAR LList* sPolyList = new LList(); //sPolyList->print(); // labeled polynomials which have passed reduction() and have to be added to list gPrev STATIC_VAR LList* completed = new LList(); // the reduced labeled polynomials which are returned from subalgorithm reduction() STATIC_VAR LList* reducedLPolys = new LList(); // while there are critical pairs to be further checked and deleted/computed while(NULL != critPairs->getFirst()) { // critPairs->getMinDeg() deletes the first elements of minimal degree from // critPairs, thus the while loop is not infinite. // adds all to be reduced S-polynomials in the list sPolyList and adds // the corresponding rules to the list rules // NOTE: inside there is a second check of criterion 2 if new rules are // added //int timer4 = initTimer(); //startTimer(); //critPairs->print(); //definition of a local numberUsefulPairs variable for the next degree //step: //if in this degree all pairs are useless, skip this degree step //completely! //long arrideg = critPairs->getFirst()->getData()->getDeg(); //if(plus && highestDegreeGBCriticalPair < critPairs->getFirst()->getData()->getDeg()) { // return gPrev; //} //else { critPairsMinDeg = critPairs->getMinDeg(); //numberUsefulPairsMinDeg = computeUsefulMinDeg(critPairsMinDeg); //if(numberUsefulPairs > 0) { //if(numberUsefulPairsMinDeg > 0) { //Print("number of useful pairs: %d\n",numberUsefulPairs); //Print("number of useless pairs: %d\n\n",numberUselessPairs); //Print("Degree of following reduction: %d\n",critPairsMinDeg->getData()->getDeg()); long degreecheck = critPairsMinDeg->getData()->getDeg(); computeSPols(critPairsMinDeg,rTag,rules,sPolyList, rejectedGBList); //} //} //} //else { // return gPrev; //} //timer4 = getTimer(); //Print("SPOLS TIMER: %d\n",timer4); //spolsTime = spolsTime + timer4; // DEBUG STUFF FOR SPOLYLIST LNode* temp = sPolyList->getFirst(); //while(NULL != temp && NULL != temp->getLPoly()) { //Print("Spolylist element: "); //pWrite(temp->getPoly()); //temp = temp->getNext(); //} // reduction process of new S-polynomials and also adds new critical pairs to critPairs //int timer3 = initTimer(); //startTimer(); //sPolyList->print(); //reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev); //Print("BEFORE REDUCTION: \n"); //Print("number of useful pairs: %d\n",numberUsefulPairs); //Print("number of useless pairs: %d\n\n",numberUselessPairs); newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination, rejectedGBList, plus); //Print("ITERATION: %d",iterationstep); //Print("NAECHSTER GRAD: %ld",degreecheck); //sleep(5); //if(i == 5 && pDeg(gPrev->getLast()->getPoly()) == 8) { // Print("RAUS BEI DEG 8 \n"); // return gPrev; //} //Print("ARRIS DEG: %ld\n",arrideg); // Arris idea stated by John in an email //if(arrisCheck(critPairs->getFirst(),gPrev->getFirst(),arrideg)) { // Print("ARRIS DEGREE: %ld\n", arrideg); // return gPrev; //} //bool aha = checkDGB(gPrev); //timer3 = getTimer(); //reductionTime = reductionTime + timer3; //Print("REDUCTION TIMER: %d\n",timer3); // DEBUG STUFF FOR GPREV //temp = gPrev->getFirst(); //int number = 1; //Print("\n\n"); //while(NULL != temp) { // Print("%d. ",number); // pWrite(temp->getPoly()); // temp = temp->getNext(); // number++; // Print("\n"); //} //sleep(5); } //Print("REDUCTION DONE\n"); //Print("%p\n",rules->getFirst()); //Print("%p\n",rTag->getFirst()); //if(rules->getFirst() != rTag->getFirst()) { //Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n"); //rTag->insert(rules->getFirst()); //} //else { //Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n"); //} lTag->insert(lTag->getFirstCurrentIdx()); //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()); //delete sPolyList; //critPairs->print(); delete critPairs; //Print("IN F5INC\n"); /* PrintS("\n\n\nRULES: \n"); RNode* tempR = rules->getFirst(); Print("%p\n",tempR); int t = 1; while(NULL != tempR) { Print("ADDRESS OF %d RNODE: %p\n",t,tempR); Print("ADDRESS OF RULE: %p\n",tempR->getRule()); pWrite(tempR->getRuleTerm()); Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm()); Print("%d\n\n",tempR->getRuleIndex()); tempR = tempR->getNext(); t++; } */ //gPrev->print(); //Print("COMPLETE REDUCTION TIME UNTIL NOW: %d\n",reductionTime); //Print("COMPLETE SPOLS TIME UNTIL NOW: %d\n",spolsTime); degreeBound = 0; return gPrev; } bool checkDGB(LList* gPrev) { Print("D-GB CHECK at degree %ld\n",pDeg(gPrev->getLast()->getPoly())); LNode* temp = gPrev->getFirst(); LNode* temp2; bool isDGb = 0; // construct the d-GB gb ideal gb = idInit(gPrev->getLength(),1); for(int j=0;j<=gPrev->getLength()-1;j++) { gb->m[j] = temp->getPoly(); pWrite(gb->m[j]); temp = temp->getNext(); } /* Kstd1_deg = pDeg(gPrev->getLast()->getPoly()); BITSET save = test; test |= Sy_bit(OPT_DEGBOUND); kStd(); test = save; */ temp = gPrev->getFirst(); while(NULL != temp) { temp2 = temp->getNext(); number nOne = nInit(1); poly lcm = pOne(); poly sp = pOne(); while(NULL != temp2) { pLcm(temp->getPoly(),temp2->getPoly(),lcm); pSetCoeff(lcm,nOne); pSetm(lcm); PrintS("LCM: "); pWrite(lcm); if(pDeg(lcm) <= pDeg(gPrev->getLast()->getPoly())) { poly u1 = pOne(); poly u2 = pOne(); u1 = pMDivide(lcm,temp->getPoly()); pSetCoeff(u1,nOne); u2 = pMDivide(lcm,temp2->getPoly()); pSetCoeff(u2,nOne); sp = ksOldSpolyRedNew(ppMult_qq(u1,temp->getPoly()), ppMult_qq(u2,temp2->getPoly())); pNorm(sp); poly reducer = pOne(); //reducer = gb->m[0]; int i = 0; pWrite(pHead(sp)); while(im[i]; if(pDivisibleBy(reducer,pHead(sp))) { poly uReducer = pOne(); uReducer = pMDivide(lcm,reducer); pSetCoeff(uReducer,nOne); sp = ksOldSpolyRedNew(sp,ppMult_qq(uReducer,reducer)); //pNorm(tempSP); //sp = tempSP; pNorm(sp); pWrite(sp); i = 0; } else { i++; } } pWrite(pHead(sp)); } temp2 = temp2->getNext(); } temp = temp->getNext(); } PrintS("------------------\n"); return isDGb; } /* * Arris Check if we are finished after the current degree step: * Checks all remaining critical pairs, i.e. those of higher degree, * by the two Buchberger criteria. * return value: 0, if all remaining critical pairs are deleted by * Buchberger's criteria * 1, otherwise */ bool arrisCheck(CNode* first, LNode* firstGCurr, long arrideg) { CNode* temp = first; //product criterion check while(NULL != temp) { if(!pLmEqual(pHead(temp->getLp2Poly()),temp->getT1())) { return 0; } temp = temp->getNext(); } // chain criterion LNode* tempPoly = firstGCurr; while(NULL != tempPoly) { LNode* tempPoly2 = tempPoly->getNext(); while(NULL != tempPoly2) { number nOne = nInit(1); poly lcm = pOne(); pLcm(tempPoly->getPoly(),tempPoly2->getPoly(),lcm); pSetCoeff(lcm,nOne); pSetm(lcm); if(pDeg(lcm) > arrideg) { LNode* tempPoly3 = firstGCurr; while(NULL != tempPoly3) { if(tempPoly3 != tempPoly2 && tempPoly3 != tempPoly && pDivisibleBy(tempPoly3->getPoly(),lcm)) { poly lcm1 = pOne(); poly lcm2 = pOne(); pLcm(tempPoly3->getPoly(),tempPoly->getPoly(),lcm1); pSetCoeff(lcm1,nOne); pSetm(lcm1); pLcm(tempPoly3->getPoly(),tempPoly2->getPoly(),lcm2); pSetCoeff(lcm2,nOne); pSetm(lcm2); if(pDeg(lcm1) < pDeg(lcm) && pDeg(lcm2) < pDeg(lcm)) { return 0; } } tempPoly3 = tempPoly3->getNext(); } } tempPoly2 = tempPoly2->getNext(); } tempPoly = tempPoly->getNext(); } return 1; } /* ================================================================ computes a list of critical pairs for the next reduction process the first element is always "useful" thus the critical pair computed is either "useful" or "useless" depending on the second element which generates the critical pair. first element in gPrev is always the newest element which must build critical pairs with all other elements in gPrev ================================================================ */ inline void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList, int plus) { //Print("IN CRITPAIRS\n"); // 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()); RuleOld* testedRuleOld = NULL; //Print("NEW: "); //pWrite(newElement->getPoly()); //Print("ADDRESS: %p",newElement); if(NULL != rules->getFirst()) { testedRuleOld = rules->getFirst()->getRuleOld(); } // computation of critical pairs while( gPrev->getLast() != temp) { //Print("TEMP: "); //pWrite(pHead(temp->getPoly())); //Print("ADDRESS: %p",temp); pLcm(newElement->getPoly(), temp->getPoly(), lcm); pSetCoeff(lcm,nOne); // computing factors u2 for new labels u1 = pMDivide(lcm,t); if(NULL == u1) { break; } pSetCoeff(u1,nOne); u2 = pMDivide(lcm,temp->getPoly()); pSetCoeff(u2,nOne); int degree = pDeg(ppMult_qq(u2,pHead(temp->getPoly()))); // testing both new labels by the F5 Criterion if(!temp->getDel()) { if(plus && highestDegreeGBCriticalPair < degree) { highestDegreeGBCriticalPair = degree; } if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag) && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag) && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) { // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater // label as first element in the CPairOld if(newElement->getIndex() == temp->getIndex() && -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) { CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, temp->getLPolyOld(), u1, newElement->getLPolyOld(), 0 , testedRuleOld); critPairs->insert(cp); // counting the number of useful pairs numberUsefulPairs++; } else { CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, newElement->getLPolyOld(), u2, temp->getLPolyOld(), 0, testedRuleOld); critPairs->insert(cp); // counting the number of useful pairs numberUsefulPairs++; } } else { // TODO: generate a list of lcms of rejected GB critical pairs and // check F5 critical pairs with it at their creation //Print("--------------------------------------------------------------------\n"); //Print("--------------------------------------------------------------------\n"); pSetm(lcm); rejectedGBList->insert(lcm); //Print("-----------------------REJECTED IN CRIT PAIR------------------------\n"); //pWrite(lcm); //Print("--------------------------------------------------------------------\n"); //rejectedGBList->print(); } } else { //Print("LABEL: "); //pWrite(ppMult_qq(u1,newElement->getTerm())); //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag) && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag) && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) { // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater // label as first element in the CPairOld if(newElement->getIndex() == temp->getIndex() && -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) { CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld); critPairs->insert(cp); numberUselessPairs++; } else { CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld); critPairs->insert(cp); numberUselessPairs++; } } //} } temp = temp->getNext(); } } /* ================================================================ computes a list of critical pairs for the next reduction process the first element is always "useless" thus the critical pair computed is "useless". first element in gPrev is always the newest element which must build critical pairs with all other elements in gPrev ================================================================ */ inline void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules, PList* rejectedGBList) { //Print("IN CRITPAIRS\n"); // 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()); RuleOld* testedRuleOld = NULL; if(NULL != rules->getFirst()) { testedRuleOld = rules->getFirst()->getRuleOld(); } // computation of critical pairs while( gPrev->getLast() != temp) { pLcm(newElement->getPoly(), temp->getPoly(), lcm); pSetCoeff(lcm,nOne); // computing factors u2 for new labels u1 = pMDivide(lcm,t); if(NULL == u1) { break; } pSetCoeff(u1,nOne); u2 = pMDivide(lcm,temp->getPoly()); pSetCoeff(u2,nOne); // testing both new labels by the F5 Criterion //Print("LABEL: "); //pWrite(ppMult_qq(u1,newElement->getTerm())); //if(rejectedGBList->check(lcm)) { // if there is equality of lcms then we need the F5 critical pair if(!criterion2(gPrev->getFirst()->getIndex(), u2, temp, rules, rTag) && !criterion2(gPrev->getFirst()->getIndex(), u1, newElement, rules, rTag) && !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) { // if they pass the test, add them to CListOld critPairs, having the LPolyOld with greater // label as first element in the CPairOld if(newElement->getIndex() == temp->getIndex() && -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) { CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld); critPairs->insert(cp); numberUselessPairs++; } else { CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld); critPairs->insert(cp); numberUselessPairs++; } } //} temp = temp->getNext(); } } /* ======================================== Criterion 1, i.e. Faugere's F5 Criterion ======================================== */ inline 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 int idx = l->getIndex(); int i; if(idx == 1) { //Print("HIER\n"); 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(l->getTerm()); //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"); if(idx != gPrev->getLast()->getIndex()) { //Print("DOCH!\n"); } return true; } //pWrite(testNode->getNext()->getPoly()); testNode = testNode->getNext(); } /* ideal testId = idInit(idx-1,1); for(i=0;im[i] = pHead(testNode->getPoly()); testNode = testNode->getNext(); } poly temp = kNF(testId,currRing->qideal,u1); //pWrite(temp); for(i=0;im[i] = NULL; } idDelete(&testId); if(NULL == temp) { //if(l->getIndex() != gPrev->getFirst()->getIndex()) { // Print("----------------------------Criterion1 not passed----------------------------------\n"); //} return true; } */ return false; } } /* ===================================== Criterion 2, i.e. Rewritten Criterion ===================================== */ inline bool criterion2(int idx, poly t, LNode* l, RList* rules, RTagList* rTag) { //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n"); /* PrintS("RULES: \n"); RNode* tempR = rules->getFirst(); Print("%p\n",tempR); int i = 1; while(NULL != tempR) { Print("ADDRESS OF %d RNODE: %p\n",i,tempR); Print("ADDRESS OF RULE: %p\n",tempR->getRule()); pWrite(tempR->getRuleTerm()); Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm()); Print("%d\n\n",tempR->getRuleIndex()); tempR = tempR->getNext(); i++; } //Print("TESTED ELEMENT: "); //pWrite(l->getPoly()); //pWrite(l->getTerm()); //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 if(idx > l->getIndex()) { return false; } RNode* testNode; // = new RNode(); testNode = rules->getFirst(); /* if(NULL == rTag->getFirst()) { if(NULL != rules->getFirst()) { testNode = rules->getFirst(); } else { return false; } } else { if(l->getIndex() > rTag->getFirst()->getRuleIndex()) { testNode = rules->getFirst(); } else { //Print("HIER\n"); //Print("DEBUG\n"); //Print("L INDEX: %d\n",l->getIndex()); *------------------------------------- * TODO: WHEN INTERREDUCING THE GB THE * INDEX OF THE PREVIOUS ELEMENTS * GETS HIGHER! *-----------------------------------* //testNode = rules->getFirst(); testNode = rTag->get(l->getIndex()); if(NULL == testNode) { testNode = rules->getFirst(); } //Print("TESTNODE ADDRESS: %p\n",testNode); } } */ //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()); // first element added to rTag was NULL, check for this //Print("%p\n",testNode->getRule()); // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1! //Print("TESTNODE: %p\n",testNode); //pWrite(testNode->getRuleTerm()); if(NULL != testNode ) { //pWrite(testNode->getRuleTerm()); } if(NULL != testNode) { if(testNode->getRuleOld() == l->getRuleOld()) { //Print("%p\n%p\n",testNode->getRule(),l->getRule()); //Print("EQUAL\n"); } else { //Print("NOT EQUAL\n"); } } while(NULL != testNode && testNode->getRuleOld() != l->getRuleOld() && l->getIndex() == testNode->getRuleOldIndex()) { //Print("%p\n",testNode); //pWrite(testNode->getRuleTerm()); //pWrite(t); //pWrite(l->getTerm()); //pWrite(u1); //Print("%d\n",testNode->getRuleIndex()); if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) { //Print("-----------------Criterion 2 NOT passed!-----------------------------------\n"); //Print("INDEX: %d\n",l->getIndex()); pDelete(&u1); //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n"); return true; } testNode = testNode->getNext(); } //delete testNode; pDelete(&u1); //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n"); return false; } /* ================================================================================================================= Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter ================================================================================================================= */ inline bool criterion2(poly t, LPolyOld* l, RList* rules, RuleOld* testedRuleOld) { //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n"); //Print("LAST RuleOld TESTED: %p",testedRuleOld); /* PrintS("RULES: \n"); RNode* tempR = rules->getFirst(); while(NULL != tempR) { pWrite(tempR->getRuleTerm()); Print("%d\n\n",tempR->getRuleIndex()); tempR = tempR->getNext(); } //Print("TESTED ELEMENT: "); //pWrite(l->getPoly()); //pWrite(l->getTerm()); //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()); // first element added to rTag was NULL, check for this while(NULL != testNode && testNode->getRuleOld() != testedRuleOld) { //pWrite(testNode->getRuleTerm()); if(pLmDivisibleByNoComp(testNode->getRuleOldTerm(),u1)) { //Print("--------------------------Criterion 2 NOT passed!------------------------------\n"); //Print("INDEX: %d\n",l->getIndex()); pDelete(&u1); //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n"); return true; } testNode = testNode->getNext(); } pDelete(&u1); //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n"); return false; } /* * check for useful pairs in the given subset of critical pairs */ int computeUsefulMinDeg(CNode* first) { CNode* temp = first; int numberUsefulPairsMinDeg = 0; while(NULL != temp) { if(!temp->getDel()) { numberUsefulPairsMinDeg++; } temp = temp->getNext(); } return numberUsefulPairsMinDeg; } /* ================================== Computation of S-Polynomials in F5 ================================== */ void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList, PList* rejectedGBList) { CNode* temp = first; //Print("\nDegree: %d\n",temp->getData()->getDeg()); // only GB-critical pairs are computed //while(NULL != temp && temp->getDel()) { // temp = temp->getNext(); //} //if(temp->getData()->getDeg() == 11) { // Print("PAIRS OF DEG 11:\n"); //} RList* f5rules = new RList(); CListOld* f5pairs = new CListOld(); poly sp = pInit(); number sign = nInit(-1); //Print("###############################IN SPOLS##############################\n"); //first->print(); /* * first of all: do everything for GB critical pairs */ while(NULL != temp) { // if(temp->getData()->getDeg() == 11) { //Print("--------------------------\n"); //Print("redundant? %d\n",temp->getDel()); //pWrite(pHead(temp->getLp1Poly())); //Print("redundant: %d\n",temp->getAdLp1()->getDel()); //pWrite(pHead(temp->getLp2Poly())); //Print("redundant: %d\n",temp->getAdLp2()->getDel()); //pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly()))); // sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), // ppMult_qq(temp->getT2(),temp->getLp2Poly())); //Print("BEGIN SPOLY2\n====================\n"); // pNorm(sp); // pWrite(pHead(sp)); //Print("--------------------------\n"); //} if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) { //if(temp->getDel() == 0 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) { if(temp->getLp2Index() == temp->getLp1Index()) { if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) { sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), ppMult_qq(temp->getT2(),temp->getLp2Poly())); pNorm(sp); if(NULL == sp) { reductionsToZero++; rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; pDelete(&sp); } else { rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld()); //Print("INSERTED\n"); numberOfSpolys++; } } else { if(highestDegreeGBCriticalPair < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) { highestDegreeGBCriticalPair = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly())); } rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly()))); //Print("rejected!\n"); //Print("CRITERION 2 in SPOLS 2nd generator\n"); } } else { sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), ppMult_qq(temp->getT2(),temp->getLp2Poly())); //Print("BEGIN SPOLY2\n====================\n"); pNorm(sp); //pWrite(sp); //Print("END SPOLY2\n====================\n"); if(NULL == sp) { reductionsToZero++; rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; pDelete(&sp); } else { rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld()); //Print("INSERTED\n"); numberOfSpolys++; } } } /* if(temp->getDel() == 0 && criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) { //Print("rejected!\n"); rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly()))); } if(temp->getDel() == 1 && !criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) { if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) { highestDegree = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly())); } if(temp->getLp2Index() == temp->getLp1Index()) { if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) { sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), ppMult_qq(temp->getT2(),temp->getLp2Poly())); pNorm(sp); if(NULL == sp) { reductionsToZero++; rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; pDelete(&sp); } else { rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; // save the address of the rule again in a different // list f5rules->insert(rules->getFirst()->getRuleOld()); f5pairs->insertWithoutSort(temp->getData()); /////////////////////////////////////// //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld()); } } } else { sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), ppMult_qq(temp->getT2(),temp->getLp2Poly())); //Print("BEGIN SPOLY2\n====================\n"); pNorm(sp); //pWrite(sp); //Print("END SPOLY2\n====================\n"); if(NULL == sp) { reductionsToZero++; //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; pDelete(&sp); } else { rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; // save the address of the rule again in a different // list f5rules->insert(rules->getFirst()->getRuleOld()); f5pairs->insertWithoutSort(temp->getData()); /////////////////////////////////////// //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld()); // numberOfSpolys++; } } } // the following else is not needed at all as we are checking // F5-critical pairs in this step /* else { if(!temp->getDel()) { rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly()))); } } */ temp = temp->getNext(); } /* temp = f5pairs->getFirst(); RNode* tempRule = f5rules->getFirst(); int howmany = 1; while(NULL != temp) { //Print("RULE: "); //pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term())); sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), ppMult_qq(temp->getT2(),temp->getLp2Poly())); pNorm(sp); if(rejectedGBList->check(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())))) { //|| (temp->getData()->getDeg() == 10 && howmany == 2)) { if((temp->getData()->getDeg() == 10) && (howmany == 2)) { //Print("HIER DRIN IM SAFTLADEN\n"); } sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld()); numberOfSpolys++; howmany++; } else { numberRejectedF5CriticalPairs++; howmany++; if(numberRejectedF5CriticalPairs < -1) { // || } else { //numberRejectedF5CriticalPairs == 7) { /* PrintS("--------------------------------- rejected F5-critical pair-------------------------------------\n"); pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly()))); PrintS("Label: "); pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term())); Print("%d\n",temp->getDel()); PrintS("Comes from:\n "); pWrite(pHead(temp->getLp1Poly())); PrintS("Label: "); pWrite(temp->getLp1Term()); Print("%d\n",temp->getLp1Index()); pWrite(pHead(temp->getLp2Poly())); PrintS("Label: "); pWrite(temp->getLp2Term()); Print("%d\n",temp->getLp2Index()); //Print("--------------------------------------LIST OF GB PAIRS REJECTED-----------------------------------------\n"); //rejectedGBList->print(); PrintS("--------------------------------------------------------------------------------------------------------\n"); //if(temp->getLp1Index() < 7) { sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,tempRule->getRuleOld()); //} //numberOfSpolys++; } //pSetExp(tempRule->getRuleOld()->getTerm(),1,1000); } temp = temp->getNext(); tempRule = tempRule->getNext(); } */ // these critical pairs can be deleted now as they are either useless for further computations or // already saved as an S-polynomial to be reduced in the following delete first; //Print("NUMBER SPOLYS: %d\n", numberOfSpolys); //Print("SPOLY LIST: \n"); //LNode* tempSpoly = sPolyList->getFirst(); //if(NULL != tempSpoly) { // pWrite(pHead(tempSpoly->getPoly())); // tempSpoly = tempSpoly->getNext(); //} //Print("-----SP------\n"); //else { // Print("EMPTY SPOLYLIST!\n"); //} } /* ======================================================================== reduction including subalgorithm topReduction() using Faugere's criteria ======================================================================== */ void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, PList* rejectedGBList, int plus) { //Print("##########################################In REDUCTION!########################################\n"); // check if sPolyList has any elements // NOTE: due to initialization sPolyList always has a default NULL element LNode* temp = sPolyList->getFirst(); while(NULL != temp) { // 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 // delete the above first element from sPolyList, temp will be either reduced to // zero or added to gPrev, but never come back to sPolyList //pWrite(sPolyList->getFirst()->getPoly()); //Print("LIST OF SPOLYNOMIALS!\n"); //sPolyList->print(); sPolyList->setFirst(temp->getNext()); poly tempNF = kNF(gbPrev,currRing->qideal,temp->getPoly()); if(NULL != tempNF) { pNorm(tempNF); temp->setPoly(tempNF); // try further reductions of temp with polynomials in gPrev // with label index = current label index: this is done such that there // is no label corruption during the reduction process //Print("lower label reduction: "); //pWrite(tempNF); topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus); } else { reductionsToZero++; delete temp; } //if(NULL != temp->getPoly()) { // criticalPair(gPrev,critPairs,lTag,rTag,rules); //} temp = sPolyList->getFirst(); } //sPolyList->print(); //delete sPolyList; } /* ======================================================================== reduction including subalgorithm topReduction() using Faugere's criteria ======================================================================== */ void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, int termination, PList* rejectedGBList, int plus) { //Print("##########################################In REDUCTION!########################################\n"); // check if sPolyList has any elements // NOTE: due to initialization sPolyList always has a default NULL element //Print("--1--\n"); LNode* temp = sPolyList->getFirst(); //Print("START OF REDUCTION: "); while(NULL != temp) { numberOfReductions++; // 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 // delete the above first element from sPolyList, temp will be either reduced to // zero or added to gPrev, but never come back to sPolyList //Print("LIST OF SPOLYNOMIALS!\n"); //sPolyList->print(); //pWrite(sPolyList->getFirst()->getPoly()); sPolyList->setFirst(temp->getNext()); //if(pDeg(temp->getPoly()) > 11) { // Print("YES!!!!!!!!!!!!!!!!\n"); //} //pWrite(temp->getPoly()); //poly tempNF = kNF(gbPrev,currRing->qideal,temp->getPoly()); //Print("!!!\n"); //if(NULL != tempNF) { //pNorm(tempNF); //temp->setPoly(tempNF); //Print("lower label reduction: "); //pWrite(tempNF); // try further reductions of temp with polynomials in gPrev // with label index = current label index: this is done such that there // is no label corruption during the reduction process findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus); //} //else { // reductionsToZero++; // delete temp; //} //if(NULL != temp->getPoly()) { // criticalPair(gPrev,critPairs,lTag,rTag,rules); //} //Print("HIER AUCH ?\n"); //Print("--2--\n"); //sPolyList->print(); //critPairs->print(); temp = sPolyList->getFirst(); //Print("%p\n",temp); } //sPolyList->print(); //delete sPolyList; //Print("REDUCTION FERTIG\n"); } /*! * ================================================================================ * searches for reducers of temp similar to the symbolic preprocessing of F4 and * divides them into a "good" and "bad" part: * * the "good" ones are the reducers which do not corrupt the label of temp, with * these the normal form of temp is computed * * the "bad" ones are the reducers which corrupt the label of temp, they are tested * later on for possible new rules and S-polynomials to be added to the algorithm * ================================================================================ */ void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, LList* reducers, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination, PList* rejectedGBList, int plus) { int canonicalize = 0; //int timerRed = 0; bool addToG = 1; number sign = nInit(-1); LList* good = new LList(); LList* bad = new LList(); LList* monomials = new LList(l->getLPolyOld()); poly u = pOne(); number nOne = nInit(1); LNode* tempRed = lTag->getFirstCurrentIdx(); LNode* tempMon = monomials->getFirst(); poly tempPoly = pInit(); poly redPoly = NULL; int idx = l->getIndex(); //Print("IN FIND REDUCERS: "); //pWrite(l->getPoly()); tempPoly = pCopy(l->getPoly()); //tempMon->setPoly(tempPoly); //while(NULL != tempMon) { // iteration over all monomials in tempMon kBucket* bucket = kBucketCreate(currRing); kBucketInit(bucket,tempPoly,0); tempPoly = kBucketGetLm(bucket); //Print("\n\n\nTO BE REDUCED: "); //pWrite(l->getPoly()); //pWrite(l->getTerm()); //pWrite(tempPoly); while(NULL != tempPoly) { // iteration of all elements in gPrev of the current index tempRed = gPrev->getFirst(); while(NULL != tempRed) { //Print("TEMPREDPOLY: "); //pWrite(tempRed->getPoly()); if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) { u = pMDivideM(tempPoly,tempRed->getPoly()); //Print("U: "); //pWrite(u); if(pLmCmp(u,pOne()) != 0) { // else u = 1 and no test need to be done! if(tempRed->getIndex() != idx) { // passing criterion1 ? if(!criterion1(gPrev,u,tempRed,lTag)) { poly tempRedPoly = tempRed->getPoly(); //Print("REDUCER: "); //pWrite(tempRedPoly); pIter(tempRedPoly); int lTempRedPoly = pLength(tempRedPoly); kBucketExtractLm(bucket); kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly); canonicalize++; //Print("Reduction\n"); if(!(canonicalize % 50)) { kBucketCanonicalize(bucket); } tempPoly = kBucketGetLm(bucket); //Print("TEMPPOLY: "); //pWrite(tempPoly); if(NULL != tempPoly) { tempRed = gPrev->getFirst(); continue; } else { break; } } } else { if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) { //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n"); //pWrite(u); //pWrite(tempRed->getTerm()); //pWrite(pHead(tempRed->getPoly())); addToG = 0; } if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) { // passing criterion2 ? if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) { // passing criterion1 ? if(!criterion1(gPrev,u,tempRed,lTag)) { if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) { if(NULL == redPoly) { bad->insert(tempRed->getLPolyOld()); addToG = 1; //poly tempRedPoly = tempRed->getPoly(); //break; } } else { poly tempRedPoly = tempRed->getPoly(); //Print("REDUCER: "); //pWrite(tempRedPoly); pIter(tempRedPoly); int lTempRedPoly = pLength(tempRedPoly); //Print("HEAD MONOMIAL KBUCKET: "); //pWrite(kBucketGetLm(bucket)); kBucketExtractLm(bucket); kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly); canonicalize++; //Print("REDUCTION\n"); addToG = 1; if(!(canonicalize % 50)) { kBucketCanonicalize(bucket); } //Print("HEAD MONOMIAL KBUCKET: "); //pWrite(kBucketGetLm(bucket)); tempPoly = kBucketGetLm(bucket); //Print("TEMPPOLY: "); //pWrite(tempPoly); if(NULL != tempPoly) { tempRed = gPrev->getFirst(); continue; } else { break; } } } } else { //Print("CRIT 1 "); if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) { //Print("NOT ALLOWED REDUCER, CRIT 1:\n"); //pWrite(u); //pWrite(tempRed->getTerm()); //pWrite(tempRed->getPoly()); if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) { //Print("REDUCER LABEL: "); //pWrite(tempRed->getTerm()); addToG = 0; } } } } else { //Print("CRIT 2 "); if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) { //Print("NOT ALLOWED REDUCER, CRIT 2:\n"); //pWrite(u); //pWrite(tempRed->getTerm()); //pWrite(tempRed->getPoly()); if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) { //Print("REDUCER LABEL: "); //pWrite(tempRed->getTerm()); addToG = 0; } } } } } else { // u = 1 => reduce without checking criteria poly tempRedPoly = tempRed->getPoly(); //Print("REDUCER: "); //pWrite(tempRedPoly); pIter(tempRedPoly); int lTempRedPoly = pLength(tempRedPoly); kBucketExtractLm(bucket); kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly); canonicalize++; //Print("Reduction\n"); if(!(canonicalize % 50)) { kBucketCanonicalize(bucket); } tempPoly = kBucketGetLm(bucket); //Print("TEMPPOLY: "); //pWrite(tempPoly); if(NULL != tempPoly) { tempRed = gPrev->getFirst(); continue; } else { break; } } } tempRed = tempRed->getNext(); } // reduction process with elements in LList* reducers if(NULL != tempPoly) { //Print("HERE\n"); tempRed = reducers->getFirst(); while(NULL != tempRed) { //Print("TEMPREDPOLY: "); //pWrite(tempRed->getPoly()); //pWrite(tempPoly); if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) { //Print("A\n"); u = pMDivideM(tempPoly,tempRed->getPoly()); //Print("U: "); //pWrite(u); if(tempRed->getIndex() != idx) { // passing criterion1 ? if(!criterion1(gPrev,u,tempRed,lTag)) { poly tempRedPoly = tempRed->getPoly(); //Print("REDUCER: "); //pWrite(ppMult_qq(u,tempRedPoly)); pIter(tempRedPoly); int lTempRedPoly = pLength(tempRedPoly); kBucketExtractLm(bucket); kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly); canonicalize++; //Print("Reduction\n"); if(!(canonicalize % 50)) { kBucketCanonicalize(bucket); } tempPoly = kBucketGetLm(bucket); //Print("TEMPPOLY: "); //pWrite(tempPoly); if(NULL != tempPoly) { tempRed = gPrev->getFirst(); continue; } else { break; } } } else { if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 0) { //Print("NOT ALLOWED REDUCER, EQUAL LABELS:\n"); //pWrite(u); //pWrite(tempRed->getTerm()); //pWrite(pHead(tempRed->getPoly())); //addToG = 0; } if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) != 0) { // passing criterion2 ? if(!criterion2(gPrev->getFirst()->getIndex(), u,tempRed,rules,rTag)) { // passing criterion1 ? if(!criterion1(gPrev,u,tempRed,lTag)) { if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) { if(NULL == redPoly) { bad->insert(tempRed->getLPolyOld()); addToG = 1; //poly tempRedPoly = tempRed->getPoly(); //break; } } else { poly tempRedPoly = tempRed->getPoly(); //Print("REDUCER: "); //pWrite(ppMult_qq(u,tempRedPoly)); pIter(tempRedPoly); int lTempRedPoly = pLength(tempRedPoly); //Print("HEAD MONOMIAL KBUCKET: "); //pWrite(kBucketGetLm(bucket)); kBucketExtractLm(bucket); kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lTempRedPoly); canonicalize++; //Print("REDUCTION\n"); addToG = 1; if(!(canonicalize % 50)) { kBucketCanonicalize(bucket); } //Print("HEAD MONOMIAL KBUCKET: "); //pWrite(kBucketGetLm(bucket)); tempPoly = kBucketGetLm(bucket); //Print("TEMPPOLY: "); //pWrite(tempPoly); if(NULL != tempPoly) { tempRed = gPrev->getFirst(); continue; } else { break; } } } } else { //Print("CRIT 1 "); if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1 ) { //Print("NOT ALLOWED REDUCER, CRIT 1:\n"); //pWrite(u); //pWrite(tempRed->getTerm()); //pWrite(tempRed->getPoly()); if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) { //Print("REDUCER LABEL: "); //pWrite(tempRed->getTerm()); addToG = 0; } } } } else { //Print("CRIT 2 "); if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) { //Print("NOT ALLOWED REDUCER, CRIT 2:\n"); //pWrite(u); //pWrite(tempRed->getTerm()); //pWrite(tempRed->getPoly()); if(pLmDivisibleByNoComp(tempRed->getTerm(),l->getTerm())) { //Print("REDUCER LABEL: "); //pWrite(tempRed->getTerm()); addToG = 0; } } } } } tempRed = tempRed->getNext(); } } if(NULL != tempPoly) { if(NULL == redPoly) { redPoly = kBucketExtractLm(bucket); } else { redPoly = p_Merge_q(redPoly,kBucketExtractLm(bucket),currRing); } // for top-reduction only redPoly = p_Merge_q(redPoly,kBucketClear(bucket),currRing); break; // end for top-reduction only tempPoly = kBucketGetLm(bucket); } } if(NULL == redPoly) { reductionsToZero++; //pDelete(&redPoly); } else { PrintS("\nELEMENT ADDED TO GPREV: "); pNorm(redPoly); if(highestDegree < pDeg(redPoly)) { highestDegree = pDeg(redPoly); } pWrite(pHead(redPoly)); //pWrite(l->getTerm()); //Print("%d\n",canonicalize); l->setPoly(redPoly); // give "l" the label if it is "useful" (addToG = 0) or "useless" // (addToG = 1) l->setDel(!addToG); Print("redundant? %d\n\n",l->getDel()); if(addToG == 0 && termination == 1) { reducers->insert(l->getLPolyOld()); } else { gPrev->insert(l->getLPolyOld()); } //Print("%d\n\n",termination); if(termination == 1) { if(addToG) { //Print("----------------HERE?-----------------\n"); criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus); } else { notInG++; //Print("\nNONONO"); //pWrite(pHead(l->getPoly())); //pWrite(l->getTerm()); } } // case in which all new elements are added to gPrev! // using boolean "addToG" to know if the element is "useful" (0) or // "useless" (1) else { if(!l->getDel()) { criticalPair(gPrev,critPairs,lTag,rTag,rules,rejectedGBList,plus); } else { criticalPair2(gPrev,critPairs,lTag,rTag,rules, rejectedGBList); } } } // if there are "bad" reducers than try to compute new S-polynomials and rules if(NULL != bad->getFirst()) { //Print("BAD STUFF LIST:\n"); //bad->print(); LNode* tempBad = bad->getFirst(); //pWrite(l->getPoly()); while(NULL != tempBad) { if(pDivisibleBy(tempBad->getPoly(),l->getPoly())) { //Print("BAD STUFF\n"); //pWrite(l->getPoly()); //pWrite(tempBad->getPoly()); u = pMDivide(l->getPoly(),tempBad->getPoly()); //Print("MULTIPLIER: "); //pWrite(u); pSetCoeff(u,nOne); if(pLmCmp(ppMult_qq(u,tempBad->getTerm()),l->getTerm()) != 0) { // passing criterion2 ? if(!criterion2(gPrev->getFirst()->getIndex(), u,tempBad,rules,rTag)) { // passing criterion1 ? if(!criterion1(gPrev,u,tempBad,lTag)) { //Print("HIERHIERHIERHIERHIERHIER\n"); rules->insert(tempBad->getIndex(),ppMult_qq(u,tempBad->getTerm())); numberOfRules++; //gPrev->print(); //pWrite(l->getPoly()); poly temp = ksOldSpolyRedNew(ppMult_qq(u,tempBad->getPoly()),l->getPoly()); //pWrite(l->getPoly()); //Print("%p\n",temp); //gPrev->print(); if(NULL != temp) { pNorm(temp); LNode* tempBadNew = new LNode(ppMult_qq(u,tempBad->getTerm()),tempBad->getIndex(),temp,rules->getFirst()->getRuleOld()); //pWrite(temp); //pWrite(tempBadNew->getPoly()); //pWrite(tempBadNew->getTerm()); //pWrite(pHead(tempBadNew->getPoly())); //Print("%p\n",tempBadNew->getPoly()); //tempRed->getLPoly()->setRule(rules->getFirst()->getRule()); tempBadNew->setDel(1); sPolyList->insertByLabel(tempBadNew); //Print("BAD SPOLYLIST: \n"); //sPolyList->print(); } } } } } //Print("HIER\n"); tempBad = tempBad->getNext(); //Print("%p\n",tempBad); } // Print("-------------------BAD STUFF LIST-----------------------------\n"); } //Print("HIER AUCH\n"); //Print("SPOLYLIST IN BAD: \n"); //sPolyList->print(); //Print("END FIND REDUCERS\n"); } /* ======================================================================================= merging 2 polynomials p & q without requiring that all monomials of p & q are different if there are equal monomials in p & q only one of these monomials (always that of p!) is taken into account ======================================================================================= poly p_MergeEq_q(poly p, poly q, const ring r) { assume(p != NULL && q != NULL); p_Test(p, r); p_Test(q, r); #if PDEBUG > 0 int l = pLength(p) + pLength(q); #endif spolyrec rp; poly a = &rp; DECLARE_LENGTH(const unsigned long length = r->CmpL_Size); DECLARE_ORDSGN(const long* ordsgn = r->ordsgn); Top: // compare p and q w.r.t. monomial ordering p_MemCmp(p->exp, q->exp, length, ordsgn, goto Equal, goto Greater , goto Smaller); Equal: a = pNext(a) = p; pIter(p); pIter(q); if(NULL == p) { if(NULL == q) { goto Finish; } else { pNext(a) = q; goto Finish; } } goto Top; Greater: a = pNext(a) = p; pIter(p); if (p==NULL) { pNext(a) = q; goto Finish;} goto Top; Smaller: a = pNext(a) = q; pIter(q); if (q==NULL) { pNext(a) = p; goto Finish;} goto Top; Finish: p_Test(pNext(&rp), r); #if PDEBUG > 0 pAssume1(l - pLength(pNext(&rp)) == 0); #endif return pNext(&rp); } */ /* ===================================================================================== top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of the same index whereas the labels are taken into account ===================================================================================== */ void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, PList* rejectedGBList, int plus) { //Print("##########################################In topREDUCTION!########################################\n"); // try l as long as there are reductors found by findReductor() LNode* gPrevRedCheck = lTag->getFirstCurrentIdx(); LNode* tempRed; poly pOne = pOne(); do { //int timer5 = initTimer(); //startTimer(); //Print("TOP REDUCTION: "); //pWrite(l->getPoly()); tempRed = findReductor(l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag); //timer5 = getTimer(); //reductionTime = reductionTime + timer5; // 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) { // needed sinc pSub destroys the arguments! //poly temp_poly_l = pInit(); //temp_poly_l = pCopy(l->getPoly()); //Print("VORHER: "); //pWrite(tempRed->getPoly()); //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly()); poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly()); rules->insert(tempRed->getIndex(),tempRed->getTerm()); //Print("NACHHER: "); //pWrite(tempRed->getPoly()); //Print("TEMP: "); //pWrite(temp); if(NULL != temp) { pNorm(temp); //tempRed->setPoly(temp); //tempRed->setDel(1); //rules->insert(tempRed->getIndex(),tempRed->getTerm()); LNode* tempRedNew = new LNode(tempRed->getTerm(),tempRed->getIndex(),temp,rules->getFirst()->getRuleOld()); //tempRed->getLPoly()->setRule(rules->getFirst()->getRule()); tempRedNew->setDel(1); sPolyList->insertByLabel(tempRedNew); } else { pDelete(&temp); reductionsToZero++; //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_poly_l = pInit(); //temp_poly_l = pCopy(l->getPoly()); //poly temp = pMinus_mm_Mult_qq(tempRed->getPoly(),pOne,l->getPoly()); //Print("REDUCER: "); //pWrite(tempRed->getPoly()); //pWrite(tempRed->getTerm()); poly temp = ksOldSpolyRedNew(l->getPoly(),tempRed->getPoly()); //Print("REDUCED ELEMENT: "); if(NULL != temp) { pNorm(temp); //pWrite(temp); poly tempNF = kNF(gbPrev,currRing->qideal,temp); pNorm(tempNF); if(NULL == tempNF) { reductionsToZero++; pDelete(&tempNF); l->setPoly(NULL); break; } l->setPoly(tempNF); gPrevRedCheck = lTag->getFirstCurrentIdx(); } else { reductionsToZero++; pDelete(&temp); l->setPoly(NULL); break; } } } else { if(NULL != l->getPoly()) { pNorm(l->getPoly()); //Print("ELEMENT ADDED TO GPREV: "); //pWrite(l->getPoly()); gPrev->insert(l->getLPolyOld()); //Print("TEMP RED == 0 "); //pWrite(l->getPoly()); //pWrite(l->getTerm()); //rules->print(); criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus); //Print("LIST OF CRITICAL PAIRS: \n"); //critPairs->print(); } break; } } while(1); } /* ===================================================================== subalgorithm to find a possible reductor for the labeled polynomial l ===================================================================== */ LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag, PList* rejectedGBList) { // allociation of memory for the possible reductor //Print("LPOLY: "); //pWrite(l->getPoly()); poly u = pOne(); poly red; number nOne = nInit(1); LNode* temp; // 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 temp = gPrevRedCheck; // 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(pHead(temp->getPoly()),t)) { // get all the information needed for the following tests // of the criteria u = pMDivide(t,temp->getPoly()); pSetCoeff(u,nOne); red = ppMult_qq(u,temp->getPoly()); pNorm(red); // check if both have the same label if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) != 0) { // passing criterion2 ? if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) { // passing criterion1 ? if(!criterion1(gPrev,u,temp,lTag)) { gPrevRedCheck = temp->getNext(); LNode* redNode = new LNode(ppMult_qq(u,temp->getTerm()),temp->getIndex(),red,NULL,NULL); return redNode; } } } if(pLmCmp(ppMult_qq(u,temp->getTerm()),l->getTerm()) == 1) { // passing criterion2 ? if(!criterion2(gPrev->getFirst()->getIndex(), u,temp,rules,rTag)) { // passing criterion1 ? if(!criterion1(gPrev,u,temp,lTag)) { poly tempSpoly = ksOldSpolyRedNew(red,l->getPoly()); rules->insert(temp->getIndex(),ppMult_qq(u,temp->getTerm())); gPrevRedCheck = temp->getNext(); if(NULL != tempSpoly) { pNorm(tempSpoly); sPolyList->insertByLabel(ppMult_qq(u,temp->getTerm()),temp->getIndex(),tempSpoly,rules->getFirst()->getRuleOld()); //Print("NEW ONE: "); //pWrite(tempSpoly); //Print("HIER\n"); //sPolyList->print(); //sleep(5); } } } } } //Print("AUCH HIER\n"); temp = temp->getNext(); } // delete temp; return NULL; } /* ========================================================================== MAIN:computes a gb of the ideal i in the ring r with our F5 implementation OPTIONS: INTEGER "opt" is to be set "0" for F5, "1" for F5R, "2" for F5C ========================================================================== */ ideal F5main(ideal id, ring r, int opt, int plus, int termination) { switch(opt) { case 0: PrintS("\nComputations are done by the standard F5 Algorithm"); break; case 1: PrintS("\nComputations are done by the variant F5R of the F5 Algorithm"); break; case 2: PrintS("\nComputations are done by the variant F5C of the F5 Algorithm"); break; default: WerrorS("\nThe option can only be set to \"0\", \"1\" or \"2\":\n\"0\": standard F5 Algorithm\n\"1\": variant F5R\n\"2\": variant F5C\nComputations are aborted!\n"); return id; } int timer = initTimer(); startTimer(); int i,j,k,l; int gbLength; // 1 polynomial for defining initial labels & further tests poly ONE = pOne(); poly pOne = pOne(); number nOne = nInit(1); // tag the first element of index i-1 for criterion 1 //Print("LTAG BEGINNING: %p\n",lTag); // DEBUGGING STUFF START //Print("NUMBER: %d\n",r->N); /* int* ev = new int[r->N +1]; for(i=0;im[i],ev,currRing); //ev2 = pGetExp(id->m[i],1); pWrite(id->m[i]); Print("EXP1: %d\n",ev[1]); Print("EXP2: %d\n",ev[2]); Print("EXP3: %d\n\n",ev[3]); Print("SUM: %ld\n\n\n",sumVector(ev,r->N)); } delete ev; */ /*DEBUGGING STUFF END */ // first element in rTag is first element of rules which is NULL RNode, // this must be done due to possible later improvements RList* rules = new RList(); //Print("RULES FIRST: %p\n",rules->getFirst()); //Print("RULES FIRST DATA: %p\n",rules->getFirst()->getRule()); //RTagList* rTag = new RTagList(rules->getFirst()); RTagList* rTag = NULL; i = 1; /*for(j=0; jm[j]) { if(pComparePolys(id->m[j],ONE)) { PrintS("One Polynomial in Input => Computations stopped\n"); ideal idNew = idInit(1,1); idNew->m[0] = ONE; return(idNew); } } }*/ ideal idNew = kInterRed(id); id = idNew; //qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]); //idShow(id); LList* gPrev = new LList(ONE, i, id->m[0]); LList* reducers = new LList(); //idShow(id); //Print("%p\n",id->m[0]); //pWrite(id->m[0]); //Print("%p\n",gPrev->getFirst()->getPoly()); //pWrite(gPrev->getFirst()->getPoly()); LTagList* lTag = new LTagList(gPrev->getFirst()); //lTag->insert(gPrev->getFirst()); lTag->setFirstCurrentIdx(gPrev->getFirst()); // computing the groebner basis of the elements of index < actual index gbLength = gPrev->getLength(); //Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength()); ideal gbPrev = idInit(gbLength,1); // initializing the groebner basis of elements of index < actual index gbPrev->m[0] = gPrev->getFirst()->getPoly(); //idShow(gbPrev); //idShow(currRing->qideal); for(i=2; i<=IDELEMS(id); i++) { LNode* gPrevTag = gPrev->getLast(); //Print("Last POlynomial in GPREV: "); //Print("%p\n",gPrevTag); //pWrite(gPrevTag->getPoly()); Print("Iteration: %d\n\n",i); gPrev = F5inc(i, id->m[i-1], gPrev, reducers, gbPrev, ONE, lTag, rules, rTag, plus, termination); //Print("%d\n",gPrev->count(gPrevTag->getNext())); //Print("%d\n",gPrev->getLength()); //Print("____________________________________ITERATION STEP DONE________________________________________\n"); // DEBUGGING STUFF LNode* temp = gPrev->getFirst(); ///////////////////////////////////////////////////////////////////////////////// // // // one needs to choose one of the following 3 implementations of the algorithm // // F5,F5R or F5C // // // ///////////////////////////////////////////////////////////////////////////////// // // standard "F5" // if(0 == opt) { if(gPrev->getLength() > gbLength) { if(i < IDELEMS(id)) { ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); LNode* temp = gPrevTag; int counter = 0; for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { temp = temp->getNext(); if(0 == temp->getDel()) { counter++; gbAdd->m[j] = temp->getPoly(); } } gbPrev = idAdd(gbPrev,gbAdd); } else { ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); LNode* temp = gPrevTag; for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { temp = temp->getNext(); gbAdd->m[j] = temp->getPoly(); } gbPrev = idAdd(gbPrev,gbAdd); } //if(i == IDELEMS(id)) { // ideal tempId = kInterRed(gbPrev); // gbPrev = tempId; //} } gbLength = gPrev->getLength(); } // // "F5R" // if(1 == opt) { if(gPrev->getLength() > gbLength) { if(i < IDELEMS(id)) { ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); LNode* temp = gPrevTag; int counter = 0; for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { temp = temp->getNext(); if(0 == temp->getDel()) { counter++; gbAdd->m[j] = temp->getPoly(); } } gbPrev = idAdd(gbPrev,gbAdd); } else { ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); LNode* temp = gPrevTag; for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { temp = temp->getNext(); gbAdd->m[j] = temp->getPoly(); } gbPrev = idAdd(gbPrev,gbAdd); } // interreduction stuff // comment this out if you want F5 instead of F5R if(igetLength(); } // // "F5C" // if(2 == opt) { if(gPrev->getLength() > gbLength) { if(i < IDELEMS(id)) { ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); LNode* temp = gPrevTag; for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { temp = temp->getNext(); gbAdd->m[j] = temp->getPoly(); } gbPrev = idAdd(gbPrev,gbAdd); } else { ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); LNode* temp = gPrevTag; for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { temp = temp->getNext(); gbAdd->m[j] = temp->getPoly(); } gbPrev = idAdd(gbPrev,gbAdd); } if(im[0]); gPrev->insert(pOne,1,gbPrev->m[1]); rules = new RList(); //rTag = new RTagList(rules->getFirst()); for(k=2; kinsert(pOne,k+1,gbPrev->m[k]); /* for(l=0; linsert(rules->getFirst()); */ } } gbLength = gPrev->getLength(); } } } timer = getTimer(); //Print("\n\nADDING TIME IN REDUCTION: %d\n\n",reductionTime); Print("\n\nNumber of zero-reductions: %d\n",reductionsToZero); Print("Number of rules: %d\n",numberOfRules); Print("Number of rejected F5-critical pairs:%d\n",numberRejectedF5CriticalPairs); Print("Number of reductions: %d\n",numberOfReductions); Print("Elements not added to G: %d\n",notInG); Print("Highest Degree during computations: %d\n",highestDegree); Print("Degree d_0 in F5+: %d\n",highestDegreeGBCriticalPair); Print("Time for computations: %d/1000 seconds\n",timer); Print("Number of elements in gb: %d\n",IDELEMS(gbPrev)); //LNode* temp = gPrev->getFirst(); //while(NULL != temp) { // pWrite(temp->getPoly()); // temp = temp->getNext(); // } //gPrev->print(); //delete lTag; delete rTag; delete gPrev; notInG = 0; numberOfRules = 0; reductionsToZero = 0; highestDegree = 0; highestDegreeGBCriticalPair = 0; reductionTime = 0; spolsTime = 0; numberUselessPairs = 0; numberUsefulPairs = 0; numberRejectedF5CriticalPairs = 0; numberOfReductions = 0; numberOfSpolys = 0; return(gbPrev); } #endif