 |
My Project
debian-1:4.1.1-p2+ds-4build2
|
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 383 of file f5gb.cc.
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();
◆ checkDGB()
bool checkDGB |
( |
LList * |
gPrev | ) |
|
Definition at line 300 of file f5gb.cc.
320 while(
NULL != temp) {
322 number nOne =
nInit(1);
325 while(
NULL != temp2) {
342 poly reducer =
pOne();
350 poly uReducer =
pOne();
371 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 845 of file f5gb.cc.
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())));
◆ computeUsefulMinDeg()
int computeUsefulMinDeg |
( |
CNode * |
first | ) |
|
◆ criterion1()
Definition at line 615 of file f5gb.cc.
617 int idx =
l->getIndex();
644 testNode = testNode->
getNext();
◆ criterion2() [1/2]
Definition at line 676 of file f5gb.cc.
699 if(idx >
l->getIndex()) {
704 testNode = rules->getFirst();
746 if(
NULL != testNode ) {
749 if(
NULL != testNode) {
773 testNode = testNode->
getNext();
◆ criterion2() [2/2]
Definition at line 788 of file f5gb.cc.
806 RNode* testNode = rules->getFirst();
810 while(
NULL != testNode && testNode->
getRuleOld() != testedRuleOld) {
819 testNode = testNode->
getNext();
◆ criticalPair()
Definition at line 442 of file f5gb.cc.
445 number nOne =
nInit(1);
456 if(
NULL != rules->getFirst()) {
457 testedRuleOld = rules->getFirst()->getRuleOld();
460 while( gPrev->
getLast() != temp) {
◆ criticalPair2()
Definition at line 554 of file f5gb.cc.
557 number nOne =
nInit(1);
565 if(
NULL != rules->getFirst()) {
566 testedRuleOld = rules->getFirst()->getRuleOld();
569 while( gPrev->
getLast() != temp) {
◆ 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 131 of file f5gb.cc.
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);
◆ F5main()
ideal F5main |
( |
ideal |
i, |
|
|
ring |
r, |
|
|
int |
opt, |
|
|
int |
plus, |
|
|
int |
termination |
|
) |
| |
Definition at line 1890 of file f5gb.cc.
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));
◆ 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 1203 of file f5gb.cc.
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) {
◆ 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 1136 of file f5gb.cc.
1144 while(
NULL != temp) {
1169 findReducers(temp,sPolyList,gbPrev,gPrev,reducers,critPairs,rules,lTag,rTag, termination, rejectedGBList,plus);
◆ qsortDegree()
void qsortDegree |
( |
poly * |
left, |
|
|
poly * |
right |
|
) |
| |
Definition at line 52 of file f5gb.cc.
57 p2 = *(left + (right - left >> 1));
75 }
while(++ptr1 <= --ptr2);
◆ reduction()
Definition at line 1090 of file f5gb.cc.
1096 while(
NULL != temp) {
1107 if(
NULL != tempNF) {
1115 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 93 of file f5gb.cc.
◆ topReduction()
Definition at line 1705 of file f5gb.cc.
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);
#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)
void qsortDegree(poly *left, poly *right)
void pNorm(poly p, const ring R=currRing)
int numberRejectedF5CriticalPairs
int highestDegreeGBCriticalPair
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
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)
void criticalPair(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *rules, PList *rejectedGBList, int plus)
static unsigned pLength(poly a)
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
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)
#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)
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
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)
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.
#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
int numberUsefulPairsMinDeg
#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)