55 p2 = *(left + (right - left >> 1));
69 }
while(++ptr1 <= --ptr2);
107 for(j=1; j<=
k; j++) {
123 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) {
126 int iterationstep =
i;
146 criticalPair(gPrev, critPairs, lTag, rTag, rules, rejectedGBList, plus);
174 critPairsMinDeg = critPairs->
getMinDeg();
183 computeSPols(critPairsMinDeg,rTag,rules,sPolyList, rejectedGBList);
208 newReduction(sPolyList, critPairs, gPrev, reducers, rules, lTag, rTag, gbPrev, termination, rejectedGBList, plus);
312 while(
NULL != temp) {
314 number nOne =
nInit(1);
317 while(
NULL != temp2) {
363 Print(
"------------------\n");
379 while(
NULL != temp) {
387 LNode* tempPoly = firstGCurr;
388 while(
NULL != tempPoly) {
390 while(
NULL != tempPoly2) {
391 number nOne =
nInit(1);
396 if(pDeg(lcm) > arrideg) {
397 LNode* tempPoly3 = firstGCurr;
398 while(
NULL != tempPoly3) {
408 if(pDeg(lcm1) < pDeg(lcm) && pDeg(lcm2) < pDeg(lcm)) {
412 tempPoly3 = tempPoly3->
getNext();
415 tempPoly2 = tempPoly2->
getNext();
417 tempPoly = tempPoly->
getNext();
437 number nOne =
nInit(1);
452 while( gPrev->
getLast() != temp) {
477 if(newElement->getIndex() == temp->getIndex() &&
480 temp->getLPolyOld(), u1, newElement->getLPolyOld(), 0 , testedRuleOld);
487 newElement->getLPolyOld(), u2, temp->getLPolyOld(), 0, testedRuleOld);
499 rejectedGBList->
insert(lcm);
515 if(newElement->getIndex() == temp->getIndex() &&
518 temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
524 newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
549 number nOne =
nInit(1);
561 while( gPrev->
getLast() != temp) {
581 if(newElement->getIndex() == temp->getIndex() &&
584 temp->getLPolyOld(), u1, newElement->getLPolyOld(), 1 , testedRuleOld);
590 newElement->getLPolyOld(), u2, temp->getLPolyOld(), 1, testedRuleOld);
596 temp = temp->getNext();
636 testNode = testNode->
getNext();
738 if(
NULL != testNode ) {
741 if(
NULL != testNode) {
765 testNode = testNode->
getNext();
802 while(
NULL != testNode && testNode->
getRuleOld() != testedRuleOld) {
811 testNode = testNode->
getNext();
824 while(
NULL != temp) {
826 numberUsefulPairsMinDeg++;
856 while(
NULL != temp) {
959 //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
964 sp = ksOldSpolyRedNew(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
965 ppMult_qq(temp->getT2(),temp->getLp2Poly()));
966 //Print("BEGIN SPOLY2\n====================\n");
969 //Print("END SPOLY2\n====================\n");
972 //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
977 rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
979 // save the address of the rule again in a different
982 f5rules->insert(rules->getFirst()->getRuleOld());
983 f5pairs->insertWithoutSort(temp->getData());
985 //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRuleOld());
990 // the following else is not needed at all as we are checking
991 // F5-critical pairs in this step
994 if(!temp->getDel()) {
995 rejectedGBList->insert(pHead(ppMult_qq(temp->getT1(),temp->getLp1Poly())));
1083 ideal gbPrev,
PList* rejectedGBList,
int plus) {
1088 while(
NULL != temp) {
1099 if(
NULL != tempNF) {
1107 topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus);
1129 ideal gbPrev,
int termination,
PList* rejectedGBList,
int plus) {
1136 while(
NULL != temp) {
1161 findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus);
1195 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) {
1196 int canonicalize = 0;
1204 number nOne =
nInit(1);
1223 while(
NULL != tempPoly) {
1226 while(
NULL != tempRed) {
1241 int lTempRedPoly =
pLength(tempRedPoly);
1246 if(!(canonicalize % 50)) {
1252 if(
NULL != tempPoly) {
1276 if(
NULL == redPoly) {
1277 bad->
insert(tempRed->getLPolyOld());
1284 poly tempRedPoly = tempRed->getPoly();
1288 int lTempRedPoly =
pLength(tempRedPoly);
1296 if(!(canonicalize % 50)) {
1304 if(
NULL != tempPoly) {
1351 int lTempRedPoly =
pLength(tempRedPoly);
1356 if(!(canonicalize % 50)) {
1362 if(
NULL != tempPoly) {
1375 if(
NULL != tempPoly) {
1378 while(
NULL != tempRed) {
1394 int lTempRedPoly =
pLength(tempRedPoly);
1399 if(!(canonicalize % 50)) {
1405 if(
NULL != tempPoly) {
1429 if(
NULL == redPoly) {
1430 bad->
insert(tempRed->getLPolyOld());
1437 poly tempRedPoly = tempRed->getPoly();
1441 int lTempRedPoly =
pLength(tempRedPoly);
1449 if(!(canonicalize % 50)) {
1457 if(
NULL != tempPoly) {
1503 if(
NULL != tempPoly) {
1504 if(
NULL == redPoly) {
1518 if(
NULL == redPoly) {
1523 Print(
"\nELEMENT ADDED TO GPREV: ");
1536 if(addToG == 0 && termination == 1) {
1543 if(termination == 1) {
1546 criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1560 criticalPair(gPrev,critPairs,lTag,rTag,rules,rejectedGBList,plus);
1563 criticalPair2(gPrev,critPairs,lTag,rTag,rules, rejectedGBList);
1575 while(
NULL != tempBad) {
1590 rules->insert(tempBad->getIndex(),
ppMult_qq(u,tempBad->getTerm()));
1600 LNode* tempBadNew =
new LNode(
ppMult_qq(u,tempBad->getTerm()),tempBad->getIndex(),temp,rules->getFirst()->getRuleOld());
1706 tempRed =
findReductor(l,sPolyList,gPrevRedCheck,gPrev,rules,lTag,rTag);
1710 if(
NULL != tempRed) {
1762 if(
NULL == tempNF) {
1790 criticalPair(gPrev,critPairs,lTag,rTag,rules, rejectedGBList,plus);
1811 number nOne =
nInit(1);
1818 temp = gPrevRedCheck;
1821 while(
NULL != temp && temp->getIndex() == l->
getIndex()) {
1837 gPrevRedCheck = temp->
getNext();
1849 rules->insert(temp->getIndex(),
ppMult_qq(u,temp->getTerm()));
1850 gPrevRedCheck = temp->
getNext();
1851 if(
NULL != tempSpoly) {
1853 sPolyList->
insertByLabel(
ppMult_qq(u,temp->getTerm()),temp->getIndex(),tempSpoly,rules->getFirst()->getRuleOld());
1865 temp = temp->getNext();
1880 ideal
F5main(ideal
id, ring
r,
int opt,
int plus,
int termination) {
1883 Print(
"\nComputations are done by the standard F5 Algorithm");
1886 Print(
"\nComputations are done by the variant F5R of the F5 Algorithm");
1889 Print(
"\nComputations are done by the variant F5C of the F5 Algorithm");
1892 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");
1903 number nOne =
nInit(1);
1960 ideal gbPrev =
idInit(gbLength,1);
1965 for(i=2; i<=
IDELEMS(
id); i++) {
1970 Print(
"Iteration: %d\n\n",i);
1971 gPrev =
F5inc(i, id->m[i-1], gPrev, reducers, gbPrev, ONE, lTag, rules, rTag, plus, termination);
1995 LNode* temp = gPrevTag;
1997 for(j=0;j<=gPrev->
getLength()-gbLength-1;j++) {
1999 if(0 == temp->getDel()) {
2004 gbPrev =
idAdd(gbPrev,gbAdd);
2008 LNode* temp = gPrevTag;
2009 for(j=0;j<=gPrev->
getLength()-gbLength-1;j++) {
2013 gbPrev =
idAdd(gbPrev,gbAdd);
2031 LNode* temp = gPrevTag;
2033 for(j=0;j<=gPrev->
getLength()-gbLength-1;j++) {
2035 if(0 == temp->getDel()) {
2040 gbPrev =
idAdd(gbPrev,gbAdd);
2044 LNode* temp = gPrevTag;
2045 for(j=0;j<=gPrev->
getLength()-gbLength-1;j++) {
2049 gbPrev =
idAdd(gbPrev,gbAdd);
2069 LNode* temp = gPrevTag;
2070 for(j=0;j<=gPrev->
getLength()-gbLength-1;j++) {
2074 gbPrev =
idAdd(gbPrev,gbAdd);
2078 LNode* temp = gPrevTag;
2079 for(j=0;j<=gPrev->
getLength()-gbLength-1;j++) {
2083 gbPrev =
idAdd(gbPrev,gbAdd);
2090 gPrev =
new LList(pOne,1,gbPrev->m[0]);
2091 gPrev->
insert(pOne,1,gbPrev->m[1]);
2092 rules =
new RList();
2094 for(k=2; k<
IDELEMS(gbPrev); k++) {
2095 gPrev->
insert(pOne,k+1,gbPrev->m[k]);
2118 Print(
"Time for computations: %d/1000 seconds\n",timer);
2119 Print(
"Number of elements in gb: %d\n",
IDELEMS(gbPrev));
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
int highestDegreeGBCriticalPair
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
void kBucketInit(kBucket_pt bucket, poly lm, int length)
void qsortDegree(poly *left, poly *right)
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)
searches for reducers of temp similar to the symbolic preprocessing of F4 and divides them into a "g...
void insert(LPolyOld *lp)
Compatiblity layer for legacy polynomial operations (over currRing)
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
structure of RuleOlds(i.e.
void setFirstCurrentIdx(LNode *l)
const poly kBucketGetLm(kBucket_pt bucket)
bool arrisCheck(CNode *first, LNode *firstGCurr, long arrideg)
void WerrorS(const char *s)
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)
void computeSPols(CNode *first, RTagList *rTag, RList *rules, LList *sPolyList, PList *rejectedGBList)
static int pLength(poly a)
poly kBucketExtractLm(kBucket_pt bucket)
RuleOld * getTestedRuleOld()
class PList of lists of PNodes
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
void criticalPair(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList, int plus)
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
LNode * getFirstCurrentIdx()
static long pTotaldegree(poly p)
bool compareMonomials(int *m1, int **m2, int numberOfRules, int k)
compares monomials, i.e.
class of labeled polynomials
ideal kInterRed(ideal F, ideal Q)
LNode * findReductor(LNode *l, LList *sPolyList, LNode *gPrevRedCheck, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, PList *rejectedGBList)
bool criterion1(LList *gPrev, poly t, LNode *l, LTagList *lTag)
long sumVector(int *v, int k)
builds the sum of the entries of the exponent vectors, i.e.
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
int computeUsefulMinDeg(CNode *first)
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether)
bool criterion2(int idx, poly t, LNode *l, RList *rules, RTagList *rTag)
ideal idInit(int idsize, int rank)
initialise an ideal / module
const Variable & v
< [in] a sqrfree bivariate poly
#define pDivisibleBy(a, b)
returns TRUE, if leading monom of a divides leading monom of b i.e., if there exists a expvector c > ...
static poly p_Merge_q(poly p, poly q, const ring r)
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
void pNorm(poly p, const ring R=currRing)
void insertByLabel(poly t, int i, poly p, RuleOld *r=NULL)
#define pInit()
allocates a new monomial and initializes everything to 0
int numberUsefulPairsMinDeg
void criticalPair2(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList)
int numberRejectedF5CriticalPairs
bool checkDGB(LList *gPrev)
ideal idAdd(ideal h1, ideal h2)
h1 + h2
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
void newReduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, LList *reducers, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, int termination, PList *rejectedGBList, int plus)
int kBucketCanonicalize(kBucket_pt bucket)
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
void topReduction(LNode *l, LList *sPolyList, LList *gPrev, CListOld *critPairs, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
#define pCopy(p)
return a copy of the poly
ideal F5main(ideal id, ring r, int opt, int plus, int termination)
structure of labeled critical pairs