PolyBoRi
SlimgbReduction.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
14 //*****************************************************************************
15 
16 #ifndef polybori_groebner_SlimgbReduction_h_
17 #define polybori_groebner_SlimgbReduction_h_
18 
19 // include basic definitions
20 #include "groebner_defs.h"
21 #include <utility>
22 #include <vector>
23 #include "LMLessCompare.h"
24 #include "GroebnerStrategy.h"
25 
27 
33 const int SLIMGB_SIMPLEST=0;
34 
35 template<int variant>
37 private:
38  const GroebnerStrategy* strat;
39  std::priority_queue<Polynomial, std::vector<Polynomial>, LMLessCompare> to_reduce;
40  public:
41  std::vector<Polynomial> result;
42 
44  this->strat=&strat;
45  }
47  void addPolynomial(const Polynomial& p);
48  void reduce();
49  //return zero at the end
50  Polynomial nextResult();
51 };
52 
53 template <int variant>
54 inline void
56  if (!(p.isZero())){
57  to_reduce.push(p);
58  }
59 }
60 
61 template <int variant>
62 inline Polynomial
64  if (result.size()==0)
65  throw std::runtime_error("Empty result in SlimgbReduction.");
66  Polynomial res=result.back();
67  result.pop_back();
68  return res;
69 }
70 
71 
72 template <>
73 inline void
75  while (!(to_reduce.empty())){
76  //cout<<"looping"<<endl;
77  std::vector<Polynomial> curr;
78  curr.push_back(to_reduce.top());
79  to_reduce.pop();
80  //cout<<curr[0];
81  Monomial lm=curr[0].lead();
82  while ((!(to_reduce.empty())) && (to_reduce.top().lead()==lm)){
83  curr.push_back(to_reduce.top());
84  to_reduce.pop();
85  //cout<<"same"<<endl;
86  //cout.flush();
87  }
88  //cout<<lm;
89  //cout.flush();
90  int index=strat->generators.select1(lm);
91  if (index>=0){
92  Polynomial p_high=(lm/strat->generators[index].lead)*strat->generators[index].p;
93  int i,s;
94  s=curr.size();
95  PBORI_ASSERT(p_high.lead()==lm);
96  for(i=0;i<s;i++){
97  curr[i]+=p_high;
98  if (!(curr[i].isZero())){
99  to_reduce.push(curr[i]);
100  }
101  }
102  } else {
103  //simly take the first, not so clever
104  Polynomial reductor=curr.back();
105  curr.pop_back();
106  int i,s;
107  s=curr.size();
108  if (s>0){
109  for(i=0;i<s;i++){
110  curr[i]+=reductor;
111  if (!(curr[i].isZero())){
112  PBORI_ASSERT(curr[i].lead()<lm);
113  to_reduce.push(curr[i]);
114  }
115 
116  }
117  PBORI_ASSERT(!(reductor.isZero()));
118  result.push_back(reductor);
119  } else{
120  PBORI_ASSERT(s==0);
121  PBORI_ASSERT(!(curr[0].isZero()));
122  result.push_back(curr[0]);
123  }
124  }
125 
126  }
127 
128 }
129 
130 
131 
133 
134 #endif /* polybori_groebner_SlimgbReduction_h_ */