Changeset 7edaddb in git


Ignore:
Timestamp:
May 27, 2013, 6:16:43 PM (11 years ago)
Author:
Oleksandr Motsak <motsak@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '0bc2210f8055033868008a3836878db65ec6f89e')
Children:
c760e259ac3027fa03d62991a376b52296dfb095
Parents:
d6283902d593a8accfa74862cafcd05348f70d1a
git-author:
Oleksandr Motsak <motsak@mathematik.uni-kl.de>2013-05-27 18:16:43+02:00
git-committer:
Oleksandr Motsak <motsak@mathematik.uni-kl.de>2014-05-07 04:41:49+02:00
Message:
Added caching (preliminary)
Location:
dyn_modules/syzextra
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • dyn_modules/syzextra/syzextra.cc

    rd62839 r7edaddb  
    154154}
    155155
     156   
     157static int cmp_poly(const poly &a, const poly &b)
     158{
     159  const int YES = 1;
     160  const int NO = -1;
     161
     162  const ring r =  (const ring) currRing; // TODO/NOTE: the structure is known: C, lp!!!
     163
     164  assume( r == currRing );
     165
     166  assume( a != NULL );
     167  assume( b != NULL );
     168
     169  assume( p_LmTest(a, r) );
     170  assume( p_LmTest(b, r) );
     171  assume( p_GetComp(a, r) == 0 );
     172  assume( p_GetComp(b, r) == 0 );
     173   
     174#ifndef NDEBUG
     175  const int __DEBUG__ = 0;
     176  if( __DEBUG__ )
     177  {
     178    PrintS("cmp_lex: a, b: \np1: "); dPrint(a, r, r, 2);
     179    PrintS("b: "); dPrint(b, r, r, 2);
     180    PrintLn();
     181  }
     182#endif
     183
     184  for (int v = rVar(r); v > 0; v--)
     185  {
     186    assume( v > 0 );
     187    assume( v <= rVar(r) );
     188
     189    const signed int d = p_GetExp(a, v, r) - p_GetExp(b, v, r);
     190
     191    if( d > 0 )
     192      return YES;
     193
     194    if( d < 0 )
     195      return NO;
     196
     197    assume( d == 0 );
     198  }
     199
     200  return 0; 
     201}
     202   
    156203END_NAMESPACE
    157204/* namespace SORT_c_ds */
     
    250297    kBucketDestroy(&m_spoly_bucket);
    251298    m_spoly_bucket = NULL;
    252   } 
     299  }
     300   
     301  for( TCache::iterator it = m_cache.begin(); it != m_cache.end(); it++ )
     302  {
     303    TP2PCache& T = it->second;
     304     
     305    for(TP2PCache::iterator vit = T.begin(); vit != T.end(); vit++ )
     306    {   
     307      p_Delete( (&(vit->second)), m_rBaseRing);
     308      p_Delete( const_cast<poly*>(&(vit->first)), m_rBaseRing);
     309    }
     310  }
    253311}
    254312  /*
     
    285343  if ( itr == m_hash.end() )
    286344    return 2; // no such leading component!!!
    287 
     345   
     346  assume( itr->first == comp );
     347   
    288348  const bool bIdealCase = (comp == 0);   
    289349  const bool bSyzCheck = syzChecker.IsNonempty(); // need to check even in ideal case????? proof?  "&& !bIdealCase"
     
    720780
    721781 
    722   poly t = TraverseTail(aa, r);
     782  poly t = TraverseTail(aa, r); 
    723783
    724784  if( a2 != NULL )
     
    730790    assume( r2 >= 0 && r2 < IDELEMS(T) );
    731791
    732     t = p_Add_q(a2, p_Add_q(t, TraverseTail(aa2, r2), R), R);
     792    t = p_Add_q(a2, p_Add_q(t, TraverseTail(aa2, r2), R), R); 
    733793
    734794    p_Delete(&aa2, R);
     
    10291089}
    10301090
     1091// namespace     {   
     1092
     1093// };
     1094
     1095bool my_p_LmCmp (poly a, poly b, const ring r) { return p_LmCmp(a, b, r) == -1; } // TODO: change to simple lex. memory compare!
     1096
     1097// NOTE: need p_Copy?????? for image + multiplier!!???
     1098// NOTE: better store complete syz. terms!!?
    10311099poly SchreyerSyzygyComputation::TraverseTail(poly multiplier, const int tail) const
    10321100{
    1033   // TODO: store (multiplier, tail) -.-^-.-^-.--> !
     1101  const ring& r = m_rBaseRing;
     1102   
    10341103  assume(m_idTails !=  NULL && m_idTails->m != NULL);
    10351104  assume( tail >= 0 && tail < IDELEMS(m_idTails) );
    1036 
     1105   
     1106/*  return ComputeImage(multiplier, tail); */
     1107 
     1108  // TODO: store (multiplier, tail) -.-^-.-^-.--> !
     1109  TCache::iterator top_itr = m_cache.find(tail);
     1110   
     1111  if ( top_itr != m_cache.end() )
     1112  {
     1113     assume( top_itr->first == tail );
     1114
     1115     TP2PCache& T = top_itr->second;
     1116     
     1117     TP2PCache::iterator itr = T.find(multiplier);
     1118     
     1119     if( itr != T.end() ) // Yey - Reuse!!!
     1120     {
     1121       assume( p_LmEqual(itr->first, multiplier, r) );
     1122       poly p = p_Copy(itr->second, r); // no copy???
     1123       if( !n_Equal( pGetCoeff(multiplier), pGetCoeff(itr->first), r) ) // normalize coeffs!?
     1124       {
     1125         number n = n_Div( pGetCoeff(multiplier), pGetCoeff(itr->first), r);
     1126         p = p_Mult_nn(p, n, r);
     1127         n_Delete(&n, r);
     1128       }
     1129       
     1130       return p;
     1131     }
     1132     
     1133     const poly p = ComputeImage(multiplier, tail);
     1134     T.insert( TP2PCache::value_type(p_Copy(multiplier, r), p) );
     1135//     T[ multiplier ] = p;
     1136     
     1137     return p_Copy(p, r);
     1138  }
     1139  CCacheCompare o(r); TP2PCache T(o);
     1140
     1141  const poly p = ComputeImage(multiplier, tail);
     1142   
     1143  T.insert( TP2PCache::value_type(p_Copy(multiplier, r), p) );
     1144   
     1145  m_cache.insert( TCache::value_type(tail, T) );
     1146
     1147  return p_Copy(p, r);
     1148}
     1149
     1150poly SchreyerSyzygyComputation::ComputeImage(poly multiplier, const int tail) const
     1151{
    10371152  const poly t = m_idTails->m[tail]; // !!!
    10381153
     
    10431158}
    10441159
    1045 
     1160   
    10461161poly SchreyerSyzygyComputation::TraverseTail(poly multiplier, poly tail) const
    10471162{
     
    11371252
    11381253  if( t != NULL )
    1139     s = p_Add_q(s, t, r);  
     1254    s = p_Add_q(s, t, r);
    11401255
    11411256  return s;
     
    14471562  if( it == m_hash.end() )
    14481563    return false;
    1449 
     1564  // assume comp!
     1565 
    14501566  const TReducers& reducers = it->second;
    14511567
     
    15361652      m_active = false;
    15371653     
    1538       m_itr = m_reds.m_hash.find(m_comp);
     1654      m_itr = m_reds.m_hash.find(m_comp); 
    15391655
    15401656      if( m_itr == m_reds.m_hash.end() )
     
    17101826    return NULL;
    17111827
     1828  // assume comp!
     1829 
    17121830  assume( m_L != NULL );
    17131831
  • dyn_modules/syzextra/syzextra.h

    rd62839 r7edaddb  
    181181
    182182extern ideal id_Copy (const ideal, const ring);
    183 
     183bool my_p_LmCmp (poly, poly, const ring);
     184
     185typedef poly TCacheKey;
     186typedef poly TCacheValue;
     187
     188struct CCacheCompare
     189{
     190    const ring & m_ring;
     191    CCacheCompare(const ring& r): m_ring(r) {}   
     192    inline bool operator() (const TCacheKey& l, const TCacheKey& r) { return my_p_LmCmp(l, r, m_ring); }
     193};
     194   
     195typedef std::map<TCacheKey, TCacheValue, CCacheCompare> TP2PCache; // deallocation??? !!!
     196typedef std::map<int, TP2PCache> TCache;
    184197
    185198/** @class SchreyerSyzygyComputation syzextra.h
     
    205218        m_syzLeads(NULL), m_syzTails(NULL),
    206219        m_LS(NULL), m_lcm(m_idLeads, setting),
    207         m_div(m_idLeads, setting), m_checker(NULL, setting),
     220        m_div(m_idLeads, setting), m_checker(NULL, setting), m_cache(),
    208221        m_sum_bucket(NULL), m_spoly_bucket(NULL)
    209222    {
     
    215228        m_idLeads(idLeads), m_idTails(id_Copy(idTails, setting.m_rBaseRing)),
    216229        m_syzLeads(syzLeads), m_syzTails(NULL),
    217         m_LS(syzLeads), m_lcm(m_idLeads, setting), 
    218         m_div(m_idLeads, setting), m_checker(NULL, setting),
     230        m_LS(syzLeads), m_lcm(m_idLeads, setting),
     231        m_div(m_idLeads, setting), m_checker(NULL, setting), m_cache(),
    219232        m_sum_bucket(NULL), m_spoly_bucket(NULL)
    220233    {
     
    253266    poly SchreyerSyzygyNF(const poly syz_lead, poly syz_2 = NULL) const;
    254267
     268    /// High level caching function!!!
    255269    poly TraverseTail(poly multiplier, const int tail) const;
    256270
    257     // called only from above and from outside (for testing)
     271    // REMOVE?
     272    /// called only from above and from outside (for testing)
    258273    poly TraverseTail(poly multiplier, poly tail) const;
    259274
    260     // TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ?
     275    /// TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ? ???
    261276    poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const;
     277
     278    /// low level computation...
     279    poly ComputeImage(poly multiplier, const int tail) const;
    262280
    263281    //
     
    325343    TTailTerms m_idTailTerms;
    326344    */
    327 
    328345   
     346    mutable TCache m_cache; // cacher comp + poly -> poly! // mutable???
     347
    329348/// TODO: look into m_idTailTerms!!!!!!!!!!!!!!!!!!!!!!!! map? heaps???
    330349    // NOTE/TODO: the following globally shared buckets violate reentrance - they should rather belong to TLS!
Note: See TracChangeset for help on using the changeset viewer.