PolyBoRi
red_tail.h
Go to the documentation of this file.
00001 // -*- c++ -*-
00002 //*****************************************************************************
00014 //*****************************************************************************
00015 
00016 #ifndef polybori_groebner_red_tail_h_
00017 #define polybori_groebner_red_tail_h_
00018 
00019 // include basic definitions
00020 #include "groebner_defs.h"
00021 #include "LexHelper.h"
00022 #include "DegOrderHelper.h"
00023 #include "BlockOrderHelper.h"
00024 #include "GroebnerStrategy.h"
00025 
00026 BEGIN_NAMESPACE_PBORIGB
00027 
00028 inline Polynomial
00029 red_tail_general(const ReductionStrategy& strat, Polynomial p){
00030 
00031   PBORI_ASSERT(!p.isZero());
00032 
00033   // int deg_bound=p.deg(); /// @todo unused?
00034   std::vector<Polynomial> res_vec;
00035   Polynomial orig_p=p;
00036   bool changed=false;
00037 
00038   // assuming non-zero
00039   Monomial lm=p.lead();
00040   res_vec.push_back(lm);
00041   p=Polynomial(p.diagram().diff(lm.diagram()));
00042 
00043   while(!(p.isZero())){
00044     
00045     //res+=lm;
00046 
00047     
00048     //p-=lm;
00049     std::vector<Monomial> irr;
00050     Polynomial::ordered_iterator it=p.orderedBegin();
00051     Polynomial::ordered_iterator end=p.orderedEnd();
00052     while((it!=end)&& (irreducible_lead(*it,strat))){
00053         irr.push_back(*it);
00054         it++;
00055     }
00056     Monomial rest_lead(p.ring());
00057     
00058     if PBORI_UNLIKELY((!(changed))&& (it==end)) return orig_p;
00059     //@todo: if it==end irr_p=p, p=Polnomial(0)
00060     Polynomial irr_p(p.ring());
00061     if PBORI_LIKELY(it!=end) {
00062       irr_p=add_up_generic(irr, p.ring().zero());
00063         rest_lead=*it;
00064         }
00065     else irr_p=p;
00066     int s;
00067     s=irr.size();
00068     PBORI_ASSERT(s==irr_p.length());
00069     //if (s!=irr_p.length()) cout<<"ADDUP FAILED!!!!!!!!!!!!!!!!!!!!!!!!\n";
00070     //for(i=0;i<s;i++){
00071     //    res_vec.push_back(irr[i]);
00072     //}
00073     res_vec.push_back(irr_p);
00074     //p=p-irr_p;
00075     p=Polynomial(p.diagram().diff(irr_p.diagram()));
00076     if PBORI_UNLIKELY(p.isZero()) break;
00077     //Monomial lm=p.lead();
00078     //res_vec.push_back(lm);
00079     
00080     
00081     //p=Polynomial(p.().diff(lm.diagram()));
00082     if (!(p.ring().ordering().isDegreeOrder()))
00083         p=nf3(strat,p, rest_lead);
00084     else{
00085         p=nf3_degree_order(strat,p,rest_lead);
00086     }
00087     changed=true;
00088   }
00089   
00090   //should use already added irr_p's
00091   return add_up_polynomials(res_vec, p.ring().zero());
00092 }
00093 
00094 
00095 template <class Helper>
00096 inline Polynomial
00097 red_tail_generic(const ReductionStrategy& strat, Polynomial p){
00098 
00099   PBORI_ASSERT(!p.isZero());
00100 
00101   // int deg_bound=p.deg(); /// @todo unused?
00102   std::vector<Polynomial> res_vec;
00103   Polynomial orig_p=p;
00104   bool changed=false;
00105 
00106   // assuming non-zero
00107   Monomial lm = p.lead();
00108   res_vec.push_back(lm);
00109   p = Polynomial(p.diagram().diff(lm.diagram()));
00110 
00111   while(!(p.isZero())){
00112   {
00113       Polynomial p_bak=p;
00114       p = cheap_reductions(strat, p);    
00115       if (p!=p_bak){
00116           changed=true;
00117       }
00118   }
00119   
00120     //p-=lm;
00121     std::vector<Monomial> irr;
00122     typename Helper::iterator_type it=Helper::begin(p);
00123     typename Helper::iterator_type it_orig=it;
00124     typename Helper::iterator_type end=Helper::end(p);
00125     bool rest_is_irreducible=false;
00126     //typedef  (typename Helper::iterator_type) it_type;
00127     //typedef  (typename it_type::value_type) mon_type;
00128     //Monomial mymon;
00129     if PBORI_LIKELY(strat.canRewrite(p)){
00130         Polynomial irreducible_part=mod_mon_set(p.diagram(),strat.minimalLeadingTerms);
00131         if (!(irreducible_part.isZero())){
00132             res_vec.push_back(irreducible_part);
00133             Polynomial p2=p+irreducible_part;
00134             it=Helper::begin(p2);
00135             it_orig=it;
00136             end=Helper::end(p2);
00137             p=p2;
00138         }
00139 
00140         while((it!=end)&& (Helper::irreducible_lead(*it,strat))){
00141             if PBORI_UNLIKELY(Helper::knowRestIsIrreducible(it,strat)){
00142                 rest_is_irreducible=true;
00143                 break;
00144             } else{
00145                 irr.push_back(*it);
00146                 it++;
00147 
00148             }
00149         }
00150     } else {
00151         rest_is_irreducible=true;
00152     }
00153     Monomial rest_lead(p.ring());
00154     
00155     if PBORI_UNLIKELY((!(changed))&& (it==end)) return orig_p;
00156     //@todo: if it==end irr_p=p, p=Polnomial(0)
00157     Polynomial irr_p(p.ring());
00158     if PBORI_LIKELY((it!=end) &&(!(rest_is_irreducible))) {
00159       irr_p=Helper::sum_range(irr,it_orig,it, p.ring().zero());//add_up_monomials(irr);
00160         rest_lead=*it;
00161         
00162         }
00163     else irr_p=p;
00164     size_t s;
00165     s=irr.size();
00166 
00167     PBORI_ASSERT((s==irr_p.length())||(rest_is_irreducible));
00168 
00169     res_vec.push_back(irr_p);
00170 
00171     p=Polynomial(p.diagram().diff(irr_p.diagram()));
00172     if PBORI_UNLIKELY(p.isZero()) break;
00173     p=Helper::nf(strat,p,rest_lead);
00174     changed=true;
00175   }
00176   
00177   //should use already added irr_p's
00178   return add_up_polynomials(res_vec, p.ring().zero());
00179 }
00180 
00181 
00182 
00183 inline Polynomial
00184 red_tail(const ReductionStrategy& strat, Polynomial p){
00185   if PBORI_UNLIKELY(p.isZero()) return p;
00186 
00187   if (p.ring().ordering().isLexicographical())
00188     return red_tail_generic<LexHelper>(strat,p);
00189   if (p.ring().ordering().isDegreeOrder())
00190     return red_tail_generic<DegOrderHelper>(strat,p);
00191   if (p.ring().ordering().isBlockOrder())
00192     return red_tail_generic<BlockOrderHelper>(strat,p);
00193   return red_tail_general(strat,p);
00194 }
00195 
00196 inline Polynomial
00197 red_tail_short(const ReductionStrategy& strat, Polynomial p){
00198   Polynomial res(p.ring());
00199   while(!(p.isZero())){
00200     Polynomial lm=p.lead();
00201     res+=lm;
00202     p-=lm;
00203     p=nf3_short(strat,p);
00204   }
00205   return res;
00206 }
00207 
00208 inline Polynomial
00209 red_tail_in_last_block(const GroebnerStrategy& strat, Polynomial p){
00210     Polynomial::navigator nav=p.navigation();
00211     idx_type last=p.ring().ordering().lastBlockStart();
00212     if ((*nav)>=last) //includes constant polynomials
00213         return p;
00214     while ((*nav)<last){
00215         nav.incrementElse();
00216     }
00217     if (nav.isConstant()){
00218         //we don't check for strat containing one at this point
00219         return p;
00220     }
00221     Polynomial l1(nav, p.ring());
00222     Polynomial l2=strat.nf(l1);
00223     if (!(l2.isZero())) l2=red_tail(strat.generators,l2);
00224     return p+(l1+l2);
00225 }
00226 
00227 
00228 END_NAMESPACE_PBORIGB
00229 
00230 #endif /* polybori_groebner_red_tail_h_ */