Changeset dd24e5 in git


Ignore:
Timestamp:
Aug 1, 2012, 5:25:00 PM (12 years ago)
Author:
Oleksandr Motsak <motsak@…>
Branches:
(u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
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)
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/schreyer.lib

    r026171 rdd24e5  
    23492349
    23502350
    2351 proc testSimple()
    2352 {
     2351proc testSimple(list #)
     2352{
     2353  def DEBUG = 0;
     2354  if(size(#) > 0) { DEBUG = #[1]; }
     2355
    23532356  system("--min-time", "1.0");
    23542357  system("--ticks-per-sec", 1);
    23552358
    23562359  // TODO: only for now!!
    2357   attrib(SSinit, "DEBUG", 0);
     2360  attrib(SSinit, "DEBUG", (DEBUG > 0));
    23582361  attrib(SSinit, "SYZCHECK", 1);
    23592362  attrib(SSinit, "KERCHECK", 1);
     
    24712474  TestSSresAttribs2tr(M);
    24722475/*
    2473 options:  1 1 0 :  Time:  10 (35 without LCM)
    2474 options:  1 1 1 :  Time:  25
    2475 lres  Time:  5/6
     2476options:  1 1 0 :  Time:  9/10 (35 without LCM)
     2477options:  1 1 1 :  Time:  8/25
     2478lres  Time:  5
    24762479nres  Time:  5
    24772480sres  Time:  693
     
    25502553  TestSSresAttribs2tr(M);
    25512554/*
    2552 options:  1 1 0 :  Time:  92 (316 without LCM)
    2553 options:  1 1 1 :  Time:  202
    2554 lres  Time:  27/28
    2555 nres  Time:  21/23
     2555options:  1 1 0 :  Time:  73/92 (316 without LCM)
     2556options:  1 1 1 :  Time:  43/202
     2557lres  Time:  25
     2558nres  Time:  20
    25562559sres  Time:  71
    25572560*/
  • dyn_modules/syzextra/syzextra.cc

    r026171 rdd24e5  
    251251  }
    252252
    253 
    254253  // TODO/NOTE: input is supposed to be (reverse-) sorted wrt "(c,ds)"!??
    255254
     
    489488}
    490489
     490
     491CReducerFinder::CLeadingTerm::CLeadingTerm(unsigned int _label,  const poly _lt, const ring R):
     492    m_sev( p_GetShortExpVector(_lt, R) ),  m_label( _label ),  m_lt( _lt )
     493    { }
     494
     495
     496CReducerFinder::~CReducerFinder()
     497{
     498  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++ )
     499  {
     500    const TReducers& v = it->second;
     501    for(TReducers::const_iterator vit = v.begin(); vit != v.end(); vit++ )
     502      delete const_cast<CLeadingTerm*>(*vit);
     503  }
     504}
     505                                   
     506CReducerFinder::CReducerFinder(const SchreyerSyzygyComputation& data): m_data(data), m_hash()
     507{
     508
     509  const ideal& L = data.m_idLeads;
     510  const ring&  R = data.m_rBaseRing;
     511//   const SchreyerSyzygyComputationFlags& attributes = data.m_atttributes;
     512//
     513//   const BOOLEAN __DEBUG__      = attributes.__DEBUG__;
     514//   const BOOLEAN __SYZCHECK__   = attributes.__SYZCHECK__;
     515//   const BOOLEAN __HYBRIDNF__   = attributes.__HYBRIDNF__;
     516//   const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__;
     517
     518
     519  assume( L != NULL );
     520  assume( R != NULL );
     521  assume( R == currRing );
     522
     523  for( int k = IDELEMS(L) - 1; k >= 0; k-- )
     524  {
     525    const poly a = L->m[k]; assume( a != NULL );
     526
     527    // NOTE: label is k \in 0 ... |L|-1!!!
     528    m_hash[p_GetComp(a, R)].push_back( new CLeadingTerm(k, a, R) );
     529  }
     530}
     531
     532
    491533CLCM::CLCM(const SchreyerSyzygyComputation& data): std::vector<bool>(), m_data(data), m_compute(false)
    492534{
     
    606648    poly a2 = pNext(a);   
    607649
     650    // Splitting 2-terms Leading syzygy module
    608651    if( a2 != NULL )
    609652    {
     
    633676      if( a2 == NULL )
    634677      {
    635         aa = p_Mult_mm(aa, L->m[r], R);
    636         a2 = FindReducer(aa, a);
     678        aa = p_Mult_mm(aa, L->m[r], R); a2 = m_div.FindReducer(aa, a);
    637679      }
    638680      assume( a2 != NULL );
     
    677719}
    678720
    679 poly SchreyerSyzygyComputation::FindReducer(poly product, poly syzterm) const
     721poly CReducerFinder::FindReducer(const poly product, const poly syzterm) const
    680722{
    681723//  return FROM_NAMESPACE(INTERNAL, _FindReducer(product, syzterm, m_idLeads, m_LS, m_rBaseRing, m_atttributes));
     
    685727//                     const SchreyerSyzygyComputationFlags attributes)
    686728
    687   const ideal& L = m_idLeads;
    688   const ideal& LS = m_LS;
    689   const ring& r = m_rBaseRing;
    690   const SchreyerSyzygyComputationFlags& attributes = m_atttributes;
     729  const ideal& L = m_data.m_idLeads;
     730  const ideal& LS = m_data.m_LS;
     731  const ring& r = m_data.m_rBaseRing;
     732  const SchreyerSyzygyComputationFlags& attributes = m_data.m_atttributes;
    691733
    692734
     
    700742  assume( L != NULL );
    701743
    702   int c = 0;
     744  long c = 0;
    703745
    704746  if (syzterm != NULL)
     
    706748
    707749  assume( c >= 0 && c < IDELEMS(L) );
    708 
    709   if (__SYZCHECK__ && syzterm != NULL)
     750 
     751  if (__DEBUG__ && (syzterm != NULL))
    710752  {
    711753    const poly m = L->m[c];
     
    722764  }
    723765
    724   // looking for an appropriate diviser q = L[k]...
    725   for( int k = IDELEMS(L)-1; k>= 0; k-- )
    726   {
    727     const poly p = L->m[k];   
    728 
    729     // ... which divides the product, looking for the _1st_ appropriate one!
    730     if( !p_LmDivisibleBy(p, product, r) )
    731       continue;
     766  const long comp = p_GetComp(product, r);
     767  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
     768
     769  assume( comp >= 0 );
     770
     771   // looking for an appropriate diviser p = L[k]...
     772#if 1
     773  CReducersHash::const_iterator it = m_hash.find(p_GetComp(product, r)); // same module component
     774   
     775  if( it == m_hash.end() )
     776    return NULL;
     777
     778  const TReducers& reducers = it->second; 
     779 
     780  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
     781  {
     782     const poly p = (*vit)->m_lt;
     783
     784     assume( p_GetComp(p, r) == comp );
     785     
     786     const int k = (*vit)->m_label;
     787
     788     assume( L->m[k] == p );
     789     
     790     const unsigned long p_sev = (*vit)->m_sev;
     791
     792     assume( p_sev == p_GetShortExpVector(p, r) );     
     793#else 
     794   for( int k = IDELEMS(L)-1; k>= 0; k-- )
     795   {
     796     const poly p = L->m[k];
     797     
     798     if ( p_GetComp(p, r) != comp )
     799       continue;
     800       
     801     const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
     802#endif
     803     
     804     if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
     805       continue;     
     806
     807//     // ... which divides the product, looking for the _1st_ appropriate one!
     808//     if( !p_LmDivisibleByNoComp(p, product, r) ) // included inside  p_LmShortDivisibleBy!
     809//       continue;
    732810
    733811
     
    758836      BOOLEAN ok = TRUE;
    759837
     838      // TODO: FindReducer in LS !!! there should be no divisors!
    760839      for(int kk = IDELEMS(LS)-1; kk>= 0; kk-- )
    761840      {
     
    842921  while (spoly != NULL)
    843922  {
    844     poly t = FindReducer(spoly, NULL);
     923    poly t = m_div.FindReducer(spoly, NULL);
    845924
    846925    p_LmDelete(&spoly, r);
     
    9421021    // NOTE: only LT(term4reduction) should be used in the following:
    9431022    poly product = pp_Mult_mm(multiplier, term4reduction, r);
    944     s = FindReducer(product, syztermCheck);
     1023    s = m_div.FindReducer(product, syztermCheck);
    9451024    p_Delete(&product, r);
    9461025  }
  • dyn_modules/syzextra/syzextra.h

    r026171 rdd24e5  
    1818
    1919#include <vector>
     20#include <map>
    2021
    2122// include basic definitions
     
    9697
    9798
     99class CReducerFinder
     100{
     101  private:
     102    class CLeadingTerm
     103    {
     104      public:
     105        CLeadingTerm(unsigned int id,  const poly p, const ring);
     106
     107      private:
     108        CLeadingTerm();
     109
     110      public:
     111
     112        const unsigned long m_sev; ///< not short exp. vector
     113        // NOTE/TODO: either of the following should be enough:
     114        const unsigned int  m_label; ///< index in the main L[] + 1
     115        const poly          m_lt; ///< the leading term itself L[label-1]
     116    };
     117
     118    typedef long TComponentKey;
     119    typedef std::vector<const CLeadingTerm*> TReducers;
     120    typedef std::map< TComponentKey, TReducers> CReducersHash;
     121   
     122  public:
     123
     124    /// goes over all leading terms
     125    CReducerFinder(const SchreyerSyzygyComputation& data);
     126
     127    ~CReducerFinder();
     128
     129    // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?   
     130    poly FindReducer(const poly product, const poly syzterm) const;
     131
     132  private:
     133    const SchreyerSyzygyComputation& m_data;
     134
     135    CReducersHash m_hash; // can also be replaced with a vector indexed by components
     136};
     137
     138
     139
    98140/** @class SchreyerSyzygyComputation syzextra.h
    99141 *
     
    109151{
    110152  friend class CLCM;
     153  friend class CReducerFinder;
    111154 
    112155  public:
     
    117160        m_idLeads(idLeads), m_idTails(idTails),
    118161        m_syzLeads(NULL), m_syzTails(NULL), m_LS(NULL), m_atttributes(attribues),
    119         m_lcm(*this)
     162        m_lcm(*this), m_div(*this)
    120163    {
    121164    }
     
    127170        m_idLeads(idLeads), m_idTails(idTails),
    128171        m_syzLeads(NULL), m_syzTails(NULL), m_LS(syzLeads), m_atttributes(attribues),
    129         m_lcm(*this)
     172        m_lcm(*this), m_div(*this)
    130173    {
    131174    }
     
    151194    void ComputeLeadingSyzygyTerms(bool bComputeSecondTerms = true);
    152195
    153     // TODO: save shortcut (syz: |-.->) LM(LM(m) * "t") -> syz?
    154     poly FindReducer(poly product, poly syzterm) const;
    155    
    156196    poly SchreyerSyzygyNF(poly syz_lead, poly syz_2) const;
    157197
     
    162202    poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const;
    163203
     204  public:
     205    /// just for testing via the wrapper below
     206    inline poly _FindReducer(const poly product, const poly syzterm) const
     207        { return m_div.FindReducer(product, syzterm); } 
     208   
    164209  protected:
    165210
     
    195240    /// Bitmask for variables occuring in leading terms
    196241    const CLCM m_lcm;
     242
     243    /// Divisor finder
     244    const CReducerFinder m_div;
    197245};
    198246
     
    229277{
    230278  SchreyerSyzygyComputation syz(L, NULL, LS, R, A);
    231   return syz.FindReducer(product, syzterm);
     279  return syz._FindReducer(product, syzterm);
    232280}
    233281
Note: See TracChangeset for help on using the changeset viewer.