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_ */
polybori::BoolePolynomial::navigation
navigator navigation() const
Navigate through structure.
Definition: BoolePolynomial.h:441
polybori::groebner::add_up_generic
Polynomial add_up_generic(const std::vector< T > &res_vec, int start, int end, Polynomial init)
Definition: add_up.h:205
polybori::BoolePolynomial::lead
monom_type lead() const
Get leading term.
Definition: BoolePolynomial.cc:225
polybori::groebner::cheap_reductions
Polynomial cheap_reductions(const ReductionStrategy &strat, Polynomial p)
Definition: nf.cc:831
END_NAMESPACE_PBORIGB
#define END_NAMESPACE_PBORIGB
Definition: groebner_defs.h:16
polybori::groebner::add_up_polynomials
Polynomial add_up_polynomials(const std::vector< Polynomial > &vec, const Polynomial &init)
Definition: add_up.h:238
polybori::BoolePolynomial::ring
const ring_type & ring() const
Access ring, where this belongs to.
Definition: BoolePolynomial.h:478
polybori::groebner::nf3_short
Polynomial nf3_short(const ReductionStrategy &strat, Polynomial p)
Definition: nf.cc:192
polybori::groebner::red_tail
Polynomial red_tail(const ReductionStrategy &strat, Polynomial p)
Definition: red_tail.h:184
polybori::BoolePolyRing::zero
dd_type zero() const
Get empty decision diagram.
Definition: BoolePolyRing.cc:42
polybori::COrderingBase::lastBlockStart
virtual idx_type lastBlockStart() const =0
Generic procedure to get index, where last block starts.
polybori::COrderingBase::isDegreeOrder
virtual bool_type isDegreeOrder() const =0
Test whether we deal with a degree-ordering.
polybori::groebner::irreducible_lead
bool irreducible_lead(Monomial lm, const ReductionStrategy &strat)
Definition: ReductionStrategy.h:107
polybori::Polynomial
BoolePolynomial Polynomial
Definition: embed.h:51
polybori::groebner::ReductionStrategy::canRewrite
bool canRewrite(const Polynomial &p) const
Definition: ReductionStrategy.h:57
BEGIN_NAMESPACE_PBORIGB
#define BEGIN_NAMESPACE_PBORIGB
Definition: groebner_defs.h:15
polybori::BoolePolyRing::ordering
order_reference ordering() const
Access ordering of *this.
Definition: BoolePolyRing.h:156
polybori::groebner::GroebnerStrategy::generators
ReductionStrategy generators
Definition: GroebnerStrategy.h:204
polybori::BoolePolynomial
This class wraps the underlying decicion diagram type and defines the necessary operations.
Definition: BoolePolynomial.h:85
PBORI_LIKELY
#define PBORI_LIKELY(expression)
For optimizing if-branches.
Definition: pbori_defs.h:56
LexHelper.h
polybori::COrderedIter
Definition: BoolePolynomial.h:63
polybori::BoolePolynomial::diagram
const dd_type & diagram() const
Read-only access to internal decision diagramm structure.
Definition: BoolePolynomial.h:461
groebner_defs.h
polybori::groebner::red_tail_general
Polynomial red_tail_general(const ReductionStrategy &strat, Polynomial p)
Definition: red_tail.h:29
polybori::groebner::mod_mon_set
MonomialSet mod_mon_set(const MonomialSet &as, const MonomialSet &vs)
Definition: nf.cc:855
BlockOrderHelper.h
polybori::groebner::GroebnerStrategy
This class defines GroebnerStrategy.
Definition: GroebnerStrategy.h:41
PBORI_ASSERT
#define PBORI_ASSERT(arg)
Definition: pbori_defs.h:118
polybori::BoolePolynomial::orderedEnd
ordered_iterator orderedEnd() const
Finish of ordering respecting iterator.
Definition: BoolePolynomial.cc:499
polybori::groebner::red_tail_short
Polynomial red_tail_short(const ReductionStrategy &strat, Polynomial p)
Definition: red_tail.h:197
polybori::BooleMonomial::diagram
const dd_type & diagram() const
Read-only access to internal decision diagramm structure.
Definition: BooleMonomial.h:213
polybori::COrderingBase::isBlockOrder
virtual bool_type isBlockOrder() const =0
Test whether we deal with a block-ordering.
polybori::groebner::red_tail_generic
Polynomial red_tail_generic(const ReductionStrategy &strat, Polynomial p)
Definition: red_tail.h:97
DegOrderHelper.h
polybori::BoolePolynomial::isZero
bool_type isZero() const
Check whether polynomial is constant zero.
Definition: BoolePolynomial.h:294
polybori::groebner::idx_type
polybori::CTypes::idx_type idx_type
Definition: groebner_defs.h:44
polybori::CCuddNavigator::isConstant
bool_type isConstant() const
Check whether constant node was reached.
Definition: CCuddNavigator.h:172
polybori::CCuddNavigator
This class defines an iterator for navigating through then and else branches of ZDDs.
Definition: CCuddNavigator.h:36
polybori::CCuddNavigator::incrementElse
self & incrementElse()
Increment in else direction.
Definition: CCuddNavigator.h:203
polybori::COrderingBase::isLexicographical
virtual bool_type isLexicographical() const =0
Check whether ring is lexicographical.
polybori::groebner::ReductionStrategy
This class defines ReductionStrategy.
Definition: ReductionStrategy.h:34
GroebnerStrategy.h
polybori::BooleMonomial
This class is just a wrapper for using variables from cudd's decicion diagram.
Definition: BooleMonomial.h:50
polybori::groebner::GroebnerStrategy::nf
Polynomial nf(Polynomial p) const
Definition: GroebnerStrategy.cc:702
polybori::groebner::ReductionTerms::minimalLeadingTerms
MinimalLeadingTerms minimalLeadingTerms
Definition: ReductionTerms.h:52
PBORI_UNLIKELY
#define PBORI_UNLIKELY(expression)
Definition: pbori_defs.h:59
polybori::groebner::nf3
Polynomial nf3(const ReductionStrategy &strat, Polynomial p, Monomial rest_lead)
Definition: nf.cc:64
polybori::BoolePolynomial::orderedBegin
ordered_iterator orderedBegin() const
Start of ordering respecting iterator.
Definition: BoolePolynomial.cc:491
polybori::groebner::red_tail_in_last_block
Polynomial red_tail_in_last_block(const GroebnerStrategy &strat, Polynomial p)
Definition: red_tail.h:209
polybori::groebner::nf3_degree_order
Polynomial nf3_degree_order(const ReductionStrategy &strat, Polynomial p, Monomial lead)
Definition: nf.cc:151