Changeset 5cecde in git


Ignore:
Timestamp:
Aug 2, 2012, 9:58:56 PM (10 years ago)
Author:
Oleksandr Motsak <motsak@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '96ce329119711a2b80858c8365abd29f8460bbfa')
Children:
e98c64edd3cf15f4e5d15991052a7bbcbb1184a5
Parents:
495328d14a955b215ad10b598e995ab522243881
git-author:
Oleksandr Motsak <motsak@mathematik.uni-kl.de>2012-08-02 21:58:56+02:00
git-committer:
Oleksandr Motsak <motsak@mathematik.uni-kl.de>2014-05-07 04:41:46+02:00
Message:
Totally bitmasked: CReducerFinder: FindReducer uses syz_checker.IsDivisible()
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/schreyer.lib

    r495328 r5cecde  
    24152415  ring AGR = (101), (a,b,c,d,e,f,g,h), dp; AGR;
    24162416  // AGR@101n7d005s010%2) medium: <= 2
    2417   ideal M = f*h-g*h,e*h-g*h,d*h-g*h,c*h-g*h,b*h-g*h,a*h-g*h,e*g+48*f*g-49*g*h,d*g+5*f*g-6*g*h,c*g+49*f*g-50*g*h,b*g-7*f*g+6*g*h,a*g-50*f*g+49*g*h,e*f-20*f*g+19*g*h,d*f+40*f*g-41*g*h,c*f-12*f*g+11*g*h,b*f+45*f*g-46*g*h,a*f+4*f*g-5*g*h,d*e-f*g,c*e-30*f*g+29*g*h,b*e-39*f*g+38*g*h,a*e+10*f*g-11*g*h,c*d-41*f*g+40*g*h,b*d-23*f*g+22*g*h,a*d-20*f*g+19*g*h,b*c+17*f*g-18*g*h,a*c+6*f*g-7*g*h,a*b+28*f*g-29*g*h,g^2*h-g*h^2,f^2*g-8*f*g^2+7*g*h^2,g*h^4+50*h^5,g^5+41*h^5,f*g^4-18*h^5,f^5+29*h^5,e^5+6*h^5,d^5-23*h^5,c^5-32*h^5,b^5+17*h^5,a^5+17*h^5,h^6;
     2417  ideal M =
     2418f*h-g*h,e*h-g*h,d*h-g*h,c*h-g*h,b*h-g*h,a*h-g*h,e*g+48*f*g-49*g*h,d*g+5*f*g-6*g*h,c*g+49*f*g-50*g*h,b*g-7*f*g+6*g*h,a*g-50*f*g+49*g*h,e*f-20*f*g+19*g*h,d*f+40*f*g-41*g*h,c*f-12*f*g+11*g*h,b*f+45*f*g-46*g*h,a*f+4*f*g-5*g*h,d*e-f*g,c*e-30*f*g+29*g*h,b*e-39*f*g+38*g*h,a*e+10*f*g-11*g*h,c*d-41*f*g+40*g*h,b*d-23*f*g+22*g*h,a*d-20*f*g+19*g*h,b*c+17*f*g-18*g*h,a*c+6*f*g-7*g*h,a*b+28*f*g-29*g*h,g^2*h-g*h^2,f^2*g-8*f*g^2+7*g*h^2,g*h^4+50*h^5,g^5+41*h^5,f*g^4-18*h^5,f^5+29*h^5,e^5+6*h^5,d^5-23*h^5,c^5-32*h^5,
     2419b^5+17*h^5,a^5+17*h^5,h^6;
    24182420  M;
    24192421  TestSSresAttribs2tr(M);
    24202422/*
    2421 options:  1 1 0 :  Time:  10
    2422 options:  1 1 1 :  Time:  6
     2423options:  1 1 0 :  Time:  3/10
     2424options:  1 1 1 :  Time:  2/6
    24232425lres  Time:  0
    2424 nres  Time:  26
     2426nres  Time:  25
    24252427sres  Time:  0
    24262428*/
     
    24742476  TestSSresAttribs2tr(M);
    24752477/*
    2476 options:  1 1 0 :  Time:  9/10 (35 without LCM)
    2477 options:  1 1 1 :  Time:  8/25
     2478options:  1 1 0 :  Time:  5/9/10 (35 without LCM)
     2479options:  1 1 1 :  Time:  6/8/25
    24782480lres  Time:  5
    24792481nres  Time:  5
     
    25532555  TestSSresAttribs2tr(M);
    25542556/*
    2555 options:  1 1 0 :  Time:  73/92 (316 without LCM)
    2556 options:  1 1 1 :  Time:  43/202
     2557options:  1 1 0 :  Time:  34/73/92 (316 without LCM)
     2558options:  1 1 1 :  Time:  35/43/202
    25572559lres  Time:  25
    25582560nres  Time:  20
  • dyn_modules/syzextra/syzextra.cc

    r495328 r5cecde  
    511511  assume( IDELEMS(L) == IDELEMS(T) );
    512512
    513   ComputeLeadingSyzygyTerms( __LEAD2SYZ__ ); // 2 terms OR 1 term!
     513  if( m_syzLeads == NULL )
     514    ComputeLeadingSyzygyTerms( __LEAD2SYZ__ ); // 2 terms OR 1 term!
     515
     516  assume( m_syzLeads != NULL );
     517
     518  if( __TAILREDSYZ__ )
     519    assume( m_checker.IsNonempty() );
    514520
    515521  ideal& LL = m_syzLeads;
     522
    516523 
    517524  const int size = IDELEMS(LL);
     
    564571      if( a2 == NULL )
    565572      {
    566         aa = p_Mult_mm(aa, L->m[r], R); a2 = m_div.FindReducer(aa, a);
     573        aa = p_Mult_mm(aa, L->m[r], R); a2 = m_div.FindReducer(aa, a, m_checker);
    567574      }
    568575      assume( a2 != NULL );
     
    600607 
    601608  // NOTE: set m_LS if tails are to be reduced!
    602 
    603   if (__TAILREDSYZ__)
     609  assume( m_syzLeads!= NULL );
     610
     611  if (__TAILREDSYZ__ && (IDELEMS(m_syzLeads) > 0))
     612  {
    604613    m_LS = m_syzLeads;
     614    m_checker.Initialize(m_syzLeads);
     615  }
    605616
    606617  (void)( __LEAD2SYZ__ );
     
    618629  const ideal& L = m_idLeads;
    619630  const ideal& T = m_idTails;
    620 //  const ideal& LS = m_LS;
    621631  const ring& r = m_rBaseRing;
    622632
     
    656666  while (spoly != NULL)
    657667  {
    658     poly t = m_div.FindReducer(spoly, NULL);
     668    poly t = m_div.FindReducer(spoly, NULL, m_checker);
    659669
    660670    p_LmDelete(&spoly, r);
     
    756766    // NOTE: only LT(term4reduction) should be used in the following:
    757767    poly product = pp_Mult_mm(multiplier, term4reduction, r);
    758     s = m_div.FindReducer(product, syztermCheck);
     768    s = m_div.FindReducer(product, syztermCheck, m_checker);
    759769    p_Delete(&product, r);
    760770  }
     
    834844}
    835845
    836 CReducerFinder::CReducerFinder(const SchreyerSyzygyComputation& data):
    837     SchreyerSyzygyComputationFlags(data),
    838     m_data(data),
     846
     847void CReducerFinder::Initialize(const ideal L)
     848{
     849  assume( m_L == NULL || m_L == L );
     850  if( m_L == NULL )
     851    m_L = L;
     852
     853  assume( m_L == L );
     854 
     855  if( L != NULL )
     856  {
     857    const ring& R = m_rBaseRing;
     858    assume( R != NULL );
     859   
     860    for( int k = IDELEMS(L) - 1; k >= 0; k-- )
     861    {
     862      const poly a = L->m[k]; // assume( a != NULL );
     863
     864      // NOTE: label is k \in 0 ... |L|-1!!!
     865      if( a != NULL )
     866        m_hash[p_GetComp(a, R)].push_back( new CLeadingTerm(k, a, R) );
     867    }
     868  }
     869}
     870
     871CReducerFinder::CReducerFinder(const ideal L, const SchreyerSyzygyComputationFlags& flags):
     872    SchreyerSyzygyComputationFlags(flags),
     873    m_L(const_cast<ideal>(L)), // for debug anyway
    839874    m_hash()
    840875{
    841   const ring&  R = m_rBaseRing;
    842   assume( data.m_rBaseRing == R );
    843   assume( R != NULL );
    844 //   const SchreyerSyzygyComputationFlags& attributes = data.m_atttributes;
    845 //
    846 //   const BOOLEAN __DEBUG__      = attributes.__DEBUG__;
    847 //   const BOOLEAN __SYZCHECK__   = attributes.__SYZCHECK__;
    848 //   const BOOLEAN __HYBRIDNF__   = attributes.__HYBRIDNF__;
    849 //   const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__;
    850 
    851 
    852   const ideal& L = data.m_idLeads; assume( L != NULL );
    853 
    854   for( int k = IDELEMS(L) - 1; k >= 0; k-- )
    855   {
    856     const poly a = L->m[k]; assume( a != NULL );
    857 
    858     // NOTE: label is k \in 0 ... |L|-1!!!
    859     m_hash[p_GetComp(a, R)].push_back( new CLeadingTerm(k, a, R) );
    860   }
    861 }
    862 
    863 
    864 poly CReducerFinder::FindReducer(const poly product, const poly syzterm) const
    865 {
    866 //  return FROM_NAMESPACE(INTERNAL, _FindReducer(product, syzterm, m_idLeads, m_LS, m_rBaseRing, m_atttributes));
    867 //  poly _FindReducer(poly product, poly syzterm,
    868 //                     ideal L, ideal LS,
    869 //                     const ring r,
    870 //                     const SchreyerSyzygyComputationFlags attributes)
    871 
    872   const ideal& L = m_data.m_idLeads;
    873   const ideal& LS = m_data.m_LS;
     876  assume( flags.m_rBaseRing == m_rBaseRing );
     877  if( L != NULL )
     878    Initialize(L);
     879}
     880
     881
     882bool CReducerFinder::IsDivisible(const poly product) const
     883{
    874884  const ring& r = m_rBaseRing;
    875 //  const SchreyerSyzygyComputationFlags& attributes = m_data.m_atttributes;
    876 
    877 
    878 //  const BOOLEAN __DEBUG__      = m_data.__DEBUG__;
    879 //  const BOOLEAN __SYZCHECK__   = m_data.__SYZCHECK__;
    880 //   const BOOLEAN __LEAD2SYZ__   = attributes.__LEAD2SYZ__;
    881 //   const BOOLEAN __HYBRIDNF__   = attributes.__HYBRIDNF__;
    882 //  const BOOLEAN __TAILREDSYZ__ = m_data.__TAILREDSYZ__;
     885 
     886  const long comp = p_GetComp(product, r);
     887  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
     888
     889  assume( comp >= 0 );
     890
     891  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
     892
     893  if( it == m_hash.end() )
     894    return false;
     895
     896  assume( m_L != NULL ); 
     897
     898  const TReducers& reducers = it->second;
     899
     900  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
     901  {
     902    const poly p = (*vit)->m_lt;
     903
     904    assume( p_GetComp(p, r) == comp );
     905
     906    const int k = (*vit)->m_label;
     907
     908    assume( m_L->m[k] == p );
     909
     910    const unsigned long p_sev = (*vit)->m_sev;
     911
     912    assume( p_sev == p_GetShortExpVector(p, r) );     
     913
     914    if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
     915      continue;
     916
     917    if( __DEBUG__ )
     918    {
     919      Print("_FindReducer::Test LS: q is divisible by LS[%d] !:((, diviser is: ", k+1);
     920      dPrint(p, r, r, 1);
     921    }
     922
     923    return true;
     924  }
     925
     926  return false;
     927}
     928
     929
     930poly CReducerFinder::FindReducer(const poly product, const poly syzterm, const CReducerFinder& syz_checker) const
     931{
     932  const ring& r = m_rBaseRing;
    883933
    884934  assume( product != NULL );
    885   assume( L != NULL );
     935
     936  const ideal& L = m_L; assume( L != NULL ); // for debug/testing only!
    886937
    887938  long c = 0;
     
    912963  assume( comp >= 0 );
    913964
     965//   for( int k = IDELEMS(L)-1; k>= 0; k-- )
     966//   {
     967//     const poly p = L->m[k];
     968//
     969//     if ( p_GetComp(p, r) != comp )
     970//       continue;
     971//
     972//     const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
     973 
    914974   // looking for an appropriate diviser p = L[k]...
    915 #if 1
    916   CReducersHash::const_iterator it = m_hash.find(p_GetComp(product, r)); // same module component
     975  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
    917976
    918977  if( it == m_hash.end() )
    919978    return NULL;
    920979
    921   const TReducers& reducers = it->second; 
    922 
     980  assume( m_L != NULL );
     981
     982  const TReducers& reducers = it->second;
     983
     984  const BOOLEAN to_check = __TAILREDSYZ__ && (syz_checker.IsNonempty());
     985
     986  const poly q = p_New(r); pNext(q) = NULL;
     987
     988  if( __DEBUG__ )
     989    p_SetCoeff0(q, 0, r); // for printing q
     990 
    923991  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
    924992  {
     
    9341002
    9351003    assume( p_sev == p_GetShortExpVector(p, r) );     
    936 #else 
    937   for( int k = IDELEMS(L)-1; k>= 0; k-- )
    938   {
    939     const poly p = L->m[k];
    940 
    941     if ( p_GetComp(p, r) != comp )
    942       continue;
    943 
    944     const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
    945 #endif
    9461004
    9471005    if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
     
    9521010//       continue;
    9531011
    954 
    955     const poly q = p_New(r);
    956     pNext(q) = NULL;
    9571012    p_ExpVectorDiff(q, product, p, r); // (LM(product) / LM(L[k]))
    9581013    p_SetComp(q, k + 1, r);
     
    9691024        }   
    9701025
    971         p_LmFree(q, r);
    9721026        continue;
    9731027      }
    9741028
    9751029    // while the complement (the fraction) is not reducible by leading syzygies
    976     if( LS != NULL )
     1030    if( to_check && syz_checker.IsDivisible(q) )
    9771031    {
    978       assume( __TAILREDSYZ__ );
    979       BOOLEAN ok = TRUE;
    980 
    981       // TODO: FindReducer in LS !!! there should be no divisors!
    982       for(int kk = IDELEMS(LS)-1; kk>= 0; kk-- )
     1032      if( __DEBUG__ )
    9831033      {
    984         const poly pp = LS->m[kk];
    985 
    986         if( p_LmDivisibleBy(pp, q, r) )
    987         {
    988 
    989           if( __DEBUG__ )
    990           {
    991             Print("_FindReducer::Test LS: q is divisible by LS[%d] !:((, diviser is: ", kk+1);
    992             dPrint(pp, r, r, 1);
    993           }   
    994 
    995           ok = FALSE; // q in <LS> :((
    996           break;                 
    997         }
     1034        PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
    9981035      }
    999 
    1000       if(!ok)
    1001       {
    1002         p_LmFree(q, r);
    1003         continue;
    1004       }
     1036     
     1037      continue;
    10051038    }
    10061039
    10071040    p_SetCoeff0(q, n_Neg( n_Div( p_GetCoeff(product, r), p_GetCoeff(p, r), r), r), r);
    10081041    return q;
    1009 
    1010   }
    1011 
     1042  }
     1043
     1044  p_LmFree(q, r);
    10121045
    10131046  return NULL;
     
    10161049
    10171050
    1018   CLCM::CLCM(const SchreyerSyzygyComputation& data):
    1019       SchreyerSyzygyComputationFlags(data), std::vector<bool>(), m_data(data), m_compute(false)
    1020   {
    1021 
    1022     const ring& R = m_rBaseRing;
    1023     assume( data.m_rBaseRing == R );
    1024     assume( R != NULL );
    1025 //  const SchreyerSyzygyComputationFlags& attributes = data.m_atttributes;
    1026 
    1027 //  const BOOLEAN __DEBUG__      = attributes.__DEBUG__;
    1028 //  const BOOLEAN __SYZCHECK__   = attributes.__SYZCHECK__;
    1029 //    const BOOLEAN __HYBRIDNF__   = m_data.__HYBRIDNF__;
    1030 //    const BOOLEAN __TAILREDSYZ__ = m_data.__TAILREDSYZ__;
    1031 
    1032 
    1033     const ideal& L = data.m_idLeads;
    1034     assume( L != NULL );
    1035 
    1036     if( __TAILREDSYZ__ && !__HYBRIDNF__ )
     1051CLCM::CLCM(const ideal& L, const SchreyerSyzygyComputationFlags& flags):
     1052    SchreyerSyzygyComputationFlags(flags), std::vector<bool>(),
     1053    m_compute(false), m_N(rVar(flags.m_rBaseRing))
     1054{
     1055  const ring& R = m_rBaseRing;
     1056  assume( flags.m_rBaseRing == R );
     1057  assume( R != NULL );
     1058
     1059  assume( L != NULL );
     1060
     1061  if( __TAILREDSYZ__ && !__HYBRIDNF__ && (L != NULL))
     1062  {
     1063    const int l = IDELEMS(L);
     1064
     1065    assume( l > 0 );
     1066
     1067    resize(l, false);
     1068
     1069    for( int k = l - 1; k >= 0; k-- )
    10371070    {
    1038       const int l = IDELEMS(L);
    1039 
    1040       resize(l, false);
    1041 
    1042       const unsigned int N = rVar(R);
    1043 
    1044       for( int k = l - 1; k >= 0; k-- )
    1045       {
    1046         const poly a = L->m[k]; assume( a != NULL );
    1047 
    1048         for (unsigned int j = N; j > 0; j--)
    1049           if ( !(*this)[j] )
    1050             (*this)[j] = (p_GetExp(a, j, R) > 0);
    1051       }
    1052 
    1053       m_compute = true;   
     1071      const poly a = L->m[k]; assume( a != NULL );
     1072
     1073      for (unsigned int j = m_N; j > 0; j--)
     1074        if ( !(*this)[j] )
     1075          (*this)[j] = (p_GetExp(a, j, R) > 0);
    10541076    }
    1055   }
    1056 
    1057 
    1058   bool CLCM::Check(const poly m) const
    1059   {
    1060     assume( m != NULL );
    1061     if( m_compute && (m != NULL))
    1062     { 
    1063       const ring& R = m_data.m_rBaseRing;
    1064 //    const SchreyerSyzygyComputationFlags& attributes = m_data.m_atttributes;
    1065 
    1066   //  const BOOLEAN __DEBUG__      = attributes.__DEBUG__;
    1067   //  const BOOLEAN __SYZCHECK__   = attributes.__SYZCHECK__;
    1068 //      const BOOLEAN __HYBRIDNF__   = m_data.__HYBRIDNF__;
    1069 //      const BOOLEAN __TAILREDSYZ__ = m_data.__TAILREDSYZ__;
    1070 
    1071       assume( R != NULL );
    1072       assume( R == currRing );
    1073 
    1074       assume( __TAILREDSYZ__ && !__HYBRIDNF__ );
    1075 
    1076       const unsigned int N = rVar(R);
    1077 
    1078       for (unsigned int j = N; j > 0; j--)
    1079         if ( (*this)[j] )
    1080           if(p_GetExp(m, j, R) > 0)
    1081             return true;
    1082 
    1083       return false;
    1084 
    1085     } else return true;
    1086   }
     1077
     1078    m_compute = true;   
     1079  }
     1080}
     1081
     1082
     1083bool CLCM::Check(const poly m) const
     1084{
     1085  assume( m != NULL );
     1086  if( m_compute && (m != NULL))
     1087  { 
     1088    const ring& R = m_rBaseRing;
     1089
     1090    assume( __TAILREDSYZ__ && !__HYBRIDNF__ );
     1091
     1092    for (unsigned int j = m_N; j > 0; j--)
     1093      if ( (*this)[j] )
     1094        if(p_GetExp(m, j, R) > 0)
     1095          return true;
     1096
     1097    return false;
     1098
     1099  } else return true;
     1100}
    10871101
    10881102
  • dyn_modules/syzextra/syzextra.h

    r495328 r5cecde  
    9595{
    9696  public:
    97     CLCM(const SchreyerSyzygyComputation& data);
     97    CLCM(const ideal& L, const SchreyerSyzygyComputationFlags& flags);
    9898
    9999    bool Check(const poly m) const;
    100100   
    101101  private:
    102     const SchreyerSyzygyComputation& m_data;
    103 
    104102    bool m_compute;
     103
     104    const unsigned int m_N; ///< number of ring variables
    105105};
    106106
     
    130130   
    131131  public:
    132 
    133132    /// goes over all leading terms
    134     CReducerFinder(const SchreyerSyzygyComputation& data);
     133    CReducerFinder(const ideal L, const SchreyerSyzygyComputationFlags& flags);
     134
     135    void Initialize(const ideal L);
    135136
    136137    ~CReducerFinder();
    137138
    138139    // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?   
    139     poly FindReducer(const poly product, const poly syzterm) const;
     140    poly FindReducer(const poly product, const poly syzterm, const CReducerFinder& checker) const;
     141
     142    bool IsDivisible(const poly q) const;
     143
     144    bool IsNonempty() const { return (m_hash.size() > 0); }
    140145
    141146  private:
    142     const SchreyerSyzygyComputation& m_data;
     147    ideal m_L; ///< only for debug
    143148
    144149    CReducersHash m_hash; // can also be replaced with a vector indexed by components
     
    169174        m_idLeads(idLeads), m_idTails(idTails),
    170175        m_syzLeads(NULL), m_syzTails(NULL), m_LS(NULL),
    171         m_lcm(*this), m_div(*this)
     176        m_lcm(m_idLeads, setting), m_div(m_idLeads, setting), m_checker(NULL, setting)
    172177    {
    173178    }
    174 
    175179
    176180    /// Construct a global object for given input data (separated into leads & tails)
     
    178182        SchreyerSyzygyComputationFlags(setting),
    179183        m_idLeads(idLeads), m_idTails(idTails),
    180         m_syzLeads(NULL), m_syzTails(NULL), m_LS(syzLeads),
    181         m_lcm(*this), m_div(*this)
     184        m_syzLeads(syzLeads), m_syzTails(NULL), m_LS(syzLeads),
     185        m_lcm(m_idLeads, setting), m_div(m_idLeads, setting), m_checker(NULL, setting)
    182186    {
     187      if( __TAILREDSYZ__ && syzLeads != NULL )
     188        m_checker.Initialize(syzLeads);
    183189    }
    184190
     
    214220    /// just for testing via the wrapper below
    215221    inline poly _FindReducer(const poly product, const poly syzterm) const
    216         { return m_div.FindReducer(product, syzterm); } 
     222        { return m_div.FindReducer(product, syzterm, m_checker); } 
    217223   
    218224  protected:
     
    240246    ideal m_syzTails;
    241247
    242     /*mutable?*/ ideal m_LS; ///< leading syzygy terms used for reducing syzygy tails
    243 
    244248    /// Bitmask for variables occuring in leading terms
    245249    const CLCM m_lcm;
     
    247251    /// Divisor finder
    248252    const CReducerFinder m_div;
     253
     254    /// for checking tail-terms and makeing them irreducible (wrt m_LS!)
     255    CReducerFinder m_checker;
     256
     257    /*mutable?*/ ideal m_LS; ///< leading syzygy terms used for reducing syzygy tails
    249258};
    250259
Note: See TracChangeset for help on using the changeset viewer.