00001 // -*- c++ -*- 00002 //***************************************************************************** 00014 //***************************************************************************** 00015 00016 #ifndef polybori_groebner_SlimgbReduction_h_ 00017 #define polybori_groebner_SlimgbReduction_h_ 00018 00019 // include basic definitions 00020 #include "groebner_defs.h" 00021 #include <utility> 00022 #include <vector> 00023 #include "LMLessCompare.h" 00024 #include "GroebnerStrategy.h" 00025 00026 BEGIN_NAMESPACE_PBORIGB 00027 00033 const int SLIMGB_SIMPLEST=0; 00034 00035 template<int variant> 00036 class SlimgbReduction{ 00037 private: 00038 const GroebnerStrategy* strat; 00039 std::priority_queue<Polynomial, std::vector<Polynomial>, LMLessCompare> to_reduce; 00040 public: 00041 std::vector<Polynomial> result; 00042 00043 SlimgbReduction(GroebnerStrategy& strat){ 00044 this->strat=&strat; 00045 } 00046 SlimgbReduction(){} 00047 void addPolynomial(const Polynomial& p); 00048 void reduce(); 00049 //return zero at the end 00050 Polynomial nextResult(); 00051 }; 00052 00053 template <int variant> 00054 inline void 00055 SlimgbReduction<variant>::addPolynomial(const Polynomial& p){ 00056 if (!(p.isZero())){ 00057 to_reduce.push(p); 00058 } 00059 } 00060 00061 template <int variant> 00062 inline Polynomial 00063 SlimgbReduction<variant>::nextResult(){ 00064 if (result.size()==0) 00065 throw std::runtime_error("Empty result in SlimgbReduction."); 00066 Polynomial res=result.back(); 00067 result.pop_back(); 00068 return res; 00069 } 00070 00071 00072 template <> 00073 inline void 00074 SlimgbReduction<SLIMGB_SIMPLEST>::reduce(){ 00075 while (!(to_reduce.empty())){ 00076 //cout<<"looping"<<endl; 00077 std::vector<Polynomial> curr; 00078 curr.push_back(to_reduce.top()); 00079 to_reduce.pop(); 00080 //cout<<curr[0]; 00081 Monomial lm=curr[0].lead(); 00082 while ((!(to_reduce.empty())) && (to_reduce.top().lead()==lm)){ 00083 curr.push_back(to_reduce.top()); 00084 to_reduce.pop(); 00085 //cout<<"same"<<endl; 00086 //cout.flush(); 00087 } 00088 //cout<<lm; 00089 //cout.flush(); 00090 int index=strat->generators.select1(lm); 00091 if (index>=0){ 00092 Polynomial p_high=(lm/strat->generators[index].lead)*strat->generators[index].p; 00093 int i,s; 00094 s=curr.size(); 00095 PBORI_ASSERT(p_high.lead()==lm); 00096 for(i=0;i<s;i++){ 00097 curr[i]+=p_high; 00098 if (!(curr[i].isZero())){ 00099 to_reduce.push(curr[i]); 00100 } 00101 } 00102 } else { 00103 //simly take the first, not so clever 00104 Polynomial reductor=curr.back(); 00105 curr.pop_back(); 00106 int i,s; 00107 s=curr.size(); 00108 if (s>0){ 00109 for(i=0;i<s;i++){ 00110 curr[i]+=reductor; 00111 if (!(curr[i].isZero())){ 00112 PBORI_ASSERT(curr[i].lead()<lm); 00113 to_reduce.push(curr[i]); 00114 } 00115 00116 } 00117 PBORI_ASSERT(!(reductor.isZero())); 00118 result.push_back(reductor); 00119 } else{ 00120 PBORI_ASSERT(s==0); 00121 PBORI_ASSERT(!(curr[0].isZero())); 00122 result.push_back(curr[0]); 00123 } 00124 } 00125 00126 } 00127 00128 } 00129 00130 00131 00132 END_NAMESPACE_PBORIGB 00133 00134 #endif /* polybori_groebner_SlimgbReduction_h_ */