/**************************************** * Computer Algebra System SINGULAR * ****************************************/ /* * ABSTRACT: f5gb interface */ #include "mod2.h" #ifdef HAVE_F5 #include #include "structs.h" #include "kutil.h" #include "omalloc.h" #include "polys.h" #include "p_polys.h" #include "p_Procs.h" #include "ideals.h" #include "febase.h" #include "kstd1.h" #include "khstd.h" #include "kbuckets.h" #include "weight.h" #include "intvec.h" #include "pInline1.h" #include "f5gb.h" #include "f5data.h" #include "f5lists.h" #include "timer.h" int notInG = 0; int numberOfRules = 0; int reductionsToZero = 0; int reductionTime = 0; int spolsTime = 0; int highestDegree = 0; int degreeBound = 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(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)) { ptr1++; } while(pTotaldegree(*ptr2, currRing) > pTotaldegree(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 termination) { //Print("in f5inc\n"); //pWrite(rules->getFirst()->getRuleTerm()); int j; //Print("%p\n",gPrev->getFirst()); //pWrite(gPrev->getFirst()->getPoly()); poly tempNF = kNF(gbPrev,currQuotient,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(); // 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(); //sPolyList->print(); // labeled polynomials which have passed reduction() and have to be added to list gPrev static LList* completed = new LList(); // the reduced labeled polynomials which are returned from subalgorithm reduction() static 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. critPairsMinDeg = critPairs->getMinDeg(); // 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(); computeSPols(critPairsMinDeg,rTag,rules,sPolyList); //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); newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination); //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"); /* Print("\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; } /* ================================================================ 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 ================================================================ */ inline void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) { //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 = pDivide(lcm,t); if(NULL == u1) { break; } pSetCoeff(u1,nOne); u2 = pDivide(lcm,pHead(temp->getPoly())); pSetCoeff(u2,nOne); // testing both new labels by the F5 Criterion 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(), testedRuleOld); critPairs->insert(cp); } else { CPairOld* cp = new CPairOld(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, newElement->getLPolyOld(), u2, temp->getLPolyOld(), testedRuleOld); critPairs->insert(cp); } } else { } 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,currQuotient,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"); /* Print("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); /* Print("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; } /* ================================== Computation of S-Polynomials in F5 ================================== */ void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) { CNode* temp = first; poly sp = pInit(); number sign = nInit(-1); //Print("###############################IN SPOLS##############################\n"); //first->print(); while(NULL != temp) { //Print("JA\n"); // only if a new RuleOld was added since the last test in subalgorithm criticalPair() //if(rules->getFirst() != rTag->getFirst()) { if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRuleOld())) { // the second component is tested only when it has the actual index, otherwise there is // no new RuleOld to test since the last test in subalgorithm criticalPair() if(highestDegree < pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly()))) { highestDegree = pDeg(ppMult_qq(temp->getT1(),temp->getLp1Poly())); //pWrite(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly()))); } if(temp->getLp2Index() == temp->getLp1Index()) { if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRuleOld())) { // computation of S-polynomial //poly p1 = temp->getLp1Poly(); //poly p2 = temp->getLp2Poly(); //pIter(p1); //pIter(p2); //sp = pAdd(ppMult_qq(temp->getT1(),p1),pMult_nn(ppMult_qq(temp->getT2(),p2),sign)); sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()), ppMult_qq(temp->getT2(),temp->getLp2Poly())); //Print("BEGIN SPOLY1\n====================\n"); pNorm(sp); //pWrite(sp); //Print("END SPOLY1\n====================\n"); if(NULL == sp) { // as rules consist only of pointers we need to save the labeled // S-polynomial also of a zero S-polynomial //zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp); // origin of RuleOld can be set NULL as the labeled polynomial // will never be used again as it is zero => no problems with // further criterion2() tests and termination conditions //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); reductionsToZero++; //Print("IN SPOLS 1\n"); //Rule* rNew = new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); //rules->insertOrdered(rNew); rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; //Print("RuleOld ADDED: \n"); //pWrite(rules->getFirst()->getRuleTerm()); //rules->print(); // as sp = NULL, delete it pDelete(&sp); //Print("HIER\n"); } else { //Print("IN SPOLS 2\n"); //Rule* rNew = new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); //rules->insertOrdered(rNew); rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; //Print("RuleOld ADDED: \n"); //pWrite(rules->getFirst()->getRuleTerm()); //rules->print(); sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld()); //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rNew); } // data is saved in sPolyList or zero => delete sp } } else { // temp->getLp2Index() < temp->getLp1Index() // computation of S-polynomial //poly p1 = temp->getLp1Poly(); //poly p2 = temp->getLp2Poly(); //pIter(p1); //pIter(p2); //sp = pAdd(ppMult_qq(temp->getT1(),p1),pMult_nn(ppMult_qq(temp->getT2(),p2),sign)); 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) { // zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp); // origin of RuleOld can be set NULL as the labeled polynomial // will never be used again as it is zero => no problems with // further criterion2() tests and termination conditions //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); reductionsToZero++; //Print("IN SPOLS 3\n"); rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; //Print("RuleOld ADDED: \n"); //pWrite(rules->getFirst()->getRuleTerm()); //rules->print(); // as sp = NULL, delete it pDelete(&sp); } else { //Print("IN SPOLS 4\n"); ////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////// // TODO: Rules inserted ordered by their label monomial!// ////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////// //Rule* rNew = new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); //RNode* rNodeNew = new RNode(rNew); //rules->insertOrdered(rNew); rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); numberOfRules++; //Print("RuleOld ADDED: \n"); //pWrite(rules->getFirst()->getRuleTerm()); //rules->print(); //Print("%d\n",rules->getFirst()->getRuleIndex()); //Print("%p\n",sPolyList->getFirst()); sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld()); //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rNew); } } } //} //Print("%p\n",temp); temp = temp->getNext(); //Print("%p\n",temp); //Print("%p\n",temp->getData()); //pWrite(temp->getLp1Poly()); } // 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; } /* ======================================================================== reduction including subalgorithm topReduction() using Faugere's criteria ======================================================================== */ void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev) { //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,currQuotient,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); } 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) { //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(); 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 //Print("LIST OF SPOLYNOMIALS!\n"); //sPolyList->print(); //pWrite(sPolyList->getFirst()->getPoly()); sPolyList->setFirst(temp->getNext()); //pWrite(temp->getPoly()); //poly tempNF = kNF(gbPrev,currQuotient,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); //} //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) { 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(); 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 = pDivideM(pHead(tempPoly),pHead(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(); } // 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 = pDivideM(pHead(tempPoly),pHead(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 { //Print("\nELEMENT ADDED TO GPREV: "); pNorm(redPoly); //pWrite(pHead(redPoly)); //pWrite(l->getTerm()); //Print("%d\n",canonicalize); l->setPoly(redPoly); 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); } else { notInG++; //Print("\nNONONO"); //pWrite(pHead(l->getPoly())); //pWrite(l->getTerm()); } } else { criticalPair(gPrev,critPairs,lTag,rTag,rules); } } // 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 = pDivide(pHead(l->getPoly()),pHead(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) { //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,currQuotient,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); //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) { // 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 = pDivide(t,pHead(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 termination) { switch(opt) { case 0: Print("\nComputations are done by the standard F5 Algorithm"); break; case 1: Print("\nComputations are done by the variant F5R of the F5 Algorithm"); break; case 2: Print("\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); //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)) { Print("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(currQuotient); 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, reducers, gbPrev, ONE, lTag, rules, rTag, 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("Elements not added to G: %d\n",notInG); Print("Highest Degree during computations: %d\n",highestDegree); 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; reductionTime = 0; spolsTime = 0; return(gbPrev); } #endif