Changeset fcb8022 in git for kernel/f5gb.cc
- Timestamp:
- Feb 8, 2009, 8:17:54 PM (15 years ago)
- Branches:
- (u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
- Children:
- 35d0d1a7256e75184cea2fe4d2e02762b243b544
- Parents:
- 9bb97ef0a0e640ba336498902b874a16dc7b978e
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/f5gb.cc
r9bb97e rfcb8022 2 2 * Computer Algebra System SINGULAR * 3 3 ****************************************/ 4 /* $Id: f5gb.cc,v 1.2 3 2009-02-06 20:12:35ederc Exp $ */4 /* $Id: f5gb.cc,v 1.24 2009-02-08 19:17:54 ederc Exp $ */ 5 5 /* 6 6 * ABSTRACT: f5gb interface … … 25 25 #include "f5lists.h" 26 26 27 27 int reductionsToZero = 0; 28 //*reductionsToZero = 0; 28 29 29 30 /* … … 69 70 ================================================== 70 71 */ 71 LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE , int* reductionsToZero) {72 LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE) { 72 73 int j; 73 74 // tag the first element of index i-1 for criterion 1 … … 100 101 // NOTE: inside there is a second check of criterion 2 if new rules are 101 102 // added 102 computeSPols(critPairsMinDeg,rTag,rules,sPolyList ,reductionsToZero);103 computeSPols(critPairsMinDeg,rTag,rules,sPolyList); 103 104 104 reducedLPolys = reduction(sPolyList, completed, g bPrev, reductionsToZero);105 reducedLPolys = reduction(sPolyList, completed, gPrev, lTag, rTag, gbPrev); 105 106 } 106 107 return gPrev; … … 124 125 poly* u2 = new poly(pInit()); 125 126 poly* lcm = new poly(pInit()); 127 poly t = pHead(first->getPoly()); 126 128 // computation of critical pairs 127 129 while( NULL != l) { … … 130 132 pLcm(first->getPoly(), l->getPoly(), *lcm); 131 133 pSetCoeff(*lcm,nOne); 132 // computing factors u1 & u2 for new labels 133 *u1 = pDivide(*lcm,pHead(first->getPoly())); 134 // computing factors u2 for new labels 135 pWrite(t); 136 *u1 = pDivide(*lcm,t); 137 pWrite(*u1); 134 138 pSetCoeff(*u1,nOne); 139 pWrite(pHead(l->getPoly())); 135 140 *u2 = pDivide(*lcm, pHead(l->getPoly())); 136 141 pSetCoeff(*u2,nOne); 142 Print("IN CRITPAIRS\n"); 137 143 pWrite(*u2); 138 144 // testing both new labels by the F5 Criterion … … 178 184 poly u1 = ppMult_qq(*t,l->getTerm()); 179 185 while(NULL != testNode) { 180 if(pLmDivisibleByNoComp( pHead(testNode->getPoly()),u1)) {186 if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) { 181 187 Print("Criterion 1 NOT passed!\n"); 182 188 return true; … … 240 246 ================================== 241 247 */ 242 void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList , int* reductionsToZero) {248 void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) { 243 249 CNode* temp = first; 244 250 poly zero = pInit(); … … 266 272 // will never be used again as it is zero => no problems with 267 273 // further criterion2() tests and termination conditions 268 *reductionsToZero++;274 reductionsToZero++; 269 275 rules->insert(temp->getLp1Index(),temp->getT1(),NULL); 276 rTag->setFirst(rules->getFirst()); 270 277 } 271 278 else { 272 279 sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp); 273 280 rules->insert(temp->getLp1Index(),temp->getT1(),sPolyList->getFirst()->getLPoly()); 281 rTag->setFirst(rules->getFirst()); 274 282 } 275 283 // data is saved in sPolyList or zero => delete sp … … 290 298 // will never be used again as it is zero => no problems with 291 299 // further criterion2() tests and termination conditions 292 *reductionsToZero++;300 reductionsToZero++; 293 301 rules->insert(temp->getLp1Index(),temp->getT1(),NULL); 302 rTag->setFirst(rules->getFirst()); 303 294 304 } 295 305 else { 296 306 sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp); 297 307 rules->insert(temp->getLp1Index(),temp->getT1(),sPolyList->getFirst()->getLPoly()); 308 rTag->setFirst(rules->getFirst()); 298 309 } 299 310 // data is saved in sPolyList or zero => delete sp … … 316 327 ======================================================================== 317 328 */ 318 LNode* reduction(LList* sPolyList, LList* completed, ideal gbPrev, int* reductionsToZero) { 319 poly zero = pInit(); 329 LNode* reduction(LList* sPolyList, LList* completed, LList* gPrev, LTagList* lTag, RTagList* rTag, 330 ideal gbPrev) { 331 // temporary normal form and zero polynomial for testing 332 poly tempNF = pInit(); 333 poly zero = pInit(); 320 334 // compute only if there are any S-polynomials to be reduced 321 335 if(NULL != sPolyList->getFirst()->getLPoly()) { 322 336 LNode* temp = sPolyList->getFirst(); 323 337 while(NULL != temp->getLPoly()) { 324 temp->setPoly(kNF(gbPrev,currQuotient,temp->getPoly())); 338 poly test = temp->getPoly(); 339 Print("ADDRESS BEFORE: %p\n",&test); 340 tempNF = kNF(gbPrev,currQuotient,temp->getPoly()); 341 temp->setPoly(tempNF); 342 Print("ADDRESS AFTER: %p\n",&test); 325 343 Print("Nach NORMAL FORM: "); 326 344 pWrite(temp->getPoly()); 327 // test if temp->getPoly() is zero polynomial 328 if(!pCmp(temp->getPoly(),zero)) { 329 *reductionsToZero++; 345 // test if normal form is zero 346 if(0 == pLmCmp(temp->getPoly(),zero)) { 347 Print("HIER\n"); 348 reductionsToZero++; 330 349 // TODO: sPolyList -> delete first element of list as it is zero and done 331 } 332 //completed = topReduction(); 333 // in topReduction() the investigated first element of sPolyList will be deleted after its 334 // reduction has finished => the next to be investigated element is the newly first element 335 // in sPolyList => the while loop is finite 336 // first possible after implementation of topReduction(): temp = sPolyList->getFirst(); 337 temp = temp->getNext(); 350 351 temp = temp->getNext(); 352 // TODO: problem is that when deleting the first element, the origin of the 353 // corresponding rule is deleted! 354 //sPolyList->setFirst(temp); 355 } 356 else { 357 //Print("HIER\n"); 358 topReduction(temp, completed, gPrev, lTag, rTag); 359 // in topReduction() the investigated first element of sPolyList will be deleted after its 360 // reduction has finished => the next to be investigated element is the newly first element 361 // in sPolyList => the while loop is finite 362 // first possible after implementation of topReduction(): temp = sPolyList->getFirst(); 363 temp = temp->getNext(); 364 } 338 365 } 339 366 } … … 349 376 ===================================================================================== 350 377 */ 351 LNode* topReduction(LNode* l, LList* gPrev, LList* completed) { 352 LPoly* red = findReductor(l, gPrev, completed); 353 return NULL; 378 void topReduction(LNode* l, LList* completed, LList* gPrev, LTagList* lTag, RTagList* rTag) { 379 Print("In topREDUCTION!\n"); 380 LRed* red = new LRed(); 381 do { 382 red = findReductor(l, completed, gPrev, lTag, rTag, 383 red->getGPrevRedCheck(), red->getCompletedRedCheck()); 384 // no reductor found 385 if(NULL == red) { 386 pNorm(l->getPoly()); 387 completed->insert(l->getLPoly()); 388 389 } 390 // reductor found 391 else { 392 Print("REDUCTOR VORHER: "); 393 pWrite(red->getPoly()); 394 red->setPoly(ppMult_nn(red->getPoly(),pGetCoeff(l->getPoly()))); 395 Print("REDUCTOR NACHHER: "); 396 pWrite(red->getPoly()); 397 } 398 } while(NULL != red); 354 399 } 355 400 … … 361 406 ===================================================================== 362 407 */ 363 LPoly* findReductor(LNode* l, LList* gPrev, LList* completed) { 408 LRed* findReductor(LNode* l,LList* completed,LList* gPrev,LTagList* lTag,RTagList* rTag, 409 LNode* gPrevRedCheck, LNode* completedRedCheck) { 410 number nOne = nInit(1); 411 poly u = pInit(); 412 poly redPoly = pInit(); 413 poly t = pHead(l->getPoly()); 414 LNode* temp = new LNode(); 415 // setting starting point for search of reductors in gPrev 416 if(NULL != gPrevRedCheck) { 417 temp = gPrevRedCheck; 418 } 419 else { 420 temp = gPrev->getFirst(); 421 } 422 // search only for reductors with the same index, as reductions with elements of lower 423 // index where already done in reduction() beforehand 424 while(NULL != temp->getLPoly() && temp->getIndex() == l->getIndex()) { 425 // divides head term t? 426 if(pLmDivisibleByNoComp(temp->getPoly(),t)) { 427 u = pDivide(t,pHead(temp->getPoly())); 428 pSetCoeff(u,nOne); 429 // multiply reductor with factor and normalize it, i.e. LC = 1 430 redPoly = ppMult_qq(u,temp->getPoly()); 431 pNorm(redPoly); 432 u = ppMult_qq(u,temp->getTerm()); 433 Print("IN FIND REDUCTOR: "); 434 pWrite(u); 435 pWrite(redPoly); 436 // same label? NOTE: also used to 437 if(pLmCmp(u,l->getTerm()) != 0) { 438 // passing criterion 2? 439 Print("HIER DRIN\n"); 440 if(!criterion2(&u,temp,rTag)) { 441 // passing criterion 1? 442 if(!criterion1(&u,temp,lTag)) { 443 // set tag findRedCheck such that you can start at this point when the 444 // next time a reductor is searched for in findReductor() 445 LRed* red = new LRed(u,temp->getIndex(),redPoly,temp->getNext(),completedRedCheck); 446 return red; 447 } 448 } 449 } 450 } 451 temp = temp->getNext(); 452 } 453 454 // do the same as above now for the elements in completed 455 if(NULL != completedRedCheck) { 456 temp = completedRedCheck; 457 } 458 else { 459 temp = completed->getFirst(); 460 } 461 // search only for reductors with the same index, as reductions with elements of lower 462 // index where already done in reduction() beforehand 463 while(NULL != temp->getLPoly()) { 464 // divides head term t? 465 if(pLmDivisibleByNoComp(temp->getPoly(),t)) { 466 u = pDivide(t,pHead(temp->getPoly())); 467 redPoly = ppMult_qq(u,temp->getPoly()); 468 u = ppMult_qq(u,temp->getTerm()); 469 Print("IN FIND REDUCTOR1: "); 470 pWrite(u); 471 pWrite(redPoly); 472 // same label? NOTE: also used to 473 if(pLmCmp(u,l->getTerm()) != 0) { 474 // passing criterion 2? 475 if(!criterion2(&u,temp,rTag)) { 476 // passing criterion 1? 477 if(!criterion1(&u,temp,lTag)) { 478 // set tag findRedCheck such that you can start at this point when the 479 // next time a reductor is searched for in findReductor() 480 LRed* red = new LRed(u,temp->getIndex(),redPoly,gPrevRedCheck,temp->getNext()); 481 return red; 482 } 483 } 484 } 485 } 486 temp = temp->getNext(); 487 } 488 489 // no reductor found 364 490 return NULL; 365 491 } … … 374 500 ideal F5main(ideal id, ring r) { 375 501 int i,j; 376 int* reductionsToZero = new int;377 *reductionsToZero = 0;502 //static int* reductionsToZero = new int; 503 //*reductionsToZero = 0; 378 504 // 1 polynomial for defining initial labels & further tests 379 505 poly ONE = pOne(); … … 407 533 idShow(id); 408 534 LList* gPrev = new LList(ONE, i, id->m[0]); 535 int gbLength = gPrev->getLength(); 409 536 pWrite(id->m[0]); 410 537 poly p = pHead(id->m[0]); … … 415 542 // computing the groebner basis of the elements of index < actual index 416 543 Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength()); 417 ideal gbPrev = idInit(g Prev->getLength(),1);544 ideal gbPrev = idInit(gbLength,1); 418 545 // initializing the groebner basis of elements of index < actual index 419 546 gbPrev->m[0] = gPrev->getFirst()->getPoly(); … … 422 549 423 550 for(i=2; i<=IDELEMS(id); i++) { 424 gPrev = F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, reductionsToZero); 551 gPrev = F5inc(i, id->m[i-1], gPrev, gbPrev, ONE); 552 // comuting new groebner basis gbPrev 553 ideal gbAdd = idInit(gPrev->getLength()-gbLength,1); 554 LNode* temp = gPrev->getFirst(); 555 for(j=0;j<=gPrev->getLength()-gbLength-1;j++) { 556 gbAdd->m[j] = temp->getPoly(); 557 temp = temp->getNext(); 558 } 559 gbPrev = idAdd(gbPrev,gbAdd); 560 Print("GROEBNER BASIS:\n====================================================\n"); 561 idShow(gbPrev); 562 Print("===================================================\n"); 563 425 564 Print("JA\n"); 426 //TODO: idAdd for computing gbPrev with the actual index!427 565 } 428 // only for debugging 429 //LNode* current; 430 //LList* g_curr = new LList(lp); 431 //} 432 //for(i=2; i<IDELEMS(id); i++) { 433 //g_curr = F5inc(&i,&id->m[i],g_prev); 434 //if(g_curr->polyTest(&ONE)) { 435 // Print("One Polynomial in Input => Computations stopped\n"); 436 // ideal id_new = idInit(1,1); 437 // id_new->m[0] = ONE; 438 // return(id_new); 439 //} 440 //} 441 Print("\n\nNumber of zero-reductions: %d\n",*reductionsToZero); 442 return(id); 566 Print("\n\nNumber of zero-reductions: %d\n",reductionsToZero); 567 return(gbPrev); 443 568 444 569
Note: See TracChangeset
for help on using the changeset viewer.