[936551] | 1 | /**************************************** |
---|
| 2 | * Computer Algebra System SINGULAR * |
---|
| 3 | ****************************************/ |
---|
[bc103b] | 4 | /* $Id: f5gb.cc,v 1.47 2009-03-16 13:30:59 Singular Exp $ */ |
---|
[936551] | 5 | /* |
---|
| 6 | * ABSTRACT: f5gb interface |
---|
| 7 | */ |
---|
[bc103b] | 8 | |
---|
[936551] | 9 | #include "mod2.h" |
---|
[ee3507] | 10 | #ifdef HAVE_F5 |
---|
[bc103b] | 11 | #include <unistd.h> |
---|
[936551] | 12 | #include "structs.h" |
---|
[bc103b] | 13 | #include "kutil.h" |
---|
[936551] | 14 | #include "omalloc.h" |
---|
| 15 | #include "polys.h" |
---|
| 16 | #include "p_polys.h" |
---|
| 17 | #include "ideals.h" |
---|
| 18 | #include "febase.h" |
---|
| 19 | #include "kstd1.h" |
---|
| 20 | #include "khstd.h" |
---|
| 21 | #include "kbuckets.h" |
---|
| 22 | #include "weight.h" |
---|
| 23 | #include "intvec.h" |
---|
| 24 | #include "pInline1.h" |
---|
| 25 | #include "f5gb.h" |
---|
[5d0556] | 26 | #include "f5data.h" |
---|
[a3771a] | 27 | #include "f5lists.h" |
---|
[fcb8022] | 28 | int reductionsToZero = 0; |
---|
[9bb97e] | 29 | |
---|
[199ae7] | 30 | /* |
---|
| 31 | ==================================================================== |
---|
| 32 | sorting ideals by decreasing total degree "left" and "right" are the |
---|
| 33 | pointer of the first and last polynomial in the considered ideal |
---|
| 34 | ==================================================================== |
---|
[ed30c5] | 35 | */ |
---|
[199ae7] | 36 | void qsortDegree(poly* left, poly* right) { |
---|
| 37 | poly* ptr1 = left; |
---|
| 38 | poly* ptr2 = right; |
---|
| 39 | poly p1,p2; |
---|
| 40 | p2 = *(left + (right - left >> 1)); |
---|
| 41 | do { |
---|
| 42 | while(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)) { |
---|
| 43 | ptr1++; |
---|
| 44 | } |
---|
| 45 | while(pTotaldegree(*ptr2, currRing) > pTotaldegree(p2,currRing)) { |
---|
| 46 | ptr2--; |
---|
| 47 | } |
---|
| 48 | if(ptr1 > ptr2) { |
---|
| 49 | break; |
---|
| 50 | } |
---|
| 51 | p1 = *ptr1; |
---|
| 52 | *ptr1 = *ptr2; |
---|
| 53 | *ptr2 = p1; |
---|
| 54 | } while(++ptr1 <= --ptr2); |
---|
| 55 | |
---|
| 56 | if(left < ptr2) { |
---|
| 57 | qsortDegree(left,ptr2); |
---|
| 58 | } |
---|
| 59 | if(ptr1 < right) { |
---|
| 60 | qsortDegree(ptr1,right); |
---|
| 61 | } |
---|
[4cfd6d] | 62 | } |
---|
| 63 | |
---|
| 64 | |
---|
[9bb97e] | 65 | |
---|
[199ae7] | 66 | /* |
---|
| 67 | ================================================== |
---|
| 68 | computes incrementally gbs of subsets of the input |
---|
| 69 | gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1} |
---|
| 70 | ================================================== |
---|
[9a6e9f] | 71 | */ |
---|
[87beab7] | 72 | LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag) { |
---|
[55a828] | 73 | //Print("in f5inc\n"); |
---|
[9cb4078] | 74 | //pWrite(rules->getFirst()->getRuleTerm()); |
---|
[9bb97e] | 75 | int j; |
---|
[eab144e] | 76 | //Print("%p\n",gPrev->getFirst()); |
---|
| 77 | //pWrite(gPrev->getFirst()->getPoly()); |
---|
[61944d0] | 78 | poly tempNF = kNF(gbPrev,currQuotient,f_i); |
---|
| 79 | f_i = tempNF; |
---|
[55a828] | 80 | //gPrev->insert(ONE,i,f_i); |
---|
| 81 | gPrev->insert(ONE,gPrev->getLength()+1,f_i); |
---|
[d51339] | 82 | // tag the first element in gPrev of the current index for findReductor() |
---|
[70c15e] | 83 | lTag->setFirstCurrentIdx(gPrev->getLast()); |
---|
[eab144e] | 84 | //Print("1st gPrev: "); |
---|
| 85 | //pWrite(gPrev->getFirst()->getPoly()); |
---|
| 86 | //Print("2nd gPrev: "); |
---|
| 87 | //pWrite(gPrev->getFirst()->getNext()->getPoly()); |
---|
[87beab7] | 88 | //pWrite(gPrev->getFirst()->getNext()->getPoly()); |
---|
[9bb97e] | 89 | CList* critPairs = new CList(); |
---|
| 90 | CNode* critPairsMinDeg = new CNode(); |
---|
[d51339] | 91 | // computation of critical pairs with checking of criterion 1 and criterion 2 and saving them |
---|
| 92 | // in the list critPairs |
---|
| 93 | criticalPair(gPrev, critPairs, lTag, rTag, rules); |
---|
[87beab7] | 94 | static LList* sPolyList = new LList(); |
---|
[c4158f] | 95 | //sPolyList->print(); |
---|
[9bb97e] | 96 | // labeled polynomials which have passed reduction() and have to be added to list gPrev |
---|
[87beab7] | 97 | static LList* completed = new LList(); |
---|
[9bb97e] | 98 | // the reduced labeled polynomials which are returned from subalgorithm reduction() |
---|
[87beab7] | 99 | static LList* reducedLPolys = new LList(); |
---|
[9bb97e] | 100 | // while there are critical pairs to be further checked and deleted/computed |
---|
[7c81165] | 101 | while(NULL != critPairs->getFirst()) { |
---|
[9bb97e] | 102 | // critPairs->getMinDeg() deletes the first elements of minimal degree from |
---|
| 103 | // critPairs, thus the while loop is not infinite. |
---|
| 104 | critPairsMinDeg = critPairs->getMinDeg(); |
---|
| 105 | // adds all to be reduced S-polynomials in the list sPolyList and adds |
---|
| 106 | // the corresponding rules to the list rules |
---|
| 107 | // NOTE: inside there is a second check of criterion 2 if new rules are |
---|
| 108 | // added |
---|
[fcb8022] | 109 | computeSPols(critPairsMinDeg,rTag,rules,sPolyList); |
---|
[7c81165] | 110 | //Print("HIER2\n"); |
---|
[87beab7] | 111 | // DEBUG STUFF FOR SPOLYLIST |
---|
| 112 | LNode* temp = sPolyList->getFirst(); |
---|
[8066e80] | 113 | //while(NULL != temp && NULL != temp->getLPoly()) { |
---|
[598870] | 114 | //Print("Spolylist element: "); |
---|
| 115 | //pWrite(temp->getPoly()); |
---|
[8066e80] | 116 | //temp = temp->getNext(); |
---|
| 117 | //} |
---|
[d51339] | 118 | // reduction process of new S-polynomials and also adds new critical pairs to critPairs |
---|
| 119 | reduction(sPolyList, critPairs, gPrev, rules, lTag, rTag, gbPrev); |
---|
[70c15e] | 120 | |
---|
| 121 | // DEBUG STUFF FOR GPREV |
---|
[598870] | 122 | //temp = gPrev->getFirst(); |
---|
| 123 | //int number = 1; |
---|
| 124 | //Print("\n\n"); |
---|
| 125 | //while(NULL != temp) { |
---|
| 126 | // Print("%d. ",number); |
---|
| 127 | // pWrite(temp->getPoly()); |
---|
| 128 | // temp = temp->getNext(); |
---|
| 129 | // number++; |
---|
| 130 | // Print("\n"); |
---|
| 131 | //} |
---|
| 132 | //sleep(5); |
---|
[70c15e] | 133 | |
---|
[87beab7] | 134 | } |
---|
[598870] | 135 | //Print("REDUCTION DONE\n"); |
---|
| 136 | //Print("%p\n",rules->getFirst()); |
---|
| 137 | //Print("%p\n",rTag->getFirst()); |
---|
[c3da59] | 138 | //if(rules->getFirst() != rTag->getFirst()) { |
---|
[598870] | 139 | //Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n"); |
---|
[c3da59] | 140 | //rTag->insert(rules->getFirst()); |
---|
| 141 | //} |
---|
| 142 | //else { |
---|
[598870] | 143 | //Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n"); |
---|
[c3da59] | 144 | //} |
---|
[d51339] | 145 | lTag->insert(lTag->getFirstCurrentIdx()); |
---|
[598870] | 146 | //Print("INDEX: %d\n",tempTag->getIndex()); |
---|
| 147 | //pWrite(tempTag->getPoly()); |
---|
| 148 | //Print("COMPLETED FIRST IN F5INC: \n"); |
---|
[eab144e] | 149 | //Print("1st gPrev: "); |
---|
| 150 | //pWrite(gPrev->getFirst()->getPoly()); |
---|
| 151 | //Print("2nd gPrev: "); |
---|
| 152 | //pWrite(gPrev->getFirst()->getNext()->getPoly()); |
---|
| 153 | //Print("3rd gPrev: "); |
---|
| 154 | //pWrite(gPrev->getFirst()->getNext()->getNext()->getPoly()); |
---|
[338842d] | 155 | //delete sPolyList; |
---|
[55a828] | 156 | //critPairs->print(); |
---|
[9cb4078] | 157 | delete critPairs; |
---|
[55a828] | 158 | //Print("IN F5INC\n"); |
---|
[9cb4078] | 159 | |
---|
[338842d] | 160 | //gPrev->print(); |
---|
[cce6ed3] | 161 | return gPrev; |
---|
| 162 | } |
---|
| 163 | |
---|
| 164 | |
---|
[9bb97e] | 165 | |
---|
[cce6ed3] | 166 | /* |
---|
| 167 | ================================================================ |
---|
| 168 | computes a list of critical pairs for the next reduction process |
---|
| 169 | first element in gPrev is always the newest element which must |
---|
| 170 | build critical pairs with all other elements in gPrev |
---|
| 171 | ================================================================ |
---|
| 172 | */ |
---|
[9cb4078] | 173 | inline void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) { |
---|
[55a828] | 174 | //Print("IN CRITPAIRS\n"); |
---|
[c9193a] | 175 | // initialization for usage in pLcm() |
---|
| 176 | number nOne = nInit(1); |
---|
| 177 | LNode* newElement = gPrev->getLast(); |
---|
| 178 | LNode* temp = gPrev->getFirst(); |
---|
| 179 | poly u1 = pOne(); |
---|
| 180 | poly u2 = pOne(); |
---|
| 181 | poly lcm = pOne(); |
---|
| 182 | poly t = pHead(newElement->getPoly()); |
---|
[c4158f] | 183 | Rule* testedRule = NULL; |
---|
| 184 | if(NULL != rules->getFirst()) { |
---|
| 185 | testedRule = rules->getFirst()->getRule(); |
---|
| 186 | } |
---|
[c9193a] | 187 | // computation of critical pairs |
---|
[7c81165] | 188 | //critPairs->print(); |
---|
[c9193a] | 189 | while( gPrev->getLast() != temp) { |
---|
| 190 | //pWrite( *(gPrev->getFirst()->getPoly()) ); |
---|
| 191 | // pWrite( *(l->getPoly()) ); |
---|
| 192 | pLcm(newElement->getPoly(), temp->getPoly(), lcm); |
---|
| 193 | pSetCoeff(lcm,nOne); |
---|
| 194 | // computing factors u2 for new labels |
---|
[24ac666] | 195 | pExpVectorDiff(u1,lcm,t); |
---|
| 196 | //pWrite(u1); |
---|
| 197 | //u1 = pDivide(lcm,t); |
---|
| 198 | //pWrite(u1); |
---|
| 199 | //pSetCoeff(u1,nOne); |
---|
| 200 | pExpVectorDiff(u2,lcm,temp->getPoly()); |
---|
| 201 | //pWrite(u2); |
---|
| 202 | //u2 = pDivide(lcm, pHead(temp->getPoly())); |
---|
| 203 | //pWrite(u2); |
---|
| 204 | //pSetCoeff(u2,nOne); |
---|
[c9193a] | 205 | //if(gPrev->getLast()->getIndex()==5) { |
---|
| 206 | //Print("IN CRITPAIRS\n"); |
---|
| 207 | // pWrite(u1); |
---|
| 208 | // Print("1st ELEMENT: "); |
---|
| 209 | // pWrite(newElement->getPoly()); |
---|
| 210 | // Print("2nd ELEMENT: "); |
---|
| 211 | // pWrite(temp->getPoly()); |
---|
| 212 | //} |
---|
| 213 | // testing both new labels by the F5 Criterion |
---|
[24ac666] | 214 | if(!criterion2(u1, newElement, rules, rTag) && !criterion2(u2, temp, rules, rTag) && |
---|
| 215 | !criterion1(gPrev,u1,newElement,lTag) && !criterion1(gPrev,u2,temp,lTag)) { |
---|
[c9193a] | 216 | // if they pass the test, add them to CList critPairs, having the LPoly with greater |
---|
| 217 | // label as first element in the CPair |
---|
| 218 | if(newElement->getIndex() == temp->getIndex() && |
---|
| 219 | -1 == pLmCmp(ppMult_qq(u1, newElement->getTerm()),ppMult_qq(u2, temp->getTerm()))) { |
---|
| 220 | //Print("zweites groesser\n"); |
---|
[7c81165] | 221 | |
---|
[c9193a] | 222 | CPair* cp = new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u2, |
---|
| 223 | temp->getLPoly(), u1, newElement->getLPoly(), testedRule); |
---|
| 224 | critPairs->insert(cp); |
---|
[7c81165] | 225 | //Print("LALA %p\n",critPairs->getFirst()); |
---|
| 226 | //sleep(5); |
---|
[c9193a] | 227 | } |
---|
| 228 | else { |
---|
| 229 | CPair* cp = new CPair(pDeg(ppMult_qq(u2,pHead(temp->getPoly()))), u1, |
---|
| 230 | newElement->getLPoly(), u2, temp->getLPoly(), testedRule); |
---|
[7c81165] | 231 | //Print("erstes groesser\n"); |
---|
[c9193a] | 232 | critPairs->insert(cp); |
---|
[7c81165] | 233 | //Print("LALA %p\n",critPairs->getFirst()); |
---|
| 234 | //sleep(5); |
---|
[c9193a] | 235 | } |
---|
| 236 | } |
---|
| 237 | else { |
---|
| 238 | } |
---|
| 239 | |
---|
| 240 | //Print("\n\n"); |
---|
| 241 | temp = temp->getNext(); |
---|
| 242 | } |
---|
| 243 | // for debugging |
---|
| 244 | //if(NULL != critPairs) { |
---|
| 245 | //critPairs->print(); |
---|
| 246 | //sleep(5); |
---|
| 247 | //} |
---|
[7c81165] | 248 | //Print("END CRITPAIRS\n"); |
---|
[c9193a] | 249 | } |
---|
| 250 | |
---|
| 251 | |
---|
| 252 | |
---|
| 253 | |
---|
[d51339] | 254 | |
---|
| 255 | |
---|
[9bb97e] | 256 | |
---|
[cce6ed3] | 257 | /* |
---|
| 258 | ======================================== |
---|
| 259 | Criterion 1, i.e. Faugere's F5 Criterion |
---|
| 260 | ======================================== |
---|
| 261 | */ |
---|
[9cb4078] | 262 | inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag) { |
---|
[a41f3aa] | 263 | // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag |
---|
[d51339] | 264 | int idx = l->getIndex(); |
---|
[24ac666] | 265 | int i; |
---|
[d51339] | 266 | if(idx == 1) { |
---|
| 267 | return false; |
---|
| 268 | } |
---|
| 269 | else { |
---|
| 270 | LNode* testNode = gPrev->getFirst(); |
---|
| 271 | // save the monom t1*label_term(l) as it is tested various times in the following |
---|
| 272 | poly u1 = ppMult_qq(t,l->getTerm()); |
---|
[598870] | 273 | //Print("------------------------------IN CRITERION 1-----------------------------------------\n"); |
---|
| 274 | //Print("TESTED ELEMENT: "); |
---|
| 275 | //pWrite(l->getPoly()); |
---|
[8066e80] | 276 | //pWrite(l->getTerm()); |
---|
[598870] | 277 | //pWrite(ppMult_qq(t,l->getTerm())); |
---|
| 278 | //Print("%d\n\n",l->getIndex()); |
---|
[24ac666] | 279 | /* |
---|
[c4158f] | 280 | while(testNode->getIndex() < idx) { // && NULL != testNode->getLPoly()) { |
---|
[598870] | 281 | //pWrite(testNode->getPoly()); |
---|
| 282 | //Print("%d\n",testNode->getIndex()); |
---|
[d51339] | 283 | if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) { |
---|
[598870] | 284 | //Print("Criterion 1 NOT passed!\n"); |
---|
[d51339] | 285 | return true; |
---|
| 286 | } |
---|
[598870] | 287 | //pWrite(testNode->getNext()->getPoly()); |
---|
[d51339] | 288 | testNode = testNode->getNext(); |
---|
[cce6ed3] | 289 | } |
---|
[24ac666] | 290 | */ |
---|
| 291 | ideal testId = idInit(idx-1,1); |
---|
| 292 | for(i=0;i<idx-1;i++) { |
---|
| 293 | testId->m[i] = pHead(testNode->getPoly()); |
---|
| 294 | testNode = testNode->getNext(); |
---|
| 295 | } |
---|
| 296 | poly temp = kNF(testId,currQuotient,u1); |
---|
| 297 | //pWrite(temp); |
---|
| 298 | for(i=0;i<IDELEMS(testId);i++) { |
---|
| 299 | testId->m[i] = NULL; |
---|
| 300 | } |
---|
| 301 | idDelete(&testId); |
---|
| 302 | if(NULL == temp) { |
---|
| 303 | return true; |
---|
| 304 | } |
---|
[d51339] | 305 | return false; |
---|
[66e7b5] | 306 | } |
---|
| 307 | } |
---|
[cce6ed3] | 308 | |
---|
[9bb97e] | 309 | |
---|
| 310 | |
---|
[66e7b5] | 311 | /* |
---|
| 312 | ===================================== |
---|
| 313 | Criterion 2, i.e. Rewritten Criterion |
---|
| 314 | ===================================== |
---|
| 315 | */ |
---|
[9cb4078] | 316 | inline bool criterion2(poly t, LNode* l, RList* rules, RTagList* rTag) { |
---|
[55a828] | 317 | //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n"); |
---|
[7c81165] | 318 | /* |
---|
| 319 | Print("RULES: \n"); |
---|
| 320 | RNode* tempR = rules->getFirst(); |
---|
| 321 | int i = 1; |
---|
[c4158f] | 322 | while(NULL != tempR) { |
---|
[7c81165] | 323 | Print("ADDRESS OF %d RNODE: %p\n",i,tempR); |
---|
| 324 | Print("ADDRESS OF RULE: %p\n",tempR->getRule()); |
---|
| 325 | pWrite(tempR->getRuleTerm()); |
---|
| 326 | Print("ADDRESS OF TERM: %p\n",tempR->getRuleTerm()); |
---|
| 327 | Print("%d\n\n",tempR->getRuleIndex()); |
---|
| 328 | tempR = tempR->getNext(); |
---|
| 329 | i++; |
---|
| 330 | } |
---|
| 331 | |
---|
[55a828] | 332 | //Print("TESTED ELEMENT: "); |
---|
| 333 | //pWrite(l->getPoly()); |
---|
| 334 | //pWrite(l->getTerm()); |
---|
| 335 | //pWrite(ppMult_qq(t,l->getTerm())); |
---|
| 336 | //Print("%d\n\n",l->getIndex()); |
---|
[c4158f] | 337 | */ |
---|
[d51339] | 338 | // start at the previously added element to gPrev, as all other elements will have the same index for sure |
---|
[c4158f] | 339 | RNode* testNode; // = new RNode(); |
---|
[e6d283f] | 340 | |
---|
[24ac666] | 341 | if(NULL == rTag->getFirst()->getRule()) { |
---|
| 342 | if(NULL != rules->getFirst()) { |
---|
| 343 | testNode = rules->getFirst(); |
---|
| 344 | } |
---|
| 345 | else { |
---|
| 346 | return false; |
---|
| 347 | } |
---|
[87beab7] | 348 | } |
---|
| 349 | else { |
---|
[24ac666] | 350 | |
---|
[87beab7] | 351 | if(l->getIndex() > rTag->getFirst()->getRuleIndex()) { |
---|
| 352 | testNode = rules->getFirst(); |
---|
| 353 | } |
---|
| 354 | else { |
---|
[e6d283f] | 355 | //Print("HIER\n"); |
---|
| 356 | //Print("DEBUG\n"); |
---|
[598870] | 357 | //Print("L INDEX: %d\n",l->getIndex()); |
---|
[fe88079] | 358 | /*------------------------------------- |
---|
| 359 | * TODO: WHEN INTERREDUCING THE GB THE |
---|
| 360 | * INDEX OF THE PREVIOUS ELEMENTS |
---|
| 361 | * GETS HIGHER! |
---|
[e6d283f] | 362 | *-----------------------------------*/ |
---|
| 363 | //testNode = rules->getFirst(); |
---|
| 364 | testNode = rTag->get(l->getIndex()); |
---|
| 365 | if(NULL == testNode) { |
---|
| 366 | testNode = rules->getFirst(); |
---|
| 367 | } |
---|
[598870] | 368 | //Print("TESTNODE ADDRESS: %p\n",testNode); |
---|
[87beab7] | 369 | } |
---|
| 370 | } |
---|
[e6d283f] | 371 | //testNode = rules->getFirst(); |
---|
[35d0d1a] | 372 | // save the monom t1*label_term(l) as it is tested various times in the following |
---|
[d51339] | 373 | poly u1 = ppMult_qq(t,l->getTerm()); |
---|
[a41f3aa] | 374 | // first element added to rTag was NULL, check for this |
---|
[87beab7] | 375 | //Print("%p\n",testNode->getRule()); |
---|
| 376 | // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1! |
---|
[fe88079] | 377 | //Print("TESTNODE: %p\n",testNode); |
---|
| 378 | //pWrite(testNode->getRuleTerm()); |
---|
[c4158f] | 379 | if(NULL != testNode ) { |
---|
[598870] | 380 | //pWrite(testNode->getRuleTerm()); |
---|
[70c15e] | 381 | } |
---|
| 382 | if(NULL != testNode) { |
---|
| 383 | if(testNode->getRule() == l->getRule()) { |
---|
[598870] | 384 | //Print("%p\n%p\n",testNode->getRule(),l->getRule()); |
---|
| 385 | //Print("EQUAL\n"); |
---|
[70c15e] | 386 | } |
---|
| 387 | else { |
---|
[598870] | 388 | //Print("NOT EQUAL\n"); |
---|
[70c15e] | 389 | } |
---|
| 390 | } |
---|
[c4158f] | 391 | while(NULL != testNode && testNode->getRule() != l->getRule() |
---|
[87beab7] | 392 | && l->getIndex() == testNode->getRuleIndex()) { |
---|
[55a828] | 393 | //Print("%p\n",testNode); |
---|
[598870] | 394 | //pWrite(testNode->getRuleTerm()); |
---|
[55a828] | 395 | //pWrite(t); |
---|
| 396 | //pWrite(l->getTerm()); |
---|
| 397 | //pWrite(u1); |
---|
[61944d0] | 398 | //Print("%d\n",testNode->getRuleIndex()); |
---|
[24ac666] | 399 | if(pLmDivisibleByNoComp(testNode->getRuleTerm(),u1)) { |
---|
[55a828] | 400 | //Print("Criterion 2 NOT passed!\n"); |
---|
[70c15e] | 401 | pDelete(&u1); |
---|
[e6d283f] | 402 | //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n"); |
---|
[66e7b5] | 403 | return true; |
---|
| 404 | } |
---|
[35d0d1a] | 405 | testNode = testNode->getNext(); |
---|
[66e7b5] | 406 | } |
---|
[fe88079] | 407 | //delete testNode; |
---|
[70c15e] | 408 | pDelete(&u1); |
---|
[e6d283f] | 409 | //Print("------------------------------IN CRITERION 2/1-----------------------------------------\n\n"); |
---|
[66e7b5] | 410 | return false; |
---|
[199ae7] | 411 | } |
---|
| 412 | |
---|
[9bb97e] | 413 | |
---|
| 414 | |
---|
[8978fd] | 415 | /* |
---|
[9bb97e] | 416 | ================================================================================================================= |
---|
| 417 | Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter |
---|
| 418 | ================================================================================================================= |
---|
[8978fd] | 419 | */ |
---|
[9cb4078] | 420 | inline bool criterion2(poly t, LPoly* l, RList* rules, Rule* testedRule) { |
---|
[55a828] | 421 | //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n"); |
---|
[598870] | 422 | //Print("LAST RULE TESTED: %p",testedRule); |
---|
[c4158f] | 423 | /* |
---|
| 424 | Print("RULES: \n"); |
---|
| 425 | RNode* tempR = rules->getFirst(); |
---|
| 426 | while(NULL != tempR) { |
---|
| 427 | pWrite(tempR->getRuleTerm()); |
---|
| 428 | Print("%d\n\n",tempR->getRuleIndex()); |
---|
| 429 | tempR = tempR->getNext(); |
---|
| 430 | } |
---|
[598870] | 431 | //Print("TESTED ELEMENT: "); |
---|
| 432 | //pWrite(l->getPoly()); |
---|
[8066e80] | 433 | //pWrite(l->getTerm()); |
---|
[598870] | 434 | //pWrite(ppMult_qq(t,l->getTerm())); |
---|
| 435 | //Print("%d\n\n",l->getIndex()); |
---|
[c4158f] | 436 | */ |
---|
[d51339] | 437 | // start at the previously added element to gPrev, as all other elements will have the same index for sure |
---|
[87beab7] | 438 | RNode* testNode = rules->getFirst(); |
---|
[8978fd] | 439 | // save the monom t1*label_term(l) as it is tested various times in the following |
---|
[d51339] | 440 | poly u1 = ppMult_qq(t,l->getTerm()); |
---|
[35d0d1a] | 441 | // first element added to rTag was NULL, check for this |
---|
[c4158f] | 442 | while(NULL != testNode && testNode->getRule() != testedRule) { |
---|
[598870] | 443 | //pWrite(testNode->getRuleTerm()); |
---|
[24ac666] | 444 | if(pLmDivisibleByNoComp(testNode->getRuleTerm(),u1)) { |
---|
[598870] | 445 | //Print("Criterion 2 NOT passed!\n"); |
---|
[70c15e] | 446 | pDelete(&u1); |
---|
[e6d283f] | 447 | //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n"); |
---|
[8978fd] | 448 | return true; |
---|
| 449 | } |
---|
[35d0d1a] | 450 | testNode = testNode->getNext(); |
---|
[8978fd] | 451 | } |
---|
[70c15e] | 452 | pDelete(&u1); |
---|
[e6d283f] | 453 | //Print("------------------------------IN CRITERION 2/2-----------------------------------------\n\n"); |
---|
[8978fd] | 454 | return false; |
---|
| 455 | } |
---|
[66e7b5] | 456 | |
---|
[9bb97e] | 457 | |
---|
| 458 | |
---|
| 459 | /* |
---|
| 460 | ================================== |
---|
| 461 | Computation of S-Polynomials in F5 |
---|
| 462 | ================================== |
---|
| 463 | */ |
---|
[fcb8022] | 464 | void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) { |
---|
[87beab7] | 465 | CNode* temp = first; |
---|
[61d32c] | 466 | poly sp = pInit(); |
---|
[eab144e] | 467 | //Print("###############################IN SPOLS##############################\n"); |
---|
[7c81165] | 468 | //first->print(); |
---|
| 469 | |
---|
| 470 | while(NULL != temp) { |
---|
| 471 | //Print("JA\n"); |
---|
[9bb97e] | 472 | // only if a new rule was added since the last test in subalgorithm criticalPair() |
---|
[87beab7] | 473 | //if(rules->getFirst() != rTag->getFirst()) { |
---|
[7c81165] | 474 | if(!criterion2(temp->getT1(),temp->getAdLp1(),rules,temp->getTestedRule())) { |
---|
[9bb97e] | 475 | // the second component is tested only when it has the actual index, otherwise there is |
---|
| 476 | // no new rule to test since the last test in subalgorithm criticalPair() |
---|
| 477 | if(temp->getLp2Index() == temp->getLp1Index()) { |
---|
[eab144e] | 478 | if(!criterion2(temp->getT2(),temp->getAdLp2(),rules,temp->getTestedRule())) { |
---|
[9bb97e] | 479 | // computation of S-polynomial |
---|
| 480 | sp = pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()), |
---|
| 481 | ppMult_qq(temp->getT2(),temp->getLp2Poly())); |
---|
[598870] | 482 | //Print("BEGIN SPOLY1\n====================\n"); |
---|
[eab144e] | 483 | pNorm(sp); |
---|
[598870] | 484 | //pWrite(sp); |
---|
| 485 | //Print("END SPOLY1\n====================\n"); |
---|
[87beab7] | 486 | if(NULL == sp) { |
---|
[9bb97e] | 487 | // as rules consist only of pointers we need to save the labeled |
---|
| 488 | // S-polynomial also of a zero S-polynomial |
---|
| 489 | //zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp); |
---|
| 490 | // origin of rule can be set NULL as the labeled polynomial |
---|
| 491 | // will never be used again as it is zero => no problems with |
---|
| 492 | // further criterion2() tests and termination conditions |
---|
[598870] | 493 | //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); |
---|
[35d0d1a] | 494 | reductionsToZero++; |
---|
[55a828] | 495 | //Print("IN SPOLS 1\n"); |
---|
[eab144e] | 496 | rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
[598870] | 497 | //Print("RULE ADDED: \n"); |
---|
| 498 | //pWrite(rules->getFirst()->getRuleTerm()); |
---|
[87beab7] | 499 | // as sp = NULL, delete it |
---|
[eab144e] | 500 | pDelete(&sp); |
---|
[598870] | 501 | //Print("HIER\n"); |
---|
[9bb97e] | 502 | } |
---|
| 503 | else { |
---|
[55a828] | 504 | //Print("IN SPOLS 2\n"); |
---|
[eab144e] | 505 | rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
[598870] | 506 | //Print("RULE ADDED: \n"); |
---|
| 507 | //pWrite(rules->getFirst()->getRuleTerm()); |
---|
[8066e80] | 508 | sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule()); |
---|
[9bb97e] | 509 | } |
---|
| 510 | // data is saved in sPolyList or zero => delete sp |
---|
| 511 | } |
---|
| 512 | } |
---|
| 513 | else { // temp->getLp2Index() < temp->getLp1Index() |
---|
| 514 | // computation of S-polynomial |
---|
| 515 | sp = pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()), |
---|
| 516 | ppMult_qq(temp->getT2(),temp->getLp2Poly())); |
---|
[598870] | 517 | //Print("BEGIN SPOLY2\n====================\n"); |
---|
[d51339] | 518 | pNorm(sp); |
---|
[598870] | 519 | //pWrite(sp); |
---|
| 520 | //Print("END SPOLY2\n====================\n"); |
---|
[87beab7] | 521 | if(NULL == sp) { |
---|
[9bb97e] | 522 | // zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp); |
---|
| 523 | // origin of rule can be set NULL as the labeled polynomial |
---|
| 524 | // will never be used again as it is zero => no problems with |
---|
| 525 | // further criterion2() tests and termination conditions |
---|
[598870] | 526 | //Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); |
---|
[fcb8022] | 527 | reductionsToZero++; |
---|
[55a828] | 528 | //Print("IN SPOLS 3\n"); |
---|
[eab144e] | 529 | rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
[598870] | 530 | //Print("RULE ADDED: \n"); |
---|
| 531 | //pWrite(rules->getFirst()->getRuleTerm()); |
---|
[87beab7] | 532 | // as sp = NULL, delete it |
---|
[eab144e] | 533 | pDelete(&sp); |
---|
[9bb97e] | 534 | } |
---|
| 535 | else { |
---|
[55a828] | 536 | //Print("IN SPOLS 4\n"); |
---|
[eab144e] | 537 | rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term())); |
---|
[598870] | 538 | //Print("RULE ADDED: \n"); |
---|
| 539 | //pWrite(rules->getFirst()->getRuleTerm()); |
---|
| 540 | //Print("%d\n",rules->getFirst()->getRuleIndex()); |
---|
| 541 | //Print("%p\n",sPolyList->getFirst()); |
---|
[61944d0] | 542 | sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule()); |
---|
[9bb97e] | 543 | } |
---|
| 544 | } |
---|
| 545 | } |
---|
[87beab7] | 546 | //} |
---|
[7c81165] | 547 | //Print("%p\n",temp); |
---|
[9bb97e] | 548 | temp = temp->getNext(); |
---|
[7c81165] | 549 | //Print("%p\n",temp); |
---|
| 550 | //Print("%p\n",temp->getData()); |
---|
| 551 | //pWrite(temp->getLp1Poly()); |
---|
[9bb97e] | 552 | } |
---|
| 553 | // these critical pairs can be deleted now as they are either useless for further computations or |
---|
| 554 | // already saved as an S-polynomial to be reduced in the following |
---|
| 555 | delete first; |
---|
| 556 | } |
---|
| 557 | |
---|
| 558 | |
---|
| 559 | |
---|
| 560 | /* |
---|
| 561 | ======================================================================== |
---|
| 562 | reduction including subalgorithm topReduction() using Faugere's criteria |
---|
| 563 | ======================================================================== |
---|
| 564 | */ |
---|
[d51339] | 565 | void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, |
---|
[fcb8022] | 566 | ideal gbPrev) { |
---|
[598870] | 567 | //Print("##########################################In REDUCTION!########################################\n"); |
---|
[416ea2] | 568 | // check if sPolyList has any elements |
---|
| 569 | // NOTE: due to initialization sPolyList always has a default NULL element |
---|
[d51339] | 570 | while(sPolyList->getLength() > 0) { |
---|
[598870] | 571 | //Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength()); |
---|
[70c15e] | 572 | if(sPolyList->getLength() > 1) { |
---|
[598870] | 573 | //Print("%p\n",sPolyList->getFirst()); |
---|
| 574 | //Print("%p\n",sPolyList->getFirst()->getLPoly()); |
---|
| 575 | //Print("%p\n",sPolyList->getFirst()->getNext()); |
---|
| 576 | //Print("%p\n",sPolyList->getFirst()->getNext()->getLPoly()); |
---|
| 577 | //Print("%p\n",sPolyList->getFirst()); |
---|
[70c15e] | 578 | } |
---|
[61944d0] | 579 | //if(gPrev->getLast()->getIndex() == 5) { |
---|
| 580 | //sPolyList->print(); |
---|
| 581 | //sleep(5); |
---|
| 582 | //} |
---|
| 583 | |
---|
[416ea2] | 584 | // temp is the first element in the sPolyList which should be reduced |
---|
| 585 | // due to earlier sorting this is the element of minimal degree AND |
---|
| 586 | // minimal label |
---|
[9bb97e] | 587 | LNode* temp = sPolyList->getFirst(); |
---|
[598870] | 588 | //pWrite(temp->getPoly()); |
---|
[416ea2] | 589 | // delete the above first element from sPolyList, temp will be either reduced to |
---|
| 590 | // zero or added to gPrev, but never come back to sPolyList |
---|
[c4158f] | 591 | if(NULL != temp) { |
---|
[598870] | 592 | sPolyList->setFirst(temp->getNext()); |
---|
| 593 | //Print("HIER\n"); |
---|
| 594 | } |
---|
| 595 | else { |
---|
| 596 | break; |
---|
| 597 | } |
---|
| 598 | //Print("HALLO %p\n",temp->getPoly()); |
---|
| 599 | //Print("%p\n",temp->getPoly()); |
---|
| 600 | //pWrite(temp->getPoly()); |
---|
| 601 | //idShow(gbPrev); |
---|
[416ea2] | 602 | poly tempNF = kNF(gbPrev,currQuotient,temp->getPoly()); |
---|
[598870] | 603 | //Print("LENGTH: %d\n",sPolyList->getLength()); |
---|
| 604 | //pWrite(tempNF); |
---|
| 605 | //pWrite(temp->getPoly()); |
---|
[416ea2] | 606 | if(NULL != tempNF) { |
---|
[c9193a] | 607 | pNorm(tempNF); |
---|
[416ea2] | 608 | // write the reduced polynomial in temp |
---|
[fcb8022] | 609 | temp->setPoly(tempNF); |
---|
[416ea2] | 610 | // try further reductions of temp with polynomials in gPrev |
---|
| 611 | // with label index = current label index: this is done such that there |
---|
| 612 | // is no label corruption during the reduction process |
---|
[61944d0] | 613 | topReduction(temp,sPolyList,gPrev,rules,lTag,rTag,gbPrev); |
---|
[70c15e] | 614 | |
---|
[d51339] | 615 | } |
---|
| 616 | if(NULL != temp->getPoly()) { |
---|
| 617 | //CList* newCritPairs = new CList; |
---|
[598870] | 618 | //Print("##################IN CRITPAIRS IN REDUCTION#####################\n"); |
---|
[9cb4078] | 619 | criticalPair(gPrev,critPairs,lTag,rTag,rules); |
---|
[8066e80] | 620 | //Print("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++H I E R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n"); |
---|
[d51339] | 621 | } |
---|
| 622 | else { |
---|
[70c15e] | 623 | //delete temp; |
---|
| 624 | LNode* tempLoop = gPrev->getFirst(); |
---|
[598870] | 625 | //Print("AUSGABE IN REDUCTION:\n"); |
---|
[8066e80] | 626 | //while(NULL != tempLoop) { |
---|
[598870] | 627 | //pWrite(tempLoop->getPoly()); |
---|
[8066e80] | 628 | //tempLoop = tempLoop->getNext(); |
---|
| 629 | //} |
---|
[70c15e] | 630 | //sleep(10); |
---|
[9bb97e] | 631 | } |
---|
[9cb4078] | 632 | |
---|
[9bb97e] | 633 | } |
---|
| 634 | } |
---|
| 635 | |
---|
| 636 | |
---|
| 637 | |
---|
| 638 | /* |
---|
| 639 | ===================================================================================== |
---|
| 640 | top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of |
---|
| 641 | the same index whereas the labels are taken into account |
---|
| 642 | ===================================================================================== |
---|
| 643 | */ |
---|
[61944d0] | 644 | void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev) { |
---|
[598870] | 645 | //Print("##########################################In topREDUCTION!########################################\n"); |
---|
[d51339] | 646 | // try l as long as there are reductors found by findReductor() |
---|
| 647 | do { |
---|
[338842d] | 648 | LNode* gPrevRedCheck = new LNode(lTag->getFirstCurrentIdx()); |
---|
[9cb4078] | 649 | //Print("gPrevCheckPOLY: "); |
---|
| 650 | //pWrite(gPrevRedCheck->getPoly()); |
---|
[338842d] | 651 | LNode* tempRed = new LNode(); |
---|
[55a828] | 652 | //Print("TESTED POLYNOMIAL IN THE FOLLOWING: "); |
---|
| 653 | //pWrite(l->getPoly()); |
---|
[c9193a] | 654 | //Print("HIER\n"); |
---|
[338842d] | 655 | tempRed = findReductor(l,gPrevRedCheck,gPrev,rules,lTag,rTag); |
---|
[fe88079] | 656 | //Print("TEMPRED NEXT: %p\n",tempRed->getNext()); |
---|
[598870] | 657 | //Print("--------------------------------HIER DEBUG 2----------------------------------\n"); |
---|
[d51339] | 658 | // if a reductor for l is found and saved in tempRed |
---|
| 659 | if(NULL != tempRed) { |
---|
| 660 | // if label of reductor is greater than the label of l we have to built a new element |
---|
| 661 | // and add it to sPolyList |
---|
[55a828] | 662 | //Print("REDUCTOR POLYNOMIAL: "); |
---|
| 663 | //pWrite(tempRed->getPoly()); |
---|
| 664 | //Print("TEMPRED: %p\n",tempRed); |
---|
| 665 | //Print("TERM: "); |
---|
| 666 | //pWrite(tempRed->getTerm()); |
---|
[d51339] | 667 | if(pLmCmp(tempRed->getTerm(),l->getTerm()) == 1) { |
---|
[61944d0] | 668 | // needed sinc pSub destroys the arguments! |
---|
[8066e80] | 669 | //Print("H----------I------------E--------------R\n"); |
---|
[61944d0] | 670 | poly temp_poly_l = pInit(); |
---|
| 671 | temp_poly_l = pCopy(l->getPoly()); |
---|
| 672 | //Print("POLYNOMIAL L: "); |
---|
| 673 | //pWrite(l->getPoly()); |
---|
| 674 | //pWrite(temp_poly_l); |
---|
| 675 | poly temp = pSub(tempRed->getPoly(),temp_poly_l); |
---|
| 676 | //Print("POLYNOMIAL L: "); |
---|
| 677 | //pWrite(l->getPoly()); |
---|
| 678 | //pWrite(temp_poly_l); |
---|
| 679 | //Print("AFTER REDUCTION STEP: "); |
---|
| 680 | //pWrite(temp); |
---|
| 681 | //sleep(20); |
---|
[598870] | 682 | //pWrite(temp); |
---|
[d51339] | 683 | if(NULL != temp) { |
---|
[70c15e] | 684 | pNorm(temp); |
---|
[d51339] | 685 | tempRed->setPoly(temp); |
---|
[61944d0] | 686 | //pWrite(tempRed->getPoly()); |
---|
[d51339] | 687 | // for debugging |
---|
[598870] | 688 | //pWrite(tempRed->getPoly()); |
---|
[55a828] | 689 | //Print("RULE ADDED\n"); |
---|
[d51339] | 690 | rules->insert(tempRed->getIndex(),tempRed->getTerm()); |
---|
| 691 | tempRed->getLPoly()->setRule(rules->getFirst()->getRule()); |
---|
[55a828] | 692 | //Print("%p\n",sPolyList->getFirst()); |
---|
| 693 | //Print("%p\n",sPolyList->getFirst()->getLPoly()); |
---|
| 694 | //Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength()); |
---|
[8066e80] | 695 | //sPolyList->print(); |
---|
| 696 | |
---|
[d51339] | 697 | sPolyList->insertByLabel(tempRed); |
---|
[55a828] | 698 | //sPolyList->print(); |
---|
[8066e80] | 699 | //Print("SPOLYLIST LENGTH: %d\n",sPolyList->getLength()); |
---|
| 700 | //Print("OH JE\n"); |
---|
[d51339] | 701 | } |
---|
| 702 | else { |
---|
| 703 | pDelete(&temp); |
---|
| 704 | reductionsToZero++; |
---|
[598870] | 705 | //Print("RULE ADDED\n"); |
---|
[55a828] | 706 | //rules->insert(tempRed->getIndex(),tempRed->getTerm()); |
---|
| 707 | //pWrite(rules->getFirst()->getRuleTerm()); |
---|
| 708 | //Print("DELETE TEMPRED\n"); |
---|
[d51339] | 709 | delete tempRed; |
---|
| 710 | } |
---|
| 711 | } |
---|
| 712 | // label of reductor is smaller than the label of l, subtract reductor from l and delete the |
---|
| 713 | // gPrevRedCheck pointer added to l during findReductor() as the head term of l changes |
---|
| 714 | // after subtraction |
---|
| 715 | else { |
---|
[61944d0] | 716 | poly temp_poly_l = pInit(); |
---|
| 717 | temp_poly_l = pCopy(l->getPoly()); |
---|
| 718 | poly temp = pSub(temp_poly_l,tempRed->getPoly()); |
---|
| 719 | //Print("AFTER REDUCTION STEP: "); |
---|
[598870] | 720 | //pWrite(temp); |
---|
[d51339] | 721 | if(NULL != temp) { |
---|
[70c15e] | 722 | pNorm(temp); |
---|
[61944d0] | 723 | poly tempNF = kNF(gbPrev,currQuotient,temp); |
---|
| 724 | pNorm(tempNF); |
---|
[c9193a] | 725 | //pWrite(tempNF); |
---|
| 726 | if(NULL == tempNF) { |
---|
| 727 | reductionsToZero++; |
---|
| 728 | pDelete(&tempNF); |
---|
| 729 | l->setPoly(NULL); |
---|
| 730 | break; |
---|
| 731 | } |
---|
[61944d0] | 732 | l->setPoly(tempNF); |
---|
[c9193a] | 733 | |
---|
| 734 | //pWrite(l->getPoly()); |
---|
[338842d] | 735 | gPrevRedCheck = lTag->getFirstCurrentIdx(); |
---|
[d51339] | 736 | } |
---|
| 737 | else { |
---|
[598870] | 738 | //Print("ZERO REDUCTION!\n"); |
---|
[70c15e] | 739 | reductionsToZero++; |
---|
[d51339] | 740 | pDelete(&temp); |
---|
| 741 | l->setPoly(NULL); |
---|
[598870] | 742 | //pWrite(gPrev->getLast()->getPoly()); |
---|
[70c15e] | 743 | break; |
---|
[d51339] | 744 | } |
---|
| 745 | } |
---|
| 746 | } |
---|
| 747 | else { |
---|
| 748 | if(NULL != l->getPoly()) { |
---|
[61944d0] | 749 | pNorm(l->getPoly()); |
---|
[55a828] | 750 | //Print("----------------------------------ADDED TO GPREV IN TOPREDUCTION:-------------------------------------- "); |
---|
| 751 | //pWrite(l->getPoly()); |
---|
| 752 | //pWrite(l->getTerm()); |
---|
| 753 | //Print("INDEX: %d\n\n\n", l->getIndex()); |
---|
[8066e80] | 754 | //sleep(20); |
---|
[d51339] | 755 | gPrev->insert(l->getLPoly()); |
---|
[598870] | 756 | //Print("GPREV: \n"); |
---|
[d51339] | 757 | LNode* tempLoop = gPrev->getFirst(); |
---|
[8066e80] | 758 | //while(NULL != tempLoop) { |
---|
[598870] | 759 | //Print("HERE\n"); |
---|
| 760 | //pWrite(tempLoop->getPoly()); |
---|
[8066e80] | 761 | //tempLoop = tempLoop->getNext(); |
---|
| 762 | //} |
---|
[d51339] | 763 | } |
---|
| 764 | break; |
---|
| 765 | } |
---|
| 766 | } while(1); |
---|
[416ea2] | 767 | } |
---|
[9bb97e] | 768 | |
---|
| 769 | |
---|
| 770 | /* |
---|
| 771 | ===================================================================== |
---|
| 772 | subalgorithm to find a possible reductor for the labeled polynomial l |
---|
| 773 | ===================================================================== |
---|
| 774 | */ |
---|
[338842d] | 775 | LNode* findReductor(LNode* l, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag) { |
---|
[d51339] | 776 | // allociation of memory for the possible reductor |
---|
[598870] | 777 | //Print("IN FIND REDUCTOR\n"); |
---|
[d51339] | 778 | poly u = pOne(); |
---|
| 779 | poly red = pOne(); |
---|
| 780 | number nOne = nInit(1); |
---|
| 781 | LNode* temp = new LNode(); |
---|
| 782 | // head term of actual element such that we do not have to call pHead at each new reductor test |
---|
| 783 | poly t = pHead(l->getPoly()); |
---|
| 784 | // if l was already checked use the information in gPrevRedCheck such |
---|
| 785 | // that we can start searching for new reducers from this point and |
---|
| 786 | // not from the first element of gPrev with the current index |
---|
[338842d] | 787 | temp = gPrevRedCheck; |
---|
[fe88079] | 788 | //temp = lTag->getFirstCurrentIdx(); |
---|
| 789 | //Print("GPREVREDCHECK: %p\n",gPrevRedCheck); |
---|
| 790 | //pWrite(gPrevRedCheck->getPoly()); |
---|
[d51339] | 791 | // search for reductors until we are at the end of gPrev resp. at the |
---|
| 792 | // end of the elements of the current index |
---|
| 793 | while(NULL != temp && temp->getIndex() == l->getIndex()) { |
---|
[338842d] | 794 | //pWrite(temp->getPoly()); |
---|
| 795 | //Print("INDEX: %d\n",temp->getIndex()); |
---|
[d51339] | 796 | // does the head of the element of gPrev divides the head of |
---|
| 797 | // the to be reduced element? |
---|
[c9193a] | 798 | //Print("-------------FOUND REDUCTORS----------------------\n"); |
---|
| 799 | //Print("\n"); |
---|
| 800 | //pWrite(temp->getPoly()); |
---|
| 801 | //pWrite(temp->getTerm()); |
---|
| 802 | //pWrite(t); |
---|
| 803 | //Print("HALLO\n"); |
---|
[24ac666] | 804 | if(pLmDivisibleByNoComp(pHead(temp->getPoly()),t)) { |
---|
[c9193a] | 805 | //Print("HALLO\n"); |
---|
[d51339] | 806 | // get all the information needed for the following tests |
---|
| 807 | // of the criteria |
---|
| 808 | u = pDivide(t,pHead(temp->getPoly())); |
---|
| 809 | pSetCoeff(u,nOne); |
---|
[c9193a] | 810 | //Print("HIER FINDRED\n"); |
---|
| 811 | //pWrite(u); |
---|
| 812 | //Print("\n"); |
---|
[d51339] | 813 | red = ppMult_qq(u,temp->getPoly()); |
---|
| 814 | pNorm(red); |
---|
[61944d0] | 815 | //u = ppMult_qq(u,temp->getTerm()); |
---|
| 816 | //pSetCoeff(u,nOne); |
---|
[d51339] | 817 | // check if both have the same label |
---|
[c9193a] | 818 | //Print("HALLO\n"); |
---|
[d51339] | 819 | if(pLmCmp(u,l->getTerm()) != 0) { |
---|
[c9193a] | 820 | //Print("HALLO\n"); |
---|
[d51339] | 821 | // passing criterion2 ? |
---|
| 822 | if(!criterion2(u,temp,rules,rTag)) { |
---|
| 823 | // passing criterion1 ? |
---|
| 824 | if(!criterion1(gPrev,u,temp,lTag)) { |
---|
[598870] | 825 | //Print("HIER DEBUG\n"); |
---|
[9cb4078] | 826 | gPrevRedCheck = temp->getNext(); |
---|
[8066e80] | 827 | LNode* redNode = new LNode(ppMult_qq(u,temp->getTerm()),temp->getIndex(),red,NULL,NULL); |
---|
[d51339] | 828 | return redNode; |
---|
| 829 | } |
---|
| 830 | } |
---|
| 831 | } |
---|
| 832 | } |
---|
[c9193a] | 833 | //Print("%p\n",temp->getNext()); |
---|
| 834 | //pWrite(temp->getPoly()); |
---|
| 835 | //Print("HALLO\n"); |
---|
[d51339] | 836 | temp = temp->getNext(); |
---|
| 837 | } |
---|
| 838 | |
---|
| 839 | // delete temp; |
---|
[598870] | 840 | //Print("1st gPrev: "); |
---|
| 841 | //pWrite(gPrev->getFirst()->getPoly()); |
---|
| 842 | //Print("2nd gPrev: "); |
---|
| 843 | //pWrite(gPrev->getFirst()->getNext()->getPoly()); |
---|
[d51339] | 844 | return NULL; |
---|
[9bb97e] | 845 | } |
---|
| 846 | |
---|
| 847 | |
---|
| 848 | |
---|
[199ae7] | 849 | /* |
---|
| 850 | ========================================================================== |
---|
[66e7b5] | 851 | MAIN:computes a gb of the ideal i in the ring r with our F5 implementation |
---|
[199ae7] | 852 | ========================================================================== |
---|
| 853 | */ |
---|
| 854 | ideal F5main(ideal id, ring r) { |
---|
[9cb4078] | 855 | int i,j,k,l; |
---|
[87beab7] | 856 | int gbLength; |
---|
[a0350e9] | 857 | // 1 polynomial for defining initial labels & further tests |
---|
[66e7b5] | 858 | poly ONE = pOne(); |
---|
[9cb4078] | 859 | poly pOne = pOne(); |
---|
| 860 | number nOne = nInit(1); |
---|
[87beab7] | 861 | // tag the first element of index i-1 for criterion 1 |
---|
| 862 | LTagList* lTag = new LTagList(); |
---|
[55a828] | 863 | //Print("LTAG BEGINNING: %p\n",lTag); |
---|
[ed30c5] | 864 | |
---|
[87beab7] | 865 | // first element in rTag is first element of rules which is NULL RNode, |
---|
| 866 | // this must be done due to possible later improvements |
---|
| 867 | RList* rules = new RList(); |
---|
[c4158f] | 868 | Print("RULES FIRST: %p\n",rules->getFirst()); |
---|
[55a828] | 869 | //Print("RULES FIRST DATA: %p\n",rules->getFirst()->getRule()); |
---|
[87beab7] | 870 | RTagList* rTag = new RTagList(rules->getFirst()); |
---|
| 871 | i = 1; |
---|
[199ae7] | 872 | for(j=0; j<IDELEMS(id); j++) { |
---|
| 873 | if(NULL != id->m[j]) { |
---|
| 874 | if(pComparePolys(id->m[j],ONE)) { |
---|
[ed30c5] | 875 | Print("One Polynomial in Input => Computations stopped\n"); |
---|
[cce6ed3] | 876 | ideal idNew = idInit(1,1); |
---|
| 877 | idNew->m[0] = ONE; |
---|
| 878 | return(idNew); |
---|
[ed30c5] | 879 | } |
---|
[cfb8edb] | 880 | } |
---|
[ed30c5] | 881 | } |
---|
[c9193a] | 882 | ideal idNew = kInterRed(id); |
---|
| 883 | id = idNew; |
---|
[24ac666] | 884 | //qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]); |
---|
[9cb4078] | 885 | idShow(id); |
---|
[9bb97e] | 886 | LList* gPrev = new LList(ONE, i, id->m[0]); |
---|
[61944d0] | 887 | //idShow(id); |
---|
[598870] | 888 | //Print("%p\n",id->m[0]); |
---|
| 889 | //pWrite(id->m[0]); |
---|
| 890 | //Print("%p\n",gPrev->getFirst()->getPoly()); |
---|
| 891 | //pWrite(gPrev->getFirst()->getPoly()); |
---|
[61d32c] | 892 | |
---|
[87beab7] | 893 | lTag->insert(gPrev->getFirst()); |
---|
[d51339] | 894 | lTag->setFirstCurrentIdx(gPrev->getFirst()); |
---|
[9bb97e] | 895 | // computing the groebner basis of the elements of index < actual index |
---|
[87beab7] | 896 | gbLength = gPrev->getLength(); |
---|
[598870] | 897 | //Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength()); |
---|
[fcb8022] | 898 | ideal gbPrev = idInit(gbLength,1); |
---|
[9bb97e] | 899 | // initializing the groebner basis of elements of index < actual index |
---|
| 900 | gbPrev->m[0] = gPrev->getFirst()->getPoly(); |
---|
[598870] | 901 | //idShow(gbPrev); |
---|
| 902 | //idShow(currQuotient); |
---|
[9bb97e] | 903 | |
---|
[cce6ed3] | 904 | for(i=2; i<=IDELEMS(id); i++) { |
---|
[d51339] | 905 | LNode* gPrevTag = gPrev->getLast(); |
---|
[598870] | 906 | //Print("Last POlynomial in GPREV: "); |
---|
| 907 | //Print("%p\n",gPrevTag); |
---|
| 908 | //pWrite(gPrevTag->getPoly()); |
---|
[87beab7] | 909 | gPrev = F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag); |
---|
[7c81165] | 910 | //Print("____________________________________ITERATION STEP DONE________________________________________\n"); |
---|
[9cb4078] | 911 | |
---|
[70c15e] | 912 | // DEBUGGING STUFF |
---|
| 913 | LNode* temp = gPrev->getFirst(); |
---|
[598870] | 914 | // computing new groebner basis gbPrev |
---|
[d51339] | 915 | if(gPrev->getLength() > gbLength) { |
---|
| 916 | ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); |
---|
[9cb4078] | 917 | LNode* temp = gPrevTag; |
---|
[598870] | 918 | //Print("%p\n",gPrevTag); |
---|
| 919 | //Print("%p\n",gPrev->getLast()); |
---|
| 920 | //pWrite(temp->getPoly()); |
---|
| 921 | //Print("LENGTH OF GPREV LIST: %d\n",gPrev->getLength()); |
---|
| 922 | //Print("%d\n",gbLength); |
---|
[55a828] | 923 | //Print("%d\n",gPrev->getLength()-gbLength-1); |
---|
[9cb4078] | 924 | for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { |
---|
[fe88079] | 925 | //Print("YES\n"); |
---|
[9cb4078] | 926 | temp = temp->getNext(); |
---|
| 927 | if(temp) { |
---|
[fe88079] | 928 | //Print("%p\n",temp); |
---|
| 929 | //pWrite(temp->getPoly()); |
---|
| 930 | //Print("%p\n",temp->getNext()); |
---|
[9cb4078] | 931 | } |
---|
| 932 | gbAdd->m[j] = temp->getPoly(); |
---|
| 933 | //pWrite(temp->getPoly()); |
---|
| 934 | } |
---|
[fe88079] | 935 | //Print("HIER AUCH\n"); |
---|
[9cb4078] | 936 | gbPrev = idAdd(gbPrev,gbAdd); |
---|
[c3da59] | 937 | |
---|
| 938 | |
---|
[9cb4078] | 939 | // interreduction stuff |
---|
[55a828] | 940 | |
---|
[9cb4078] | 941 | if(i<IDELEMS(id)) { |
---|
| 942 | ideal tempId = kInterRed(gbPrev); |
---|
[24ac666] | 943 | //idShow(tempId); |
---|
[d738b47] | 944 | sleep(5); |
---|
[9cb4078] | 945 | gbPrev = tempId; |
---|
[24ac666] | 946 | //qsortDegree(&gbPrev->m[0],&gbPrev->m[IDELEMS(gbPrev)-1]); |
---|
[9cb4078] | 947 | delete gPrev; |
---|
[fe88079] | 948 | //Print("RULES FIRST NOW1: %p\n",rules->getFirst()); |
---|
[55a828] | 949 | //Print("HIER\n"); |
---|
[9cb4078] | 950 | delete rules; |
---|
[c3da59] | 951 | //delete rTag; |
---|
[55a828] | 952 | //Print("HIER AUCH\n"); |
---|
[fe88079] | 953 | //Print("%p\n",rules->getFirst()); |
---|
| 954 | gPrev = new LList(pOne,1,gbPrev->m[0]); |
---|
[9cb4078] | 955 | gPrev->insert(pOne,1,gbPrev->m[1]); |
---|
| 956 | poly tempPoly = pInit(); |
---|
| 957 | pSetCoeff(tempPoly,nOne); |
---|
| 958 | pLcm(pHead(gbPrev->m[0]),pHead(gbPrev->m[1]),tempPoly); |
---|
| 959 | rules = new RList(); |
---|
[e6d283f] | 960 | rTag = new RTagList(rules->getFirst()); |
---|
[c3da59] | 961 | |
---|
[fe88079] | 962 | //Print("%p\n",rules->getFirst()); |
---|
| 963 | //pWrite(tempPoly); |
---|
[9cb4078] | 964 | rules->insert(2,tempPoly); |
---|
[e6d283f] | 965 | rTag->insert(rules->getFirst()); |
---|
| 966 | //Print("%p\n",rules->getFirst()); |
---|
| 967 | //Print("%p\n",rTag->getFirst()); |
---|
[fe88079] | 968 | //Print("%p\n",rules->getFirst()); |
---|
| 969 | //Print("%p\n",rules->getFirst()->getNext()->getNext()); |
---|
| 970 | //Print("HIERLALA\n"); |
---|
| 971 | //pWrite(rules->getFirst()->getRuleTerm()); |
---|
[55a828] | 972 | // Print("RULES FIRST NOW2: %p\n",rules->getFirst()); |
---|
[9cb4078] | 973 | for(k=2; k<IDELEMS(gbPrev); k++) { |
---|
| 974 | gPrev->insert(pOne,k+1,gbPrev->m[k]); |
---|
| 975 | for(l=0; l<k; l++) { |
---|
[55a828] | 976 | //pWrite(gbPrev->m[k]); |
---|
| 977 | //pWrite(gbPrev->m[l]); |
---|
[9cb4078] | 978 | pLcm(pHead(gbPrev->m[k]),pHead(gbPrev->m[l]),tempPoly); |
---|
| 979 | pSetCoeff(tempPoly,nOne); |
---|
| 980 | rules->insert(k+1,tempPoly); |
---|
| 981 | } |
---|
[c3da59] | 982 | rTag->insert(rules->getFirst()); |
---|
[9cb4078] | 983 | } |
---|
| 984 | } |
---|
[55a828] | 985 | |
---|
[9cb4078] | 986 | gbLength = gPrev->getLength(); |
---|
[e6d283f] | 987 | //Print("HIER\n"); |
---|
[d51339] | 988 | } |
---|
[55a828] | 989 | //gPrev->print(); |
---|
[9cb4078] | 990 | //int anzahl = 1; |
---|
[598870] | 991 | //while(NULL != temp) { |
---|
| 992 | // Print("%d. Element: ",anzahl); |
---|
| 993 | // pWrite(temp->getPoly()); |
---|
| 994 | // Print("\n"); |
---|
| 995 | // temp = temp->getNext(); |
---|
| 996 | // anzahl++; |
---|
| 997 | //} |
---|
| 998 | //sleep(5); |
---|
| 999 | //Print("GROEBNER BASIS:\n====================================================\n"); |
---|
| 1000 | //idShow(gbPrev); |
---|
| 1001 | //Print("===================================================\n"); |
---|
| 1002 | //Print("JA\n"); |
---|
[cce6ed3] | 1003 | } |
---|
[c4158f] | 1004 | //idShow(gbPrev); |
---|
[fcb8022] | 1005 | Print("\n\nNumber of zero-reductions: %d\n",reductionsToZero); |
---|
[598870] | 1006 | //LNode* temp = gPrev->getFirst(); |
---|
| 1007 | //while(NULL != temp) { |
---|
| 1008 | // pWrite(temp->getPoly()); |
---|
| 1009 | // temp = temp->getNext(); |
---|
| 1010 | // } |
---|
[338842d] | 1011 | //gPrev->print(); |
---|
| 1012 | //delete lTag; |
---|
| 1013 | //delete rTag; |
---|
[9cb4078] | 1014 | //delete gPrev; |
---|
[fcb8022] | 1015 | return(gbPrev); |
---|
[9a6e9f] | 1016 | |
---|
| 1017 | |
---|
[936551] | 1018 | } |
---|
[9a6e9f] | 1019 | |
---|
[936551] | 1020 | #endif |
---|