PolyBoRi
SlimgbReduction.h
Go to the documentation of this file.
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_ */