Changeset 6bfd78 in git

Timestamp:

Feb 12, 2013, 6:33:16 PM (10 years ago)

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')

Children:

13a431151fe0f14cbbed84bbf95df65eff7bc567

Parents:

1a4c34381788487464977b182596acb57f904d2f

git-author:

Oleksandr Motsak <motsak@mathematik.uni-kl.de>2013-02-12 18:33:16+01:00

git-committer:

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

Message:

Added CDivisorEnumerator(2) - to be used by CReducerFinder

add: FindReducer + multiplier!

Location:

dyn_modules/syzextra

Files:

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

dyn_modules/syzextra/syzextra.cc

@@ -1019 +1019 @@
 
   assume( p_GetComp(p, r) == p_GetComp(t, r) );
-  assume( p_GetComp(m, r) == 0 );
+// assume( p_GetComp(m, r) == 0 );
 
 //  const int k = m_label;
@@ -1036 +1036 @@
 }
 
+
+
+/// TODO:
+class CDivisorEnumerator: public SchreyerSyzygyComputationFlags
+{
+  private: 
+    const CReducerFinder& m_reds;
+    const poly m_product;
+    const unsigned long m_not_sev;
+    const unsigned long m_comp;
+
+    CReducerFinder::CReducersHash::const_iterator m_itr;
+    CReducerFinder::TReducers::const_iterator m_current, m_finish;
+
+    bool m_active;
+
+  public:
+    CDivisorEnumerator(const CReducerFinder& self, const poly product):
+        SchreyerSyzygyComputationFlags(self),
+        m_reds(self),
+        m_product(product),
+        m_not_sev(~p_GetShortExpVector(product, m_rBaseRing)),
+        m_comp(p_GetComp(product, m_rBaseRing)),
+        m_itr(), m_current(), m_finish(),
+        m_active(false)
+    {
+      assume( m_comp >= 0 );
+      assume( m_reds.m_L != NULL );  
+    }
+
+    inline bool Reset()
+    {
+      m_active = false;
+      
+      m_itr = m_reds.m_hash.find(m_comp);
+
+      if( m_itr == m_reds.m_hash.end() )
+        return false;
+
+      assume( m_itr->first == m_comp );
+
+      m_current = (m_itr->second).begin();
+      m_finish = (m_itr->second).end();
+
+      if (m_current == m_finish)
+        return false;
+
+//      m_active = true;
+      return true;      
+    }
+
+    const CLeadingTerm& Current() const
+    {
+      assume( m_active );
+      assume( m_current != m_finish );
+
+      return *(*m_current);
+    }
+ 
+    inline bool MoveNext()
+    {
+      assume( m_current != m_finish );
+
+      if( m_active )
+        ++m_current;
+      else
+        m_active = true; // for Current()
+      
+      // looking for the next good entry
+      for( ; m_current != m_finish; ++m_current )
+      {
+        assume( m_reds.m_L->m[Current().m_label] == Current().m_lt );
+
+        if( Current().DivisibilityCheck(m_product, m_not_sev, m_rBaseRing) )
+        {
+          if( __DEBUG__ )
+          {
+            Print("CDivisorEnumerator::MoveNext::est LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + Current().m_label);
+            dPrint(Current().m_lt, m_rBaseRing, m_rBaseRing, 1);
+          }
+
+//          m_active = true;
+          return true;
+        }
+      }
+
+      // the end... :(
+      assume( m_current == m_finish );
+      
+      m_active = false;
+      return false;
+    }
+};
+
+
+
 bool CReducerFinder::IsDivisible(const poly product) const
 {
+  CDivisorEnumerator itr(*this, product);
+  if( !itr.Reset() )
+    return false;
+
+  return itr.MoveNext();
+  
+/*  
   const ring& r = m_rBaseRing;
   
@@ -1047 +1150 @@
   CReducersHash::const_iterator it = m_hash.find(comp); // same module component
 
+  assume( m_L != NULL );  
+
   if( it == m_hash.end() )
     return false;
-
-  assume( m_L != NULL );  
 
   const TReducers& reducers = it->second;
@@ -1071 +1174 @@
 
   return false;
+*/  
 }
 
@@ -1104 +1208 @@
 #endif
 
+/// TODO:
+class CDivisorEnumerator2: public SchreyerSyzygyComputationFlags
+{
+  private: 
+    const CReducerFinder& m_reds;
+    const poly m_multiplier, m_term;
+    const unsigned long m_not_sev;
+    const unsigned long m_comp;
+
+    CReducerFinder::CReducersHash::const_iterator m_itr;
+    CReducerFinder::TReducers::const_iterator m_current, m_finish;
+
+    bool m_active;
+
+  public:
+    CDivisorEnumerator2(const CReducerFinder& self, const poly m, const poly t):
+        SchreyerSyzygyComputationFlags(self),
+        m_reds(self),
+        m_multiplier(m), m_term(t),
+        m_not_sev(~p_GetShortExpVector(m, t, m_rBaseRing)),
+        m_comp(p_GetComp(t, m_rBaseRing)),
+        m_itr(), m_current(), m_finish(),
+        m_active(false)
+    {
+      assume( m_comp >= 0 );
+      assume( m_reds.m_L != NULL );  
+      assume( m_multiplier != NULL ); 
+      assume( m_term != NULL );
+//      assume( p_GetComp(m_multiplier, m_rBaseRing) == 0 );
+    }
+
+    inline bool Reset()
+    {
+      m_active = false;
+      
+      m_itr = m_reds.m_hash.find(m_comp);
+
+      if( m_itr == m_reds.m_hash.end() )
+        return false;
+
+      assume( m_itr->first == m_comp );
+
+      m_current = (m_itr->second).begin();
+      m_finish = (m_itr->second).end();
+
+      if (m_current == m_finish)
+        return false;
+
+      return true;      
+    }
+
+    const CLeadingTerm& Current() const
+    {
+      assume( m_active );
+      assume( m_current != m_finish );
+
+      return *(*m_current);
+    }
+ 
+    inline bool MoveNext()
+    {
+      assume( m_current != m_finish );
+
+      if( m_active )
+        ++m_current;
+      else 
+        m_active = true;
+         
+      
+      // looking for the next good entry
+      for( ; m_current != m_finish; ++m_current )
+      {
+        assume( m_reds.m_L->m[Current().m_label] == Current().m_lt );
+
+        if( Current().DivisibilityCheck(m_multiplier, m_term, m_not_sev, m_rBaseRing) )
+        {
+          if( __DEBUG__ )
+          {
+            Print("CDivisorEnumerator::MoveNext::est LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + Current().m_label);
+            dPrint(Current().m_lt, m_rBaseRing, m_rBaseRing, 1);
+          }
+
+//          m_active = true;
+          return true;
+          
+        }
+      }
+
+      // the end... :(
+      assume( m_current == m_finish );
+      
+      m_active = false;
+      return false;
+    }
+};
+   
 poly CReducerFinder::FindReducer(const poly multiplier, const poly t,
-                                 const poly syzterm, const CReducerFinder& syz_checker) const
-{
-  // don't case about the module component of multiplier (as it may be
-  // the syzygy term)
+                                 const poly syzterm,
+                                 const CReducerFinder& syz_checker) const
+{
+  CDivisorEnumerator2 itr(*this, multiplier, t);
+  if( !itr.Reset() )
+    return NULL;
+
+  // don't care about the module component of multiplier (as it may be the syzygy term)
   // product = multiplier * t?
   const ring& r = m_rBaseRing;
@@ -1141 +1345 @@
     p_Delete(&pr, r);    
   }
-
-  const long comp = p_GetComp(t, r);
-  
-  const unsigned long not_sev = ~p_GetShortExpVector(multiplier, t, r); // !
-
-  assume( comp >= 0 );
-
-//   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!!!
-
-   // looking for an appropriate diviser p = L[k]...
-  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
-
-  if( it == m_hash.end() )
-    return NULL;
-
-  assume( m_L != NULL );
-
-  const TReducers& reducers = it->second;
-
+   
   const BOOLEAN to_check = (syz_checker.IsNonempty()); // __TAILREDSYZ__ && 
 
@@ -1174 +1353 @@
     p_SetCoeff0(q, 0, r); // for printing q
 
-  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
-  {
-
-    const poly p = (*vit)->m_lt;
-    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) );     
-
-//    if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
-//      continue;     
-
-    if( !(*vit)->DivisibilityCheck(multiplier, t, not_sev, r) )
-      continue;
-    
-    
-//    if (p_sev & not_sev) continue;
-//    if( !_p_LmDivisibleByNoComp(p, multiplier, t, r) ) continue;     
-
-
-    p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t        
+  while( itr.MoveNext() )
+  {
+    const poly p = itr.Current().m_lt;
+    const int k  = itr.Current().m_label;
+     
+    p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t // TODO: do it once?
     p_ExpVectorDiff(q, q, p, r); // (LM(product) / LM(L[k]))
     
@@ -1236 +1398 @@
 
   return NULL;
-}
-
-
-poly CReducerFinder::FindReducer(const poly product, const poly syzterm, const CReducerFinder& syz_checker) const
-{
-  const ring& r = m_rBaseRing;
-
-  assume( product != NULL );
-
-  const ideal& L = m_L; assume( L != NULL ); // for debug/testing only!
-
-  long c = 0;
-
-  if (syzterm != NULL)
-    c = p_GetComp(syzterm, r) - 1;
-
-  assume( c >= 0 && c < IDELEMS(L) );
-
-  if (__DEBUG__ && (syzterm != NULL))
-  {
-    const poly m = L->m[c];
-
-    assume( m != NULL ); assume( pNext(m) == NULL );
-
-    poly lm = p_Mult_mm(leadmonom(syzterm, r), m, r);
-    assume( p_EqualPolys(lm, product, r) );
-
-    //  def @@c = leadcomp(syzterm); int @@r = int(@@c);
-    //  def @@product = leadmonomial(syzterm) * L[@@r];
-
-    p_Delete(&lm, r);    
-  }
-
-  const long comp = p_GetComp(product, r);
-  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
-
-  assume( comp >= 0 );
+
+   
+  
+   
+   
+#if 0
+  const long comp = p_GetComp(t, r); assume( comp >= 0 );
+  const unsigned long not_sev = ~p_GetShortExpVector(multiplier, t, r); // !
 
 //   for( int k = IDELEMS(L)-1; k>= 0; k-- )
@@ -1282 +1415 @@
 // 
 //     const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
-  
+
    // looking for an appropriate diviser p = L[k]...
   CReducersHash::const_iterator it = m_hash.find(comp); // same module component
@@ -1293 +1426 @@
   const TReducers& reducers = it->second;
 
-  const BOOLEAN to_check = (syz_checker.IsNonempty()); // __TAILREDSYZ__ && 
-
-  const poly q = p_New(r); pNext(q) = NULL;
-
-  if( __DEBUG__ )
-    p_SetCoeff0(q, 0, r); // for printing q
-  
   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) );     
-
-    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;
-
-    p_ExpVectorDiff(q, product, p, r); // (LM(product) / LM(L[k]))
+//    const unsigned long p_sev = (*vit)->m_sev;
+//    assume( p_sev == p_GetShortExpVector(p, r) );     
+
+//    if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
+//      continue;     
+
+    if( !(*vit)->DivisibilityCheck(multiplier, t, not_sev, r) )
+      continue;
+    
+    
+//    if (p_sev & not_sev) continue;
+//    if( !_p_LmDivisibleByNoComp(p, multiplier, t, r) ) continue;     
+
+
+    p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t        
+    p_ExpVectorDiff(q, q, p, r); // (LM(product) / LM(L[k]))
+    
     p_SetComp(q, k + 1, r);
     p_Setm(q, r);
@@ -1345 +1474 @@
         PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
       }
+
+      continue;
+    }
+
+    number n = n_Mult( p_GetCoeff(multiplier, r), p_GetCoeff(t, r), r);
+    p_SetCoeff0(q, n_Neg( n_Div(n, p_GetCoeff(p, r), r), r), r);
+    n_Delete(&n, r);
+    
+    return q;
+  }
+
+  p_LmFree(q, r);
+
+  return NULL;
+#endif
+}
+
+
+poly CReducerFinder::FindReducer(const poly product, const poly syzterm, const CReducerFinder& syz_checker) const
+{
+  const ring& r = m_rBaseRing;
+
+  assume( product != NULL );
+
+  const ideal& L = m_L; assume( L != NULL ); // for debug/testing only!
+
+  long c = 0;
+
+  if (syzterm != NULL)
+    c = p_GetComp(syzterm, r) - 1;
+
+  assume( c >= 0 && c < IDELEMS(L) );
+
+  if (__DEBUG__ && (syzterm != NULL))
+  {
+    const poly m = L->m[c];
+
+    assume( m != NULL ); assume( pNext(m) == NULL );
+
+    poly lm = p_Mult_mm(leadmonom(syzterm, r), m, r);
+    assume( p_EqualPolys(lm, product, r) );
+
+    //  def @@c = leadcomp(syzterm); int @@r = int(@@c);
+    //  def @@product = leadmonomial(syzterm) * L[@@r];
+
+    p_Delete(&lm, r);    
+  }
+
+  const long comp = p_GetComp(product, r);
+  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
+
+  assume( comp >= 0 );
+
+//   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!!!
+  
+   // looking for an appropriate diviser p = L[k]...
+  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
+
+  if( it == m_hash.end() )
+    return NULL;
+
+  assume( m_L != NULL );
+
+  const TReducers& reducers = it->second;
+
+  const BOOLEAN to_check = (syz_checker.IsNonempty()); // __TAILREDSYZ__ && 
+
+  const poly q = p_New(r); pNext(q) = NULL;
+
+  if( __DEBUG__ )
+    p_SetCoeff0(q, 0, r); // for printing q
+  
+  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) );     
+
+    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;
+
+    p_ExpVectorDiff(q, product, p, r); // (LM(product) / LM(L[k]))
+    p_SetComp(q, k + 1, r);
+    p_Setm(q, r);
+
+    // cannot allow something like: a*gen(i) - a*gen(i)
+    if (syzterm != NULL && (k == c))
+      if (p_ExpVectorEqual(syzterm, q, r))
+      {
+        if( __DEBUG__ )
+        {
+          Print("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
+          dPrint(syzterm, r, r, 1);
+        }    
+
+        continue;
+      }
+
+    // while the complement (the fraction) is not reducible by leading syzygies 
+    if( to_check && syz_checker.IsDivisible(q) ) 
+    {
+      if( __DEBUG__ )
+      {
+        PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
+      }
       
       continue;

dyn_modules/syzextra/syzextra.h

@@ -139 +139 @@
 class CReducerFinder: public SchreyerSyzygyComputationFlags
 {
+  friend class CDivisorEnumerator;
+  friend class CDivisorEnumerator2;
   private:
     typedef long TComponentKey;
@@ -144 +146 @@
     typedef std::map< TComponentKey, TReducers> CReducersHash;
 
-/*
-    /// TODO:
-    class const_iterator: public TReducers::const_iterator
-    {
-      typedef TReducers::const_iterator TBase;
-      private: 
-//        const TReducers& m_reds;
-        const TBase m_the_end;
-
-        const_iterator(TBase start, TBase end):
-            TBase(start), m_the_end(end)
-        { find_proper(); }
-                    
-      public:        
-        inline bool at_end() const { return m_the_end == (*this); }
-
-        inline const_iterator& operator++()
-        {
-          find_next();
-          return *this;
-        }
-        
-        inline const_iterator operator++(int)
-        {
-          const_iterator tmp(*this);
-          find_next();
-          return tmp;
-        }
-
-      protected:
-        bool is_proper() const; // difficult - needs all of CReducerFinder internals!?
-        
-        inline void find_next()
-        {
-          while (!at_end())
-          {
-            static_cast<TBase*>(this)->operator++();
-            if( is_proper() ) break;
-          }
-        }
-    };
-*/
-    
   public:
     /// goes over all leading terms