30 #define pDeg(A) p_Deg(A,currRing)
57 p2 = *(left + (right - left >> 1));
75 }
while(++ptr1 <= --ptr2);
115 for(
j=1;
j<=
k;
j++) {
131 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) {
134 int iterationstep =
i;
154 criticalPair(gPrev, critPairs, lTag, rTag, rules, rejectedGBList, plus);
182 critPairsMinDeg = critPairs->
getMinDeg();
191 computeSPols(critPairsMinDeg,rTag,rules,sPolyList, rejectedGBList);
216 newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination, rejectedGBList, plus);
320 while(
NULL != temp) {
322 number nOne =
nInit(1);
325 while(
NULL != temp2) {
342 poly reducer =
pOne();
350 poly uReducer =
pOne();
371 PrintS(
"------------------\n");
387 while(
NULL != temp) {
395 LNode* tempPoly = firstGCurr;
396 while(
NULL != tempPoly) {
398 while(
NULL != tempPoly2) {
399 number nOne =
nInit(1);
405 LNode* tempPoly3 = firstGCurr;
406 while(
NULL != tempPoly3) {
420 tempPoly3 = tempPoly3->
getNext();
423 tempPoly2 = tempPoly2->
getNext();
425 tempPoly = tempPoly->
getNext();
445 number nOne =
nInit(1);
460 while( gPrev->
getLast() != temp) {
557 number nOne =
nInit(1);
569 while( gPrev->
getLast() != temp) {
617 int idx =
l->getIndex();
644 testNode = testNode->
getNext();
699 if(idx >
l->getIndex()) {
746 if(
NULL != testNode ) {
749 if(
NULL != testNode) {
773 testNode = testNode->
getNext();
810 while(
NULL != testNode && testNode->
getRuleOld() != testedRuleOld) {
819 testNode = testNode->
getNext();
832 while(
NULL != temp) {
864 while(
NULL != temp) {
967 //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
972 sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
973 ppMult_qq(temp->getT2(),temp->getLp2Poly()));
974 //Print("BEGIN SPOLY2\n====================\n");
977 //Print("END SPOLY2\n====================\n");
980 //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
985 rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
987 // save the address of the rule again in a different
990 f5rules->insert(rules->getFirst()->getRuleOld());
991 f5pairs->insertWithoutSort(temp->getData());
993 //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
998 // the following else is not needed at all as we are checking
999 // F5-critical pairs in this step
1002 if(!temp->getDel()) {
1003 rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
1091 ideal gbPrev,
PList* rejectedGBList,
int plus) {
1096 while(
NULL != temp) {
1107 if(
NULL != tempNF) {
1115 topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus);
1137 ideal gbPrev,
int termination,
PList* rejectedGBList,
int plus) {
1144 while(
NULL != temp) {
1169 findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus);
1203 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) {
1204 int canonicalize = 0;
1212 number nOne =
nInit(1);
1215 poly tempPoly =
pInit();
1216 poly redPoly =
NULL;
1217 int idx =
l->getIndex();
1220 tempPoly =
pCopy(
l->getPoly());
1231 while(
NULL != tempPoly) {
1234 while(
NULL != tempRed) {
1238 u = pMDivideM(tempPoly,tempRed->
getPoly());
1245 poly tempRedPoly = tempRed->
getPoly();
1249 int lTempRedPoly =
pLength(tempRedPoly);
1254 if(!(canonicalize % 50)) {
1260 if(
NULL != tempPoly) {
1284 if(
NULL == redPoly) {
1292 poly tempRedPoly = tempRed->
getPoly();
1296 int lTempRedPoly =
pLength(tempRedPoly);
1304 if(!(canonicalize % 50)) {
1312 if(
NULL != tempPoly) {
1355 poly tempRedPoly = tempRed->
getPoly();
1359 int lTempRedPoly =
pLength(tempRedPoly);
1364 if(!(canonicalize % 50)) {
1370 if(
NULL != tempPoly) {
1383 if(
NULL != tempPoly) {
1386 while(
NULL != tempRed) {
1392 u = pMDivideM(tempPoly,tempRed->
getPoly());
1398 poly tempRedPoly = tempRed->
getPoly();
1402 int lTempRedPoly =
pLength(tempRedPoly);
1407 if(!(canonicalize % 50)) {
1413 if(
NULL != tempPoly) {
1437 if(
NULL == redPoly) {
1445 poly tempRedPoly = tempRed->
getPoly();
1449 int lTempRedPoly =
pLength(tempRedPoly);
1457 if(!(canonicalize % 50)) {
1465 if(
NULL != tempPoly) {
1511 if(
NULL != tempPoly) {
1512 if(
NULL == redPoly) {
1526 if(
NULL == redPoly) {
1532 PrintS(
"\nELEMENT ADDED TO GPREV: ");
1541 l->setPoly(redPoly);
1545 Print(
"redundant? %d\n\n",
l->getDel());
1546 if(addToG == 0 && termination == 1) {
1547 reducers->
insert(
l->getLPolyOld());
1550 gPrev->
insert(
l->getLPolyOld());
1553 if(termination == 1) {
1556 criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1570 criticalPair(gPrev,critPairs,lTag,rTag,rules,rejectedGBList,plus);
1573 criticalPair2(gPrev,critPairs,lTag,rTag,rules, rejectedGBList);
1585 while(
NULL != tempBad) {
1716 tempRed =
findReductor(
l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag);
1720 if(
NULL != tempRed) {
1772 if(
NULL == tempNF) {
1791 if(
NULL !=
l->getPoly()) {
1795 gPrev->
insert(
l->getLPolyOld());
1800 criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1821 number nOne =
nInit(1);
1824 poly t =
pHead(
l->getPoly());
1828 temp = gPrevRedCheck;
1847 gPrevRedCheck = temp->
getNext();
1860 gPrevRedCheck = temp->
getNext();
1861 if(
NULL != tempSpoly) {
1890 ideal
F5main(ideal
id, ring r,
int opt,
int plus,
int termination)
1895 PrintS(
"\nComputations are done by the standard F5 Algorithm");
1898 PrintS(
"\nComputations are done by the variant F5R of the F5 Algorithm");
1901 PrintS(
"\nComputations are done by the variant F5C of the F5 Algorithm");
1904 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");
1915 number nOne =
nInit(1);
1972 ideal gbPrev =
idInit(gbLength,1);
1982 Print(
"Iteration: %d\n\n",
i);
1983 gPrev =
F5inc(
i, id->m[
i-1], gPrev, reducers, gbPrev, ONE, lTag, rules, rTag, plus, termination);
2007 LNode* temp = gPrevTag;
2011 if(0 == temp->
getDel()) {
2016 gbPrev =
idAdd(gbPrev,gbAdd);
2020 LNode* temp = gPrevTag;
2025 gbPrev =
idAdd(gbPrev,gbAdd);
2043 LNode* temp = gPrevTag;
2047 if(0 == temp->
getDel()) {
2052 gbPrev =
idAdd(gbPrev,gbAdd);
2056 LNode* temp = gPrevTag;
2061 gbPrev =
idAdd(gbPrev,gbAdd);
2081 LNode* temp = gPrevTag;
2086 gbPrev =
idAdd(gbPrev,gbAdd);
2090 LNode* temp = gPrevTag;
2095 gbPrev =
idAdd(gbPrev,gbAdd);
2104 rules =
new RList();
2130 Print(
"Time for computations: %d/1000 seconds\n",timer);
2131 Print(
"Number of elements in gb: %d\n",
IDELEMS(gbPrev));