red_tail.h
Go to the documentation of this file.
// -*- c++ -*-
//*****************************************************************************
//*****************************************************************************
#ifndef polybori_groebner_red_tail_h_
#define polybori_groebner_red_tail_h_
// include basic definitions
#include "groebner_defs.h"
#include "LexHelper.h"
#include "DegOrderHelper.h"
#include "BlockOrderHelper.h"
#include "GroebnerStrategy.h"
BEGIN_NAMESPACE_PBORIGB
inline Polynomial
red_tail_general(const ReductionStrategy& strat, Polynomial p){
PBORI_ASSERT(!p.isZero());
// int deg_bound=p.deg(); /// @todo unused?
std::vector<Polynomial> res_vec;
Polynomial orig_p=p;
bool changed=false;
// assuming non-zero
Monomial lm=p.lead();
res_vec.push_back(lm);
p=Polynomial(p.diagram().diff(lm.diagram()));
while(!(p.isZero())){
//res+=lm;
//p-=lm;
std::vector<Monomial> irr;
Polynomial::ordered_iterator it=p.orderedBegin();
Polynomial::ordered_iterator end=p.orderedEnd();
while((it!=end)&& (irreducible_lead(*it,strat))){
irr.push_back(*it);
it++;
}
Monomial rest_lead(p.ring());
if PBORI_UNLIKELY((!(changed))&& (it==end)) return orig_p;
//@todo: if it==end irr_p=p, p=Polnomial(0)
Polynomial irr_p(p.ring());
if PBORI_LIKELY(it!=end) {
irr_p=add_up_generic(irr, p.ring().zero());
rest_lead=*it;
}
else irr_p=p;
int s;
s=irr.size();
PBORI_ASSERT(s==irr_p.length());
//if (s!=irr_p.length()) cout<<"ADDUP FAILED!!!!!!!!!!!!!!!!!!!!!!!!\n";
//for(i=0;i<s;i++){
// res_vec.push_back(irr[i]);
//}
res_vec.push_back(irr_p);
//p=p-irr_p;
p=Polynomial(p.diagram().diff(irr_p.diagram()));
if PBORI_UNLIKELY(p.isZero()) break;
//Monomial lm=p.lead();
//res_vec.push_back(lm);
//p=Polynomial(p.().diff(lm.diagram()));
if (!(p.ring().ordering().isDegreeOrder()))
p=nf3(strat,p, rest_lead);
else{
p=nf3_degree_order(strat,p,rest_lead);
}
changed=true;
}
//should use already added irr_p's
return add_up_polynomials(res_vec, p.ring().zero());
}
template <class Helper>
inline Polynomial
red_tail_generic(const ReductionStrategy& strat, Polynomial p){
PBORI_ASSERT(!p.isZero());
// int deg_bound=p.deg(); /// @todo unused?
std::vector<Polynomial> res_vec;
Polynomial orig_p=p;
bool changed=false;
// assuming non-zero
Monomial lm = p.lead();
res_vec.push_back(lm);
p = Polynomial(p.diagram().diff(lm.diagram()));
while(!(p.isZero())){
{
Polynomial p_bak=p;
p = cheap_reductions(strat, p);
if (p!=p_bak){
changed=true;
}
}
//p-=lm;
std::vector<Monomial> irr;
typename Helper::iterator_type it=Helper::begin(p);
typename Helper::iterator_type it_orig=it;
typename Helper::iterator_type end=Helper::end(p);
bool rest_is_irreducible=false;
//typedef (typename Helper::iterator_type) it_type;
//typedef (typename it_type::value_type) mon_type;
//Monomial mymon;
if PBORI_LIKELY(strat.canRewrite(p)){
Polynomial irreducible_part=mod_mon_set(p.diagram(),strat.minimalLeadingTerms);
if (!(irreducible_part.isZero())){
res_vec.push_back(irreducible_part);
Polynomial p2=p+irreducible_part;
it=Helper::begin(p2);
it_orig=it;
end=Helper::end(p2);
p=p2;
}
while((it!=end)&& (Helper::irreducible_lead(*it,strat))){
if PBORI_UNLIKELY(Helper::knowRestIsIrreducible(it,strat)){
rest_is_irreducible=true;
break;
} else{
irr.push_back(*it);
it++;
}
}
} else {
rest_is_irreducible=true;
}
Monomial rest_lead(p.ring());
if PBORI_UNLIKELY((!(changed))&& (it==end)) return orig_p;
//@todo: if it==end irr_p=p, p=Polnomial(0)
Polynomial irr_p(p.ring());
if PBORI_LIKELY((it!=end) &&(!(rest_is_irreducible))) {
irr_p=Helper::sum_range(irr,it_orig,it, p.ring().zero());//add_up_monomials(irr);
rest_lead=*it;
}
else irr_p=p;
size_t s;
s=irr.size();
PBORI_ASSERT((s==irr_p.length())||(rest_is_irreducible));
res_vec.push_back(irr_p);
p=Polynomial(p.diagram().diff(irr_p.diagram()));
if PBORI_UNLIKELY(p.isZero()) break;
p=Helper::nf(strat,p,rest_lead);
changed=true;
}
//should use already added irr_p's
return add_up_polynomials(res_vec, p.ring().zero());
}
inline Polynomial
red_tail(const ReductionStrategy& strat, Polynomial p){
if PBORI_UNLIKELY(p.isZero()) return p;
if (p.ring().ordering().isLexicographical())
return red_tail_generic<LexHelper>(strat,p);
if (p.ring().ordering().isDegreeOrder())
return red_tail_generic<DegOrderHelper>(strat,p);
if (p.ring().ordering().isBlockOrder())
return red_tail_generic<BlockOrderHelper>(strat,p);
return red_tail_general(strat,p);
}
inline Polynomial
red_tail_short(const ReductionStrategy& strat, Polynomial p){
Polynomial res(p.ring());
while(!(p.isZero())){
Polynomial lm=p.lead();
res+=lm;
p-=lm;
p=nf3_short(strat,p);
}
return res;
}
inline Polynomial
red_tail_in_last_block(const GroebnerStrategy& strat, Polynomial p){
Polynomial::navigator nav=p.navigation();
idx_type last=p.ring().ordering().lastBlockStart();
if ((*nav)>=last) //includes constant polynomials
return p;
while ((*nav)<last){
nav.incrementElse();
}
if (nav.isConstant()){
//we don't check for strat containing one at this point
return p;
}
Polynomial l1(nav, p.ring());
Polynomial l2=strat.nf(l1);
if (!(l2.isZero())) l2=red_tail(strat.generators,l2);
return p+(l1+l2);
}
END_NAMESPACE_PBORIGB
#endif /* polybori_groebner_red_tail_h_ */