PolyBoRi
|
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_ */