Changeset c7d29b in git for dyn_modules/syzextra/syzextra.cc
- Timestamp:
- Jul 23, 2012, 6:29:21 PM (12 years ago)
- Branches:
- (u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
- Children:
- c93fda01f3f4eb9609a2210ea9eec1816d8fb7f1
- Parents:
- 4eba3ad2d6dfbd57121d3a026b973301857fa069
- git-author:
- Oleksandr Motsak <motsak@mathematik.uni-kl.de>2012-07-23 18:29:21+02:00
- git-committer:
- Oleksandr Motsak <motsak@mathematik.uni-kl.de>2014-05-07 04:41:46+02:00
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
dyn_modules/syzextra/syzextra.cc
r4eba3ad rc7d29b 223 223 224 224 225 BEGIN_NAMESPACE(INTERNAL) 226 227 ideal _ComputeLeadingSyzygyTerms(const ideal& id, 228 const ring r, 229 const SchreyerSyzygyComputationFlags attributes) 230 { 231 // const BOOLEAN __DEBUG__ = attributes.__DEBUG__; 225 ideal SchreyerSyzygyComputation::Compute1LeadingSyzygyTerms() 226 { 227 const ideal& id = m_idLeads; 228 const ring& r = m_rBaseRing; 229 const SchreyerSyzygyComputationFlags& attributes = m_atttributes; 230 231 232 // const BOOLEAN __DEBUG__ = attributes.__DEBUG__; 232 233 // const BOOLEAN __SYZCHECK__ = attributes.__SYZCHECK__; 233 234 const BOOLEAN __LEAD2SYZ__ = attributes.__LEAD2SYZ__; 234 235 // const BOOLEAN __HYBRIDNF__ = attributes.__HYBRIDNF__; 235 236 // const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__; 236 237 237 238 assume(!__LEAD2SYZ__); 238 239 239 240 // 1. set of components S? … … 338 339 } 339 340 340 ideal _Compute2LeadingSyzygyTerms(const ideal& id, 341 const ring r, 342 const SchreyerSyzygyComputationFlags attributes) 343 { 341 ideal SchreyerSyzygyComputation::Compute2LeadingSyzygyTerms() 342 { 343 const ideal& id = m_idLeads; 344 const ring& r = m_rBaseRing; 345 const SchreyerSyzygyComputationFlags& attributes = m_atttributes; 346 344 347 // const BOOLEAN __DEBUG__ = attributes.__DEBUG__; 345 348 // const BOOLEAN __SYZCHECK__ = attributes.__SYZCHECK__; … … 486 489 } 487 490 488 poly _FindReducer(poly product, poly syzterm, 489 ideal L, ideal LS, 490 const ring r, 491 const SchreyerSyzygyComputationFlags attributes) 492 { 491 void SchreyerSyzygyComputation::ComputeSyzygy() 492 { 493 // FROM_NAMESPACE(INTERNAL, _ComputeSyzygy(m_idLeads, m_idTails, m_syzLeads, m_syzTails, m_rBaseRing, m_atttributes)); // TODO: just a wrapper for now :/ 494 495 assume( m_idLeads != NULL ); 496 assume( m_idTails != NULL ); 497 498 const ideal& L = m_idLeads; 499 const ideal& T = m_idTails; 500 501 ideal& TT = m_syzTails; 502 const ring& R = m_rBaseRing; 503 const SchreyerSyzygyComputationFlags& attributes = m_atttributes; 504 505 // const BOOLEAN __DEBUG__ = attributes.__DEBUG__; 506 // const BOOLEAN __SYZCHECK__ = attributes.__SYZCHECK__; 507 const BOOLEAN __LEAD2SYZ__ = attributes.__LEAD2SYZ__; 508 const BOOLEAN __HYBRIDNF__ = attributes.__HYBRIDNF__; 509 const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__; 510 511 assume( R == currRing ); // For attributes :-/ 512 513 assume( IDELEMS(L) == IDELEMS(T) ); 514 515 ComputeLeadingSyzygyTerms( __LEAD2SYZ__ ); // 2 terms OR 1 term! 516 517 ideal& LL = m_syzLeads; 518 519 const int size = IDELEMS(LL); 520 521 TT = idInit(size, 0); 522 523 if( size == 1 && LL->m[0] == NULL ) 524 return; 525 526 527 ideal LS = NULL; 528 529 if( __TAILREDSYZ__ ) 530 LS = LL; 531 532 for( int k = size - 1; k >= 0; k-- ) 533 { 534 const poly a = LL->m[k]; assume( a != NULL ); 535 536 const int r = p_GetComp(a, R) - 1; 537 538 assume( r >= 0 && r < IDELEMS(T) ); 539 assume( r >= 0 && r < IDELEMS(L) ); 540 541 poly aa = leadmonom(a, R); assume( aa != NULL); // :( 542 543 poly a2 = pNext(a); 544 545 if( a2 != NULL ) 546 { 547 TT->m[k] = a2; pNext(a) = NULL; 548 } 549 550 if( ! __HYBRIDNF__ ) 551 { 552 poly t = TraverseTail(aa, T->m[r]); 553 554 if( a2 != NULL ) 555 { 556 assume( __LEAD2SYZ__ ); 557 558 const int r2 = p_GetComp(a2, R) - 1; poly aa2 = leadmonom(a2, R); // :( 559 560 assume( r2 >= 0 && r2 < IDELEMS(T) ); 561 562 TT->m[k] = p_Add_q(a2, p_Add_q(t, TraverseTail(aa2, T->m[r2]), R), R); 563 564 p_Delete(&aa2, R); 565 } else 566 TT->m[k] = p_Add_q(t, ReduceTerm(aa, L->m[r], a), R); 567 568 } else 569 { 570 if( a2 == NULL ) 571 { 572 aa = p_Mult_mm(aa, L->m[r], R); 573 a2 = FindReducer(aa, a); 574 } 575 assume( a2 != NULL ); 576 577 TT->m[k] = SchreyerSyzygyNF(a, a2); // will copy a2 :( 578 579 p_Delete(&a2, R); 580 } 581 p_Delete(&aa, R); 582 } 583 584 TT->rank = id_RankFreeModule(TT, R); 585 } 586 587 void SchreyerSyzygyComputation::ComputeLeadingSyzygyTerms(bool bComputeSecondTerms) 588 { 589 const SchreyerSyzygyComputationFlags& attributes = m_atttributes; 590 591 const BOOLEAN __LEAD2SYZ__ = attributes.__LEAD2SYZ__; 592 const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__; 593 594 if( bComputeSecondTerms ) 595 // m_syzLeads = FROM_NAMESPACE(INTERNAL, _Compute2LeadingSyzygyTerms(m_idLeads, m_rBaseRing, m_atttributes)); 596 m_syzLeads = Compute2LeadingSyzygyTerms(); 597 else 598 m_syzLeads = Compute1LeadingSyzygyTerms(); 599 // m_syzLeads = FROM_NAMESPACE(INTERNAL, _ComputeLeadingSyzygyTerms(m_idLeads, m_rBaseRing, m_atttributes)); 600 601 // NOTE: set m_LS if tails are to be reduced! 602 603 if (__TAILREDSYZ__) 604 m_LS = m_syzLeads; 605 } 606 607 poly SchreyerSyzygyComputation::FindReducer(poly product, poly syzterm) const 608 { 609 // return FROM_NAMESPACE(INTERNAL, _FindReducer(product, syzterm, m_idLeads, m_LS, m_rBaseRing, m_atttributes)); 610 // poly _FindReducer(poly product, poly syzterm, 611 // ideal L, ideal LS, 612 // const ring r, 613 // const SchreyerSyzygyComputationFlags attributes) 614 615 const ideal& L = m_idLeads; 616 const ideal& LS = m_LS; 617 const ring& r = m_rBaseRing; 618 const SchreyerSyzygyComputationFlags& attributes = m_atttributes; 619 620 493 621 const BOOLEAN __DEBUG__ = attributes.__DEBUG__; 494 622 const BOOLEAN __SYZCHECK__ = attributes.__SYZCHECK__; 495 623 // const BOOLEAN __LEAD2SYZ__ = attributes.__LEAD2SYZ__; 496 624 // const BOOLEAN __HYBRIDNF__ = attributes.__HYBRIDNF__; 497 //const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__;625 const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__; 498 626 499 627 assume( product != NULL ); … … 555 683 if( LS != NULL ) 556 684 { 685 assume( __TAILREDSYZ__ ); 557 686 BOOLEAN ok = TRUE; 558 687 … … 591 720 } 592 721 593 poly _ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck, 594 ideal L, ideal T, ideal LS, 595 const ring r, const SchreyerSyzygyComputationFlags attributes); 596 597 poly _TraverseTail(poly multiplier, poly tail, 598 ideal L, ideal T, ideal LS, 599 const ring r, 600 const SchreyerSyzygyComputationFlags attributes) 601 { 722 723 poly SchreyerSyzygyComputation::SchreyerSyzygyNF(poly syz_lead, poly syz_2) const 724 { 725 // return FROM_NAMESPACE(INTERNAL, _SchreyerSyzygyNF(syz_lead, syz_2, m_idLeads, m_idTails, m_LS, m_rBaseRing, m_atttributes)); 726 // poly _SchreyerSyzygyNF(poly syz_lead, poly syz_2, 727 // ideal L, ideal T, ideal LS, 728 // const ring r, 729 // const SchreyerSyzygyComputationFlags attributes) 730 // { 731 732 const ideal& L = m_idLeads; 733 const ideal& T = m_idTails; 734 const ideal& LS = m_LS; 735 const ring& r = m_rBaseRing; 736 const SchreyerSyzygyComputationFlags& attributes = m_atttributes; 737 738 602 739 // const BOOLEAN __DEBUG__ = attributes.__DEBUG__; 603 740 // const BOOLEAN __SYZCHECK__ = attributes.__SYZCHECK__; … … 606 743 // const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__; 607 744 608 assume( multiplier != NULL ); 745 assume( syz_lead != NULL ); 746 assume( syz_2 != NULL ); 609 747 610 748 assume( L != NULL ); 611 749 assume( T != NULL ); 612 750 613 poly s = NULL; 614 615 // iterate over the tail 616 for(poly p = tail; p != NULL; p = pNext(p)) 617 s = p_Add_q(s, _ReduceTerm(multiplier, p, NULL, L, T, LS, r, attributes), r); 618 619 return s; 620 } 621 622 623 poly _ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck, 624 ideal L, ideal T, ideal LS, 625 const ring r, 626 const SchreyerSyzygyComputationFlags attributes) 627 { 751 assume( IDELEMS(L) == IDELEMS(T) ); 752 753 int c = p_GetComp(syz_lead, r) - 1; 754 755 assume( c >= 0 && c < IDELEMS(T) ); 756 757 poly p = leadmonom(syz_lead, r); // :( 758 poly spoly = pp_Mult_qq(p, T->m[c], r); 759 p_Delete(&p, r); 760 761 762 c = p_GetComp(syz_2, r) - 1; 763 assume( c >= 0 && c < IDELEMS(T) ); 764 765 p = leadmonom(syz_2, r); // :( 766 spoly = p_Add_q(spoly, pp_Mult_qq(p, T->m[c], r), r); 767 p_Delete(&p, r); 768 769 poly tail = p_Copy(syz_2, r); // TODO: use bucket!? 770 771 while (spoly != NULL) 772 { 773 poly t = FindReducer(spoly, NULL); 774 775 p_LmDelete(&spoly, r); 776 777 if( t != NULL ) 778 { 779 p = leadmonom(t, r); // :( 780 c = p_GetComp(t, r) - 1; 781 782 assume( c >= 0 && c < IDELEMS(T) ); 783 784 spoly = p_Add_q(spoly, pp_Mult_qq(p, T->m[c], r), r); 785 786 p_Delete(&p, r); 787 788 tail = p_Add_q(tail, t, r); 789 } 790 } 791 792 return tail; 793 } 794 795 796 poly SchreyerSyzygyComputation::TraverseTail(poly multiplier, poly tail) const 797 { 798 const ideal& L = m_idLeads; 799 const ideal& T = m_idTails; 800 const ideal& LS = m_LS; 801 const ring& r = m_rBaseRing; 802 const SchreyerSyzygyComputationFlags& attributes = m_atttributes; 803 804 // return FROM_NAMESPACE(INTERNAL, _TraverseTail(multiplier, tail, m_idLeads, m_idTails, m_LS, m_rBaseRing, m_atttributes)); 805 // poly _TraverseTail(poly multiplier, poly tail, 806 // ideal L, ideal T, ideal LS, 807 // const ring r, 808 // const SchreyerSyzygyComputationFlags attributes) 809 // { 810 811 628 812 // const BOOLEAN __DEBUG__ = attributes.__DEBUG__; 629 813 // const BOOLEAN __SYZCHECK__ = attributes.__SYZCHECK__; … … 633 817 634 818 assume( multiplier != NULL ); 635 assume( term4reduction != NULL );636 637 819 638 820 assume( L != NULL ); 639 821 assume( T != NULL ); 640 822 641 // assume(r == currRing); // ?642 643 // simple implementation with FindReducer:644 823 poly s = NULL; 645 824 646 if(1) 647 { 648 // NOTE: only LT(term4reduction) should be used in the following: 649 poly product = pp_Mult_mm(multiplier, term4reduction, r); 650 s = _FindReducer(product, syztermCheck, L, LS, r, attributes); 651 p_Delete(&product, r); 652 } 653 654 if( s == NULL ) // No Reducer? 655 return s; 656 657 poly b = leadmonom(s, r); 658 659 const int c = p_GetComp(s, r) - 1; 660 assume( c >= 0 && c < IDELEMS(T) ); 661 662 const poly tail = T->m[c]; 663 664 if( tail != NULL ) 665 s = p_Add_q(s, _TraverseTail(b, tail, L, T, LS, r, attributes), r); 825 // iterate over the tail 826 for(poly p = tail; p != NULL; p = pNext(p)) 827 s = p_Add_q(s, ReduceTerm(multiplier, p, NULL), r); 666 828 667 829 return s; … … 669 831 670 832 671 poly _SchreyerSyzygyNF(poly syz_lead, poly syz_2, 672 ideal L, ideal T, ideal LS, 673 const ring r, 674 const SchreyerSyzygyComputationFlags attributes) 675 { 833 834 835 poly SchreyerSyzygyComputation::ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const 836 { 837 const ideal& L = m_idLeads; 838 const ideal& T = m_idTails; 839 const ideal& LS = m_LS; 840 const ring& r = m_rBaseRing; 841 const SchreyerSyzygyComputationFlags& attributes = m_atttributes; 842 843 // return FROM_NAMESPACE(INTERNAL, _ReduceTerm(multiplier, term4reduction, syztermCheck, m_idLeads, m_idTails, m_LS, m_rBaseRing, m_atttributes)); 844 // poly _ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck, 845 // ideal L, ideal T, ideal LS, 846 // const ring r, 847 // const SchreyerSyzygyComputationFlags attributes) 848 849 850 676 851 // const BOOLEAN __DEBUG__ = attributes.__DEBUG__; 677 852 // const BOOLEAN __SYZCHECK__ = attributes.__SYZCHECK__; … … 680 855 // const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__; 681 856 682 assume( syz_lead != NULL ); 683 assume( syz_2 != NULL ); 857 assume( multiplier != NULL ); 858 assume( term4reduction != NULL ); 859 684 860 685 861 assume( L != NULL ); 686 862 assume( T != NULL ); 687 863 688 assume( IDELEMS(L) == IDELEMS(T) ); 689 690 int c = p_GetComp(syz_lead, r) - 1; 691 864 // assume(r == currRing); // ? 865 866 // simple implementation with FindReducer: 867 poly s = NULL; 868 869 if(1) 870 { 871 // NOTE: only LT(term4reduction) should be used in the following: 872 poly product = pp_Mult_mm(multiplier, term4reduction, r); 873 s = FindReducer(product, syztermCheck); 874 p_Delete(&product, r); 875 } 876 877 if( s == NULL ) // No Reducer? 878 return s; 879 880 poly b = leadmonom(s, r); 881 882 const int c = p_GetComp(s, r) - 1; 692 883 assume( c >= 0 && c < IDELEMS(T) ); 693 884 694 poly p = leadmonom(syz_lead, r); // :( 695 poly spoly = pp_Mult_qq(p, T->m[c], r); 696 p_Delete(&p, r); 697 698 699 c = p_GetComp(syz_2, r) - 1; 700 assume( c >= 0 && c < IDELEMS(T) ); 701 702 p = leadmonom(syz_2, r); // :( 703 spoly = p_Add_q(spoly, pp_Mult_qq(p, T->m[c], r), r); 704 p_Delete(&p, r); 705 706 poly tail = p_Copy(syz_2, r); // TODO: use bucket!? 707 708 while (spoly != NULL) 709 { 710 poly t = _FindReducer(spoly, NULL, L, LS, r, attributes); 711 712 p_LmDelete(&spoly, r); 713 714 if( t != NULL ) 715 { 716 p = leadmonom(t, r); // :( 717 c = p_GetComp(t, r) - 1; 718 719 assume( c >= 0 && c < IDELEMS(T) ); 720 721 spoly = p_Add_q(spoly, pp_Mult_qq(p, T->m[c], r), r); 722 723 p_Delete(&p, r); 724 725 tail = p_Add_q(tail, t, r); 726 } 727 } 728 729 return tail; 730 } 731 732 733 void _ComputeSyzygy(const ideal L, const ideal T, 734 ideal& LL, ideal& TT, 735 const ring R, 736 const SchreyerSyzygyComputationFlags attributes) 737 { 738 // const BOOLEAN __DEBUG__ = attributes.__DEBUG__; 739 // const BOOLEAN __SYZCHECK__ = attributes.__SYZCHECK__; 740 const BOOLEAN __LEAD2SYZ__ = attributes.__LEAD2SYZ__; 741 const BOOLEAN __HYBRIDNF__ = attributes.__HYBRIDNF__; 742 const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__; 743 744 assume( R == currRing ); // For attributes :-/ 745 746 assume( IDELEMS(L) == IDELEMS(T) ); 747 748 if( __LEAD2SYZ__ ) 749 LL = _Compute2LeadingSyzygyTerms(L, R, attributes); // 2 terms! 750 else 751 LL = _ComputeLeadingSyzygyTerms(L, R, attributes); // 1 term! 752 753 const int size = IDELEMS(LL); 754 755 TT = idInit(size, 0); 756 757 if( size == 1 && LL->m[0] == NULL ) 758 return; 759 760 761 ideal LS = NULL; 762 763 if( __TAILREDSYZ__ ) 764 LS = LL; 765 766 for( int k = size - 1; k >= 0; k-- ) 767 { 768 const poly a = LL->m[k]; assume( a != NULL ); 769 770 const int r = p_GetComp(a, R) - 1; 771 772 assume( r >= 0 && r < IDELEMS(T) ); 773 assume( r >= 0 && r < IDELEMS(L) ); 774 775 poly aa = leadmonom(a, R); assume( aa != NULL); // :( 776 777 poly a2 = pNext(a); 778 779 if( a2 != NULL ) 780 { 781 TT->m[k] = a2; pNext(a) = NULL; 782 } 783 784 if( ! __HYBRIDNF__ ) 785 { 786 poly t = _TraverseTail(aa, T->m[r], L, T, LS, R, attributes); 787 788 if( a2 != NULL ) 789 { 790 assume( __LEAD2SYZ__ ); 791 792 const int r2 = p_GetComp(a2, R) - 1; poly aa2 = leadmonom(a2, R); // :( 793 794 assume( r2 >= 0 && r2 < IDELEMS(T) ); 795 796 TT->m[k] = p_Add_q(a2, p_Add_q(t, _TraverseTail(aa2, T->m[r2], L, T, LS, R, attributes), R), R); 797 798 p_Delete(&aa2, R); 799 } else 800 TT->m[k] = p_Add_q(t, _ReduceTerm(aa, L->m[r], a, L, T, LS, R, attributes), R); 801 802 } else 803 { 804 if( a2 == NULL ) 805 { 806 aa = p_Mult_mm(aa, L->m[r], R); 807 a2 = _FindReducer(aa, a, L, LS, R, attributes); 808 } 809 assume( a2 != NULL ); 810 811 TT->m[k] = _SchreyerSyzygyNF(a, a2, L, T, LS, R, attributes); // will copy a2 :( 812 813 p_Delete(&a2, R); 814 } 815 p_Delete(&aa, R); 816 } 817 818 TT->rank = id_RankFreeModule(TT, R); 819 } 820 821 END_NAMESPACE 822 823 824 // TODO: wrapper layer, just for now... dissolve! 825 826 void SchreyerSyzygyComputation::ComputeSyzygy() 827 { 828 /// assumes m_syzLeads == m_syzTails == NULL! 829 FROM_NAMESPACE(INTERNAL, _ComputeSyzygy(m_idLeads, m_idTails, m_syzLeads, m_syzTails, m_rBaseRing, m_atttributes)); // TODO: just a wrapper for now :/ 830 } 831 832 void SchreyerSyzygyComputation::ComputeLeadingSyzygyTerms(bool bComputeSecondTerms) 833 { 834 if( bComputeSecondTerms ) 835 m_syzLeads = FROM_NAMESPACE(INTERNAL, _Compute2LeadingSyzygyTerms(m_idLeads, m_rBaseRing, m_atttributes)); 836 else 837 m_syzLeads = FROM_NAMESPACE(INTERNAL, _ComputeLeadingSyzygyTerms(m_idLeads, m_rBaseRing, m_atttributes)); 838 839 // NOTE: set m_LS if tails are to be reduced! 840 } 841 842 poly SchreyerSyzygyComputation::FindReducer(poly product, poly syzterm) const 843 { 844 return FROM_NAMESPACE(INTERNAL, _FindReducer(product, syzterm, m_idLeads, m_LS, m_rBaseRing, m_atttributes)); 845 } 846 847 poly SchreyerSyzygyComputation::SchreyerSyzygyNF(poly syz_lead, poly syz_2) const 848 { 849 return FROM_NAMESPACE(INTERNAL, _SchreyerSyzygyNF(syz_lead, syz_2, m_idLeads, m_idTails, m_LS, m_rBaseRing, m_atttributes)); 850 } 851 852 poly SchreyerSyzygyComputation::TraverseTail(poly multiplier, poly tail) const 853 { 854 return FROM_NAMESPACE(INTERNAL, _TraverseTail(multiplier, tail, m_idLeads, m_idTails, m_LS, m_rBaseRing, m_atttributes)); 855 } 856 857 poly SchreyerSyzygyComputation::ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const 858 { 859 return FROM_NAMESPACE(INTERNAL, _ReduceTerm(multiplier, term4reduction, syztermCheck, m_idLeads, m_idTails, m_LS, m_rBaseRing, m_atttributes)); 860 } 885 const poly tail = T->m[c]; 886 887 if( tail != NULL ) 888 s = p_Add_q(s, TraverseTail(b, tail), r); 889 890 return s; 891 } 892 893 894 861 895 862 896
Note: See TracChangeset
for help on using the changeset viewer.