Changeset a7d970 in git for kernel/tgb_internal.h
 Timestamp:
 Feb 22, 2007, 11:45:12 AM (16 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')
 Children:
 ebe987f7339e431a23e717106ffe22dacf14a1a2
 Parents:
 490afd567a4f8c21b1a8b7bff89f26c3053d6a38
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

kernel/tgb_internal.h
r490afd5 ra7d970 5 5 * Computer Algebra System SINGULAR * 6 6 ****************************************/ 7 /* $Id: tgb_internal.h,v 1.5 5 20070220 15:11:04bricken Exp $ */7 /* $Id: tgb_internal.h,v 1.56 20070222 10:45:00 bricken Exp $ */ 8 8 /* 9 9 * ABSTRACT: tgb internal .h file … … 18 18 #include "polys.h" 19 19 #include "stdlib.h" 20 #include <modulop.h> 20 21 //#define USE_NORO 1 21 //#define NORO_CACHE 1 22 //#define NORO_SPARSE_ROWS_PRE 1 23 //#define NORO_NON_POLY 1 22 #ifdef USE_NORO 23 #define NORO_CACHE 1 24 #define NORO_SPARSE_ROWS_PRE 1 25 #define NORO_NON_POLY 1 26 #endif 24 27 #ifdef NORO_CACHE 25 28 //#include <map> … … 388 391 389 392 } 390 391 393 #ifdef NORO_CACHE 394 typedef unsigned short tgb_uint16; 395 typedef unsigned char tgb_uint8; 396 typedef unsigned int tgb_uint32; 397 class NoroCacheNode{ 398 public: 399 NoroCacheNode** branches; 400 int branches_len; 401 402 403 NoroCacheNode(){ 404 branches=NULL; 405 branches_len=0; 406 407 } 408 NoroCacheNode* setNode(int branch, NoroCacheNode* node){ 409 if (branch>=branches_len){ 410 if (branches==NULL){ 411 branches_len=branch+1; 412 branches_len=si_max(branches_len,3); 413 branches=(NoroCacheNode**) omalloc(branches_len*sizeof(NoroCacheNode*)); 414 int i; 415 for(i=0;i<branches_len;i++){ 416 branches[i]=NULL; 417 } 418 }else{ 419 int branches_len_old=branches_len; 420 branches_len=branch+1; 421 branches=(NoroCacheNode**) omrealloc(branches,branches_len*sizeof(NoroCacheNode*)); 422 int i; 423 for(i=branches_len_old;i<branches_len;i++){ 424 branches[i]=NULL; 425 } 426 } 427 } 428 assume(branches[branch]==NULL); 429 branches[branch]=node; 430 return node; 431 } 432 NoroCacheNode* getBranch(int branch){ 433 if (branch<branches_len) return branches[branch]; 434 return NULL; 435 } 436 virtual ~NoroCacheNode(){ 437 int i; 438 for(i=0;i<branches_len;i++){ 439 delete branches[i]; 440 } 441 omfree(branches); 442 } 443 NoroCacheNode* getOrInsertBranch(int branch){ 444 if ((branch<branches_len)&&(branches[branch])) 445 return branches[branch]; 446 else{ 447 return setNode(branch,new NoroCacheNode()); 448 } 449 } 450 }; 451 class DenseRow{ 452 public: 453 number* array; 454 int begin; 455 int end; 456 DenseRow(){ 457 array=NULL; 458 } 459 ~DenseRow(){ 460 omfree(array); 461 } 462 }; 463 class SparseRow{ 464 public: 465 int* idx_array; 466 number* coef_array; 467 int len; 468 SparseRow(){ 469 len=0; 470 idx_array=NULL; 471 coef_array=NULL; 472 } 473 SparseRow(int n){ 474 len=n; 475 idx_array=(int*) omalloc(n*sizeof(int)); 476 coef_array=(number*) omalloc(n*sizeof(number)); 477 } 478 ~SparseRow(){ 479 omfree(idx_array); 480 omfree(coef_array); 481 } 482 }; 483 484 class DataNoroCacheNode:public NoroCacheNode{ 485 public: 486 487 int value_len; 488 poly value_poly; 489 #ifdef NORO_SPARSE_ROWS_PRE 490 SparseRow* row; 491 #else 492 DenseRow* row; 493 #endif 494 int term_index; 495 DataNoroCacheNode(poly p, int len){ 496 value_len=len; 497 value_poly=p; 498 row=NULL; 499 term_index=1; 500 } 501 #ifdef NORO_SPARSE_ROWS_PRE 502 DataNoroCacheNode(SparseRow* row){ 503 if (row!=NULL) 504 value_len=row>len; 505 else 506 value_len=0; 507 value_poly=NULL; 508 this>row=row; 509 term_index=1; 510 } 511 #endif 512 ~DataNoroCacheNode( 513 ){ 514 //p_Delete(&value_poly,currRing); 515 if (row) delete row; 516 } 517 }; 518 class NoroCache{ 519 public: 520 poly temp_term; 521 void evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders); 522 void collectIrreducibleMonomials( std::vector<DataNoroCacheNode*>& res); 523 void collectIrreducibleMonomials(int level, NoroCacheNode* node, std::vector<DataNoroCacheNode*>& res); 524 void evaluateRows(); 525 void evaluateRows(int level, NoroCacheNode* node); 526 #ifdef NORO_RED_ARRAY_RESERVER 527 int reserved; 528 poly* recursionPolyBuffer; 529 #endif 530 static const int backLinkCode=222; 531 DataNoroCacheNode* insert(poly term, poly nf, int len){ 532 //assume(impl.find(p_Copy(term,currRing))==impl.end()); 533 //assume(len==pLength(nf)); 534 assume(npIsOne(p_GetCoeff(term,currRing))); 535 if (term==nf){ 536 term=p_Copy(term,currRing); 537 538 ressources.push_back(term); 539 nIrreducibleMonomials++; 540 return treeInsertBackLink(term); 541 542 } else{ 543 544 if (nf){ 545 //nf=p_Copy(nf,currRing); 546 assume(p_LmCmp(nf,term,currRing)==1); 547 ressources.push_back(nf); 548 } 549 return treeInsert(term,nf,len); 550 551 } 552 553 //impl[term]=std::pair<PolySimple,int> (nf,len); 554 } 555 #ifdef NORO_SPARSE_ROWS_PRE 556 DataNoroCacheNode* insert(poly term, SparseRow* srow){ 557 //assume(impl.find(p_Copy(term,currRing))==impl.end()); 558 //assume(len==pLength(nf)); 559 560 return treeInsert(term,srow); 561 562 563 //impl[term]=std::pair<PolySimple,int> (nf,len); 564 } 565 #endif 566 DataNoroCacheNode* insertAndTransferOwnerShip(poly t, ring r){ 567 568 ressources.push_back(t); 569 DataNoroCacheNode* res=treeInsertBackLink(t); 570 res>term_index=nIrreducibleMonomials; 571 nIrreducibleMonomials++; 572 return res; 573 } 574 poly lookup(poly term, BOOLEAN& succ, int & len); 575 DataNoroCacheNode* getCacheReference(poly term); 576 NoroCache(){ 577 buffer=NULL; 578 #ifdef NORO_RED_ARRAY_RESERVER 579 reserved=0; 580 recursionPolyBuffer=(poly*)omalloc(1000000*sizeof(poly)); 581 #endif 582 nIrreducibleMonomials=0; 583 nReducibleMonomials=0; 584 temp_term=pOne(); 585 } 586 #ifdef NORO_RED_ARRAY_RESERVER 587 poly* reserve(int n){ 588 poly* res=recursionPolyBuffer+reserved; 589 reserved+=n; 590 return res; 591 } 592 void free(int n){ 593 reserved=n; 594 } 595 #endif 596 ~NoroCache(){ 597 int s=ressources.size(); 598 int i; 599 for(i=0;i<s;i++){ 600 p_Delete(&ressources[i].impl,currRing); 601 } 602 p_Delete(&temp_term,currRing); 603 #ifdef NORO_RED_ARRAY_RESERVER 604 omfree(recursionPolyBuffer); 605 #endif 606 } 607 608 int nIrreducibleMonomials; 609 int nReducibleMonomials; 610 protected: 611 DataNoroCacheNode* treeInsert(poly term,poly nf,int len){ 612 int i; 613 nReducibleMonomials++; 614 int nvars=pVariables; 615 NoroCacheNode* parent=&root; 616 for(i=1;i<nvars;i++){ 617 parent=parent>getOrInsertBranch(p_GetExp(term,i,currRing)); 618 } 619 return (DataNoroCacheNode*) parent>setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(nf,len)); 620 } 621 #ifdef NORO_SPARSE_ROWS_PRE 622 DataNoroCacheNode* treeInsert(poly term,SparseRow* srow){ 623 int i; 624 nReducibleMonomials++; 625 int nvars=pVariables; 626 NoroCacheNode* parent=&root; 627 for(i=1;i<nvars;i++){ 628 parent=parent>getOrInsertBranch(p_GetExp(term,i,currRing)); 629 } 630 return (DataNoroCacheNode*) parent>setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(srow)); 631 } 632 #endif 633 DataNoroCacheNode* treeInsertBackLink(poly term){ 634 int i; 635 int nvars=pVariables; 636 NoroCacheNode* parent=&root; 637 for(i=1;i<nvars;i++){ 638 parent=parent>getOrInsertBranch(p_GetExp(term,i,currRing)); 639 } 640 return (DataNoroCacheNode*) parent>setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(term,backLinkCode)); 641 } 642 643 //@TODO descruct nodes; 644 typedef std::vector<PolySimple> poly_vec; 645 poly_vec ressources; 646 //typedef std::map<PolySimple,std::pair<PolySimple,int> > cache_map; 647 //cache_map impl; 648 NoroCacheNode root; 649 number* buffer; 650 }; 651 MonRedResNP noro_red_mon_to_non_poly(poly t, NoroCache* cache,slimgb_alg* c); 652 template<class storage_type> SparseRow* noro_red_to_non_poly_t(poly p, int &len, NoroCache* cache,slimgb_alg* c){ 653 assume(len==pLength(p)); 654 poly orig_p=p; 655 if (p==NULL) { 656 len=0; 657 return NULL; 658 } 659 660 number zero=npInit(0); 661 MonRedResNP* mon=(MonRedResNP*) omalloc(len*sizeof(MonRedResNP)); 662 int i=0; 663 664 while(p){ 665 666 poly t=p; 667 pIter(p); 668 pNext(t)=NULL; 669 670 #ifndef NDEBUG 671 number coef_debug=p_GetCoeff(t,currRing); 672 #endif 673 MonRedResNP red=noro_red_mon_to_non_poly(t,cache,c); 674 mon[i]=red; 675 i++; 676 } 677 678 assume(i==len); 679 len=i; 680 //in the loop before nIrreducibleMonomials increases, so position here is important 681 storage_type* temp_array=(storage_type*) omalloc(cache>nIrreducibleMonomials*sizeof(storage_type)); 682 int temp_size=cache>nIrreducibleMonomials; 683 memset(temp_array,0,sizeof(storage_type)*cache>nIrreducibleMonomials); 684 for(i=0;i<len;i++){ 685 MonRedResNP red=mon[i]; 686 if ((red.ref)){ 687 if (red.ref>row){ 688 SparseRow* row=red.ref>row; 689 number coef=red.coef; 690 int j; 691 if (!(npIsOne(coef))){ 692 for(j=0;j<row>len;j++){ 693 int idx=row>idx_array[j]; 694 assume(!(npIsZero(coef))); 695 assume(!(npIsZero(row>coef_array[j]))); 696 temp_array[idx]=(storage_type) (unsigned int) npAddM((number) temp_array[idx],npMultM(row>coef_array[j],coef)); 697 assume(idx<temp_size); 698 }}else{ 699 for(j=0;j<row>len;j++){ 700 int idx=row>idx_array[j]; 701 temp_array[idx]=(storage_type) (unsigned int) npAddM((number) temp_array[idx],row>coef_array[j]); 702 assume(idx<temp_size); 703 } 704 } 705 } 706 else{ 707 if (red.ref>value_len==NoroCache::backLinkCode){ 708 temp_array[red.ref>term_index]=(storage_type) (unsigned int) npAddM((number) temp_array[red.ref>term_index],red.coef); 709 } else { 710 //PrintS("third case\n"); 711 } 712 } 713 } 714 } 715 int non_zeros=0; 716 for(i=0;i<cache>nIrreducibleMonomials;i++){ 717 if (!(temp_array[i]==0)){ 718 non_zeros++; 719 } 720 } 721 SparseRow* res=new SparseRow(non_zeros); 722 int pos=0; 723 for(i=0;i<cache>nIrreducibleMonomials;i++){ 724 if (!(0==temp_array[i])){ 725 726 res>idx_array[pos]=i; 727 res>coef_array[pos]=(number) temp_array[i]; 728 729 pos++; 730 } 731 732 } 733 omfree(temp_array); 734 735 omfree(mon); 736 return res; 737 } 738 #endif 392 739 static wlen_type pair_weighted_length(int i, int j, slimgb_alg* c); 393 740 wlen_type pELength(poly p, ring r); 394 741 void simplest_gauss_modp(number* a, int nrows,int ncols); 742 395 743 // a: a[0,0],a[0,1]....a[nrows1,ncols1] 396 744 // assume: field is Zp
Note: See TracChangeset
for help on using the changeset viewer.