Changeset 1a4c343 in git

Timestamp:

Sep 12, 2012, 6:31:08 PM (12 years ago)

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')

Children:

6bfd784a2ae971e2eddfc0b8e22c9b276d9aa341

Parents:

1cf13b33d55ec9d3d521a0c38c579e836bd8400d

git-author:

Oleksandr Motsak <motsak@mathematik.uni-kl.de>2012-09-12 18:31:08+02:00

git-committer:

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

Message:

Starting tail terms preprocessing:

TODO: need a vector of "term + arrow_cache" structures
TODO: need a better CReducerFinder for arrow_cache...!!!

add: DivisibilityCheck + Separation of minor preparations for tail terms preprocessing!

NOTE: not yet :(((

Location:

dyn_modules/syzextra

Files:

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

dyn_modules/syzextra/syzextra.cc

@@ -222 +222 @@
 }
 
+/// Clean up all the accumulated data
+void SchreyerSyzygyComputation::CleanUp()
+{
+  /*
+  for( TTailTerms::const_iterator it = m_idTailTerms.begin(); it != m_idTailTerms.end(); it++ )
+  {
+    const TTail& v = *it;
+    for(TTail::const_iterator vit = v.begin(); vit != v.end(); vit++ )
+      delete const_cast<CTailTerm*>(*vit);
+  }
+  */
+}
+
+
+
+void SchreyerSyzygyComputation::SetUpTailTerms(const ideal idTails)
+{
+  assume( idTails != NULL );
+  assume( idTails->m != NULL );
+/*  
+  m_idTailTerms.resize( IDELEMS(idTails) );
+  
+  for( unsigned int p = IDELEMS(idTails) - 1; p >= 0; p -- )
+  {
+    TTail& v = m_idTailTerms[p];
+    poly t = idTails->m[p];
+    v.resize( pLength(t) );
+
+    unsigned int pp = 0;
+    
+    while( t != NULL )
+    {
+      assume( t != NULL );
+      // TODO: compute L:t!
+//      ideal reducers;      
+//      CReducerFinder m_reducers
+      
+      CTailTerm* d = v[pp] = new CTailTerm();
+      
+      ++pp; pIter(t);
+    }
+  }
+*/
+}
+
+
+
 ideal SchreyerSyzygyComputation::Compute1LeadingSyzygyTerms()
 {
@@ -851 +898 @@
    
 
-CReducerFinder::CLeadingTerm::CLeadingTerm(unsigned int _label,  const poly _lt, const ring R):
+CLeadingTerm::CLeadingTerm(unsigned int _label,  const poly _lt, const ring R):
     m_sev( p_GetShortExpVector(_lt, R) ),  m_label( _label ),  m_lt( _lt )
 { }
@@ -900 +947 @@
     Initialize(L);
 }
-
-
-bool CReducerFinder::IsDivisible(const poly product) const
-{
-  const ring& r = m_rBaseRing;
-  
-  const long comp = p_GetComp(product, r);
-  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
-
-  assume( comp >= 0 );
-
-  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
-
-  if( it == m_hash.end() )
-    return false;
-
-  assume( m_L != 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( m_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( __DEBUG__ )
-    {
-      Print("_FindReducer::Test LS: q is divisible by LS[%d] !:((, diviser is: ", k+1);
-      dPrint(p, r, r, 1);
-    }
-
-    return true;
-  }
-
-  return false;
-}
-
-
-#ifndef NDEBUG
-void CReducerFinder::DebugPrint() const
-{
-  const ring& r = m_rBaseRing;
-
-  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++)
-  {
-    Print("Hash Key: %d, Values: \n", it->first);
-    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) == it->first );
-
-      const int k = (*vit)->m_label;
-
-      assume( m_L->m[k] == p );
-
-      const unsigned long p_sev = (*vit)->m_sev;
-
-      assume( p_sev == p_GetShortExpVector(p, r) );
-
-      Print("L[%d]: ", k); dPrint(p, r, r, 0); Print("SEV: %dl\n", p_sev);      
-    }
-  }
-}
-#endif
-
 
 /// _p_LmDivisibleByNoComp for a | b*c
@@ -1027 +994 @@
 }
 
+bool CLeadingTerm::DivisibilityCheck(const poly product, const unsigned long not_sev, const ring r) const
+{
+  const poly p = m_lt;
+
+  assume( p_GetComp(p, r) == p_GetComp(product, r) );
+
+  const int k = m_label;
+
+//  assume( m_L->m[k] == p );
+
+  const unsigned long p_sev = m_sev;
+
+  assume( p_sev == p_GetShortExpVector(p, r) );     
+
+  return p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r);
+
+}
+
+/// as DivisibilityCheck(multiplier * t, ...) for monomial 'm'
+/// and a module term 't'
+bool CLeadingTerm::DivisibilityCheck(const poly m, const poly t, const unsigned long not_sev, const ring r) const
+{
+  const poly p = m_lt;
+
+  assume( p_GetComp(p, r) == p_GetComp(t, r) );
+  assume( p_GetComp(m, r) == 0 );
+
+//  const int k = m_label;
+//  assume( m_L->m[k] == p );
+
+  const unsigned long p_sev = m_sev;
+  assume( p_sev == p_GetShortExpVector(p, r) );     
+
+  if (p_sev & not_sev)
+    return false;
+
+  return _p_LmDivisibleByNoComp(p, m, t, r);
+
+//  return p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r);
+
+}
+
+bool CReducerFinder::IsDivisible(const poly product) const
+{
+  const ring& r = m_rBaseRing;
+  
+  const long comp = p_GetComp(product, r);
+  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
+
+  assume( comp >= 0 );
+
+  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
+
+  if( it == m_hash.end() )
+    return false;
+
+  assume( m_L != NULL );  
+
+  const TReducers& reducers = it->second;
+
+  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
+  {
+    assume( m_L->m[(*vit)->m_label] == (*vit)->m_lt );
+
+    if( (*vit)->DivisibilityCheck(product, not_sev, r) )
+    {
+      if( __DEBUG__ )
+      {
+        Print("_FindReducer::Test LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + (*vit)->m_label);
+        dPrint((*vit)->m_lt, r, r, 1);
+      }
+
+      return true;
+    }
+  }
+
+  return false;
+}
+
+
+#ifndef NDEBUG
+void CReducerFinder::DebugPrint() const
+{
+  const ring& r = m_rBaseRing;
+
+  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++)
+  {
+    Print("Hash Key: %d, Values: \n", it->first);
+    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) == it->first );
+
+      const int k = (*vit)->m_label;
+
+      assume( m_L->m[k] == p );
+
+      const unsigned long p_sev = (*vit)->m_sev;
+
+      assume( p_sev == p_GetShortExpVector(p, r) );
+
+      Print("L[%d]: ", k); dPrint(p, r, r, 0); Print("SEV: %dl\n", p_sev);      
+    }
+  }
+}
+#endif
 
 poly CReducerFinder::FindReducer(const poly multiplier, const poly t,
@@ -1100 +1176 @@
   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) );     
+//    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 (p_sev & not_sev)
+    if( !(*vit)->DivisibilityCheck(multiplier, t, not_sev, r) )
       continue;
-
-    if( !_p_LmDivisibleByNoComp(p, multiplier, t, r) )
-      continue;     
+    
+    
+//    if (p_sev & not_sev) continue;
+//    if( !_p_LmDivisibleByNoComp(p, multiplier, t, r) ) continue;     
 
 

dyn_modules/syzextra/syzextra.h

@@ -112 +112 @@
 
 
+class CLeadingTerm
+{
+  public: 
+    CLeadingTerm(unsigned int label,  const poly lt, const ring);
+
+  public:
+
+    const unsigned long m_sev; ///< not short exp. vector
+        // NOTE/TODO: either of the following should be enough:
+    const unsigned int  m_label; ///< index in the main L[] + 1
+    const poly          m_lt; ///< the leading term itself L[label-1]
+
+  public:
+    bool DivisibilityCheck(const poly product, const unsigned long not_sev, const ring r) const;
+    bool DivisibilityCheck(const poly multiplier, const poly t, const unsigned long not_sev, const ring r) const;
+
+  private:
+    // disable the following:
+    CLeadingTerm();
+    CLeadingTerm(const CLeadingTerm&);
+    void operator=(const CLeadingTerm&);
+};
+
+
+// TODO: needs a specialized variant without a component (hash!)
 class CReducerFinder: public SchreyerSyzygyComputationFlags
 {
   private:
-    class CLeadingTerm
-    {
-      public: 
-        CLeadingTerm(unsigned int id,  const poly p, const ring);
-
-      private:
-        CLeadingTerm();
-
-      public:
-
-        const unsigned long m_sev; ///< not short exp. vector
-        // NOTE/TODO: either of the following should be enough:
-        const unsigned int  m_label; ///< index in the main L[] + 1
-        const poly          m_lt; ///< the leading term itself L[label-1]
-    };
-
     typedef long TComponentKey;
     typedef std::vector<const CLeadingTerm*> TReducers;
     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:
@@ -143 +195 @@
     ~CReducerFinder();
 
-    // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?    
-    poly FindReducer(const poly product, const poly syzterm, const CReducerFinder& checker) const;
+    // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?
+    poly // const_iterator // TODO: return const_iterator it, s.th: it->m_lt is the needed 
+    FindReducer(const poly product, const poly syzterm, const CReducerFinder& checker) const;
 
     bool IsDivisible(const poly q) const;
@@ -160 +213 @@
 
     CReducersHash m_hash; // can also be replaced with a vector indexed by components
+
+  private:
+    CReducerFinder(const CReducerFinder&);
+    void operator=(const CReducerFinder&);
 };
 
@@ -180 +237 @@
   
   public:
-
     /// Construct a global object for given input data (separated into leads & tails)
     SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const SchreyerSyzygyComputationFlags setting):
@@ -188 +244 @@
         m_lcm(m_idLeads, setting), m_div(m_idLeads, setting), m_checker(NULL, setting)
     {
+      if( __TAILREDSYZ__ && !__IGNORETAILS__)
+      {
+        if( idTails != NULL )
+          SetUpTailTerms(idTails);
+      }
     }
 
@@ -197 +258 @@
         m_lcm(m_idLeads, setting), m_div(m_idLeads, setting), m_checker(NULL, setting)
     {
-      if( __TAILREDSYZ__ && !__IGNORETAILS__ && syzLeads != NULL )
-        m_checker.Initialize(syzLeads);
+      if( __TAILREDSYZ__ && !__IGNORETAILS__)
+      {
+        if (syzLeads != NULL)
+          m_checker.Initialize(syzLeads);
+        if( idTails != NULL )
+          SetUpTailTerms(idTails);
+      }
     }
 
-    
     /// Destructor should not destruct the resulting m_syzLeads, m_syzTails. 
     ~SchreyerSyzygyComputation(){ CleanUp(); }
+
+    /// Convert the given ideal of tails into the internal representation (with reducers!)
+    void SetUpTailTerms(const ideal idTails);
+    
+    void CleanUp();
 
     /// Read off the results while detaching them from this object
@@ -233 +303 @@
     // 
     poly TraverseNF(const poly syz_lead, const poly syz_2 = NULL) const;
+
     
   public:
@@ -247 +318 @@
     ideal Compute2LeadingSyzygyTerms();
 
-    /// Clean up all the accumulated data
-    void CleanUp() {}
-
   private:
     /// input leading terms
@@ -273 +341 @@
 
     /*mutable?*/ ideal m_LS; ///< leading syzygy terms used for reducing syzygy tails
+
+    /*
+    // need more data here:
+    // (m_idLeads : m_tailterm) = (m, pos, compl), s.th: compl * m_tailterm divides m_idLeads[pos]
+    // but resulting sysygy compl * gen(pos) should not be in 
+    // Idea: extend CReducerFinder??!!
+    struct CTailTerm
+    {
+      const poly m_tailterm;
+      
+      const CReducerFinder m_reducers; // positions are labels (in m_idLeads)...
+      // compl - to be computed if needed? 
+
+      CTailTerm(const poly tt, const CReducerFinder reds): m_tailterm(tt), m_reducers(reds) {}
+    };
+
+    typedef std::vector<const CTailTerm*> TTail;
+    typedef std::vector<TTail> TTailTerms;
+    
+    TTailTerms m_idTailTerms;
+    */
 };