Changeset 7edaddb in git

Timestamp:

May 27, 2013, 6:16:43 PM (10 years ago)

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')

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:

• syzextra.cc (modified) (11 diffs)
• syzextra.h (modified) (5 diffs)

dyn_modules/syzextra/syzextra.cc

@@ -154 +154 @@
 }
 
+   
+static int cmp_poly(const poly &a, const poly &b)
+{
+  const int YES = 1;
+  const int NO = -1;
+
+  const ring r =  (const ring) currRing; // TODO/NOTE: the structure is known: C, lp!!!
+
+  assume( r == currRing );
+
+  assume( a != NULL );
+  assume( b != NULL );
+
+  assume( p_LmTest(a, r) );
+  assume( p_LmTest(b, r) );
+  assume( p_GetComp(a, r) == 0 );
+  assume( p_GetComp(b, r) == 0 );
+   
+#ifndef NDEBUG
+  const int __DEBUG__ = 0;
+  if( __DEBUG__ )
+  {
+    PrintS("cmp_lex: a, b: \np1: "); dPrint(a, r, r, 2);
+    PrintS("b: "); dPrint(b, r, r, 2);
+    PrintLn();
+  }
+#endif
+
+  for (int v = rVar(r); v > 0; v--)
+  {
+    assume( v > 0 );
+    assume( v <= rVar(r) );
+
+    const signed int d = p_GetExp(a, v, r) - p_GetExp(b, v, r);
+
+    if( d > 0 )
+      return YES;
+
+    if( d < 0 )
+      return NO;
+
+    assume( d == 0 );
+  }
+
+  return 0;  
+}
+   
 END_NAMESPACE
 /* namespace SORT_c_ds */
@@ -250 +297 @@
     kBucketDestroy(&m_spoly_bucket);
     m_spoly_bucket = NULL;
-  }  
+  }
+   
+  for( TCache::iterator it = m_cache.begin(); it != m_cache.end(); it++ )
+  {
+    TP2PCache& T = it->second;
+     
+    for(TP2PCache::iterator vit = T.begin(); vit != T.end(); vit++ )
+    {   
+      p_Delete( (&(vit->second)), m_rBaseRing);
+      p_Delete( const_cast<poly*>(&(vit->first)), m_rBaseRing);
+    }
+  }
 }
   /*
@@ -285 +343 @@
   if ( itr == m_hash.end() ) 
     return 2; // no such leading component!!!
-
+   
+  assume( itr->first == comp );
+   
   const bool bIdealCase = (comp == 0);    
   const bool bSyzCheck = syzChecker.IsNonempty(); // need to check even in ideal case????? proof?  "&& !bIdealCase"
@@ -720 +780 @@
 
   
-  poly t = TraverseTail(aa, r);
+  poly t = TraverseTail(aa, r); 
 
   if( a2 != NULL )
@@ -730 +790 @@
     assume( r2 >= 0 && r2 < IDELEMS(T) );
 
-    t = p_Add_q(a2, p_Add_q(t, TraverseTail(aa2, r2), R), R);
+    t = p_Add_q(a2, p_Add_q(t, TraverseTail(aa2, r2), R), R); 
 
     p_Delete(&aa2, R);
@@ -1029 +1089 @@
 }
 
+// namespace     {   
+
+// };
+
+bool my_p_LmCmp (poly a, poly b, const ring r) { return p_LmCmp(a, b, r) == -1; } // TODO: change to simple lex. memory compare!
+
+// NOTE: need p_Copy?????? for image + multiplier!!???
+// NOTE: better store complete syz. terms!!?
 poly SchreyerSyzygyComputation::TraverseTail(poly multiplier, const int tail) const
 {
-  // TODO: store (multiplier, tail) -.-^-.-^-.--> !
+  const ring& r = m_rBaseRing;
+   
   assume(m_idTails !=  NULL && m_idTails->m != NULL);
   assume( tail >= 0 && tail < IDELEMS(m_idTails) );
-
+   
+/*  return ComputeImage(multiplier, tail); */
+  
+  // TODO: store (multiplier, tail) -.-^-.-^-.--> !
+  TCache::iterator top_itr = m_cache.find(tail);
+   
+  if ( top_itr != m_cache.end() )
+  {
+     assume( top_itr->first == tail );
+
+     TP2PCache& T = top_itr->second;
+     
+     TP2PCache::iterator itr = T.find(multiplier);
+     
+     if( itr != T.end() ) // Yey - Reuse!!!
+     {
+       assume( p_LmEqual(itr->first, multiplier, r) ); 
+       poly p = p_Copy(itr->second, r); // no copy???
+       if( !n_Equal( pGetCoeff(multiplier), pGetCoeff(itr->first), r) ) // normalize coeffs!?
+       {
+         number n = n_Div( pGetCoeff(multiplier), pGetCoeff(itr->first), r); 
+         p = p_Mult_nn(p, n, r); 
+         n_Delete(&n, r);
+       }
+        
+       return p;
+     }
+     
+     const poly p = ComputeImage(multiplier, tail);
+     T.insert( TP2PCache::value_type(p_Copy(multiplier, r), p) );
+//     T[ multiplier ] = p;
+     
+     return p_Copy(p, r);
+  }
+  CCacheCompare o(r); TP2PCache T(o);
+
+  const poly p = ComputeImage(multiplier, tail);
+   
+  T.insert( TP2PCache::value_type(p_Copy(multiplier, r), p) );
+   
+  m_cache.insert( TCache::value_type(tail, T) );
+
+  return p_Copy(p, r);
+}
+
+poly SchreyerSyzygyComputation::ComputeImage(poly multiplier, const int tail) const
+{
   const poly t = m_idTails->m[tail]; // !!!
 
@@ -1043 +1158 @@
 }
 
-
+   
 poly SchreyerSyzygyComputation::TraverseTail(poly multiplier, poly tail) const
 {
@@ -1137 +1252 @@
 
   if( t != NULL )
-    s = p_Add_q(s, t, r);  
+    s = p_Add_q(s, t, r); 
 
   return s;
@@ -1447 +1562 @@
   if( it == m_hash.end() )
     return false;
-
+  // assume comp!
+ 
   const TReducers& reducers = it->second;
 
@@ -1536 +1652 @@
       m_active = false;
       
-      m_itr = m_reds.m_hash.find(m_comp);
+      m_itr = m_reds.m_hash.find(m_comp); 
 
       if( m_itr == m_reds.m_hash.end() )
@@ -1710 +1826 @@
     return NULL;
 
+  // assume comp!
+ 
   assume( m_L != NULL );
 

dyn_modules/syzextra/syzextra.h

@@ -181 +181 @@
 
 extern ideal id_Copy (const ideal, const ring);
-
+bool my_p_LmCmp (poly, poly, const ring);
+
+typedef poly TCacheKey;
+typedef poly TCacheValue;
+
+struct CCacheCompare
+{
+    const ring & m_ring; 
+    CCacheCompare(const ring& r): m_ring(r) {}   
+    inline bool operator() (const TCacheKey& l, const TCacheKey& r) { return my_p_LmCmp(l, r, m_ring); }
+};
+   
+typedef std::map<TCacheKey, TCacheValue, CCacheCompare> TP2PCache; // deallocation??? !!!
+typedef std::map<int, TP2PCache> TCache;
 
 /** @class SchreyerSyzygyComputation syzextra.h
@@ -205 +218 @@
         m_syzLeads(NULL), m_syzTails(NULL),
         m_LS(NULL), m_lcm(m_idLeads, setting), 
-        m_div(m_idLeads, setting), m_checker(NULL, setting),
+        m_div(m_idLeads, setting), m_checker(NULL, setting), m_cache(),
         m_sum_bucket(NULL), m_spoly_bucket(NULL)
     {
@@ -215 +228 @@
         m_idLeads(idLeads), m_idTails(id_Copy(idTails, setting.m_rBaseRing)), 
         m_syzLeads(syzLeads), m_syzTails(NULL),
-        m_LS(syzLeads), m_lcm(m_idLeads, setting), 
-        m_div(m_idLeads, setting), m_checker(NULL, setting),
+        m_LS(syzLeads), m_lcm(m_idLeads, setting),
+        m_div(m_idLeads, setting), m_checker(NULL, setting), m_cache(),
         m_sum_bucket(NULL), m_spoly_bucket(NULL)
     {
@@ -253 +266 @@
     poly SchreyerSyzygyNF(const poly syz_lead, poly syz_2 = NULL) const;
 
+    /// High level caching function!!! 
     poly TraverseTail(poly multiplier, const int tail) const;
 
-    // called only from above and from outside (for testing)
+    // REMOVE?
+    /// called only from above and from outside (for testing)
     poly TraverseTail(poly multiplier, poly tail) const;
 
-    // TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ?
+    /// TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ? ???
     poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const;
+
+    /// low level computation...
+    poly ComputeImage(poly multiplier, const int tail) const;
 
     // 
@@ -325 +343 @@
     TTailTerms m_idTailTerms;
     */
-
    
+    mutable TCache m_cache; // cacher comp + poly -> poly! // mutable???
+
 /// TODO: look into m_idTailTerms!!!!!!!!!!!!!!!!!!!!!!!! map? heaps???
     // NOTE/TODO: the following globally shared buckets violate reentrance - they should rather belong to TLS!