Changeset 7edaddb in git for dyn_modules/syzextra/syzextra.cc

Timestamp:

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

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

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)

File:

• dyn_modules/syzextra/syzextra.cc (modified) (11 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 );