PolyBoRi
red_tail.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
14 //*****************************************************************************
15 
16 #ifndef polybori_groebner_red_tail_h_
17 #define polybori_groebner_red_tail_h_
18 
19 // include basic definitions
20 #include "groebner_defs.h"
21 #include "LexHelper.h"
22 #include "DegOrderHelper.h"
23 #include "BlockOrderHelper.h"
24 #include "GroebnerStrategy.h"
25 
27 
28 inline Polynomial
30 
31  PBORI_ASSERT(!p.isZero());
32 
33  // int deg_bound=p.deg(); /// @todo unused?
34  std::vector<Polynomial> res_vec;
35  Polynomial orig_p=p;
36  bool changed=false;
37 
38  // assuming non-zero
39  Monomial lm=p.lead();
40  res_vec.push_back(lm);
41  p=Polynomial(p.diagram().diff(lm.diagram()));
42 
43  while(!(p.isZero())){
44 
45  //res+=lm;
46 
47 
48  //p-=lm;
49  std::vector<Monomial> irr;
52  while((it!=end)&& (irreducible_lead(*it,strat))){
53  irr.push_back(*it);
54  it++;
55  }
56  Monomial rest_lead(p.ring());
57 
58  if PBORI_UNLIKELY((!(changed))&& (it==end)) return orig_p;
59  //@todo: if it==end irr_p=p, p=Polnomial(0)
60  Polynomial irr_p(p.ring());
61  if PBORI_LIKELY(it!=end) {
62  irr_p=add_up_generic(irr, p.ring().zero());
63  rest_lead=*it;
64  }
65  else irr_p=p;
66  int s;
67  s=irr.size();
68  PBORI_ASSERT(s==irr_p.length());
69  //if (s!=irr_p.length()) cout<<"ADDUP FAILED!!!!!!!!!!!!!!!!!!!!!!!!\n";
70  //for(i=0;i<s;i++){
71  // res_vec.push_back(irr[i]);
72  //}
73  res_vec.push_back(irr_p);
74  //p=p-irr_p;
75  p=Polynomial(p.diagram().diff(irr_p.diagram()));
76  if PBORI_UNLIKELY(p.isZero()) break;
77  //Monomial lm=p.lead();
78  //res_vec.push_back(lm);
79 
80 
81  //p=Polynomial(p.().diff(lm.diagram()));
82  if (!(p.ring().ordering().isDegreeOrder()))
83  p=nf3(strat,p, rest_lead);
84  else{
85  p=nf3_degree_order(strat,p,rest_lead);
86  }
87  changed=true;
88  }
89 
90  //should use already added irr_p's
91  return add_up_polynomials(res_vec, p.ring().zero());
92 }
93 
94 
95 template <class Helper>
96 inline Polynomial
98 
99  PBORI_ASSERT(!p.isZero());
100 
101  // int deg_bound=p.deg(); /// @todo unused?
102  std::vector<Polynomial> res_vec;
103  Polynomial orig_p=p;
104  bool changed=false;
105 
106  // assuming non-zero
107  Monomial lm = p.lead();
108  res_vec.push_back(lm);
109  p = Polynomial(p.diagram().diff(lm.diagram()));
110 
111  while(!(p.isZero())){
112  {
113  Polynomial p_bak=p;
114  p = cheap_reductions(strat, p);
115  if (p!=p_bak){
116  changed=true;
117  }
118  }
119 
120  //p-=lm;
121  std::vector<Monomial> irr;
122  typename Helper::iterator_type it=Helper::begin(p);
123  typename Helper::iterator_type it_orig=it;
124  typename Helper::iterator_type end=Helper::end(p);
125  bool rest_is_irreducible=false;
126  //typedef (typename Helper::iterator_type) it_type;
127  //typedef (typename it_type::value_type) mon_type;
128  //Monomial mymon;
129  if PBORI_LIKELY(strat.canRewrite(p)){
130  Polynomial irreducible_part=mod_mon_set(p.diagram(),strat.minimalLeadingTerms);
131  if (!(irreducible_part.isZero())){
132  res_vec.push_back(irreducible_part);
133  Polynomial p2=p+irreducible_part;
134  it=Helper::begin(p2);
135  it_orig=it;
136  end=Helper::end(p2);
137  p=p2;
138  }
139 
140  while((it!=end)&& (Helper::irreducible_lead(*it,strat))){
141  if PBORI_UNLIKELY(Helper::knowRestIsIrreducible(it,strat)){
142  rest_is_irreducible=true;
143  break;
144  } else{
145  irr.push_back(*it);
146  it++;
147 
148  }
149  }
150  } else {
151  rest_is_irreducible=true;
152  }
153  Monomial rest_lead(p.ring());
154 
155  if PBORI_UNLIKELY((!(changed))&& (it==end)) return orig_p;
156  //@todo: if it==end irr_p=p, p=Polnomial(0)
157  Polynomial irr_p(p.ring());
158  if PBORI_LIKELY((it!=end) &&(!(rest_is_irreducible))) {
159  irr_p=Helper::sum_range(irr,it_orig,it, p.ring().zero());//add_up_monomials(irr);
160  rest_lead=*it;
161 
162  }
163  else irr_p=p;
164  size_t s;
165  s=irr.size();
166 
167  PBORI_ASSERT((s==irr_p.length())||(rest_is_irreducible));
168 
169  res_vec.push_back(irr_p);
170 
171  p=Polynomial(p.diagram().diff(irr_p.diagram()));
172  if PBORI_UNLIKELY(p.isZero()) break;
173  p=Helper::nf(strat,p,rest_lead);
174  changed=true;
175  }
176 
177  //should use already added irr_p's
178  return add_up_polynomials(res_vec, p.ring().zero());
179 }
180 
181 
182 
183 inline Polynomial
185  if PBORI_UNLIKELY(p.isZero()) return p;
186 
187  if (p.ring().ordering().isLexicographical())
188  return red_tail_generic<LexHelper>(strat,p);
189  if (p.ring().ordering().isDegreeOrder())
190  return red_tail_generic<DegOrderHelper>(strat,p);
191  if (p.ring().ordering().isBlockOrder())
192  return red_tail_generic<BlockOrderHelper>(strat,p);
193  return red_tail_general(strat,p);
194 }
195 
196 inline Polynomial
198  Polynomial res(p.ring());
199  while(!(p.isZero())){
200  Polynomial lm=p.lead();
201  res+=lm;
202  p-=lm;
203  p=nf3_short(strat,p);
204  }
205  return res;
206 }
207 
208 inline Polynomial
211  idx_type last=p.ring().ordering().lastBlockStart();
212  if ((*nav)>=last) //includes constant polynomials
213  return p;
214  while ((*nav)<last){
215  nav.incrementElse();
216  }
217  if (nav.isConstant()){
218  //we don't check for strat containing one at this point
219  return p;
220  }
221  Polynomial l1(nav, p.ring());
222  Polynomial l2=strat.nf(l1);
223  if (!(l2.isZero())) l2=red_tail(strat.generators,l2);
224  return p+(l1+l2);
225 }
226 
227 
229 
230 #endif /* polybori_groebner_red_tail_h_ */