Changeset dd24e5 in git for dyn_modules/syzextra/syzextra.cc

Timestamp:

Aug 1, 2012, 5:25:00 PM (11 years ago)

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '1d362c315e551a5b527ab0759f8839cf0e94f3a5')

Children:

495328d14a955b215ad10b598e995ab522243881

Parents:

026171e1f09fe373a5c6ea5ed0b8db1abeb952f3

git-author:

Oleksandr Motsak <motsak@mathematik.uni-kl.de>2012-08-01 17:25:00+02:00

git-committer:

Oleksandr Motsak <motsak@mathematik.uni-kl.de>2014-05-07 04:41:46+02:00

Message:

separated FindReducer into a separate class CReducerFinder (m_div)

TODO: deal with m_LS via another CReducerFinder?

NOTE: this change resulted in some speedups esp. for Hybrid approach (see schreyer.lib)

File:

• dyn_modules/syzextra/syzextra.cc (modified) (12 diffs)

dyn_modules/syzextra/syzextra.cc

@@ -251 +251 @@
   }
 
-
   // TODO/NOTE: input is supposed to be (reverse-) sorted wrt "(c,ds)"!??
 
@@ -489 +488 @@
 }
 
+
+CReducerFinder::CLeadingTerm::CLeadingTerm(unsigned int _label,  const poly _lt, const ring R):
+    m_sev( p_GetShortExpVector(_lt, R) ),  m_label( _label ),  m_lt( _lt )
+    { }
+
+
+CReducerFinder::~CReducerFinder()
+{
+  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++ )
+  {
+    const TReducers& v = it->second;
+    for(TReducers::const_iterator vit = v.begin(); vit != v.end(); vit++ )
+      delete const_cast<CLeadingTerm*>(*vit);
+  }
+}
+                                   
+CReducerFinder::CReducerFinder(const SchreyerSyzygyComputation& data): m_data(data), m_hash()
+{
+
+  const ideal& L = data.m_idLeads;
+  const ring&  R = data.m_rBaseRing;
+//   const SchreyerSyzygyComputationFlags& attributes = data.m_atttributes;
+// 
+//   const BOOLEAN __DEBUG__      = attributes.__DEBUG__;
+//   const BOOLEAN __SYZCHECK__   = attributes.__SYZCHECK__;
+//   const BOOLEAN __HYBRIDNF__   = attributes.__HYBRIDNF__;
+//   const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__;
+
+
+  assume( L != NULL );
+  assume( R != NULL );
+  assume( R == currRing );
+
+  for( int k = IDELEMS(L) - 1; k >= 0; k-- )
+  {
+    const poly a = L->m[k]; assume( a != NULL );
+
+    // NOTE: label is k \in 0 ... |L|-1!!!
+    m_hash[p_GetComp(a, R)].push_back( new CLeadingTerm(k, a, R) );
+  }
+}
+
+
 CLCM::CLCM(const SchreyerSyzygyComputation& data): std::vector<bool>(), m_data(data), m_compute(false)
 {
@@ -606 +648 @@
     poly a2 = pNext(a);    
 
+    // Splitting 2-terms Leading syzygy module
     if( a2 != NULL )
     {
@@ -633 +676 @@
       if( a2 == NULL )
       {
-        aa = p_Mult_mm(aa, L->m[r], R);
-        a2 = FindReducer(aa, a); 
+        aa = p_Mult_mm(aa, L->m[r], R); a2 = m_div.FindReducer(aa, a); 
       }
       assume( a2 != NULL );
@@ -677 +719 @@
 }
 
-poly SchreyerSyzygyComputation::FindReducer(poly product, poly syzterm) const
+poly CReducerFinder::FindReducer(const poly product, const poly syzterm) const
 {
 //  return FROM_NAMESPACE(INTERNAL, _FindReducer(product, syzterm, m_idLeads, m_LS, m_rBaseRing, m_atttributes));
@@ -685 +727 @@
 //                     const SchreyerSyzygyComputationFlags attributes)
 
-  const ideal& L = m_idLeads;
-  const ideal& LS = m_LS;
-  const ring& r = m_rBaseRing;
-  const SchreyerSyzygyComputationFlags& attributes = m_atttributes;
+  const ideal& L = m_data.m_idLeads;
+  const ideal& LS = m_data.m_LS;
+  const ring& r = m_data.m_rBaseRing;
+  const SchreyerSyzygyComputationFlags& attributes = m_data.m_atttributes;
 
 
@@ -700 +742 @@
   assume( L != NULL );
 
-  int c = 0;
+  long c = 0;
 
   if (syzterm != NULL)
@@ -706 +748 @@
 
   assume( c >= 0 && c < IDELEMS(L) );
-
-  if (__SYZCHECK__ && syzterm != NULL)
+  
+  if (__DEBUG__ && (syzterm != NULL))
   {
     const poly m = L->m[c];
@@ -722 +764 @@
   }
 
-  // looking for an appropriate diviser q = L[k]...
-  for( int k = IDELEMS(L)-1; k>= 0; k-- )
-  {
-    const poly p = L->m[k];    
-
-    // ... which divides the product, looking for the _1st_ appropriate one!
-    if( !p_LmDivisibleBy(p, product, r) )
-      continue;
+  const long comp = p_GetComp(product, r);
+  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
+
+  assume( comp >= 0 );
+
+   // looking for an appropriate diviser p = L[k]...
+#if 1
+  CReducersHash::const_iterator it = m_hash.find(p_GetComp(product, r)); // same module component
+   
+  if( it == m_hash.end() )
+    return NULL;
+
+  const TReducers& reducers = it->second;  
+  
+  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
+  {
+     const poly p = (*vit)->m_lt;
+
+     assume( p_GetComp(p, r) == comp );
+     
+     const int k = (*vit)->m_label;
+
+     assume( L->m[k] == p );
+     
+     const unsigned long p_sev = (*vit)->m_sev;
+
+     assume( p_sev == p_GetShortExpVector(p, r) );     
+#else  
+   for( int k = IDELEMS(L)-1; k>= 0; k-- )
+   {
+     const poly p = L->m[k];
+     
+     if ( p_GetComp(p, r) != comp )
+       continue;
+       
+     const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
+#endif
+     
+     if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
+       continue;     
+
+//     // ... which divides the product, looking for the _1st_ appropriate one!
+//     if( !p_LmDivisibleByNoComp(p, product, r) ) // included inside  p_LmShortDivisibleBy!
+//       continue;
 
 
@@ -758 +836 @@
       BOOLEAN ok = TRUE;
 
+      // TODO: FindReducer in LS !!! there should be no divisors!
       for(int kk = IDELEMS(LS)-1; kk>= 0; kk-- )
       {
@@ -842 +921 @@
   while (spoly != NULL)
   {
-    poly t = FindReducer(spoly, NULL);
+    poly t = m_div.FindReducer(spoly, NULL);
 
     p_LmDelete(&spoly, r);
@@ -942 +1021 @@
     // NOTE: only LT(term4reduction) should be used in the following:
     poly product = pp_Mult_mm(multiplier, term4reduction, r);
-    s = FindReducer(product, syztermCheck);
+    s = m_div.FindReducer(product, syztermCheck);
     p_Delete(&product, r);
   }