PolyBoRi
LLReduction.h
Go to the documentation of this file.
00001 // -*- c++ -*-
00002 //*****************************************************************************
00014 //*****************************************************************************
00015 
00016 #ifndef polybori_groebner_LLReduction_h_
00017 #define polybori_groebner_LLReduction_h_
00018 
00019 // include basic definitions
00020 #include "groebner_defs.h"
00021 
00022 BEGIN_NAMESPACE_PBORIGB
00023 
00028 template <bool have_redsb, bool single_call_for_noredsb,
00029           bool fast_multiplication>
00030 class LLReduction {
00031 public:
00032 
00033   template<class RingType>
00034   LLReduction(const RingType& ring): cache_mgr(ring) {}
00035 
00036   Polynomial multiply(const Polynomial &p, const Polynomial& q){
00037     typedef CommutativeCacheManager<CCacheTypes::multiply_recursive>
00038       cache_mgr_type;
00039     
00040     return dd_multiply<fast_multiplication>(cache_mgr_type(p.ring()), 
00041                                             p.navigation(), q.navigation(),
00042                                             BoolePolynomial(p.ring()));
00043   }
00044 
00045   Polynomial operator()(const Polynomial& p, MonomialSet::navigator r_nav);
00046 
00047 protected:
00048   typedef PBORI::CacheManager<CCacheTypes::ll_red_nf> cache_mgr_type;
00049   cache_mgr_type cache_mgr;
00050 };
00051 
00052 
00053 template <bool have_redsb, bool single_call_for_noredsb, bool fast_multiplication>
00054 Polynomial
00055 LLReduction<have_redsb, single_call_for_noredsb,
00056             fast_multiplication>::operator() (const Polynomial& p,
00057                                               MonomialSet::navigator r_nav) {     
00058 
00059   if PBORI_UNLIKELY(p.isConstant()) return p;
00060     
00061   MonomialSet::navigator p_nav=p.navigation();
00062   idx_type p_index=*p_nav;
00063   
00064   while((*r_nav)<p_index) {
00065     r_nav.incrementThen();
00066   }
00067   
00068   if PBORI_UNLIKELY(r_nav.isConstant())
00069     return p;
00070 
00071   MonomialSet::navigator cached = cache_mgr.find(p_nav, r_nav);
00072 
00073   if PBORI_LIKELY(cached.isValid()) 
00074     return MonomialSet(cache_mgr.generate(cached));
00075 
00076   Polynomial res(0, p.ring());
00077 
00078   Polynomial p_nav_else(cache_mgr.generate(p_nav.elseBranch()));
00079   Polynomial p_nav_then(cache_mgr.generate(p_nav.thenBranch()));
00080 
00081   if ((*r_nav) == p_index){
00082     Polynomial r_nav_else(cache_mgr.generate(r_nav.elseBranch()));
00083 
00084     if ((!have_redsb) && single_call_for_noredsb) { 
00085       res = operator()(p_nav_else + multiply(r_nav_else, p_nav_then), 
00086                        r_nav.thenBranch());
00087     }
00088     else {
00089       Polynomial tmp1 = operator()(p_nav_else, r_nav.thenBranch());
00090       Polynomial tmp2 = operator()(p_nav_then, r_nav.thenBranch());
00091 
00092       Polynomial tmp( have_redsb? r_nav_else:
00093                       operator()(r_nav_else, r_nav.thenBranch()) );
00094       res = tmp1 + multiply(tmp, tmp2);
00095     }
00096   } 
00097   else{
00098     PBORI_ASSERT((*r_nav)>p_index);
00099     res = MonomialSet( p_index,
00100                        operator()(p_nav_then, r_nav).diagram(),
00101                        operator()(p_nav_else, r_nav).diagram());
00102       
00103   }
00104 
00105   cache_mgr.insert(p_nav, r_nav, res.navigation());
00106   return res;
00107 }
00108 
00109 END_NAMESPACE_PBORIGB
00110 
00111 #endif /* polybori_LLReduction_h_ */