Changeset 1d9469 in git for kernel/gfan.cc
- Timestamp:
- Oct 1, 2009, 9:57:24 AM (15 years ago)
- Branches:
- (u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
- Children:
- 418bd6de476ff6f8e0ea70a0de50d16f54b890d3
- Parents:
- ac6e45db1f490e638b067d932fc2c4100bc9526c
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/gfan.cc
rac6e45 r1d9469 2 2 Compute the Groebner fan of an ideal 3 3 $Author: monerjan $ 4 $Date: 2009-10-01 07: 15:49$5 $Header: /exports/cvsroot-2/cvsroot/kernel/gfan.cc,v 1.9 2 2009-10-01 07:15:49monerjan Exp $6 $Id: gfan.cc,v 1.9 2 2009-10-01 07:15:49monerjan Exp $4 $Date: 2009-10-01 07:57:24 $ 5 $Header: /exports/cvsroot-2/cvsroot/kernel/gfan.cc,v 1.93 2009-10-01 07:57:24 monerjan Exp $ 6 $Id: gfan.cc,v 1.93 2009-10-01 07:57:24 monerjan Exp $ 7 7 */ 8 8 … … 290 290 * @see facet 291 291 */ 292 /*class gcone 293 finally this should become s.th. like gconelib.{h,cc} to provide an API 292 293 294 /** \brief Default constructor. 295 * 296 * Initialises this->next=NULL and this->facetPtr=NULL 297 */ 298 gcone::gcone() 299 { 300 this->next=NULL; 301 this->facetPtr=NULL; //maybe this->facetPtr = new facet(); 302 this->baseRing=currRing; 303 this->counter++; 304 this->UCN=this->counter; 305 this->numFacets=0; 306 this->ivIntPt=NULL; 307 } 308 309 /** \brief Constructor with ring and ideal 310 * 311 * This constructor takes the root ring and the root ideal as parameters and stores 312 * them in the private members gcone::rootRing and gcone::inputIdeal 313 * Since knowledge of the root ring is only needed when using reverse search, 314 * this constructor is not needed when using the "second" method 294 315 */ 295 class gcone 296 { 297 private: 298 ring rootRing; //good to know this -> generic walk 299 ideal inputIdeal; //the original 300 ring baseRing; //the basering of the cone 301 /* TODO in order to save memory use pointers to rootRing and inputIdeal instead */ 302 intvec *ivIntPt; //an interior point of the cone 303 int UCN; //unique number of the cone 304 static int counter; 305 306 public: 307 /** \brief Pointer to the first facet */ 308 facet *facetPtr; //Will hold the adress of the first facet; set by gcone::getConeNormals 309 310 /** # of variables in the ring */ 311 int numVars; //#of variables in the ring 312 313 /** # of facets of the cone 314 * This value is set by gcone::getConeNormals 315 */ 316 int numFacets; //#of facets of the cone 317 318 /** 319 * At least as a workaround we store the irredundant facets of a matrix here. 320 * Otherwise, since we throw away non-flippable facets, facets2Matrix will not 321 * yield all the necessary information 322 */ 323 dd_MatrixPtr ddFacets; //Matrix to store irredundant facets of the cone 324 325 /** Contains the Groebner basis of the cone. Is set by gcone::getGB(ideal I)*/ 326 ideal gcBasis; //GB of the cone, set by gcone::getGB(); 327 gcone *next; //Pointer to *previous* cone in search tree 328 329 /** \brief Default constructor. 330 * 331 * Initialises this->next=NULL and this->facetPtr=NULL 332 */ 333 gcone() 334 { 335 this->next=NULL; 336 this->facetPtr=NULL; //maybe this->facetPtr = new facet(); 337 this->baseRing=currRing; 338 this->counter++; 339 this->UCN=this->counter; 340 this->numFacets=0; 341 this->ivIntPt=NULL; 342 } 343 344 /** \brief Constructor with ring and ideal 345 * 346 * This constructor takes the root ring and the root ideal as parameters and stores 347 * them in the private members gcone::rootRing and gcone::inputIdeal 348 * Since knowledge of the root ring is only needed when using reverse search, 349 * this constructor is not needed when using the "second" method 350 */ 351 gcone(ring r, ideal I) 352 { 353 this->next=NULL; 354 this->facetPtr=NULL; 355 this->rootRing=r; 356 this->inputIdeal=I; 357 this->baseRing=currRing; 358 this->counter++; 359 this->UCN=this->counter; 360 this->numFacets=0; 361 this->ivIntPt=NULL; 362 } 363 364 /** \brief Copy constructor 365 * 366 * Copies a cone, sets this->gcBasis to the flipped GB 367 * Call this only after a successful call to gcone::flip which sets facet::flipGB 368 */ 369 gcone(const gcone& gc, const facet &f) 370 { 371 this->next=NULL; 372 this->numVars=gc.numVars; 373 this->counter++; 374 this->UCN=this->counter; 375 this->facetPtr=NULL; 376 this->gcBasis=idCopy(f.flipGB); 377 this->inputIdeal=idCopy(this->gcBasis); 378 this->baseRing=rCopy(f.flipRing); 379 this->numFacets=0; 380 this->ivIntPt=NULL; 316 gcone::gcone(ring r, ideal I) 317 { 318 this->next=NULL; 319 this->facetPtr=NULL; 320 this->rootRing=r; 321 this->inputIdeal=I; 322 this->baseRing=currRing; 323 this->counter++; 324 this->UCN=this->counter; 325 this->numFacets=0; 326 this->ivIntPt=NULL; 327 } 328 329 /** \brief Copy constructor 330 * 331 * Copies a cone, sets this->gcBasis to the flipped GB 332 * Call this only after a successful call to gcone::flip which sets facet::flipGB 333 */ 334 gcone::gcone(const gcone& gc, const facet &f) 335 { 336 this->next=NULL; 337 this->numVars=gc.numVars; 338 this->counter++; 339 this->UCN=this->counter; 340 this->facetPtr=NULL; 341 this->gcBasis=idCopy(f.flipGB); 342 this->inputIdeal=idCopy(this->gcBasis); 343 this->baseRing=rCopy(f.flipRing); 344 this->numFacets=0; 345 this->ivIntPt=NULL; 381 346 //rComplete(this->baseRing); 382 347 //rChangeCurrRing(this->baseRing); 348 } 349 350 /** \brief Default destructor 351 */ 352 gcone::~gcone() 353 { 354 //NOTE SAVE THE FACET STRUCTURE!!! 355 } 356 357 /** \brief Set the interior point of a cone */ 358 void gcone::setIntPoint(intvec *iv) 359 { 360 this->ivIntPt=ivCopy(iv); 361 } 362 363 /** \brief Return the interior point */ 364 intvec *gcone::getIntPoint() 365 { 366 return this->ivIntPt; 367 } 368 369 /** \brief Print the interior point */ 370 void gcone::showIntPoint() 371 { 372 ivIntPt->show(); 373 } 374 375 /** \brief Print facets 376 * This is mainly for debugging purposes. Usually called from within gdb 377 */ 378 void gcone::showFacets(short codim) 379 { 380 facet *f; 381 switch(codim) 382 { 383 case 1: 384 f = this->facetPtr; 385 break; 386 case 2: 387 f = this->facetPtr->codim2Ptr; 388 break; 389 } 390 391 intvec *iv; 392 while(f!=NULL) 393 { 394 iv = f->getFacetNormal(); 395 cout << "("; 396 iv->show(1,0); 397 if(f->isFlippable==FALSE) 398 cout << ")* "; 399 else 400 cout << ") "; 401 f=f->next; 402 } 403 cout << endl; 404 } 405 406 /** For debugging purposes only */ 407 void gcone::showSLA(facet &f) 408 { 409 facet *fAct; 410 fAct = &f; 411 facet *codim2Act; 412 codim2Act = fAct->codim2Ptr; 413 intvec *fNormal;// = new intvec(this->numVars); 414 intvec *f2Normal; 415 cout << endl; 416 while(fAct!=NULL) 417 { 418 fNormal=fAct->getFacetNormal(); 419 cout << "("; 420 fNormal->show(1,0); 421 if(fAct->isFlippable==TRUE) 422 cout << ") "; 423 else 424 cout << ")* "; 425 codim2Act = fAct->codim2Ptr; 426 cout << " Codim2: "; 427 while(codim2Act!=NULL) 428 { 429 f2Normal = codim2Act->getFacetNormal(); 430 cout << "("; 431 f2Normal->show(1,0); 432 cout << ") "; 433 codim2Act = codim2Act->next; 383 434 } 384 385 /** \brief Default destructor 386 */ 387 ~gcone() 388 { 389 //NOTE SAVE THE FACET STRUCTURE!!! 390 } 391 392 /** \brief Set the interior point of a cone */ 393 void setIntPoint(intvec *iv) 394 { 395 this->ivIntPt=ivCopy(iv); 396 } 397 398 /** \brief Return the interior point */ 399 intvec *getIntPoint() 400 { 401 return this->ivIntPt; 402 } 403 404 /** \brief Print the interior point */ 405 void showIntPoint() 406 { 407 ivIntPt->show(); 408 } 409 410 /** \brief Print facets 411 * This is mainly for debugging purposes. Usually called from within gdb 412 */ 413 void showFacets(short codim=1) 414 { 415 facet *f; 416 switch(codim) 417 { 418 case 1: 419 f = this->facetPtr; 420 break; 421 case 2: 422 f = this->facetPtr->codim2Ptr; 423 break; 424 } 425 426 intvec *iv; 427 while(f!=NULL) 428 { 429 iv = f->getFacetNormal(); 430 cout << "("; 431 iv->show(1,0); 432 if(f->isFlippable==FALSE) 433 cout << ")* "; 434 else 435 cout << ") "; 436 f=f->next; 437 } 438 cout << endl; 439 } 440 441 /** For debugging purposes only */ 442 void showSLA(facet &f) 443 { 444 facet *fAct; 445 fAct = &f; 446 facet *codim2Act; 447 codim2Act = fAct->codim2Ptr; 448 intvec *fNormal;// = new intvec(this->numVars); 449 intvec *f2Normal; 450 cout << endl; 451 while(fAct!=NULL) 452 { 453 fNormal=fAct->getFacetNormal(); 454 cout << "("; 455 fNormal->show(1,0); 456 if(fAct->isFlippable==TRUE) 457 cout << ") "; 458 else 459 cout << ")* "; 460 codim2Act = fAct->codim2Ptr; 461 cout << " Codim2: "; 462 while(codim2Act!=NULL) 463 { 464 f2Normal = codim2Act->getFacetNormal(); 465 cout << "("; 466 f2Normal->show(1,0); 467 cout << ") "; 468 codim2Act = codim2Act->next; 469 } 470 cout << "UCN = " << fAct->getUCN() << endl; 471 fAct = fAct->next; 472 } 473 } 474 475 void idDebugPrint(ideal const &I) 476 { 477 int numElts=IDELEMS(I); 478 cout << "Ideal with " << numElts << " generators" << endl; 479 cout << "Leading terms: "; 480 for (int ii=0;ii<numElts;ii++) 481 { 482 pWrite0(pHead(I->m[ii])); 483 cout << ","; 484 } 485 cout << endl; 486 } 487 488 /** \brief Set gcone::numFacets */ 489 void setNumFacets() 490 { 491 } 492 493 /** \brief Get gcone::numFacets */ 494 int getNumFacets() 495 { 496 return this->numFacets; 497 } 498 499 int getUCN() 500 { 501 if(this!=NULL) 502 return this->UCN; 503 else 504 return -1; 505 } 506 507 /** \brief Compute the normals of the cone 508 * 509 * This method computes a representation of the cone in terms of facet normals. It takes an ideal 510 * as its input. Redundancies are automatically removed using cddlib's dd_MatrixCanonicalize. 511 * Other methods for redundancy checkings might be implemented later. See Anders' diss p.44. 512 * Note that in order to use cddlib a 0-th column has to be added to the matrix since cddlib expects 513 * each row to represent an inequality of type const+x1+...+xn <= 0. While computing the normals we come across 514 * the set \f$ \partial\mathcal{G} \f$ which we might store for later use. C.f p71 of journal 515 * As a result of this procedure the pointer facetPtr points to the first facet of the cone. 516 * 517 * Optionally, if the parameter bool compIntPoint is set to TRUE the method will also compute 518 * an interior point of the cone. 519 */ 520 void getConeNormals(ideal const &I, bool compIntPoint=FALSE) 521 { 522 #ifdef gfan_DEBUG 523 std::cout << "*** Computing Inequalities... ***" << std::endl; 435 cout << "UCN = " << fAct->getUCN() << endl; 436 fAct = fAct->next; 437 } 438 } 439 440 void gcone::idDebugPrint(ideal const &I) 441 { 442 int numElts=IDELEMS(I); 443 cout << "Ideal with " << numElts << " generators" << endl; 444 cout << "Leading terms: "; 445 for (int ii=0;ii<numElts;ii++) 446 { 447 pWrite0(pHead(I->m[ii])); 448 cout << ","; 449 } 450 cout << endl; 451 } 452 453 /** \brief Set gcone::numFacets */ 454 void gcone::setNumFacets() 455 { 456 } 457 458 /** \brief Get gcone::numFacets */ 459 int gcone::getNumFacets() 460 { 461 return this->numFacets; 462 } 463 464 int gcone::getUCN() 465 { 466 if(this!=NULL) 467 return this->UCN; 468 else 469 return -1; 470 } 471 /** \brief Compute the normals of the cone 472 * 473 * This method computes a representation of the cone in terms of facet normals. It takes an ideal 474 * as its input. Redundancies are automatically removed using cddlib's dd_MatrixCanonicalize. 475 * Other methods for redundancy checkings might be implemented later. See Anders' diss p.44. 476 * Note that in order to use cddlib a 0-th column has to be added to the matrix since cddlib expects 477 * each row to represent an inequality of type const+x1+...+xn <= 0. While computing the normals we come across 478 * the set \f$ \partial\mathcal{G} \f$ which we might store for later use. C.f p71 of journal 479 * As a result of this procedure the pointer facetPtr points to the first facet of the cone. 480 * 481 * Optionally, if the parameter bool compIntPoint is set to TRUE the method will also compute 482 * an interior point of the cone. 483 */ 484 void gcone::getConeNormals(ideal const &I, bool compIntPoint) 485 { 486 #ifdef gfan_DEBUG 487 std::cout << "*** Computing Inequalities... ***" << std::endl; 524 488 #endif 525 489 //All variables go here - except ineq matrix and *v, see below 526 527 528 529 530 531 532 533 534 535 536 537 538 539 490 int lengthGB=IDELEMS(I); // # of polys in the groebner basis 491 int pCompCount; // # of terms in a poly 492 poly aktpoly; 493 int numvar = pVariables; // # of variables in a polynomial (or ring?) 494 int leadexp[numvar]; // dirty hack of exp.vects 495 int aktexp[numvar]; 496 int cols,rows; // will contain the dimensions of the ineq matrix - deprecated by 497 dd_rowrange ddrows; 498 dd_colrange ddcols; 499 dd_rowset ddredrows; // # of redundant rows in ddineq 500 dd_rowset ddlinset; // the opposite 501 dd_rowindex ddnewpos; // all to make dd_Canonicalize happy 502 dd_NumberType ddnumb=dd_Integer; //Number type 503 dd_ErrorType dderr=dd_NoError; // 540 504 // End of var declaration 541 505 #ifdef gfan_DEBUG … … 543 507 // cout << "The current ring has " << numvar << " variables" << endl; 544 508 #endif 545 509 cols = numvar; 546 510 547 511 //Compute the # inequalities i.e. rows of the matrix 548 549 550 551 552 553 512 rows=0; //Initialization 513 for (int ii=0;ii<IDELEMS(I);ii++) 514 { 515 aktpoly=(poly)I->m[ii]; 516 rows=rows+pLength(aktpoly)-1; 517 } 554 518 #ifdef gfan_DEBUG 555 519 // cout << "rows=" << rows << endl; 556 520 // cout << "Will create a " << rows << " x " << cols << " matrix to store inequalities" << endl; 557 521 #endif 558 559 560 561 562 563 522 dd_rowrange aktmatrixrow=0; // needed to store the diffs of the expvects in the rows of ddineq 523 dd_set_global_constants(); 524 ddrows=rows; 525 ddcols=cols; 526 dd_MatrixPtr ddineq; //Matrix to store the inequalities 527 ddineq=dd_CreateMatrix(ddrows,ddcols+1); //The first col has to be 0 since cddlib checks for additive consts there 564 528 565 529 // We loop through each g\in GB and compute the resulting inequalities 566 567 568 569 530 for (int i=0; i<IDELEMS(I); i++) 531 { 532 aktpoly=(poly)I->m[i]; //get aktpoly as i-th component of I 533 pCompCount=pLength(aktpoly); //How many terms does aktpoly consist of? 570 534 #ifdef gfan_DEBUG 571 535 // cout << "Poly No. " << i << " has " << pCompCount << " components" << endl; 572 536 #endif 573 537 574 575 538 int *v=(int *)omAlloc((numvar+1)*sizeof(int)); 539 pGetExpV(aktpoly,v); //find the exp.vect in v[1],...,v[n], use pNext(p) 576 540 577 541 //Store leadexp for aktpoly 578 579 580 542 for (int kk=0;kk<numvar;kk++) 543 { 544 leadexp[kk]=v[kk+1]; 581 545 //Since we need to know the difference of leadexp with the other expvects we do nothing here 582 546 //but compute the diff below 583 547 } 584 548 585 549 586 587 588 589 590 591 592 593 550 while (pNext(aktpoly)!=NULL) //move to next term until NULL 551 { 552 aktpoly=pNext(aktpoly); 553 pSetm(aktpoly); //doesn't seem to help anything 554 pGetExpV(aktpoly,v); 555 for (int kk=0;kk<numvar;kk++) 556 { 557 aktexp[kk]=v[kk+1]; 594 558 //ineq[aktmatrixrow][kk]=leadexp[kk]-aktexp[kk]; //dito 595 596 597 598 599 600 559 dd_set_si(ddineq->matrix[(dd_rowrange)aktmatrixrow][kk+1],leadexp[kk]-aktexp[kk]); //because of the 1st col being const 0 560 } 561 aktmatrixrow=aktmatrixrow+1; 562 }//while 563 564 } //for 601 565 602 566 //Maybe add another row to contain the constraints of the standard simplex? … … 609 573 // The inequalities are now stored in ddineq 610 574 // Next we check for superflous rows 611 612 613 614 615 616 #ifdef gfan_DEBUG 617 618 575 ddredrows = dd_RedundantRows(ddineq, &dderr); 576 if (dderr!=dd_NoError) // did an error occur? 577 { 578 dd_WriteErrorMessages(stderr,dderr); //if so tell us 579 } 580 #ifdef gfan_DEBUG 581 else 582 { 619 583 // cout << "Redundant rows: "; 620 584 // set_fwrite(stdout, ddredrows); //otherwise print the redundant rows 621 585 }//if dd_Error 622 586 #endif 623 587 //Remove reduntant rows here! 624 625 626 588 dd_MatrixCanonicalize(&ddineq, &ddlinset, &ddredrows, &ddnewpos, &dderr); 589 ddrows = ddineq->rowsize; //Size of the matrix with redundancies removed 590 ddcols = ddineq->colsize; 627 591 628 592 //ddCreateMatrix(ddrows,ddcols+1); 629 593 ddFacets = dd_CopyMatrix(ddineq); 630 594 #ifdef gfan_DEBUG 631 595 // cout << "Having removed redundancies, the normals now read:" << endl; … … 635 599 #endif 636 600 637 601 /*Write the normals into class facet*/ 638 602 #ifdef gfan_DEBUG 639 603 // cout << "Creating list of normals" << endl; 640 604 #endif 641 605 /*The pointer *fRoot should be the return value of this function*/ 642 606 //facet *fRoot = new facet(); //instantiate new facet 643 607 //fRoot->setUCN(this->getUCN()); 644 608 //this->facetPtr = fRoot; //set variable facetPtr of class gcone to first facet 645 609 facet *fAct; //pointer to active facet 646 610 //fAct = fRoot; //Seems to do the trick. fRoot and fAct have to point to the same adress! 647 611 //std::cout << "fRoot = " << fRoot << ", fAct = " << fAct << endl; 648 649 650 651 652 653 654 655 612 int numNonFlip=0; 613 for (int kk = 0; kk<ddrows; kk++) 614 { 615 intvec *load = new intvec(this->numVars); //intvec to store a single facet normal that will then be stored via setFacetNormal 616 for (int jj = 1; jj <ddcols; jj++) 617 { 618 double foo; 619 foo = mpq_get_d(ddineq->matrix[kk][jj]); 656 620 #ifdef gfan_DEBUG 657 621 // std::cout << "fAct is " << foo << " at " << fAct << std::endl; 658 622 #endif 659 660 623 (*load)[jj-1] = (int)foo; //store typecasted entry at pos jj-1 of load 624 }//for (int jj = 1; jj <ddcols; jj++) 661 625 662 663 626 /*Quick'n'dirty hack for flippability*/ 627 bool isFlip=FALSE; 664 628 665 666 667 668 629 for (int jj = 0; jj<load->length(); jj++) 630 { 631 intvec *ivCanonical = new intvec(load->length()); 632 (*ivCanonical)[jj]=1; 669 633 // cout << "dotProd=" << dotProduct(*load,*ivCanonical) << endl; 670 634 if (dotProduct(*load,*ivCanonical)<0) 671 635 //if (ivMult(load,ivCanonical)<0) 672 673 674 675 676 677 678 679 680 681 682 683 684 685 636 { 637 isFlip=TRUE; 638 break; //URGHS 639 } 640 } 641 if (isFlip==FALSE) 642 { 643 this->numFacets++; 644 numNonFlip++; 645 if(this->numFacets==1) 646 { 647 facet *fRoot = new facet(); 648 this->facetPtr = fRoot; 649 fAct = fRoot; 686 650 687 688 689 690 691 692 693 694 695 696 #ifdef gfan_DEBUG 697 698 699 700 #endif 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 651 } 652 else 653 { 654 fAct->next = new facet(); 655 fAct = fAct->next; 656 } 657 fAct->isFlippable=FALSE; 658 fAct->setFacetNormal(load); 659 fAct->setUCN(this->getUCN()); 660 #ifdef gfan_DEBUG 661 cout << "Marking facet ("; 662 load->show(1,0); 663 cout << ") as non flippable" << endl; 664 #endif 665 } 666 else 667 { /*Now load should be full and we can call setFacetNormal*/ 668 this->numFacets++; 669 if(this->numFacets==1) 670 { 671 facet *fRoot = new facet(); 672 this->facetPtr = fRoot; 673 fAct = fRoot; 674 } 675 else 676 { 677 fAct->next = new facet(); 678 fAct = fAct->next; 679 } 680 fAct->isFlippable=TRUE; 681 fAct->setFacetNormal(load); 682 fAct->setUCN(this->getUCN()); 683 }//if (isFlippable==FALSE) 720 684 //delete load; 721 685 }//for (int kk = 0; kk<ddrows; kk++) 722 686 723 687 //In cases like I=<x-1,y-1> there are only non-flippable facets... 724 725 726 727 688 if(numNonFlip==this->numFacets) 689 { 690 cerr << "Only non-flippable facets. Terminating..." << endl; 691 } 728 692 729 693 /* 730 731 732 733 694 Now we should have a linked list containing the facet normals of those facets that are 695 -irredundant 696 -flipable 697 Adressing is done via *facetPtr 734 698 */ 735 699 736 737 738 739 740 741 742 743 744 745 746 747 748 700 if (compIntPoint==TRUE) 701 { 702 intvec *iv = new intvec(this->numVars); 703 dd_MatrixPtr posRestr=dd_CreateMatrix(this->numVars,this->numVars+1); 704 int jj=1; 705 for (int ii=0;ii<=this->numVars;ii++) 706 { 707 dd_set_si(posRestr->matrix[ii][jj],1); 708 jj++; 709 } 710 dd_MatrixAppendTo(&ddineq,posRestr); 711 interiorPoint(ddineq, *iv); //NOTE ddineq contains non-flippable facets 712 this->setIntPoint(iv); //stores the interior point in gcone::ivIntPt 749 713 //delete iv; 750 714 } 751 715 752 716 //Compute the number of facets … … 764 728 //dd_free_global_constants(); 765 729 766 767 768 769 770 771 772 773 voidgetCodim2Normals(gcone const &gc)774 730 }//method getConeNormals(ideal I) 731 732 /** \brief Compute the (codim-2)-facets of a given cone 733 * This method is used during noRevS 734 * Additionally we check whether the codim2-facet normal is strictly positive. Otherwise 735 * the facet is marked as non-flippable. 736 */ 737 void gcone::getCodim2Normals(gcone const &gc) 738 { 775 739 //this->facetPtr->codim2Ptr = new facet(2); //instantiate a (codim-2)-facet 776 777 778 740 facet *fAct; 741 fAct = this->facetPtr; 742 facet *codim2Act; 779 743 //codim2Act = this->facetPtr->codim2Ptr; 780 744 781 782 783 784 785 786 745 dd_set_global_constants(); 746 747 dd_MatrixPtr ddineq,P,ddakt; 748 dd_rowset impl_linset, redset; 749 dd_ErrorType err; 750 dd_rowindex newpos; 787 751 788 752 //ddineq = facets2Matrix(gc); //get a matrix representation of the cone 789 753 ddineq = dd_CopyMatrix(gc.ddFacets); 790 754 791 792 793 794 795 796 797 798 755 /*Now set appropriate linearity*/ 756 dd_PolyhedraPtr ddpolyh; 757 for (int ii=0; ii<this->numFacets; ii++) 758 { 759 ddakt = dd_CopyMatrix(ddineq); 760 ddakt->representation=dd_Inequality; 761 set_addelem(ddakt->linset,ii+1); 762 dd_MatrixCanonicalize(&ddakt, &impl_linset, &redset, &newpos, &err); 799 763 800 764 #ifdef gfan_DEBUG … … 802 766 // dd_WriteMatrix(stdout,ddakt); 803 767 #endif 804 805 768 ddpolyh=dd_DDMatrix2Poly(ddakt, &err); 769 P=dd_CopyGenerators(ddpolyh); 806 770 #ifdef gfan_DEBUG 807 771 // cout << "Codim2 facet:" << endl; … … 810 774 #endif 811 775 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 776 /* We loop through each row of P 777 * normalize it by making all entries integer ones 778 * and add the resulting vector to the int matrix facet::codim2Facets 779 */ 780 for (int jj=1;jj<=P->rowsize;jj++) 781 { 782 fAct->numCodim2Facets++; 783 if(fAct->numCodim2Facets==1) 784 { 785 fAct->codim2Ptr = new facet(2); 786 codim2Act = fAct->codim2Ptr; 787 } 788 else 789 { 790 codim2Act->next = new facet(2); 791 codim2Act = codim2Act->next; 792 } 793 intvec *n = new intvec(this->numVars); 794 makeInt(P,jj,*n); 795 codim2Act->setFacetNormal(n); 796 delete n; 797 } 798 /*We check whether the facet spanned by the codim-2 facets 799 * intersects with the positive orthant. Otherwise we define this 800 * facet to be non-flippable 801 */ 802 intvec *iv_intPoint = new intvec(this->numVars); 803 dd_MatrixPtr shiftMatrix; 804 dd_MatrixPtr intPointMatrix; 805 shiftMatrix = dd_CreateMatrix(this->numVars,this->numVars+1); 806 for(int kk=0;kk<this->numVars;kk++) 807 { 808 dd_set_si(shiftMatrix->matrix[kk][0],1); 809 dd_set_si(shiftMatrix->matrix[kk][kk+1],1); 810 } 811 intPointMatrix=dd_MatrixAppend(ddakt,shiftMatrix); 848 812 //dd_WriteMatrix(stdout,intPointMatrix); 849 interiorPoint(intPointMatrix,*iv_intPoint); 850 for(int ll=0;ll<this->numVars;ll++) 851 { 852 if( (*iv_intPoint)[ll] < 0 ) 853 { 854 fAct->isFlippable=FALSE; 855 break; 856 } 857 } 858 /*End of check*/ 859 fAct = fAct->next; 860 dd_FreeMatrix(ddakt); 861 dd_FreePolyhedra(ddpolyh); 862 delete iv_intPoint; 863 }//while 813 interiorPoint(intPointMatrix,*iv_intPoint); 814 for(int ll=0;ll<this->numVars;ll++) 815 { 816 if( (*iv_intPoint)[ll] < 0 ) 817 { 818 fAct->isFlippable=FALSE; 819 break; 820 } 864 821 } 865 866 /** \brief Compute the Groebner Basis on the other side of a shared facet 867 * 868 * Implements algorithm 4.3.2 from Anders' thesis. 869 * As shown there it is not necessary to compute an interior point. The knowledge of the facet normal 870 * suffices. A term \f$ x^\gamma \f$ of \f$ g \f$ is in \f$ in_\omega(g) \f$ iff \f$ \gamma - leadexp(g)\f$ 871 * is parallel to \f$ leadexp(g) \f$ 872 * Parallelity is checked using basic linear algebra. See gcone::isParallel. 873 * Other possibilities include computing the rank of the matrix consisting of the vectors in question and 874 * computing an interior point of the facet and taking all terms having the same weight with respect 875 * to this interior point. 876 *\param ideal, facet 877 * Input: a marked,reduced Groebner basis and a facet 878 */ 879 void flip(ideal gb, facet *f) //Compute "the other side" 880 { 881 intvec *fNormal = new intvec(this->numVars); //facet normal, check for parallelity 882 fNormal = f->getFacetNormal(); //read this->fNormal; 822 /*End of check*/ 823 fAct = fAct->next; 824 dd_FreeMatrix(ddakt); 825 dd_FreePolyhedra(ddpolyh); 826 delete iv_intPoint; 827 }//while 828 } 829 830 /** \brief Compute the Groebner Basis on the other side of a shared facet 831 * 832 * Implements algorithm 4.3.2 from Anders' thesis. 833 * As shown there it is not necessary to compute an interior point. The knowledge of the facet normal 834 * suffices. A term \f$ x^\gamma \f$ of \f$ g \f$ is in \f$ in_\omega(g) \f$ iff \f$ \gamma - leadexp(g)\f$ 835 * is parallel to \f$ leadexp(g) \f$ 836 * Parallelity is checked using basic linear algebra. See gcone::isParallel. 837 * Other possibilities include computing the rank of the matrix consisting of the vectors in question and 838 * computing an interior point of the facet and taking all terms having the same weight with respect 839 * to this interior point. 840 *\param ideal, facet 841 * Input: a marked,reduced Groebner basis and a facet 842 */ 843 void gcone::flip(ideal gb, facet *f) //Compute "the other side" 844 { 845 intvec *fNormal = new intvec(this->numVars); //facet normal, check for parallelity 846 fNormal = f->getFacetNormal(); //read this->fNormal; 883 847 #ifdef gfan_DEBUG 884 848 //std::cout << "===" << std::endl; 885 886 849 std::cout << "running gcone::flip" << std::endl; 850 std::cout << "flipping UCN " << this->getUCN() << endl; 887 851 // for(int ii=0;ii<IDELEMS(gb);ii++) //not very handy with large examples 888 852 // { 889 853 // pWrite((poly)gb->m[ii]); 890 854 // } 891 892 893 894 855 cout << "over facet ("; 856 fNormal->show(1,0); 857 cout << ") with UCN " << f->getUCN(); 858 std::cout << std::endl; 895 859 #endif 896 897 898 899 900 901 902 903 904 905 906 907 908 860 /*1st step: Compute the initial ideal*/ 861 poly initialFormElement[IDELEMS(gb)]; //array of #polys in GB to store initial form 862 ideal initialForm=idInit(IDELEMS(gb),this->gcBasis->rank); 863 poly aktpoly; 864 intvec *check = new intvec(this->numVars); //array to store the difference of LE and v 865 866 for (int ii=0;ii<IDELEMS(gb);ii++) 867 { 868 aktpoly = (poly)gb->m[ii]; 869 int *v=(int *)omAlloc((this->numVars+1)*sizeof(int)); 870 int *leadExpV=(int *)omAlloc((this->numVars+1)*sizeof(int)); 871 pGetExpV(aktpoly,leadExpV); //find the leading exponent in leadExpV[1],...,leadExpV[n], use pNext(p) 872 initialFormElement[ii]=pHead(aktpoly); 909 873 910 911 912 913 914 915 916 917 874 while(pNext(aktpoly)!=NULL) /*loop trough terms and check for parallelity*/ 875 { 876 aktpoly=pNext(aktpoly); //next term 877 pSetm(aktpoly); 878 pGetExpV(aktpoly,v); 879 /* Convert (int)v into (intvec)check */ 880 for (int jj=0;jj<this->numVars;jj++) 881 { 918 882 //cout << "v["<<jj+1<<"]="<<v[jj+1]<<endl; 919 883 //cout << "leadExpV["<<jj+1<<"]="<<leadExpV[jj+1]<<endl; 920 921 884 (*check)[jj]=v[jj+1]-leadExpV[jj+1]; 885 } 922 886 #ifdef gfan_DEBUG 923 887 // cout << "check="; … … 926 890 #endif 927 891 //TODO why not *check, *fNormal???? 928 929 892 if (isParallel(*check,*fNormal)) //pass *check when 893 { 930 894 // cout << "Parallel vector found, adding to initialFormElement" << endl; 931 932 933 895 initialFormElement[ii] = pAdd(pCopy(initialFormElement[ii]),(poly)pHead(aktpoly)); 896 } 897 }//while 934 898 #ifdef gfan_DEBUG 935 899 // cout << "Initial Form="; … … 937 901 // cout << "---" << endl; 938 902 #endif 939 940 941 903 /*Now initialFormElement must be added to (ideal)initialForm */ 904 initialForm->m[ii]=initialFormElement[ii]; 905 }//for 942 906 #ifdef gfan_DEBUG 943 907 /* cout << "Initial ideal is: " << endl; 944 945 908 idShow(initialForm); 909 //f->printFlipGB();*/ 946 910 // cout << "===" << endl; 947 911 #endif 948 912 //delete check; 949 913 950 914 /*2nd step: lift initial ideal to a GB of the neighbouring cone using minus alpha as weight*/ 951 915 /*Substep 2.1 952 953 954 955 916 compute $G_{-\alpha}(in_v(I)) 917 see journal p. 66 918 NOTE Check for different rings. Prolly it will not always be necessary to add a weight, if the 919 srcRing already has a weighted ordering 956 920 */ 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 921 ring srcRing=currRing; 922 ring tmpRing; 923 924 if( (srcRing->order[0]!=ringorder_a)) 925 { 926 tmpRing=rCopyAndAddWeight(srcRing,ivNeg(fNormal)); 927 } 928 else 929 { 930 tmpRing=rCopy0(srcRing); 931 int length=fNormal->length(); 932 int *A=(int *)omAlloc0(length*sizeof(int)); 933 for(int jj=0;jj<length;jj++) 934 { 935 A[jj]=-(*fNormal)[jj]; 936 } 937 omFree(tmpRing->wvhdl[0]); 938 tmpRing->wvhdl[0]=(int*)A; 939 tmpRing->block1[0]=length; 940 rComplete(tmpRing); 941 } 942 rChangeCurrRing(tmpRing); 979 943 980 944 //rWrite(currRing); cout << endl; 981 945 982 983 946 ideal ina; 947 ina=idrCopyR(initialForm,srcRing); 984 948 #ifdef gfan_DEBUG 985 949 // cout << "ina="; 986 950 // idShow(ina); cout << endl; 987 951 #endif 988 952 ideal H; 989 953 //H=kStd(ina,NULL,isHomog,NULL); //we know it is homogeneous 990 991 954 H=kStd(ina,NULL,testHomog,NULL); 955 idSkipZeroes(H); 992 956 #ifdef gfan_DEBUG 993 957 // cout << "H="; idShow(H); cout << endl; 994 958 #endif 995 959 /*Substep 2.2 996 960 do the lifting and mark according to H 997 961 */ 998 999 1000 1001 962 rChangeCurrRing(srcRing); 963 ideal srcRing_H; 964 ideal srcRing_HH; 965 srcRing_H=idrCopyR(H,tmpRing); 1002 966 #ifdef gfan_DEBUG 1003 967 // cout << "srcRing_H = "; 1004 968 // idShow(srcRing_H); cout << endl; 1005 969 #endif 1006 970 srcRing_HH=ffG(srcRing_H,this->gcBasis); 1007 971 #ifdef gfan_DEBUG 1008 972 // cout << "srcRing_HH = "; … … 1010 974 #endif 1011 975 /*Substep 2.2.1 1012 1013 1014 1015 1016 1017 976 Mark according to G_-\alpha 977 Here we have a minimal basis srcRing_HH. In order to turn this basis into a reduced basis 978 we have to compute an interior point of C(srcRing_HH). For this we need to know the cone 979 represented by srcRing_HH MARKED ACCORDING TO G_{-\alpha} 980 Thus we check whether the leading monomials of srcRing_HH and srcRing_H coincide. If not we 981 compute the difference accordingly 1018 982 */ 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 983 dd_set_global_constants(); 984 bool markingsAreCorrect=FALSE; 985 dd_MatrixPtr intPointMatrix; 986 int iPMatrixRows=0; 987 dd_rowrange aktrow=0; 988 for (int ii=0;ii<IDELEMS(srcRing_HH);ii++) 989 { 990 poly aktpoly=(poly)srcRing_HH->m[ii]; 991 iPMatrixRows = iPMatrixRows+pLength(aktpoly)-1; 992 } 1029 993 /* additionally one row for the standard-simplex and another for a row that becomes 0 during 1030 994 construction of the differences 1031 995 */ 1032 intPointMatrix = dd_CreateMatrix(iPMatrixRows+10,this->numVars+1); //iPMatrixRows+10; 1033 intPointMatrix->numbtype=dd_Integer; //NOTE: DO NOT REMOVE OR CHANGE TO dd_Rational 1034 1035 for (int ii=0;ii<IDELEMS(srcRing_HH);ii++) 1036 { 1037 markingsAreCorrect=FALSE; //crucial to initialise here 1038 poly aktpoly=srcRing_HH->m[ii]; 1039 /*Comparison of leading monomials is done via exponent vectors*/ 1040 for (int jj=0;jj<IDELEMS(H);jj++) 996 intPointMatrix = dd_CreateMatrix(iPMatrixRows+10,this->numVars+1); //iPMatrixRows+10; 997 intPointMatrix->numbtype=dd_Integer; //NOTE: DO NOT REMOVE OR CHANGE TO dd_Rational 998 999 for (int ii=0;ii<IDELEMS(srcRing_HH);ii++) 1000 { 1001 markingsAreCorrect=FALSE; //crucial to initialise here 1002 poly aktpoly=srcRing_HH->m[ii]; 1003 /*Comparison of leading monomials is done via exponent vectors*/ 1004 for (int jj=0;jj<IDELEMS(H);jj++) 1005 { 1006 int *src_ExpV = (int *)omAlloc((this->numVars+1)*sizeof(int)); 1007 int *dst_ExpV = (int *)omAlloc((this->numVars+1)*sizeof(int)); 1008 pGetExpV(aktpoly,src_ExpV); 1009 rChangeCurrRing(tmpRing); //this ring change is crucial! 1010 pGetExpV(pCopy(H->m[ii]),dst_ExpV); 1011 rChangeCurrRing(srcRing); 1012 bool expVAreEqual=TRUE; 1013 for (int kk=1;kk<=this->numVars;kk++) 1014 { 1015 #ifdef gfan_DEBUG 1016 //cout << src_ExpV[kk] << "," << dst_ExpV[kk] << endl; 1017 #endif 1018 if (src_ExpV[kk]!=dst_ExpV[kk]) 1041 1019 { 1042 int *src_ExpV = (int *)omAlloc((this->numVars+1)*sizeof(int)); 1043 int *dst_ExpV = (int *)omAlloc((this->numVars+1)*sizeof(int)); 1044 pGetExpV(aktpoly,src_ExpV); 1045 rChangeCurrRing(tmpRing); //this ring change is crucial! 1046 pGetExpV(pCopy(H->m[ii]),dst_ExpV); 1047 rChangeCurrRing(srcRing); 1048 bool expVAreEqual=TRUE; 1049 for (int kk=1;kk<=this->numVars;kk++) 1050 { 1051 #ifdef gfan_DEBUG 1052 //cout << src_ExpV[kk] << "," << dst_ExpV[kk] << endl; 1053 #endif 1054 if (src_ExpV[kk]!=dst_ExpV[kk]) 1055 { 1056 expVAreEqual=FALSE; 1057 } 1058 } 1020 expVAreEqual=FALSE; 1021 } 1022 } 1059 1023 //if (*src_ExpV == *dst_ExpV) 1060 1061 1062 1024 if (expVAreEqual==TRUE) 1025 { 1026 markingsAreCorrect=TRUE; //everything is fine 1063 1027 #ifdef gfan_DEBUG 1064 1028 // cout << "correct markings" << endl; 1065 1029 #endif 1066 1067 1068 1069 1030 }//if (pHead(aktpoly)==pHead(H->m[jj]) 1031 delete src_ExpV; 1032 delete dst_ExpV; 1033 }//for (int jj=0;jj<IDELEMS(H);jj++) 1070 1034 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1035 int *v=(int *)omAlloc((this->numVars+1)*sizeof(int)); 1036 int *leadExpV=(int *)omAlloc((this->numVars+1)*sizeof(int)); 1037 if (markingsAreCorrect==TRUE) 1038 { 1039 pGetExpV(aktpoly,leadExpV); 1040 } 1041 else 1042 { 1043 rChangeCurrRing(tmpRing); 1044 pGetExpV(pHead(H->m[ii]),leadExpV); //We use H->m[ii] as leading monomial 1045 rChangeCurrRing(srcRing); 1046 } 1047 /*compute differences of the expvects*/ 1048 while (pNext(aktpoly)!=NULL) 1049 { 1086 1050 /*The following if-else-block makes sure the first term (i.e. the wrongly marked term) 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1051 is not omitted when computing the differences*/ 1052 if(markingsAreCorrect==TRUE) 1053 { 1054 aktpoly=pNext(aktpoly); 1055 pGetExpV(aktpoly,v); 1056 } 1057 else 1058 { 1059 pGetExpV(pHead(aktpoly),v); 1060 markingsAreCorrect=TRUE; 1061 } 1062 1063 for (int jj=0;jj<this->numVars;jj++) 1064 { 1065 /*Store into ddMatrix*/ 1066 dd_set_si(intPointMatrix->matrix[aktrow][jj+1],leadExpV[jj+1]-v[jj+1]); 1067 } 1068 aktrow +=1; 1069 } 1070 delete v; 1071 delete leadExpV; 1072 }//for (int ii=0;ii<IDELEMS(srcRing_HH);ii++) 1073 /*Now we add the constraint for the standard simplex*/ 1074 /*NOTE:Might actually work without the standard simplex*/ 1075 dd_set_si(intPointMatrix->matrix[aktrow][0],-1); 1076 for (int jj=1;jj<=this->numVars;jj++) 1077 { 1078 dd_set_si(intPointMatrix->matrix[aktrow][jj],1); 1079 } 1116 1080 //Let's make sure we compute interior points from the positive orthant 1117 1118 1119 1120 1121 1122 1123 1124 1125 1081 dd_MatrixPtr posRestr=dd_CreateMatrix(this->numVars,this->numVars+1); 1082 int jj=1; 1083 for (int ii=0;ii<this->numVars;ii++) 1084 { 1085 dd_set_si(posRestr->matrix[ii][jj],1); 1086 jj++; 1087 } 1088 dd_MatrixAppendTo(&intPointMatrix,posRestr); 1089 dd_FreeMatrix(posRestr); 1126 1090 #ifdef gfan_DEBUG 1127 1091 // dd_WriteMatrix(stdout,intPointMatrix); 1128 1092 #endif 1129 1130 1131 1132 1093 intvec *iv_weight = new intvec(this->numVars); 1094 interiorPoint(intPointMatrix, *iv_weight); //iv_weight now contains the interior point 1095 dd_FreeMatrix(intPointMatrix); 1096 dd_free_global_constants(); 1133 1097 1134 1098 /*Step 3 1135 1099 turn the minimal basis into a reduced one 1136 1100 */ 1137 1101 //ring dstRing=rCopyAndAddWeight(tmpRing,iv_weight); … … 1142 1106 //cout << "PLING" << endl; 1143 1107 /*ring dstRing=rCopy0(srcRing); 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1108 for (int ii=0;ii<this->numVars;ii++) 1109 { 1110 dstRing->wvhdl[0][ii]=(*iv_weight)[ii]; 1111 }*/ 1112 ring dstRing=rCopy0(tmpRing); 1113 int length=iv_weight->length(); 1114 int *A=(int *)omAlloc0(length*sizeof(int)); 1115 for(int jj=0;jj<length;jj++) 1116 { 1117 A[jj]=(*iv_weight)[jj]; 1118 } 1119 dstRing->wvhdl[0]=(int*)A; 1120 rComplete(dstRing); 1121 rChangeCurrRing(dstRing); 1158 1122 //rDelete(tmpRing); 1159 1123 delete iv_weight; 1160 1124 //#ifdef gfan_DEBUG 1161 1125 rWrite(dstRing); cout << endl; 1162 1126 //#endif 1163 1164 1127 ideal dstRing_I; 1128 dstRing_I=idrCopyR(srcRing_HH,srcRing); 1165 1129 //dstRing_I=idrCopyR(inputIdeal,srcRing); 1166 1130 //validOpts<1>=TRUE; … … 1168 1132 //idShow(dstRing_I); 1169 1133 #endif 1170 1171 1172 1173 #ifdef gfan_DEBUG 1174 1175 #endif 1176 1134 BITSET save=test; 1135 test|=Sy_bit(OPT_REDSB); 1136 test|=Sy_bit(OPT_REDTAIL); 1137 #ifdef gfan_DEBUG 1138 test|=Sy_bit(6); //OPT_DEBUG 1139 #endif 1140 ideal tmpI; 1177 1141 //NOTE Any of the two variants of tmpI={idrCopy(),dstRing_I} does the trick 1178 1142 //tmpI = idrCopyR(this->inputIdeal,this->baseRing); 1179 1180 1181 1143 tmpI = dstRing_I; 1144 dstRing_I=kStd(tmpI,NULL,testHomog,NULL); 1145 idNorm(dstRing_I); 1182 1146 //kInterRed(dstRing_I); 1183 1184 1185 1186 1187 1188 1147 idSkipZeroes(dstRing_I); 1148 test=save; 1149 /*End of step 3 - reduction*/ 1150 1151 f->setFlipGB(dstRing_I);//store the flipped GB 1152 f->flipRing=rCopy(dstRing); //store the ring on the other side 1189 1153 //#ifdef gfan_DEBUG 1190 1154 cout << "Flipped GB is UCN " << counter+1 << ":" << endl; 1191 1155 //f->printFlipGB(); 1192 1193 1156 this->idDebugPrint(dstRing_I); 1157 cout << endl; 1194 1158 //#endif 1195 1159 rChangeCurrRing(srcRing); //return to the ring we started the computation of flipGB in 1196 1160 // rDelete(dstRing); 1197 1161 }//void flip(ideal gb, facet *f) 1198 1162 1199 1200 1201 1202 1203 1204 1205 1163 /** \brief Compute the remainder of a polynomial by a given ideal 1164 * 1165 * Compute \f$ f^{\mathcal{G}} \f$ 1166 * Algorithm is taken from Cox, Little, O'Shea, IVA 2nd Ed. p 62 1167 * However, since we are only interested in the remainder, there is no need to 1168 * compute the factors \f$ a_i \f$ 1169 */ 1206 1170 //NOTE: Should be replaced by kNF or kNF2 1207 polyrestOfDiv(poly const &f, ideal const &I)1208 1171 poly gcone::restOfDiv(poly const &f, ideal const &I) 1172 { 1209 1173 // cout << "Entering restOfDiv" << endl; 1210 1174 poly p=f; 1211 1175 //pWrite(p); 1212 1213 1214 1215 1216 1217 1218 1219 1176 poly r=NULL; //The zero polynomial 1177 int ii; 1178 bool divOccured; 1179 1180 while (p!=NULL) 1181 { 1182 ii=1; 1183 divOccured=FALSE; 1220 1184 1221 1222 1223 1224 1225 1185 while( (ii<=IDELEMS(I) && (divOccured==FALSE) )) 1186 { 1187 if (pDivisibleBy(I->m[ii-1],p)) //does LM(I->m[ii]) divide LM(p) ? 1188 { 1189 poly step1,step2,step3; 1226 1190 //cout << "dividing "; pWrite(pHead(p));cout << "by ";pWrite(pHead(I->m[ii-1])); cout << endl; 1227 1191 step1 = pDivideM(pHead(p),pHead(I->m[ii-1])); 1228 1192 //cout << "LT(p)/LT(f_i)="; pWrite(step1); cout << endl; 1229 1230 1193 step2 = ppMult_qq(step1, I->m[ii-1]); 1194 step3 = pSub(pCopy(p), step2); 1231 1195 //p=pSub(p,pMult( pDivide(pHead(p),pHead(I->m[ii])), I->m[ii])); 1232 1196 //pSetm(p); 1233 1234 1197 pSort(step3); //must be here, otherwise strange behaviour with many +o+o+o+o+ terms 1198 p=step3; 1235 1199 //pWrite(p); 1236 1237 1238 1239 1240 1241 1242 1243 1244 1200 divOccured=TRUE; 1201 } 1202 else 1203 { 1204 ii += 1; 1205 }//if (pLmDivisibleBy(I->m[ii],p,currRing)) 1206 }//while( (ii<IDELEMS(I) && (divOccured==FALSE) )) 1207 if (divOccured==FALSE) 1208 { 1245 1209 //cout << "TICK 5" << endl; 1246 1247 1248 1210 r=pAdd(pCopy(r),pHead(p)); 1211 pSetm(r); 1212 pSort(r); 1249 1213 //cout << "r="; pWrite(r); cout << endl; 1250 1214 1251 1252 1253 1254 1255 1256 1257 1258 1215 if (pLength(p)!=1) 1216 { 1217 p=pSub(pCopy(p),pHead(p)); //Here it may occur that p=0 instead of p=NULL 1218 } 1219 else 1220 { 1221 p=NULL; //Hack to correct this situation 1222 } 1259 1223 //cout << "p="; pWrite(p); 1260 1261 1262 1263 1264 1265 1266 1267 1268 idealffG(ideal const &H, ideal const &G)1269 1224 }//if (divOccured==FALSE) 1225 }//while (p!=0) 1226 return r; 1227 }//poly restOfDiv(poly const &f, ideal const &I) 1228 1229 /** \brief Compute \f$ f-f^{\mathcal{G}} \f$ 1230 */ 1231 //NOTE: use kNF or kNF2 instead of restOfDivision 1232 ideal gcone::ffG(ideal const &H, ideal const &G) 1233 { 1270 1234 // cout << "Entering ffG" << endl; 1271 1272 1273 1274 1275 1276 1235 int size=IDELEMS(H); 1236 ideal res=idInit(size,1); 1237 poly temp1, temp2, temp3; //polys to temporarily store values for pSub 1238 for (int ii=0;ii<size;ii++) 1239 { 1240 res->m[ii]=restOfDiv(H->m[ii],G); 1277 1241 //res->m[ii]=kNF(G, NULL,H->m[ii]); 1278 1279 1280 1281 1242 temp1=H->m[ii]; 1243 temp2=res->m[ii]; 1244 temp3=pSub(temp1, temp2); 1245 res->m[ii]=temp3; 1282 1246 //res->m[ii]=pSub(temp1,temp2); //buggy 1283 1247 //pSort(res->m[ii]); 1284 1248 //pSetm(res->m[ii]); 1285 1249 //cout << "res->m["<<ii<<"]=";pWrite(res->m[ii]); 1286 } 1287 return res; 1288 } 1289 1290 /** \brief Compute a Groebner Basis 1291 * 1292 * Computes the Groebner basis and stores the result in gcone::gcBasis 1293 *\param ideal 1294 *\return void 1295 */ 1296 void getGB(ideal const &inputIdeal) 1297 { 1298 BITSET save=test; 1299 test|=Sy_bit(OPT_REDSB); 1300 test|=Sy_bit(OPT_REDTAIL); 1301 ideal gb; 1302 gb=kStd(inputIdeal,NULL,testHomog,NULL); 1303 idSkipZeroes(gb); 1304 this->gcBasis=gb; //write the GB into gcBasis 1305 test=save; 1306 }//void getGB 1307 1308 /** \brief The Generic Groebner Walk due to FJLT 1309 * Needed for computing the search facet 1310 */ 1311 ideal GenGrbWlk(ideal, ideal) 1312 { 1313 }//GGW 1314 1315 /** \brief Compute the negative of a given intvec 1316 */ 1317 intvec *ivNeg(const intvec *iv) 1318 { 1319 intvec *res = new intvec(iv->length()); 1320 res=ivCopy(iv); 1321 *res *= (int)-1; 1322 return res; 1323 } 1324 1325 1326 /** \brief Compute the dot product of two intvecs 1327 * 1328 */ 1329 int dotProduct(intvec const &iva, intvec const &ivb) 1330 { 1331 int res=0; 1332 for (int i=0;i<this->numVars;i++) 1333 { 1334 res = res+(iva[i]*ivb[i]); 1335 } 1336 return res; 1337 }//int dotProduct 1338 1339 /** \brief Check whether two intvecs are parallel 1340 * 1341 * \f$ \alpha\parallel\beta\Leftrightarrow\langle\alpha,\beta\rangle^2=\langle\alpha,\alpha\rangle\langle\beta,\beta\rangle \f$ 1342 */ 1343 bool isParallel(intvec const &a, intvec const &b) 1344 { 1345 int lhs,rhs; 1346 bool res; 1347 lhs=dotProduct(a,b)*dotProduct(a,b); 1348 rhs=dotProduct(a,a)*dotProduct(b,b); 1250 } 1251 return res; 1252 } 1253 1254 /** \brief Compute a Groebner Basis 1255 * 1256 * Computes the Groebner basis and stores the result in gcone::gcBasis 1257 *\param ideal 1258 *\return void 1259 */ 1260 void gcone::getGB(ideal const &inputIdeal) 1261 { 1262 BITSET save=test; 1263 test|=Sy_bit(OPT_REDSB); 1264 test|=Sy_bit(OPT_REDTAIL); 1265 ideal gb; 1266 gb=kStd(inputIdeal,NULL,testHomog,NULL); 1267 idSkipZeroes(gb); 1268 this->gcBasis=gb; //write the GB into gcBasis 1269 test=save; 1270 }//void getGB 1271 1272 /** \brief Compute the negative of a given intvec 1273 */ 1274 intvec *gcone::ivNeg(const intvec *iv) 1275 { 1276 intvec *res = new intvec(iv->length()); 1277 res=ivCopy(iv); 1278 *res *= (int)-1; 1279 return res; 1280 } 1281 1282 1283 /** \brief Compute the dot product of two intvecs 1284 * 1285 */ 1286 int gcone::dotProduct(intvec const &iva, intvec const &ivb) 1287 { 1288 int res=0; 1289 for (int i=0;i<this->numVars;i++) 1290 { 1291 res = res+(iva[i]*ivb[i]); 1292 } 1293 return res; 1294 }//int dotProduct 1295 1296 /** \brief Check whether two intvecs are parallel 1297 * 1298 * \f$ \alpha\parallel\beta\Leftrightarrow\langle\alpha,\beta\rangle^2=\langle\alpha,\alpha\rangle\langle\beta,\beta\rangle \f$ 1299 */ 1300 bool gcone::isParallel(intvec const &a, intvec const &b) 1301 { 1302 int lhs,rhs; 1303 bool res; 1304 lhs=dotProduct(a,b)*dotProduct(a,b); 1305 rhs=dotProduct(a,a)*dotProduct(b,b); 1349 1306 //cout << "LHS="<<lhs<<", RHS="<<rhs<<endl; 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 voidinteriorPoint(dd_MatrixPtr const &M, intvec &iv) //no const &M here since we want to remove redundant rows1366 1367 1368 1369 1370 1371 1372 1373 1307 if (lhs==rhs) 1308 { 1309 res = TRUE; 1310 } 1311 else 1312 { 1313 res = FALSE; 1314 } 1315 return res; 1316 }//bool isParallel 1317 1318 /** \brief Compute an interior point of a given cone 1319 * Result will be written into intvec iv. 1320 * Any rational point is automatically converted into an integer. 1321 */ 1322 void gcone::interiorPoint(dd_MatrixPtr const &M, intvec &iv) //no const &M here since we want to remove redundant rows 1323 { 1324 dd_LPPtr lp,lpInt; 1325 dd_ErrorType err=dd_NoError; 1326 dd_LPSolverType solver=dd_DualSimplex; 1327 dd_LPSolutionPtr lpSol=NULL; 1328 dd_rowset ddlinset,ddredrows; //needed for dd_FindRelativeInterior 1329 dd_rowindex ddnewpos; 1330 dd_NumberType numb; 1374 1331 //M->representation=dd_Inequality; 1375 1332 //M->objective-dd_LPMin; //Not sure whether this is needed … … 1379 1336 1380 1337 /*NOTE: Leave the following line commented out! 1381 1382 1338 * Otherwise it will cause interior points that are not strictly positive on some examples 1339 * 1383 1340 */ 1384 1341 //dd_MatrixCanonicalize(&M, &ddlinset, &ddredrows, &ddnewpos, &err); … … 1387 1344 //dd_WriteMatrix(stdout,M); 1388 1345 1389 1390 1391 1346 lp=dd_Matrix2LP(M, &err); 1347 if (err!=dd_NoError){cout << "Error during dd_Matrix2LP in gcone::interiorPoint" << endl;} 1348 if (lp==NULL){cout << "LP is NULL" << endl;} 1392 1349 #ifdef gfan_DEBUG 1393 1350 // dd_WriteLP(stdout,lp); 1394 1351 #endif 1395 1352 1396 1397 1353 lpInt=dd_MakeLPforInteriorFinding(lp); 1354 if (err!=dd_NoError){cout << "Error during dd_MakeLPForInteriorFinding in gcone::interiorPoint" << endl;} 1398 1355 #ifdef gfan_DEBUG 1399 1356 // dd_WriteLP(stdout,lpInt); 1400 1357 #endif 1401 1358 1402 1403 1404 1405 1406 1407 1359 dd_FindRelativeInterior(M,&ddlinset,&ddredrows,&lpSol,&err); 1360 if (err!=dd_NoError) 1361 { 1362 cout << "Error during dd_FindRelativeInterior in gcone::interiorPoint" << endl; 1363 dd_WriteErrorMessages(stdout, err); 1364 } 1408 1365 1409 1366 //dd_LPSolve(lpInt,solver,&err); //This will not result in a point from the relative interior 1410 1367 if (err!=dd_NoError){cout << "Error during dd_LPSolve" << endl;} 1411 1368 1412 1369 //lpSol=dd_CopyLPSolution(lpInt); 1413 1414 #ifdef gfan_DEBUG 1415 1416 1417 1418 1419 1420 1370 if (err!=dd_NoError){cout << "Error during dd_CopyLPSolution" << endl;} 1371 #ifdef gfan_DEBUG 1372 cout << "Interior point: "; 1373 for (int ii=1; ii<(lpSol->d)-1;ii++) 1374 { 1375 dd_WriteNumber(stdout,lpSol->sol[ii]); 1376 } 1377 cout << endl; 1421 1378 #endif 1422 1379 1423 1380 //NOTE The following strongly resembles parts of makeInt. 1424 1381 //Maybe merge sometimes 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1382 mpz_t kgV; mpz_init(kgV); 1383 mpz_set_str(kgV,"1",10); 1384 mpz_t den; mpz_init(den); 1385 mpz_t tmp; mpz_init(tmp); 1386 mpq_get_den(tmp,lpSol->sol[1]); 1387 for (int ii=1;ii<(lpSol->d)-1;ii++) 1388 { 1389 mpq_get_den(den,lpSol->sol[ii+1]); 1390 mpz_lcm(kgV,tmp,den); 1391 mpz_set(tmp, kgV); 1392 } 1393 mpq_t qkgV; 1394 mpq_init(qkgV); 1395 mpq_set_z(qkgV,kgV); 1396 for (int ii=1;ii<(lpSol->d)-1;ii++) 1397 { 1398 mpq_t product; 1399 mpq_init(product); 1400 mpq_mul(product,qkgV,lpSol->sol[ii]); 1401 iv[ii-1]=(int)mpz_get_d(mpq_numref(product)); 1402 mpq_clear(product); 1403 } 1447 1404 #ifdef gfan_DEBUG 1448 1405 // iv.show(); 1449 1406 // cout << endl; 1450 1407 #endif 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 ringrCopyAndAddWeight(ring const &r, intvec const *ivw)1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1408 mpq_clear(qkgV); 1409 mpz_clear(tmp); 1410 mpz_clear(den); 1411 mpz_clear(kgV); 1412 1413 dd_FreeLPSolution(lpSol); 1414 dd_FreeLPData(lpInt); 1415 dd_FreeLPData(lp); 1416 set_free(ddlinset); 1417 set_free(ddredrows); 1418 1419 }//void interiorPoint(dd_MatrixPtr const &M) 1420 1421 /** \brief Copy a ring and add a weighted ordering in first place 1422 * 1423 */ 1424 ring gcone::rCopyAndAddWeight(ring const &r, intvec const *ivw) 1425 { 1426 ring res=rCopy0(r); 1427 int jj; 1428 1429 omFree(res->order); 1430 res->order =(int *)omAlloc0(4*sizeof(int)); 1431 omFree(res->block0); 1432 res->block0=(int *)omAlloc0(4*sizeof(int)); 1433 omFree(res->block1); 1434 res->block1=(int *)omAlloc0(4*sizeof(int)); 1435 omfree(res->wvhdl); 1436 res->wvhdl =(int **)omAlloc0(4*sizeof(int**)); 1437 1438 res->order[0]=ringorder_a; 1439 res->block0[0]=1; 1440 res->block1[0]=res->N;; 1441 res->order[1]=ringorder_dp; //basically useless, since that should never be used 1442 res->block0[1]=1; 1443 res->block1[1]=res->N;; 1444 res->order[2]=ringorder_C; 1445 1446 int length=ivw->length(); 1447 int *A=(int *)omAlloc0(length*sizeof(int)); 1448 for (jj=0;jj<length;jj++) 1449 { 1450 A[jj]=(*ivw)[jj]; 1451 } 1452 res->wvhdl[0]=(int *)A; 1453 res->block1[0]=length; 1454 1455 rComplete(res); 1456 return res; 1457 }//rCopyAndAdd 1501 1458 1502 1459 ring rCopyAndChangeWeight(ring const &r, intvec *ivw) 1503 1504 1505 1506 1460 { 1461 ring res=rCopy0(currRing); 1462 rComplete(res); 1463 rSetWeightVec(res,(int64*)ivw); 1507 1464 //rChangeCurrRing(rnew); 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 boolisSearchFacet(gcone &gcTmp, facet *testfacet)1520 1521 1522 1523 1465 return res; 1466 } 1467 1468 /** \brief Checks whether a given facet is a search facet 1469 * Determines whether a given facet of a cone is the search facet of a neighbouring cone 1470 * This is done in the following way: 1471 * We loop through all facets of the cone and find the "smallest" facet, i.e. the unique facet 1472 * that is first crossed during the generic walk. 1473 * We then check whether the fNormal of this facet is parallel to the fNormal of our testfacet. 1474 * If this is the case, then our facet is indeed a search facet and TRUE is retuned. 1475 */ 1476 bool gcone::isSearchFacet(gcone &gcTmp, facet *testfacet) 1477 { 1478 ring actRing=currRing; 1479 facet *facetPtr=(facet*)gcTmp.facetPtr; 1480 facet *fMin=new facet(*facetPtr); //Pointer to the "minimal" facet 1524 1481 //facet *fMin = new facet(tmpcone.facetPtr); 1525 1482 //fMin=tmpcone.facetPtr; //Initialise to first facet of tmpcone 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 #ifdef gfan_DEBUG 1549 1550 1551 #endif 1552 1553 1554 1555 #ifdef gfan_DEBUG 1556 1557 #endif 1558 1559 1560 1561 1562 1563 1483 facet *fAct; //Ptr to alpha_i 1484 facet *fCmp; //Ptr to alpha_j 1485 fAct = fMin; 1486 fCmp = fMin->next; 1487 1488 rChangeCurrRing(this->rootRing); //because we compare the monomials in the rootring 1489 poly p=pInit(); 1490 poly q=pInit(); 1491 intvec *alpha_i = new intvec(this->numVars); 1492 intvec *alpha_j = new intvec(this->numVars); 1493 intvec *sigma = new intvec(this->numVars); 1494 sigma=gcTmp.getIntPoint(); 1495 1496 int *u=(int *)omAlloc((this->numVars+1)*sizeof(int)); 1497 int *v=(int *)omAlloc((this->numVars+1)*sizeof(int)); 1498 u[0]=0; v[0]=0; 1499 int weight1,weight2; 1500 while(fAct->next->next!=NULL) //NOTE this is ugly. Can it be done without fCmp? 1501 { 1502 /* Get alpha_i and alpha_{i+1} */ 1503 alpha_i=fAct->getFacetNormal(); 1504 alpha_j=fCmp->getFacetNormal(); 1505 #ifdef gfan_DEBUG 1506 alpha_i->show(); 1507 alpha_j->show(); 1508 #endif 1509 /*Compute the dot product of sigma and alpha_{i,j}*/ 1510 weight1=dotProduct(sigma,alpha_i); 1511 weight2=dotProduct(sigma,alpha_j); 1512 #ifdef gfan_DEBUG 1513 cout << "weight1=" << weight1 << " " << "weight2=" << weight2 << endl; 1514 #endif 1515 /*Adjust alpha_i and alpha_i+1 accordingly*/ 1516 for(int ii=1;ii<=this->numVars;ii++) 1517 { 1518 u[ii]=weight1*(*alpha_i)[ii-1]; 1519 v[ii]=weight2*(*alpha_j)[ii-1]; 1520 } 1564 1521 1565 1566 1567 1568 1569 1570 1571 1522 /*Now p_weight and q_weight need to be compared as exponent vectors*/ 1523 pSetCoeff0(p,nInit(1)); 1524 pSetCoeff0(q,nInit(1)); 1525 pSetExpV(p,u); 1526 pSetm(p); 1527 pSetExpV(q,v); 1528 pSetm(q); 1572 1529 #ifdef gfan_DEBUG 1573 1530 pWrite(p);pWrite(q); 1574 1531 #endif 1575 1532 /*We want to check whether x^p < x^q 1576 => want to check for return value 1 */ 1577 if (pLmCmp(p,q)==1) //i.e. x^q is smaller 1578 { 1579 fMin=fCmp; 1580 fAct=fMin; 1581 fCmp=fCmp->next; 1533 => want to check for return value 1 */ 1534 if (pLmCmp(p,q)==1) //i.e. x^q is smaller 1535 { 1536 fMin=fCmp; 1537 fAct=fMin; 1538 fCmp=fCmp->next; 1539 } 1540 else 1541 { 1542 //fAct=fAct->next; 1543 if(fCmp->next!=NULL) 1544 { 1545 fCmp=fCmp->next; 1546 } 1547 else 1548 { 1549 fAct=fAct->next; 1550 } 1551 } 1552 //fAct=fAct->next; 1553 }//while(fAct.facetPtr->next!=NULL) 1554 delete alpha_i,alpha_j,sigma; 1555 1556 /*If testfacet was minimal then fMin should still point there */ 1557 1558 //if(fMin->getFacetNormal()==ivNeg(testfacet.getFacetNormal())) 1559 #ifdef gfan_DEBUG 1560 cout << "Checking for parallelity" << endl <<" fMin is"; 1561 fMin->printNormal(); 1562 cout << "testfacet is "; 1563 testfacet->printNormal(); 1564 cout << endl; 1565 #endif 1566 if (fMin==gcTmp.facetPtr) 1567 //if(areEqual(fMin->getFacetNormal(),ivNeg(testfacet.getFacetNormal()))) 1568 //if (isParallel(fMin->getFacetNormal(),testfacet->getFacetNormal())) 1569 { 1570 cout << "Parallel" << endl; 1571 rChangeCurrRing(actRing); 1572 //delete alpha_min, test; 1573 return TRUE; 1574 } 1575 else 1576 { 1577 cout << "Not parallel" << endl; 1578 rChangeCurrRing(actRing); 1579 //delete alpha_min, test; 1580 return FALSE; 1581 } 1582 }//bool isSearchFacet 1583 1584 /** \brief Check for equality of two intvecs 1585 */ 1586 bool gcone::areEqual(intvec const &a, intvec const &b) 1587 { 1588 bool res=TRUE; 1589 for(int ii=0;ii<this->numVars;ii++) 1590 { 1591 if(a[ii]!=b[ii]) 1592 { 1593 res=FALSE; 1594 break; 1595 } 1596 } 1597 return res; 1598 } 1599 1600 /** \brief The reverse search algorithm 1601 */ 1602 void gcone::reverseSearch(gcone *gcAct) //no const possible here since we call gcAct->flip 1603 { 1604 facet *fAct=new facet(); 1605 fAct = gcAct->facetPtr; 1606 1607 while(fAct!=NULL) 1608 { 1609 cout << "======================"<< endl; 1610 gcAct->flip(gcAct->gcBasis,gcAct->facetPtr); 1611 gcone *gcTmp = new gcone(*gcAct); 1612 //idShow(gcTmp->gcBasis); 1613 gcTmp->getConeNormals(gcTmp->gcBasis, TRUE); 1614 #ifdef gfan_DEBUG 1615 facet *f = new facet(); 1616 f=gcTmp->facetPtr; 1617 while(f!=NULL) 1618 { 1619 f->printNormal(); 1620 f=f->next; 1621 } 1622 #endif 1623 gcTmp->showIntPoint(); 1624 /*recursive part goes gere*/ 1625 if (isSearchFacet(*gcTmp,(facet*)gcAct->facetPtr)) 1626 { 1627 gcAct->next=gcTmp; 1628 cout << "PING"<< endl; 1629 reverseSearch(gcTmp); 1630 } 1631 else 1632 { 1633 delete gcTmp; 1634 /*NOTE remove fAct from linked list. It's no longer needed*/ 1635 } 1636 /*recursion ends*/ 1637 fAct = fAct->next; 1638 }//while(fAct->next!=NULL) 1639 }//reverseSearch 1640 1641 /** \brief The new method of Markwig and Jensen 1642 * Compute gcBasis and facets for the arbitrary starting cone. Store \f$(codim-1)\f$-facets as normals. 1643 * In order to represent a facet uniquely compute also the \f$(codim-2)\f$-facets and norm by the gcd of the components. 1644 * Keep a list of facets as a linked list containing an intvec and an integer matrix. 1645 * Since a \f$(codim-1)\f$-facet belongs to exactly two full dimensional cones, we remove a facet from the list as 1646 * soon as we compute this facet again. Comparison of facets is done by... 1647 */ 1648 void gcone::noRevS(gcone &gcRoot, bool usingIntPoint) 1649 { 1650 facet *SearchListRoot = new facet(); //The list containing ALL facets we come across 1651 facet *SearchListAct; 1652 SearchListAct = NULL; 1653 //SearchListAct = SearchListRoot; 1654 1655 gcone *gcAct; 1656 gcAct = &gcRoot; 1657 gcone *gcPtr; //Pointer to end of linked list of cones 1658 gcPtr = &gcRoot; 1659 gcone *gcNext; //Pointer to next cone to be visited 1660 gcNext = &gcRoot; 1661 gcone *gcHead; 1662 gcHead = &gcRoot; 1663 1664 facet *fAct; 1665 fAct = gcAct->facetPtr; 1666 1667 ring rAct; 1668 rAct = currRing; 1669 1670 int UCNcounter=gcAct->getUCN(); 1671 #ifdef gfan_DEBUG 1672 cout << "NoRevs" << endl; 1673 cout << "Facets are:" << endl; 1674 gcAct->showFacets(); 1675 #endif 1676 1677 gcAct->getCodim2Normals(*gcAct); 1678 1679 //Compute unique representation of codim-2-facets 1680 gcAct->normalize(); 1681 1682 /*Make a copy of the facet list of first cone 1683 Since the operations getCodim2Normals and normalize affect the facets 1684 we must not memcpy them before these ops! 1685 */ 1686 intvec *fNormal;// = new intvec(this->numVars); 1687 intvec *f2Normal;// = new intvec(this->numVars); 1688 facet *codim2Act; codim2Act = NULL; 1689 facet *sl2Root; //sl2Root = new facet(2); 1690 facet *sl2Act; //sl2Act = sl2Root; 1691 1692 for(int ii=0;ii<this->numFacets;ii++) 1693 { 1694 //only copy flippable facets! 1695 if(fAct->isFlippable==TRUE) 1696 { 1697 fNormal = fAct->getFacetNormal(); 1698 if( ii==0 || (ii>0 && SearchListAct==NULL) ) //1st facet may be non-flippable 1699 { 1700 SearchListAct = SearchListRoot; 1701 //memcpy(SearchListAct,fAct,sizeof(facet)); 1702 } 1703 else 1704 { 1705 SearchListAct->next = new facet(); 1706 SearchListAct = SearchListAct->next; 1707 //memcpy(SearchListAct,fAct,sizeof(facet)); 1708 } 1709 SearchListAct->setFacetNormal(fNormal); 1710 SearchListAct->setUCN(this->getUCN()); 1711 SearchListAct->numCodim2Facets=fAct->numCodim2Facets; 1712 SearchListAct->isFlippable=TRUE; 1713 //Copy codim2-facets 1714 codim2Act=fAct->codim2Ptr; 1715 SearchListAct->codim2Ptr = new facet(2); 1716 sl2Root = SearchListAct->codim2Ptr; 1717 sl2Act = sl2Root; 1718 //while(codim2Act!=NULL) 1719 for(int jj=0;jj<fAct->numCodim2Facets;jj++) 1720 { 1721 f2Normal = codim2Act->getFacetNormal(); 1722 if(jj==0) 1723 { 1724 sl2Act = sl2Root; 1725 sl2Act->setFacetNormal(f2Normal); 1582 1726 } 1583 1727 else 1584 1728 { 1585 //fAct=fAct->next; 1586 if(fCmp->next!=NULL) 1587 { 1588 fCmp=fCmp->next; 1589 } 1590 else 1591 { 1592 fAct=fAct->next; 1593 } 1594 } 1595 //fAct=fAct->next; 1596 }//while(fAct.facetPtr->next!=NULL) 1597 delete alpha_i,alpha_j,sigma; 1598 1599 /*If testfacet was minimal then fMin should still point there */ 1600 1601 //if(fMin->getFacetNormal()==ivNeg(testfacet.getFacetNormal())) 1602 #ifdef gfan_DEBUG 1603 cout << "Checking for parallelity" << endl <<" fMin is"; 1604 fMin->printNormal(); 1605 cout << "testfacet is "; 1606 testfacet->printNormal(); 1607 cout << endl; 1608 #endif 1609 if (fMin==gcTmp.facetPtr) 1610 //if(areEqual(fMin->getFacetNormal(),ivNeg(testfacet.getFacetNormal()))) 1611 //if (isParallel(fMin->getFacetNormal(),testfacet->getFacetNormal())) 1612 { 1613 cout << "Parallel" << endl; 1614 rChangeCurrRing(actRing); 1615 //delete alpha_min, test; 1616 return TRUE; 1617 } 1618 else 1619 { 1620 cout << "Not parallel" << endl; 1621 rChangeCurrRing(actRing); 1622 //delete alpha_min, test; 1623 return FALSE; 1624 } 1625 }//bool isSearchFacet 1626 1627 /** \brief Check for equality of two intvecs 1628 */ 1629 bool areEqual(intvec const &a, intvec const &b) 1630 { 1631 bool res=TRUE; 1632 for(int ii=0;ii<this->numVars;ii++) 1633 { 1634 if(a[ii]!=b[ii]) 1635 { 1636 res=FALSE; 1637 break; 1638 } 1639 } 1640 return res; 1729 sl2Act->next = new facet(2); 1730 sl2Act = sl2Act->next; 1731 sl2Act->setFacetNormal(f2Normal); 1732 } 1733 codim2Act = codim2Act->next; 1734 } 1735 fAct = fAct->next; 1736 }//if(fAct->isFlippable==TRUE) 1737 else {fAct = fAct->next;} 1738 }//End of copying facets into SLA 1739 1740 SearchListAct = SearchListRoot; //Set to beginning of list 1741 /*Make SearchList doubly linked*/ 1742 while(SearchListAct!=NULL) 1743 { 1744 if(SearchListAct->next!=NULL) 1745 { 1746 SearchListAct->next->prev = SearchListAct; 1641 1747 } 1642 1643 /** \brief The reverse search algorithm 1644 */ 1645 void reverseSearch(gcone *gcAct) //no const possible here since we call gcAct->flip 1646 { 1647 facet *fAct=new facet(); 1648 fAct = gcAct->facetPtr; 1649 1650 while(fAct!=NULL) 1651 { 1652 cout << "======================"<< endl; 1653 gcAct->flip(gcAct->gcBasis,gcAct->facetPtr); 1654 gcone *gcTmp = new gcone(*gcAct); 1655 //idShow(gcTmp->gcBasis); 1656 gcTmp->getConeNormals(gcTmp->gcBasis, TRUE); 1657 #ifdef gfan_DEBUG 1658 facet *f = new facet(); 1659 f=gcTmp->facetPtr; 1660 while(f!=NULL) 1661 { 1662 f->printNormal(); 1663 f=f->next; 1664 } 1665 #endif 1666 gcTmp->showIntPoint(); 1667 /*recursive part goes gere*/ 1668 if (isSearchFacet(*gcTmp,(facet*)gcAct->facetPtr)) 1669 { 1670 gcAct->next=gcTmp; 1671 cout << "PING"<< endl; 1672 reverseSearch(gcTmp); 1673 } 1674 else 1675 { 1676 delete gcTmp; 1677 /*NOTE remove fAct from linked list. It's no longer needed*/ 1678 } 1679 /*recursion ends*/ 1680 fAct = fAct->next; 1681 }//while(fAct->next!=NULL) 1682 }//reverseSearch 1683 1684 /** \brief The new method of Markwig and Jensen 1685 * Compute gcBasis and facets for the arbitrary starting cone. Store \f$(codim-1)\f$-facets as normals. 1686 * In order to represent a facet uniquely compute also the \f$(codim-2)\f$-facets and norm by the gcd of the components. 1687 * Keep a list of facets as a linked list containing an intvec and an integer matrix. 1688 * Since a \f$(codim-1)\f$-facet belongs to exactly two full dimensional cones, we remove a facet from the list as 1689 * soon as we compute this facet again. Comparison of facets is done by... 1690 */ 1691 void noRevS(gcone &gcRoot, bool usingIntPoint=FALSE) 1692 { 1693 facet *SearchListRoot = new facet(); //The list containing ALL facets we come across 1694 facet *SearchListAct; 1695 SearchListAct = NULL; 1696 //SearchListAct = SearchListRoot; 1697 1698 gcone *gcAct; 1699 gcAct = &gcRoot; 1700 gcone *gcPtr; //Pointer to end of linked list of cones 1701 gcPtr = &gcRoot; 1702 gcone *gcNext; //Pointer to next cone to be visited 1703 gcNext = &gcRoot; 1704 gcone *gcHead; 1705 gcHead = &gcRoot; 1706 1707 facet *fAct; 1708 fAct = gcAct->facetPtr; 1709 1710 ring rAct; 1711 rAct = currRing; 1712 1713 int UCNcounter=gcAct->getUCN(); 1714 #ifdef gfan_DEBUG 1715 cout << "NoRevs" << endl; 1716 cout << "Facets are:" << endl; 1717 gcAct->showFacets(); 1718 #endif 1719 1720 gcAct->getCodim2Normals(*gcAct); 1721 1722 //Compute unique representation of codim-2-facets 1723 gcAct->normalize(); 1724 1725 /*Make a copy of the facet list of first cone 1726 Since the operations getCodim2Normals and normalize affect the facets 1727 we must not memcpy them before these ops! 1728 */ 1729 intvec *fNormal;// = new intvec(this->numVars); 1730 intvec *f2Normal;// = new intvec(this->numVars); 1731 facet *codim2Act; codim2Act = NULL; 1732 facet *sl2Root; //sl2Root = new facet(2); 1733 facet *sl2Act; //sl2Act = sl2Root; 1734 1735 for(int ii=0;ii<this->numFacets;ii++) 1736 { 1737 //only copy flippable facets! 1738 if(fAct->isFlippable==TRUE) 1739 { 1740 fNormal = fAct->getFacetNormal(); 1741 if( ii==0 || (ii>0 && SearchListAct==NULL) ) //1st facet may be non-flippable 1742 { 1743 SearchListAct = SearchListRoot; 1744 //memcpy(SearchListAct,fAct,sizeof(facet)); 1745 } 1746 else 1747 { 1748 SearchListAct->next = new facet(); 1749 SearchListAct = SearchListAct->next; 1750 //memcpy(SearchListAct,fAct,sizeof(facet)); 1751 } 1752 SearchListAct->setFacetNormal(fNormal); 1753 SearchListAct->setUCN(this->getUCN()); 1754 SearchListAct->numCodim2Facets=fAct->numCodim2Facets; 1755 SearchListAct->isFlippable=TRUE; 1756 //Copy codim2-facets 1757 codim2Act=fAct->codim2Ptr; 1758 SearchListAct->codim2Ptr = new facet(2); 1759 sl2Root = SearchListAct->codim2Ptr; 1760 sl2Act = sl2Root; 1761 //while(codim2Act!=NULL) 1762 for(int jj=0;jj<fAct->numCodim2Facets;jj++) 1763 { 1764 f2Normal = codim2Act->getFacetNormal(); 1765 if(jj==0) 1766 { 1767 sl2Act = sl2Root; 1768 sl2Act->setFacetNormal(f2Normal); 1769 } 1770 else 1771 { 1772 sl2Act->next = new facet(2); 1773 sl2Act = sl2Act->next; 1774 sl2Act->setFacetNormal(f2Normal); 1775 } 1776 codim2Act = codim2Act->next; 1777 } 1778 fAct = fAct->next; 1779 }//if(fAct->isFlippable==TRUE) 1780 else {fAct = fAct->next;} 1781 }//End of copying facets into SLA 1782 1783 SearchListAct = SearchListRoot; //Set to beginning of list 1784 /*Make SearchList doubly linked*/ 1785 while(SearchListAct!=NULL) 1786 { 1787 if(SearchListAct->next!=NULL) 1788 { 1789 SearchListAct->next->prev = SearchListAct; 1790 } 1791 SearchListAct = SearchListAct->next; 1792 } 1793 SearchListAct = SearchListRoot; //Set to beginning of List 1794 1795 fAct = gcAct->facetPtr; 1748 SearchListAct = SearchListAct->next; 1749 } 1750 SearchListAct = SearchListRoot; //Set to beginning of List 1751 1752 fAct = gcAct->facetPtr; 1796 1753 //NOTE Disabled until code works as expected 1797 1754 //gcAct->writeConeToFile(*gcAct); 1798 1755 1799 1800 1756 /*End of initialisation*/ 1757 fAct = SearchListAct; 1801 1758 /*2nd step 1802 1803 1759 Choose a facet from fListPtr, flip it and forget the previous cone 1760 We always choose the first facet from fListPtr as facet to be flipped 1804 1761 */ 1805 1806 1807 1762 while((SearchListAct!=NULL))// && counter<10) 1763 {//NOTE See to it that the cone is only changed after ALL facets have been flipped! 1764 fAct = SearchListAct; 1808 1765 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 #ifdef gfan_DEBUG 1820 1766 while(fAct!=NULL) 1767 { //Since SLA should only contain flippables there should be no need to check for that 1768 gcAct->flip(gcAct->gcBasis,fAct); 1769 ring rTmp=rCopy(fAct->flipRing); 1770 rComplete(rTmp); 1771 rChangeCurrRing(rTmp); 1772 gcone *gcTmp = new gcone::gcone(*gcAct,*fAct); 1773 gcTmp->getConeNormals(gcTmp->gcBasis, FALSE); 1774 gcTmp->getCodim2Normals(*gcTmp); 1775 gcTmp->normalize(); 1776 #ifdef gfan_DEBUG 1777 gcTmp->showFacets(1); 1821 1778 #endif 1822 1779 //gcTmp->writeConeToFile(*gcTmp); 1823 1824 1825 #ifdef gfan_DEBUG 1826 1827 1828 #endif 1829 1780 /*add facets to SLA here*/ 1781 SearchListRoot=gcTmp->enqueueNewFacets(*SearchListRoot); 1782 #ifdef gfan_DEBUG 1783 if(SearchListRoot!=NULL) 1784 gcTmp->showSLA(*SearchListRoot); 1785 #endif 1786 rChangeCurrRing(gcAct->baseRing); 1830 1787 //rDelete(rTmp); 1831 1832 1833 1834 1835 1836 1837 1838 1839 1788 gcPtr->next=gcTmp; 1789 gcPtr=gcPtr->next; 1790 if(fAct->getUCN() == fAct->next->getUCN()) 1791 { 1792 fAct=fAct->next; 1793 } 1794 else 1795 break; 1796 }//while( ( (fAct->next!=NULL) && (fAct->getUCN()==fAct->next->getUCN() ) ) ); 1840 1797 //Search for cone with smallest UCN 1841 1842 1843 1798 gcNext = gcHead; 1799 while(gcNext!=NULL) 1800 { 1844 1801 //if( gcNext->getUCN() == UCNcounter+1 ) 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1802 if( gcNext->getUCN() == SearchListRoot->getUCN() ) 1803 { 1804 gcAct = gcNext; 1805 rAct=rCopy(gcAct->baseRing); 1806 rComplete(rAct); 1807 rChangeCurrRing(rAct); 1808 break; 1809 } 1810 gcNext = gcNext->next; 1811 } 1812 UCNcounter++; 1856 1813 //SearchListAct = SearchListAct->next; 1857 1814 //SearchListAct = fAct->next; 1858 1859 1860 1815 SearchListAct = SearchListRoot; 1816 } 1817 cout << endl << "Found " << counter << " cones - terminating" << endl; 1861 1818 1862 1819 //NOTE Hm, comment in and get a crash for free... … … 1870 1827 //NOTE: gcTmp may be deleted, gcRoot from main proc should probably not! 1871 1828 1872 }//void noRevS(gcone &gc) 1873 1874 1875 /** \brief Make a set of rational vectors into integers 1876 * 1877 * We compute the lcm of the denominators and multiply with this to get integer values. 1878 * \param dd_MatrixPtr,intvec 1879 */ 1880 void makeInt(dd_MatrixPtr const &M, int const line, intvec &n) 1881 { 1882 mpz_t denom[this->numVars]; 1829 }//void noRevS(gcone &gc) 1830 1831 1832 /** \brief Make a set of rational vectors into integers 1833 * 1834 * We compute the lcm of the denominators and multiply with this to get integer values. 1835 * \param dd_MatrixPtr,intvec 1836 */ 1837 void gcone::makeInt(dd_MatrixPtr const &M, int const line, intvec &n) 1838 { 1839 mpz_t denom[this->numVars]; 1840 for(int ii=0;ii<this->numVars;ii++) 1841 { 1842 mpz_init_set_str(denom[ii],"0",10); 1843 } 1844 1845 mpz_t kgV,tmp; 1846 mpz_init(kgV); 1847 mpz_init(tmp); 1848 1849 for (int ii=0;ii<(M->colsize)-1;ii++) 1850 { 1851 mpz_t z; 1852 mpz_init(z); 1853 mpq_get_den(z,M->matrix[line-1][ii+1]); 1854 mpz_set( denom[ii], z); 1855 mpz_clear(z); 1856 } 1857 1858 /*Compute lcm of the denominators*/ 1859 mpz_set(tmp,denom[0]); 1860 for (int ii=0;ii<(M->colsize)-1;ii++) 1861 { 1862 mpz_lcm(kgV,tmp,denom[ii]); 1863 mpz_set(tmp,kgV); 1864 } 1865 1866 /*Multiply the nominators by kgV*/ 1867 mpq_t qkgV,res; 1868 mpq_init(qkgV); 1869 mpq_set_str(qkgV,"1",10); 1870 mpq_canonicalize(qkgV); 1871 1872 mpq_init(res); 1873 mpq_set_str(res,"1",10); 1874 mpq_canonicalize(res); 1875 1876 mpq_set_num(qkgV,kgV); 1877 1878 // mpq_canonicalize(qkgV); 1879 for (int ii=0;ii<(M->colsize)-1;ii++) 1880 { 1881 mpq_mul(res,qkgV,M->matrix[line-1][ii+1]); 1882 n[ii]=(int)mpz_get_d(mpq_numref(res)); 1883 } 1884 //mpz_clear(denom[this->numVars]); 1885 mpz_clear(kgV); 1886 mpq_clear(qkgV); mpq_clear(res); 1887 1888 } 1889 /** 1890 * For all codim-2-facets we compute the gcd of the components of the facet normal and 1891 * divide it out. Thus we get a normalized representation of each 1892 * (codim-2)-facet normal, i.e. a primitive vector 1893 */ 1894 void gcone::normalize() 1895 { 1896 int ggT=1; 1897 facet *fAct; 1898 facet *codim2Act; 1899 fAct = this->facetPtr; 1900 codim2Act = fAct->codim2Ptr; 1901 intvec *n = new intvec(this->numVars); 1902 1903 //while(codim2Act->next!=NULL) 1904 while(fAct!=NULL) 1905 { 1906 while(codim2Act!=NULL) 1907 { 1908 n=codim2Act->getFacetNormal(); 1883 1909 for(int ii=0;ii<this->numVars;ii++) 1884 1910 { 1885 mpz_init_set_str(denom[ii],"0",10); 1886 } 1887 1888 mpz_t kgV,tmp; 1889 mpz_init(kgV); 1890 mpz_init(tmp); 1891 1892 for (int ii=0;ii<(M->colsize)-1;ii++) 1893 { 1894 mpz_t z; 1895 mpz_init(z); 1896 mpq_get_den(z,M->matrix[line-1][ii+1]); 1897 mpz_set( denom[ii], z); 1898 mpz_clear(z); 1899 } 1900 1901 /*Compute lcm of the denominators*/ 1902 mpz_set(tmp,denom[0]); 1903 for (int ii=0;ii<(M->colsize)-1;ii++) 1904 { 1905 mpz_lcm(kgV,tmp,denom[ii]); 1906 mpz_set(tmp,kgV); 1907 } 1908 1909 /*Multiply the nominators by kgV*/ 1910 mpq_t qkgV,res; 1911 mpq_init(qkgV); 1912 mpq_set_str(qkgV,"1",10); 1913 mpq_canonicalize(qkgV); 1914 1915 mpq_init(res); 1916 mpq_set_str(res,"1",10); 1917 mpq_canonicalize(res); 1918 1919 mpq_set_num(qkgV,kgV); 1920 1921 // mpq_canonicalize(qkgV); 1922 for (int ii=0;ii<(M->colsize)-1;ii++) 1923 { 1924 mpq_mul(res,qkgV,M->matrix[line-1][ii+1]); 1925 n[ii]=(int)mpz_get_d(mpq_numref(res)); 1926 } 1927 //mpz_clear(denom[this->numVars]); 1928 mpz_clear(kgV); 1929 mpq_clear(qkgV); mpq_clear(res); 1930 1911 ggT = intgcd(ggT,(*n)[ii]); 1912 } 1913 for(int ii=0;ii<this->numVars;ii++) 1914 { 1915 (*n)[ii] = ((*n)[ii])/ggT; 1916 } 1917 codim2Act->setFacetNormal(n); 1918 codim2Act = codim2Act->next; 1931 1919 } 1932 /** 1933 * For all codim-2-facets we compute the gcd of the components of the facet normal and 1934 * divide it out. Thus we get a normalized representation of each 1935 * (codim-2)-facet normal, i.e. a primitive vector 1936 */ 1937 void normalize() 1938 { 1939 int ggT=1; 1940 facet *fAct; 1941 facet *codim2Act; 1942 fAct = this->facetPtr; 1943 codim2Act = fAct->codim2Ptr; 1944 intvec *n = new intvec(this->numVars); 1945 1946 //while(codim2Act->next!=NULL) 1947 while(fAct!=NULL) 1948 { 1949 while(codim2Act!=NULL) 1950 { 1951 n=codim2Act->getFacetNormal(); 1952 for(int ii=0;ii<this->numVars;ii++) 1953 { 1954 ggT = intgcd(ggT,(*n)[ii]); 1955 } 1956 for(int ii=0;ii<this->numVars;ii++) 1957 { 1958 (*n)[ii] = ((*n)[ii])/ggT; 1959 } 1960 codim2Act->setFacetNormal(n); 1961 codim2Act = codim2Act->next; 1962 } 1963 fAct = fAct->next; 1964 } 1920 fAct = fAct->next; 1921 } 1965 1922 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1923 } 1924 /** \brief Enqueue new facets into the searchlist 1925 * The searchlist (SLA for short) is implemented as a FIFO 1926 * Checks are done as follows: 1927 * 1) Check facet fAct against all facets in SLA for parallelity. If it is not parallel to any one add it. 1928 * 2) If it is parallel compare the codim2 facets. If they coincide the facets are equal and we delete the 1929 * facet from SLA and do not add fAct. 1930 * It may very well happen, that SLA=\f$ \emptyset \f$ but we do not have checked all fActs yet. In this case we 1931 * can be sure, that none of the facets that are still there already were in SLA once, so we just dump them into SLA. 1932 * Takes ptr to search list root 1933 * Returns a pointer to new first element of Searchlist 1934 */ 1978 1935 //void enqueueNewFacets(facet &f) 1979 facet *enqueueNewFacets(facet &f)1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 1936 facet * gcone::enqueueNewFacets(facet &f) 1937 { 1938 facet *slHead; 1939 slHead = &f; 1940 facet *slAct; //called with f=SearchListRoot 1941 slAct = &f; 1942 facet *slEnd; //Pointer to end of SLA 1943 slEnd = &f; 1944 facet *slEndStatic; //marks the end before a new facet is added 1945 facet *fAct; 1946 fAct = this->facetPtr; 1947 facet *codim2Act; 1948 codim2Act = this->facetPtr->codim2Ptr; 1949 facet *sl2Act; 1950 sl2Act = f.codim2Ptr; 1951 /** Pointer to a facet that will be deleted */ 1952 facet *deleteMarker; 1953 deleteMarker = NULL; 1954 1955 /** Flag to indicate a facet that should be added to SLA*/ 1956 bool doNotAdd=FALSE; 1957 /** \brief Flag to mark a facet that might be added 1958 * The following case may occur: 1959 * A facet fAct is found to be parallel but not equal to the current facet slAct from SLA. 1960 * This does however not mean that there does not exist a facet behind the current slAct that is actually equal 1961 * to fAct. In this case we set the boolean flag maybe to TRUE. If we encounter an equality lateron, it is reset to 1962 * FALSE and the according slAct is deleted. 1963 * If slAct->next==NULL AND maybe==TRUE we know, that fAct must be added 1964 */ 1965 volatile bool maybe=FALSE; 1966 /**A facet was removed, lengthOfSearchlist-- thus we must not rely on 1967 * if(notParallelCtr==lengthOfSearchList) but rather 1968 * if( (notParallelCtr==lengthOfSearchList && removalOccured==FALSE) 1969 */ 1970 volatile bool removalOccured=FALSE; 1971 int ctr=0; //encountered equalities in SLA 1972 int notParallelCtr=0; 1973 int lengthOfSearchList=1; 1974 while(slEnd->next!=NULL) 1975 { 1976 slEnd=slEnd->next; 1977 lengthOfSearchList++; 1978 } 1979 slEndStatic = slEnd; 1980 /*1st step: compare facetNormals*/ 1981 intvec *fNormal=NULL; //= new intvec(this->numVars); 1982 intvec *f2Normal=NULL; //= new intvec(this->numVars); 1983 intvec *slNormal=NULL; //= new intvec(this->numVars); 1984 intvec *sl2Normal=NULL; //= new intvec(this->numVars); 1985 1986 while(fAct!=NULL) 1987 { 1988 if(fAct->isFlippable==TRUE) 1989 { 1990 maybe=FALSE; 1991 doNotAdd=TRUE; 1992 fNormal=fAct->getFacetNormal(); 1993 slAct = slHead; 1994 notParallelCtr=0; 2038 1995 // delete deleteMarker; 2039 1996 // deleteMarker=NULL; 2040 1997 /*If slAct==NULL and fAct!=NULL 2041 we just copy all remaining facets into SLA*/ 1998 we just copy all remaining facets into SLA*/ 1999 if(slAct==NULL) 2000 { 2001 facet *fCopy; 2002 fCopy = fAct; 2003 while(fCopy!=NULL) 2004 { 2042 2005 if(slAct==NULL) 2043 2006 { 2044 facet *fCopy; 2045 fCopy = fAct; 2046 while(fCopy!=NULL) 2007 slAct = new facet(); 2008 slHead = slAct; 2009 } 2010 else 2011 { 2012 slAct->next = new facet(); 2013 slAct = slAct->next; 2014 } 2015 slAct->setFacetNormal(fAct->getFacetNormal()); 2016 slAct->setUCN(fAct->getUCN()); 2017 slAct->isFlippable=fAct->isFlippable; 2018 facet *f2Copy; 2019 f2Copy = fCopy->codim2Ptr; 2020 sl2Act = slAct->codim2Ptr; 2021 while(f2Copy!=NULL) 2022 { 2023 if(sl2Act==NULL) 2047 2024 { 2048 if(slAct==NULL) 2049 { 2050 slAct = new facet(); 2051 slHead = slAct; 2052 } 2053 else 2054 { 2055 slAct->next = new facet(); 2056 slAct = slAct->next; 2057 } 2058 slAct->setFacetNormal(fAct->getFacetNormal()); 2059 slAct->setUCN(fAct->getUCN()); 2060 slAct->isFlippable=fAct->isFlippable; 2061 facet *f2Copy; 2062 f2Copy = fCopy->codim2Ptr; 2063 sl2Act = slAct->codim2Ptr; 2064 while(f2Copy!=NULL) 2065 { 2066 if(sl2Act==NULL) 2067 { 2068 sl2Act = new facet(2); 2069 slAct->codim2Ptr = sl2Act; 2070 } 2071 else 2072 { 2073 facet *marker; 2074 marker = sl2Act; 2075 sl2Act->next = new facet(2); 2076 sl2Act = sl2Act->next; 2077 sl2Act->prev = marker; 2078 } 2079 sl2Act->setFacetNormal(f2Copy->getFacetNormal()); 2080 sl2Act->setUCN(f2Copy->getUCN()); 2081 f2Copy = f2Copy->next; 2082 } 2083 fCopy = fCopy->next; 2025 sl2Act = new facet(2); 2026 slAct->codim2Ptr = sl2Act; 2084 2027 } 2085 break; 2028 else 2029 { 2030 facet *marker; 2031 marker = sl2Act; 2032 sl2Act->next = new facet(2); 2033 sl2Act = sl2Act->next; 2034 sl2Act->prev = marker; 2035 } 2036 sl2Act->setFacetNormal(f2Copy->getFacetNormal()); 2037 sl2Act->setUCN(f2Copy->getUCN()); 2038 f2Copy = f2Copy->next; 2086 2039 } 2087 /*End of */ 2088 while(slAct!=NULL) 2040 fCopy = fCopy->next; 2041 } 2042 break; 2043 } 2044 /*End of */ 2045 while(slAct!=NULL) 2089 2046 //while(slAct!=slEndStatic->next) 2090 2047 { 2091 2048 // if(deleteMarker!=NULL) 2092 2049 // { … … 2094 2051 // deleteMarker=NULL; 2095 2052 // } 2096 removalOccured=FALSE; 2097 slNormal = slAct->getFacetNormal(); 2098 #ifdef gfan_DEBUG 2099 cout << "Checking facet ("; 2100 fNormal->show(1,1); 2101 cout << ") against ("; 2102 slNormal->show(1,1); 2103 cout << ")" << endl; 2104 #endif 2105 if(!isParallel(fNormal, slNormal)) 2053 removalOccured=FALSE; 2054 slNormal = slAct->getFacetNormal(); 2055 #ifdef gfan_DEBUG 2056 cout << "Checking facet ("; 2057 fNormal->show(1,1); 2058 cout << ") against ("; 2059 slNormal->show(1,1); 2060 cout << ")" << endl; 2061 #endif 2062 if(!isParallel(fNormal, slNormal)) 2063 { 2064 notParallelCtr++; 2065 // slAct = slAct->next; 2066 } 2067 else //fN and slN are parallel 2068 { 2069 //We check whether the codim-2-facets coincide 2070 codim2Act = fAct->codim2Ptr; 2071 ctr=0; 2072 while(codim2Act!=NULL) 2073 { 2074 f2Normal = codim2Act->getFacetNormal(); 2075 //sl2Act = f.codim2Ptr; 2076 sl2Act = slAct->codim2Ptr; 2077 while(sl2Act!=NULL) 2106 2078 { 2107 notParallelCtr++; 2108 // slAct = slAct->next; 2079 sl2Normal = sl2Act->getFacetNormal(); 2080 if(areEqual(f2Normal, sl2Normal)) 2081 ctr++; 2082 sl2Act = sl2Act->next; 2083 }//while(sl2Act!=NULL) 2084 codim2Act = codim2Act->next; 2085 }//while(codim2Act!=NULL) 2086 if(ctr==fAct->numCodim2Facets) //facets ARE equal 2087 { 2088 #ifdef gfan_DEBUG 2089 cout << "Removing facet ("; 2090 slNormal->show(1,0); 2091 cout << ") from SLA:" << endl; 2092 fAct->fDebugPrint(); 2093 slAct->fDebugPrint(); 2094 #endif 2095 removalOccured=TRUE; 2096 slAct->isFlippable=FALSE; 2097 doNotAdd=TRUE; 2098 maybe=FALSE; 2099 if(slAct==slHead) //We want to delete the first element of SearchList 2100 { 2101 deleteMarker = slHead; 2102 slHead = slAct->next; 2103 if(slHead!=NULL) 2104 slHead->prev = NULL; 2105 //set a bool flag to mark slAct as to be deleted 2106 }//NOTE find a way to delete without affecting slAct = slAct->next 2107 else if(slAct==slEndStatic) 2108 { 2109 deleteMarker = slAct; 2110 if(slEndStatic->next==NULL) 2111 { 2112 slEndStatic = slEndStatic->prev; 2113 slEndStatic->next = NULL; 2114 slEnd = slEndStatic; 2115 } 2116 else //we already added a facet after slEndStatic 2117 { 2118 slEndStatic->prev->next = slEndStatic->next; 2119 slEndStatic->next->prev = slEndStatic->prev; 2120 slEndStatic = slEndStatic->prev; 2121 //slEnd = slEndStatic; 2122 } 2123 } 2124 else 2125 { 2126 deleteMarker = slAct; 2127 slAct->prev->next = slAct->next; 2128 slAct->next->prev = slAct->prev; 2109 2129 } 2110 else //fN and slN are parallel2111 {2112 //We check whether the codim-2-facets coincide2113 codim2Act = fAct->codim2Ptr;2114 ctr=0;2115 while(codim2Act!=NULL)2116 {2117 f2Normal = codim2Act->getFacetNormal();2118 //sl2Act = f.codim2Ptr;2119 sl2Act = slAct->codim2Ptr;2120 while(sl2Act!=NULL)2121 {2122 sl2Normal = sl2Act->getFacetNormal();2123 if(areEqual(f2Normal, sl2Normal))2124 ctr++;2125 sl2Act = sl2Act->next;2126 }//while(sl2Act!=NULL)2127 codim2Act = codim2Act->next;2128 }//while(codim2Act!=NULL)2129 if(ctr==fAct->numCodim2Facets) //facets ARE equal2130 {2131 #ifdef gfan_DEBUG2132 cout << "Removing facet (";2133 slNormal->show(1,0);2134 cout << ") from SLA:" << endl;2135 fAct->fDebugPrint();2136 slAct->fDebugPrint();2137 #endif2138 removalOccured=TRUE;2139 slAct->isFlippable=FALSE;2140 doNotAdd=TRUE;2141 maybe=FALSE;2142 if(slAct==slHead) //We want to delete the first element of SearchList2143 {2144 deleteMarker = slHead;2145 slHead = slAct->next;2146 if(slHead!=NULL)2147 slHead->prev = NULL;2148 //set a bool flag to mark slAct as to be deleted2149 }//NOTE find a way to delete without affecting slAct = slAct->next2150 else if(slAct==slEndStatic)2151 {2152 deleteMarker = slAct;2153 if(slEndStatic->next==NULL)2154 {2155 slEndStatic = slEndStatic->prev;2156 slEndStatic->next = NULL;2157 slEnd = slEndStatic;2158 }2159 else //we already added a facet after slEndStatic2160 {2161 slEndStatic->prev->next = slEndStatic->next;2162 slEndStatic->next->prev = slEndStatic->prev;2163 slEndStatic = slEndStatic->prev;2164 //slEnd = slEndStatic;2165 }2166 }2167 else2168 {2169 deleteMarker = slAct;2170 slAct->prev->next = slAct->next;2171 slAct->next->prev = slAct->prev;2172 }2173 2130 2174 2131 //update lengthOfSearchList 2175 2132 lengthOfSearchList--; 2176 2133 //delete slAct; 2177 2134 //slAct=NULL; … … 2180 2137 //deleteMarker=NULL; 2181 2138 //fAct = fAct->next; 2182 2183 2184 2139 break; 2140 }//if(ctr==fAct->numCodim2Facets) 2141 else //facets are parallel but NOT equal. But this does not imply that there 2185 2142 //is no other facet later in SLA that might be equal. 2186 2187 2143 { 2144 maybe=TRUE; 2188 2145 // if(slAct->next==NULL && maybe==TRUE) 2189 2146 // { … … 2194 2151 // else 2195 2152 // slAct=slAct->next; 2196 2153 } 2197 2154 //slAct = slAct->next; 2198 2155 //delete deleteMarker; 2199 2200 2201 2202 2203 2204 2205 2156 }//if(!isParallel(fNormal, slNormal)) 2157 if( (slAct->next==NULL) && (maybe==TRUE) ) 2158 { 2159 doNotAdd=FALSE; 2160 break; 2161 } 2162 slAct = slAct->next; 2206 2163 /* NOTE The following lines must not be here but rather called inside the if-block above. 2207 2208 2164 Otherwise results get crappy. Unfortunately there are two slAct=slAct->next calls now, 2165 (not nice!) but since they are in seperate branches of the if-statement there should not 2209 2166 be a way it gets called twice thus ommiting one facet: 2210 2167 slAct = slAct->next;*/ 2211 2168 //delete deleteMarker; 2212 2169 //deleteMarker=NULL; 2213 2170 //if slAct was marked as to be deleted, delete it here! 2214 }//while(slAct!=NULL) 2215 if( (notParallelCtr==lengthOfSearchList && removalOccured==FALSE) || (doNotAdd==FALSE) ) 2216 //if( (notParallelCtr==lengthOfSearchList ) || doNotAdd==FALSE ) 2171 }//while(slAct!=NULL) 2172 if( (notParallelCtr==lengthOfSearchList && removalOccured==FALSE) || (doNotAdd==FALSE) ) 2173 //if( (notParallelCtr==lengthOfSearchList ) || doNotAdd==FALSE ) 2174 { 2175 #ifdef gfan_DEBUG 2176 cout << "Adding facet ("; 2177 fNormal->show(1,0); 2178 cout << ") to SLA " << endl; 2179 #endif 2180 //Add fAct to SLA 2181 facet *marker; 2182 marker = slEnd; 2183 facet *f2Act; 2184 f2Act = fAct->codim2Ptr; 2185 2186 slEnd->next = new facet(); 2187 slEnd = slEnd->next; 2188 facet *slEndCodim2Root; 2189 facet *slEndCodim2Act; 2190 slEndCodim2Root = slEnd->codim2Ptr; 2191 slEndCodim2Act = slEndCodim2Root; 2192 2193 slEnd->setUCN(this->getUCN()); 2194 slEnd->isFlippable = TRUE; 2195 slEnd->setFacetNormal(fNormal); 2196 slEnd->prev = marker; 2197 //Copy codim2-facets 2198 intvec *f2Normal;// = new intvec(this->numVars); 2199 while(f2Act!=NULL) 2200 { 2201 f2Normal=f2Act->getFacetNormal(); 2202 if(slEndCodim2Root==NULL) 2217 2203 { 2218 #ifdef gfan_DEBUG 2219 cout << "Adding facet ("; 2220 fNormal->show(1,0); 2221 cout << ") to SLA " << endl; 2222 #endif 2223 //Add fAct to SLA 2224 facet *marker; 2225 marker = slEnd; 2226 facet *f2Act; 2227 f2Act = fAct->codim2Ptr; 2228 2229 slEnd->next = new facet(); 2230 slEnd = slEnd->next; 2231 facet *slEndCodim2Root; 2232 facet *slEndCodim2Act; 2233 slEndCodim2Root = slEnd->codim2Ptr; 2204 slEndCodim2Root = new facet(2); 2205 slEnd->codim2Ptr = slEndCodim2Root; 2206 slEndCodim2Root->setFacetNormal(f2Normal); 2234 2207 slEndCodim2Act = slEndCodim2Root; 2235 2236 slEnd->setUCN(this->getUCN()); 2237 slEnd->isFlippable = TRUE; 2238 slEnd->setFacetNormal(fNormal); 2239 slEnd->prev = marker; 2240 //Copy codim2-facets 2241 intvec *f2Normal;// = new intvec(this->numVars); 2242 while(f2Act!=NULL) 2243 { 2244 f2Normal=f2Act->getFacetNormal(); 2245 if(slEndCodim2Root==NULL) 2246 { 2247 slEndCodim2Root = new facet(2); 2248 slEnd->codim2Ptr = slEndCodim2Root; 2249 slEndCodim2Root->setFacetNormal(f2Normal); 2250 slEndCodim2Act = slEndCodim2Root; 2251 } 2252 else 2253 { 2254 slEndCodim2Act->next = new facet(2); 2255 slEndCodim2Act = slEndCodim2Act->next; 2256 slEndCodim2Act->setFacetNormal(f2Normal); 2257 } 2258 f2Act = f2Act->next; 2259 } 2260 lengthOfSearchList++; 2208 } 2209 else 2210 { 2211 slEndCodim2Act->next = new facet(2); 2212 slEndCodim2Act = slEndCodim2Act->next; 2213 slEndCodim2Act->setFacetNormal(f2Normal); 2214 } 2215 f2Act = f2Act->next; 2216 } 2217 lengthOfSearchList++; 2261 2218 //delete f2Normal; 2262 2263 2264 2265 2266 2267 2268 2269 2270 2219 }//if( (notParallelCtr==lengthOfSearchList && removalOccured==FALSE) || 2220 fAct = fAct->next; 2221 }//if(fAct->isFlippable==TRUE) 2222 else 2223 { 2224 fAct = fAct->next; 2225 } 2226 }//while(fAct!=NULL) 2227 return slHead; 2271 2228 // delete sl2Normal; 2272 2229 // delete slNormal; 2273 2230 // delete f2Normal; 2274 2231 // delete fNormal; 2275 2276 2277 2278 2279 intintgcd(int a, int b)2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 dd_MatrixPtrfacets2Matrix(gcone const &gc)2299 2300 2301 2232 }//addC2N 2233 2234 /** \brief Compute the gcd of two ints 2235 */ 2236 int gcone::intgcd(int a, int b) 2237 { 2238 int r, p=a, q=b; 2239 if(p < 0) 2240 p = -p; 2241 if(q < 0) 2242 q = -q; 2243 while(q != 0) 2244 { 2245 r = p % q; 2246 p = q; 2247 q = r; 2248 } 2249 return p; 2250 } 2251 2252 /** \brief Construct a dd_MatrixPtr from a cone's list of facets 2253 * 2254 */ 2255 dd_MatrixPtr gcone::facets2Matrix(gcone const &gc) 2256 { 2257 facet *fAct; 2258 fAct = gc.facetPtr; 2302 2259 2303 2304 2305 2306 2307 2308 2309 2310 2311 2260 dd_MatrixPtr M; 2261 dd_rowrange ddrows; 2262 dd_colrange ddcols; 2263 ddcols=(this->numVars)+1; 2264 ddrows=this->numFacets; 2265 dd_NumberType numb = dd_Integer; 2266 M=dd_CreateMatrix(ddrows,ddcols); 2267 2268 int jj=0; 2312 2269 //while(fAct->next!=NULL) 2313 while(fAct!=NULL) 2314 { 2315 intvec *comp; 2316 comp = fAct->getFacetNormal(); 2317 for(int ii=0;ii<this->numVars;ii++) 2318 { 2319 dd_set_si(M->matrix[jj][ii+1],(*comp)[ii]); 2320 } 2321 jj++; 2322 fAct=fAct->next; 2323 } 2324 2325 return M; 2270 while(fAct!=NULL) 2271 { 2272 intvec *comp; 2273 comp = fAct->getFacetNormal(); 2274 for(int ii=0;ii<this->numVars;ii++) 2275 { 2276 dd_set_si(M->matrix[jj][ii+1],(*comp)[ii]); 2326 2277 } 2327 2328 /** \brief Write information about a cone into a file on disk 2329 * 2330 * This methods writes the information needed for the "second" method into a file. 2331 * The file's is divided in sections containing information on 2332 * 1) the ring 2333 * 2) the cone's Groebner Basis 2334 * 3) the cone's facets 2335 * Each line contains exactly one date 2336 * Each section starts with its name in CAPITALS 2337 */ 2338 void writeConeToFile(gcone const &gc, bool usingIntPoints=FALSE) 2339 { 2340 int UCN=gc.UCN; 2341 stringstream ss; 2342 ss << UCN; 2343 string UCNstr = ss.str(); 2344 2345 char prefix[]="/tmp/cone"; 2346 char *UCNstring; 2347 strcpy(UCNstring,UCNstr.c_str()); 2348 char suffix[]=".sg"; 2349 char *filename=strcat(prefix,UCNstring); 2350 strcat(filename,suffix); 2278 jj++; 2279 fAct=fAct->next; 2280 } 2281 2282 return M; 2283 } 2284 2285 /** \brief Write information about a cone into a file on disk 2286 * 2287 * This methods writes the information needed for the "second" method into a file. 2288 * The file's is divided in sections containing information on 2289 * 1) the ring 2290 * 2) the cone's Groebner Basis 2291 * 3) the cone's facets 2292 * Each line contains exactly one date 2293 * Each section starts with its name in CAPITALS 2294 */ 2295 void gcone::writeConeToFile(gcone const &gc, bool usingIntPoints) 2296 { 2297 int UCN=gc.UCN; 2298 stringstream ss; 2299 ss << UCN; 2300 string UCNstr = ss.str(); 2301 2302 char prefix[]="/tmp/cone"; 2303 char *UCNstring; 2304 strcpy(UCNstring,UCNstr.c_str()); 2305 char suffix[]=".sg"; 2306 char *filename=strcat(prefix,UCNstring); 2307 strcat(filename,suffix); 2351 2308 2352 ofstream gcOutputFile(filename); 2353 facet *fAct = new facet(); //NOTE Why new? 2354 fAct = gc.facetPtr; 2355 2356 char *ringString = rString(currRing); 2357 2358 if (!gcOutputFile) 2359 { 2360 cout << "Error opening file for writing in writeConeToFile" << endl; 2309 ofstream gcOutputFile(filename); 2310 facet *fAct = new facet(); //NOTE Why new? 2311 fAct = gc.facetPtr; 2312 2313 char *ringString = rString(currRing); 2314 2315 if (!gcOutputFile) 2316 { 2317 cout << "Error opening file for writing in writeConeToFile" << endl; 2318 } 2319 else 2320 { gcOutputFile << "UCN" << endl; 2321 gcOutputFile << this->UCN << endl; 2322 gcOutputFile << "RING" << endl; 2323 gcOutputFile << ringString << endl; 2324 //Write this->gcBasis into file 2325 gcOutputFile << "GCBASIS" << endl; 2326 for (int ii=0;ii<IDELEMS(gc.gcBasis);ii++) 2327 { 2328 gcOutputFile << p_String((poly)gc.gcBasis->m[ii],gc.baseRing) << endl; 2329 } 2330 2331 gcOutputFile << "FACETS" << endl; 2332 //while(fAct->next!=NULL) 2333 while(fAct!=NULL) 2334 { 2335 intvec *iv = new intvec(gc.numVars); 2336 iv=fAct->getFacetNormal(); 2337 for (int ii=0;ii<iv->length();ii++) 2338 { 2339 if (ii<iv->length()-1) 2340 { 2341 gcOutputFile << (*iv)[ii] << ","; 2361 2342 } 2362 2343 else 2363 { gcOutputFile << "UCN" << endl; 2364 gcOutputFile << this->UCN << endl; 2365 gcOutputFile << "RING" << endl; 2366 gcOutputFile << ringString << endl; 2367 //Write this->gcBasis into file 2368 gcOutputFile << "GCBASIS" << endl; 2369 for (int ii=0;ii<IDELEMS(gc.gcBasis);ii++) 2370 { 2371 gcOutputFile << p_String((poly)gc.gcBasis->m[ii],gc.baseRing) << endl; 2372 } 2344 { 2345 gcOutputFile << (*iv)[ii] << endl; 2346 } 2347 } 2348 fAct=fAct->next; 2349 //delete iv; iv=NULL; 2350 } 2373 2351 2374 gcOutputFile << "FACETS" << endl; 2375 //while(fAct->next!=NULL) 2376 while(fAct!=NULL) 2377 { 2378 intvec *iv = new intvec(gc.numVars); 2379 iv=fAct->getFacetNormal(); 2380 for (int ii=0;ii<iv->length();ii++) 2381 { 2382 if (ii<iv->length()-1) 2383 { 2384 gcOutputFile << (*iv)[ii] << ","; 2385 } 2386 else 2387 { 2388 gcOutputFile << (*iv)[ii] << endl; 2389 } 2390 } 2391 fAct=fAct->next; 2392 //delete iv; iv=NULL; 2393 } 2394 2395 gcOutputFile.close(); 2352 gcOutputFile.close(); 2396 2353 //delete fAct; fAct=NULL; 2397 } 2398 2399 }//writeConeToFile(gcone const &gc) 2400 2401 /** \brief Reads a cone from a file identified by its number 2402 */ 2403 void readConeFromFile(int gcNum) 2404 { 2405 } 2406 2407 friend class facet; 2408 };//class gcone 2354 } 2355 2356 }//writeConeToFile(gcone const &gc) 2357 2358 /** \brief Reads a cone from a file identified by its number 2359 */ 2360 void gcone::readConeFromFile(int gcNum) 2361 { 2362 } 2363 2409 2364 2410 2365 int gcone::counter=0;
Note: See TracChangeset
for help on using the changeset viewer.