 |
My Project
debian-1:4.1.2-p1+ds-2
|
Go to the source code of this file.
|
void | qsortDegree (poly *left, poly *right) |
|
long | sumVector (int *v, int k) |
|
bool | compareMonomials (int *m1, int **m2, int numberOfRuleOlds) |
|
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 | criticalPair (LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *RuleOlds, PList *rejectedGBList, int plus) |
|
bool | checkDGB (LList *gPrev) |
|
bool | arrisCheck (CNode *first, LNode *firstGCurr, long arrisdeg) |
|
void | criticalPair2 (LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *RuleOlds, PList *rejectedGBList) |
|
bool | criterion1 (LList *gPrev, poly t, LNode *l, LTagList *lTag) |
|
bool | criterion2 (int idx, poly t, LNode *l, RList *RuleOlds, RTagList *rTag) |
|
bool | criterion2 (poly t, LPolyOld *l, RList *RuleOlds, RuleOld *testedRuleOld) |
|
int | computeUsefulMinDeg (CNode *first) |
|
void | computeSPols (CNode *first, RTagList *rTag, RList *RuleOlds, LList *sPolyList, PList *rejectedGBList) |
|
void | reduction (LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *RuleOlds, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus) |
|
void | newReduction (LList *sPolyList, CListOld *critPairs, LList *gPrev, LList *reducers, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, int termination, PList *rejectedGBList, int plus) |
|
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) |
|
void | topReduction (LNode *l, LList *sPolyList, LList *gPrev, CListOld *critPairs, RList *RuleOlds, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus) |
|
LNode * | findReductor (LNode *l, LList *sPolyList, LNode *gPrevRedCheck, LList *gPrev, RList *RuleOlds, LTagList *lTag, RTagList *rTag) |
|
ideal | F5main (ideal i, ring r, int opt, int plus, int termination) |
|
◆ arrisCheck()
bool arrisCheck |
( |
CNode * |
first, |
|
|
LNode * |
firstGCurr, |
|
|
long |
arrisdeg |
|
) |
| |
Definition at line 382 of file f5gb.cc.
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();
◆ checkDGB()
bool checkDGB |
( |
LList * |
gPrev | ) |
|
Definition at line 299 of file f5gb.cc.
319 while(
NULL != temp) {
321 number nOne =
nInit(1);
324 while(
NULL != temp2) {
341 poly reducer =
pOne();
349 poly uReducer =
pOne();
370 PrintS(
"------------------\n");
◆ compareMonomials()
bool compareMonomials |
( |
int * |
m1, |
|
|
int ** |
m2, |
|
|
int |
numberOfRuleOlds |
|
) |
| |
compare monomials, i.e. divisibility tests for criterion 1 and criterion 2
◆ computeSPols()
Definition at line 844 of file f5gb.cc.
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())));
◆ computeUsefulMinDeg()
int computeUsefulMinDeg |
( |
CNode * |
first | ) |
|
◆ criterion1()
Definition at line 614 of file f5gb.cc.
616 int idx =
l->getIndex();
643 testNode = testNode->
getNext();
◆ criterion2() [1/2]
Definition at line 675 of file f5gb.cc.
698 if(idx >
l->getIndex()) {
703 testNode = rules->getFirst();
745 if(
NULL != testNode ) {
748 if(
NULL != testNode) {
772 testNode = testNode->
getNext();
◆ criterion2() [2/2]
Definition at line 787 of file f5gb.cc.
805 RNode* testNode = rules->getFirst();
809 while(
NULL != testNode && testNode->
getRuleOld() != testedRuleOld) {
818 testNode = testNode->
getNext();
◆ criticalPair()
Definition at line 441 of file f5gb.cc.
444 number nOne =
nInit(1);
455 if(
NULL != rules->getFirst()) {
456 testedRuleOld = rules->getFirst()->getRuleOld();
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);
538 temp = temp->getNext();
◆ criticalPair2()
Definition at line 553 of file f5gb.cc.
556 number nOne =
nInit(1);
564 if(
NULL != rules->getFirst()) {
565 testedRuleOld = rules->getFirst()->getRuleOld();
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();
◆ F5inc()
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 |
|
) |
| |
Definition at line 130 of file f5gb.cc.
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);
◆ F5main()
ideal F5main |
( |
ideal |
i, |
|
|
ring |
r, |
|
|
int |
opt, |
|
|
int |
plus, |
|
|
int |
termination |
|
) |
| |
Definition at line 1889 of file f5gb.cc.
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));
◆ findReducers()
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 "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 RuleOlds and S-polynomials to be added to the algorithm
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
Definition at line 1202 of file f5gb.cc.
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());
1394 if(tempRed->getIndex() != idx) {
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());
1627 tempBad = tempBad->getNext();
◆ findReductor()
◆ newReduction()
void newReduction |
( |
LList * |
sPolyList, |
|
|
CListOld * |
critPairs, |
|
|
LList * |
gPrev, |
|
|
LList * |
reducers, |
|
|
RList * |
rules, |
|
|
LTagList * |
lTag, |
|
|
RTagList * |
rTag, |
|
|
ideal |
gbPrev, |
|
|
int |
termination, |
|
|
PList * |
rejectedGBList, |
|
|
int |
plus |
|
) |
| |
|
inline |
Definition at line 1135 of file f5gb.cc.
1143 while(
NULL != temp) {
1168 findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus);
◆ qsortDegree()
void qsortDegree |
( |
poly * |
left, |
|
|
poly * |
right |
|
) |
| |
Definition at line 51 of file f5gb.cc.
56 p2 = *(left + (right - left >> 1));
74 }
while(++ptr1 <= --ptr2);
◆ reduction()
Definition at line 1089 of file f5gb.cc.
1095 while(
NULL != temp) {
1106 if(
NULL != tempNF) {
1114 topReduction(temp,sPolyList,gPrev,critPairs,rules,lTag,rTag,gbPrev, rejectedGBList,plus);
◆ sumVector()
long sumVector |
( |
int * |
v, |
|
|
int |
k |
|
) |
| |
builds the sum of the entries of the exponent vectors, i.e. the degree
of the corresponding monomial
builds the sum of the entries of the exponent vectors, i.e. the degree
of the corresponding monomial
Definition at line 92 of file f5gb.cc.
◆ topReduction()
Definition at line 1704 of file f5gb.cc.
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);
#define pDivisibleBy(a, b)
returns TRUE, if leading monom of a divides leading monom of b i.e., if there exists a expvector c > ...
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
void qsortDegree(poly *left, poly *right)
void pNorm(poly p, const ring R=currRing)
void computeSPols(CNode *first, RTagList *rTag, RList *rules, LList *sPolyList, PList *rejectedGBList)
LNode * getFirstCurrentIdx()
static poly p_Merge_q(poly p, poly q, const ring r)
ideal idAdd(ideal h1, ideal h2)
h1 + h2
VAR int highestDegreeGBCriticalPair
LNode * findReductor(LNode *l, LList *sPolyList, LNode *gPrevRedCheck, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, PList *rejectedGBList)
const poly kBucketGetLm(kBucket_pt bucket)
bool criterion2(int idx, poly t, LNode *l, RList *rules, RTagList *rTag)
VAR int numberUsefulPairs
void criticalPair(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList, int plus)
static unsigned pLength(poly a)
poly kBucketExtractLm(kBucket_pt bucket)
void PrintS(const char *s)
RuleOld * getTestedRuleOld()
void kBucketInit(kBucket_pt bucket, poly lm, int length)
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...
bool criterion1(LList *gPrev, poly t, LNode *l, LTagList *lTag)
VAR int numberOfReductions
#define pInit()
allocates a new monomial and initializes everything to 0
void setFirstCurrentIdx(LNode *l)
void criticalPair2(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList)
void insertByLabel(poly t, int i, poly p, RuleOld *r=NULL)
VAR int numberUsefulPairsMinDeg
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
VAR int numberUselessPairs
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)
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
void newReduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, LList *reducers, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, int termination, PList *rejectedGBList, int plus)
VAR int numberRejectedF5CriticalPairs
ideal idInit(int idsize, int rank)
initialise an ideal / module
void topReduction(LNode *l, LList *sPolyList, LList *gPrev, CListOld *critPairs, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
void WerrorS(const char *s)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
const Variable & v
< [in] a sqrfree bivariate poly
static long p_Totaldegree(poly p, const ring r)
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
class PList of lists of PNodes
#define pCopy(p)
return a copy of the poly
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)
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
ideal kInterRed(ideal F, ideal Q)
void insert(LPolyOld *lp)
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether)