29 #define pDeg(A) p_Deg(A,currRing)
56 p2 = *(left + (right - left >> 1));
74 }
while(++ptr1 <= --ptr2);
114 for(
j=1;
j<=
k;
j++) {
130 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) {
133 int iterationstep =
i;
153 criticalPair(gPrev, critPairs, lTag, rTag, rules, rejectedGBList, plus);
181 critPairsMinDeg = critPairs->
getMinDeg();
190 computeSPols(critPairsMinDeg,rTag,rules,sPolyList, rejectedGBList);
201 LNode* temp = sPolyList->getFirst();
215 newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination, rejectedGBList, plus);
319 while(
NULL != temp) {
321 number nOne =
nInit(1);
324 while(
NULL != temp2) {
341 poly reducer =
pOne();
349 poly uReducer =
pOne();
370 PrintS(
"------------------\n");
386 while(
NULL != temp) {
394 LNode* tempPoly = firstGCurr;
395 while(
NULL != tempPoly) {
397 while(
NULL != tempPoly2) {
398 number nOne =
nInit(1);
404 LNode* tempPoly3 = firstGCurr;
405 while(
NULL != tempPoly3) {
419 tempPoly3 = tempPoly3->
getNext();
422 tempPoly2 = tempPoly2->
getNext();
424 tempPoly = tempPoly->
getNext();
444 number nOne =
nInit(1);
459 while( gPrev->
getLast() != temp) {
484 if(newElement->getIndex() == temp->getIndex() &&
487 temp->getLPolyOld(), u1, newElement->getLPolyOld(), 0 , testedRuleOld);
494 newElement->getLPolyOld(), u2, temp->getLPolyOld(), 0, testedRuleOld);
522 if(newElement->getIndex() == temp->getIndex() &&
525 temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
531 newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
556 number nOne =
nInit(1);
568 while( gPrev->
getLast() != temp) {
588 if(newElement->getIndex() == temp->getIndex() &&
591 temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
597 newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
603 temp = temp->getNext();
616 int idx =
l->getIndex();
643 testNode = testNode->
getNext();
698 if(idx >
l->getIndex()) {
745 if(
NULL != testNode ) {
748 if(
NULL != testNode) {
772 testNode = testNode->
getNext();
809 while(
NULL != testNode && testNode->
getRuleOld() != testedRuleOld) {
818 testNode = testNode->
getNext();
831 while(
NULL != temp) {
863 while(
NULL != temp) {
966 //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
971 sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
972 ppMult_qq(temp->getT2(),temp->getLp2Poly()));
973 //Print("BEGIN SPOLY2\n====================\n");
976 //Print("END SPOLY2\n====================\n");
979 //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
984 rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
986 // save the address of the rule again in a different
989 f5rules->insert(rules->getFirst()->getRuleOld());
990 f5pairs->insertWithoutSort(temp->getData());
992 //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
997 // the following else is not needed at all as we are checking
998 // F5-critical pairs in this step
1001 if(!temp->getDel()) {
1002 rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
1090 ideal gbPrev,
PList* rejectedGBList,
int plus) {
1095 while(
NULL != temp) {
1106 if(
NULL != tempNF) {
1114 topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus);
1136 ideal gbPrev,
int termination,
PList* rejectedGBList,
int plus) {
1143 while(
NULL != temp) {
1168 findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus);
1202 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) {
1203 int canonicalize = 0;
1211 number nOne =
nInit(1);
1214 poly tempPoly =
pInit();
1215 poly redPoly =
NULL;
1216 int idx =
l->getIndex();
1219 tempPoly =
pCopy(
l->getPoly());
1230 while(
NULL != tempPoly) {
1233 while(
NULL != tempRed) {
1237 u = pMDivideM(tempPoly,tempRed->
getPoly());
1244 poly tempRedPoly = tempRed->
getPoly();
1248 int lTempRedPoly =
pLength(tempRedPoly);
1253 if(!(canonicalize % 50)) {
1259 if(
NULL != tempPoly) {
1283 if(
NULL == redPoly) {
1284 bad->insert(tempRed->getLPolyOld());
1291 poly tempRedPoly = tempRed->getPoly();
1295 int lTempRedPoly =
pLength(tempRedPoly);
1303 if(!(canonicalize % 50)) {
1311 if(
NULL != tempPoly) {
1354 poly tempRedPoly = tempRed->
getPoly();
1358 int lTempRedPoly =
pLength(tempRedPoly);
1363 if(!(canonicalize % 50)) {
1369 if(
NULL != tempPoly) {
1382 if(
NULL != tempPoly) {
1385 while(
NULL != tempRed) {
1391 u = pMDivideM(tempPoly,tempRed->
getPoly());
1397 poly tempRedPoly = tempRed->
getPoly();
1401 int lTempRedPoly =
pLength(tempRedPoly);
1406 if(!(canonicalize % 50)) {
1412 if(
NULL != tempPoly) {
1436 if(
NULL == redPoly) {
1437 bad->insert(tempRed->getLPolyOld());
1444 poly tempRedPoly = tempRed->getPoly();
1448 int lTempRedPoly =
pLength(tempRedPoly);
1456 if(!(canonicalize % 50)) {
1464 if(
NULL != tempPoly) {
1510 if(
NULL != tempPoly) {
1511 if(
NULL == redPoly) {
1525 if(
NULL == redPoly) {
1531 PrintS(
"\nELEMENT ADDED TO GPREV: ");
1540 l->setPoly(redPoly);
1544 Print(
"redundant? %d\n\n",
l->getDel());
1545 if(addToG == 0 && termination == 1) {
1546 reducers->
insert(
l->getLPolyOld());
1549 gPrev->
insert(
l->getLPolyOld());
1552 if(termination == 1) {
1555 criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1569 criticalPair(gPrev,critPairs,lTag,rTag,rules,rejectedGBList,plus);
1572 criticalPair2(gPrev,critPairs,lTag,rTag,rules, rejectedGBList);
1584 while(
NULL != tempBad) {
1599 rules->insert(tempBad->getIndex(),
ppMult_qq(u,tempBad->getTerm()));
1609 LNode* tempBadNew =
new LNode(
ppMult_qq(u,tempBad->getTerm()),tempBad->getIndex(),temp,rules->getFirst()->getRuleOld());
1715 tempRed =
findReductor(
l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag);
1719 if(
NULL != tempRed) {
1771 if(
NULL == tempNF) {
1790 if(
NULL !=
l->getPoly()) {
1794 gPrev->
insert(
l->getLPolyOld());
1799 criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1820 number nOne =
nInit(1);
1823 poly t =
pHead(
l->getPoly());
1827 temp = gPrevRedCheck;
1830 while(
NULL != temp && temp->getIndex() ==
l->getIndex()) {
1846 gPrevRedCheck = temp->
getNext();
1858 rules->insert(temp->getIndex(),
ppMult_qq(u,temp->getTerm()));
1859 gPrevRedCheck = temp->
getNext();
1860 if(
NULL != tempSpoly) {
1862 sPolyList->
insertByLabel(
ppMult_qq(u,temp->getTerm()),temp->getIndex(),tempSpoly,rules->getFirst()->getRuleOld());
1874 temp = temp->getNext();
1889 ideal
F5main(ideal
id, ring r,
int opt,
int plus,
int termination)
1894 PrintS(
"\nComputations are done by the standard F5 Algorithm");
1897 PrintS(
"\nComputations are done by the variant F5R of the F5 Algorithm");
1900 PrintS(
"\nComputations are done by the variant F5C of the F5 Algorithm");
1903 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");
1914 number nOne =
nInit(1);
1971 ideal gbPrev =
idInit(gbLength,1);
1981 Print(
"Iteration: %d\n\n",
i);
1982 gPrev =
F5inc(
i, id->m[
i-1], gPrev, reducers, gbPrev, ONE, lTag, rules, rTag, plus, termination);
2006 LNode* temp = gPrevTag;
2010 if(0 == temp->getDel()) {
2015 gbPrev =
idAdd(gbPrev,gbAdd);
2019 LNode* temp = gPrevTag;
2024 gbPrev =
idAdd(gbPrev,gbAdd);
2042 LNode* temp = gPrevTag;
2046 if(0 == temp->getDel()) {
2051 gbPrev =
idAdd(gbPrev,gbAdd);
2055 LNode* temp = gPrevTag;
2060 gbPrev =
idAdd(gbPrev,gbAdd);
2080 LNode* temp = gPrevTag;
2085 gbPrev =
idAdd(gbPrev,gbAdd);
2089 LNode* temp = gPrevTag;
2094 gbPrev =
idAdd(gbPrev,gbAdd);
2103 rules =
new RList();
2129 Print(
"Time for computations: %d/1000 seconds\n",timer);
2130 Print(
"Number of elements in gb: %d\n",
IDELEMS(gbPrev));