Changeset 1a4c343 in git


Ignore:
Timestamp:
Sep 12, 2012, 6:31:08 PM (10 years ago)
Author:
Oleksandr Motsak <motsak@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '2234726c50d679d6664181a5c72f75a6fd64a787')
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:
2 edited

Legend:

Unmodified
Added
Removed
  • dyn_modules/syzextra/syzextra.cc

    r1cf13b r1a4c343  
    222222}
    223223
     224/// Clean up all the accumulated data
     225void SchreyerSyzygyComputation::CleanUp()
     226{
     227  /*
     228  for( TTailTerms::const_iterator it = m_idTailTerms.begin(); it != m_idTailTerms.end(); it++ )
     229  {
     230    const TTail& v = *it;
     231    for(TTail::const_iterator vit = v.begin(); vit != v.end(); vit++ )
     232      delete const_cast<CTailTerm*>(*vit);
     233  }
     234  */
     235}
     236
     237
     238
     239void SchreyerSyzygyComputation::SetUpTailTerms(const ideal idTails)
     240{
     241  assume( idTails != NULL );
     242  assume( idTails->m != NULL );
     243/* 
     244  m_idTailTerms.resize( IDELEMS(idTails) );
     245 
     246  for( unsigned int p = IDELEMS(idTails) - 1; p >= 0; p -- )
     247  {
     248    TTail& v = m_idTailTerms[p];
     249    poly t = idTails->m[p];
     250    v.resize( pLength(t) );
     251
     252    unsigned int pp = 0;
     253   
     254    while( t != NULL )
     255    {
     256      assume( t != NULL );
     257      // TODO: compute L:t!
     258//      ideal reducers;     
     259//      CReducerFinder m_reducers
     260     
     261      CTailTerm* d = v[pp] = new CTailTerm();
     262     
     263      ++pp; pIter(t);
     264    }
     265  }
     266*/
     267}
     268
     269
     270
    224271ideal SchreyerSyzygyComputation::Compute1LeadingSyzygyTerms()
    225272{
     
    851898   
    852899
    853 CReducerFinder::CLeadingTerm::CLeadingTerm(unsigned int _label,  const poly _lt, const ring R):
     900CLeadingTerm::CLeadingTerm(unsigned int _label,  const poly _lt, const ring R):
    854901    m_sev( p_GetShortExpVector(_lt, R) ),  m_label( _label ),  m_lt( _lt )
    855902{ }
     
    900947    Initialize(L);
    901948}
    902 
    903 
    904 bool CReducerFinder::IsDivisible(const poly product) const
    905 {
    906   const ring& r = m_rBaseRing;
    907  
    908   const long comp = p_GetComp(product, r);
    909   const unsigned long not_sev = ~p_GetShortExpVector(product, r);
    910 
    911   assume( comp >= 0 );
    912 
    913   CReducersHash::const_iterator it = m_hash.find(comp); // same module component
    914 
    915   if( it == m_hash.end() )
    916     return false;
    917 
    918   assume( m_L != NULL ); 
    919 
    920   const TReducers& reducers = it->second;
    921 
    922   for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
    923   {
    924     const poly p = (*vit)->m_lt;
    925 
    926     assume( p_GetComp(p, r) == comp );
    927 
    928     const int k = (*vit)->m_label;
    929 
    930     assume( m_L->m[k] == p );
    931 
    932     const unsigned long p_sev = (*vit)->m_sev;
    933 
    934     assume( p_sev == p_GetShortExpVector(p, r) );     
    935 
    936     if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
    937       continue;
    938 
    939     if( __DEBUG__ )
    940     {
    941       Print("_FindReducer::Test LS: q is divisible by LS[%d] !:((, diviser is: ", k+1);
    942       dPrint(p, r, r, 1);
    943     }
    944 
    945     return true;
    946   }
    947 
    948   return false;
    949 }
    950 
    951 
    952 #ifndef NDEBUG
    953 void CReducerFinder::DebugPrint() const
    954 {
    955   const ring& r = m_rBaseRing;
    956 
    957   for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++)
    958   {
    959     Print("Hash Key: %d, Values: \n", it->first);
    960     const TReducers& reducers = it->second;
    961 
    962     for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
    963     {
    964       const poly p = (*vit)->m_lt;
    965 
    966       assume( p_GetComp(p, r) == it->first );
    967 
    968       const int k = (*vit)->m_label;
    969 
    970       assume( m_L->m[k] == p );
    971 
    972       const unsigned long p_sev = (*vit)->m_sev;
    973 
    974       assume( p_sev == p_GetShortExpVector(p, r) );
    975 
    976       Print("L[%d]: ", k); dPrint(p, r, r, 0); Print("SEV: %dl\n", p_sev);     
    977     }
    978   }
    979 }
    980 #endif
    981 
    982949
    983950/// _p_LmDivisibleByNoComp for a | b*c
     
    1027994}
    1028995
     996bool CLeadingTerm::DivisibilityCheck(const poly product, const unsigned long not_sev, const ring r) const
     997{
     998  const poly p = m_lt;
     999
     1000  assume( p_GetComp(p, r) == p_GetComp(product, r) );
     1001
     1002  const int k = m_label;
     1003
     1004//  assume( m_L->m[k] == p );
     1005
     1006  const unsigned long p_sev = m_sev;
     1007
     1008  assume( p_sev == p_GetShortExpVector(p, r) );     
     1009
     1010  return p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r);
     1011
     1012}
     1013
     1014/// as DivisibilityCheck(multiplier * t, ...) for monomial 'm'
     1015/// and a module term 't'
     1016bool CLeadingTerm::DivisibilityCheck(const poly m, const poly t, const unsigned long not_sev, const ring r) const
     1017{
     1018  const poly p = m_lt;
     1019
     1020  assume( p_GetComp(p, r) == p_GetComp(t, r) );
     1021  assume( p_GetComp(m, r) == 0 );
     1022
     1023//  const int k = m_label;
     1024//  assume( m_L->m[k] == p );
     1025
     1026  const unsigned long p_sev = m_sev;
     1027  assume( p_sev == p_GetShortExpVector(p, r) );     
     1028
     1029  if (p_sev & not_sev)
     1030    return false;
     1031
     1032  return _p_LmDivisibleByNoComp(p, m, t, r);
     1033
     1034//  return p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r);
     1035
     1036}
     1037
     1038bool CReducerFinder::IsDivisible(const poly product) const
     1039{
     1040  const ring& r = m_rBaseRing;
     1041 
     1042  const long comp = p_GetComp(product, r);
     1043  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
     1044
     1045  assume( comp >= 0 );
     1046
     1047  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
     1048
     1049  if( it == m_hash.end() )
     1050    return false;
     1051
     1052  assume( m_L != NULL ); 
     1053
     1054  const TReducers& reducers = it->second;
     1055
     1056  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
     1057  {
     1058    assume( m_L->m[(*vit)->m_label] == (*vit)->m_lt );
     1059
     1060    if( (*vit)->DivisibilityCheck(product, not_sev, r) )
     1061    {
     1062      if( __DEBUG__ )
     1063      {
     1064        Print("_FindReducer::Test LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + (*vit)->m_label);
     1065        dPrint((*vit)->m_lt, r, r, 1);
     1066      }
     1067
     1068      return true;
     1069    }
     1070  }
     1071
     1072  return false;
     1073}
     1074
     1075
     1076#ifndef NDEBUG
     1077void CReducerFinder::DebugPrint() const
     1078{
     1079  const ring& r = m_rBaseRing;
     1080
     1081  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++)
     1082  {
     1083    Print("Hash Key: %d, Values: \n", it->first);
     1084    const TReducers& reducers = it->second;
     1085
     1086    for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
     1087    {
     1088      const poly p = (*vit)->m_lt;
     1089
     1090      assume( p_GetComp(p, r) == it->first );
     1091
     1092      const int k = (*vit)->m_label;
     1093
     1094      assume( m_L->m[k] == p );
     1095
     1096      const unsigned long p_sev = (*vit)->m_sev;
     1097
     1098      assume( p_sev == p_GetShortExpVector(p, r) );
     1099
     1100      Print("L[%d]: ", k); dPrint(p, r, r, 0); Print("SEV: %dl\n", p_sev);     
     1101    }
     1102  }
     1103}
     1104#endif
    10291105
    10301106poly CReducerFinder::FindReducer(const poly multiplier, const poly t,
     
    11001176  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
    11011177  {
     1178
    11021179    const poly p = (*vit)->m_lt;
    1103 
    1104     assume( p_GetComp(p, r) == comp );
    1105 
    11061180    const int k = (*vit)->m_label;
    11071181
    11081182    assume( L->m[k] == p );
    11091183
    1110     const unsigned long p_sev = (*vit)->m_sev;
    1111 
    1112     assume( p_sev == p_GetShortExpVector(p, r) );     
     1184//    const unsigned long p_sev = (*vit)->m_sev;
     1185//    assume( p_sev == p_GetShortExpVector(p, r) );     
    11131186
    11141187//    if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
    11151188//      continue;     
    11161189
    1117     if (p_sev & not_sev)
     1190    if( !(*vit)->DivisibilityCheck(multiplier, t, not_sev, r) )
    11181191      continue;
    1119 
    1120     if( !_p_LmDivisibleByNoComp(p, multiplier, t, r) )
    1121       continue;     
     1192   
     1193   
     1194//    if (p_sev & not_sev) continue;
     1195//    if( !_p_LmDivisibleByNoComp(p, multiplier, t, r) ) continue;     
    11221196
    11231197
  • dyn_modules/syzextra/syzextra.h

    r1cf13b r1a4c343  
    112112
    113113
     114class CLeadingTerm
     115{
     116  public:
     117    CLeadingTerm(unsigned int label,  const poly lt, const ring);
     118
     119  public:
     120
     121    const unsigned long m_sev; ///< not short exp. vector
     122        // NOTE/TODO: either of the following should be enough:
     123    const unsigned int  m_label; ///< index in the main L[] + 1
     124    const poly          m_lt; ///< the leading term itself L[label-1]
     125
     126  public:
     127    bool DivisibilityCheck(const poly product, const unsigned long not_sev, const ring r) const;
     128    bool DivisibilityCheck(const poly multiplier, const poly t, const unsigned long not_sev, const ring r) const;
     129
     130  private:
     131    // disable the following:
     132    CLeadingTerm();
     133    CLeadingTerm(const CLeadingTerm&);
     134    void operator=(const CLeadingTerm&);
     135};
     136
     137
     138// TODO: needs a specialized variant without a component (hash!)
    114139class CReducerFinder: public SchreyerSyzygyComputationFlags
    115140{
    116141  private:
    117     class CLeadingTerm
    118     {
    119       public:
    120         CLeadingTerm(unsigned int id,  const poly p, const ring);
    121 
    122       private:
    123         CLeadingTerm();
    124 
    125       public:
    126 
    127         const unsigned long m_sev; ///< not short exp. vector
    128         // NOTE/TODO: either of the following should be enough:
    129         const unsigned int  m_label; ///< index in the main L[] + 1
    130         const poly          m_lt; ///< the leading term itself L[label-1]
    131     };
    132 
    133142    typedef long TComponentKey;
    134143    typedef std::vector<const CLeadingTerm*> TReducers;
    135144    typedef std::map< TComponentKey, TReducers> CReducersHash;
     145
     146/*
     147    /// TODO:
     148    class const_iterator: public TReducers::const_iterator
     149    {
     150      typedef TReducers::const_iterator TBase;
     151      private:
     152//        const TReducers& m_reds;
     153        const TBase m_the_end;
     154
     155        const_iterator(TBase start, TBase end):
     156            TBase(start), m_the_end(end)
     157        { find_proper(); }
     158                   
     159      public:       
     160        inline bool at_end() const { return m_the_end == (*this); }
     161
     162        inline const_iterator& operator++()
     163        {
     164          find_next();
     165          return *this;
     166        }
     167       
     168        inline const_iterator operator++(int)
     169        {
     170          const_iterator tmp(*this);
     171          find_next();
     172          return tmp;
     173        }
     174
     175      protected:
     176        bool is_proper() const; // difficult - needs all of CReducerFinder internals!?
     177       
     178        inline void find_next()
     179        {
     180          while (!at_end())
     181          {
     182            static_cast<TBase*>(this)->operator++();
     183            if( is_proper() ) break;
     184          }
     185        }
     186    };
     187*/
    136188   
    137189  public:
     
    143195    ~CReducerFinder();
    144196
    145     // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?   
    146     poly FindReducer(const poly product, const poly syzterm, const CReducerFinder& checker) const;
     197    // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?
     198    poly // const_iterator // TODO: return const_iterator it, s.th: it->m_lt is the needed
     199    FindReducer(const poly product, const poly syzterm, const CReducerFinder& checker) const;
    147200
    148201    bool IsDivisible(const poly q) const;
     
    160213
    161214    CReducersHash m_hash; // can also be replaced with a vector indexed by components
     215
     216  private:
     217    CReducerFinder(const CReducerFinder&);
     218    void operator=(const CReducerFinder&);
    162219};
    163220
     
    180237 
    181238  public:
    182 
    183239    /// Construct a global object for given input data (separated into leads & tails)
    184240    SchreyerSyzygyComputation(const ideal idLeads, const ideal idTails, const SchreyerSyzygyComputationFlags setting):
     
    188244        m_lcm(m_idLeads, setting), m_div(m_idLeads, setting), m_checker(NULL, setting)
    189245    {
     246      if( __TAILREDSYZ__ && !__IGNORETAILS__)
     247      {
     248        if( idTails != NULL )
     249          SetUpTailTerms(idTails);
     250      }
    190251    }
    191252
     
    197258        m_lcm(m_idLeads, setting), m_div(m_idLeads, setting), m_checker(NULL, setting)
    198259    {
    199       if( __TAILREDSYZ__ && !__IGNORETAILS__ && syzLeads != NULL )
    200         m_checker.Initialize(syzLeads);
     260      if( __TAILREDSYZ__ && !__IGNORETAILS__)
     261      {
     262        if (syzLeads != NULL)
     263          m_checker.Initialize(syzLeads);
     264        if( idTails != NULL )
     265          SetUpTailTerms(idTails);
     266      }
    201267    }
    202268
    203    
    204269    /// Destructor should not destruct the resulting m_syzLeads, m_syzTails.
    205270    ~SchreyerSyzygyComputation(){ CleanUp(); }
     271
     272    /// Convert the given ideal of tails into the internal representation (with reducers!)
     273    void SetUpTailTerms(const ideal idTails);
     274   
     275    void CleanUp();
    206276
    207277    /// Read off the results while detaching them from this object
     
    233303    //
    234304    poly TraverseNF(const poly syz_lead, const poly syz_2 = NULL) const;
     305
    235306   
    236307  public:
     
    247318    ideal Compute2LeadingSyzygyTerms();
    248319
    249     /// Clean up all the accumulated data
    250     void CleanUp() {}
    251 
    252320  private:
    253321    /// input leading terms
     
    273341
    274342    /*mutable?*/ ideal m_LS; ///< leading syzygy terms used for reducing syzygy tails
     343
     344    /*
     345    // need more data here:
     346    // (m_idLeads : m_tailterm) = (m, pos, compl), s.th: compl * m_tailterm divides m_idLeads[pos]
     347    // but resulting sysygy compl * gen(pos) should not be in
     348    // Idea: extend CReducerFinder??!!
     349    struct CTailTerm
     350    {
     351      const poly m_tailterm;
     352     
     353      const CReducerFinder m_reducers; // positions are labels (in m_idLeads)...
     354      // compl - to be computed if needed?
     355
     356      CTailTerm(const poly tt, const CReducerFinder reds): m_tailterm(tt), m_reducers(reds) {}
     357    };
     358
     359    typedef std::vector<const CTailTerm*> TTail;
     360    typedef std::vector<TTail> TTailTerms;
     361   
     362    TTailTerms m_idTailTerms;
     363    */
    275364};
    276365
Note: See TracChangeset for help on using the changeset viewer.