PolyBoRi
nf.h
Go to the documentation of this file.
00001 /*
00002  *  nf.h
00003  *  PolyBoRi
00004  *
00005  *  Created by Michael Brickenstein on 25.04.06.
00006  *  Copyright 2006 The PolyBoRi Team. See LICENSE file.
00007  *
00008  */
00009 #include <algorithm>
00010 #include <vector>
00011 #include <queue>
00012 #include "groebner_alg.h"
00013 #if HAVE_M4RI
00014 extern "C"{
00015 #include "m4ri/m4ri.h"
00016 
00017 #ifndef __M4RI_TWOPOW
00018 #define __M4RI_TWOPOW TWOPOW
00019 #endif
00020 }
00021 #endif
00022 #ifndef PBORI_GB_NF_H
00023 #define PBORI_GB_NF_H
00024 BEGIN_NAMESPACE_PBORIGB
00025 
00026 
00027 void drawmatrix(mzd_t* mat, const char* filename);
00028 
00029 Polynomial add_up_exponents(const std::vector<Exponent>& vec);
00030 Polynomial add_up_monomials(const std::vector<Monomial>& res_vec);
00031 
00032 
00033 int select_no_deg_growth(const ReductionStrategy& strat, const Monomial& m);
00034 
00035 
00036 
00037 
00038 class LMLessCompare{
00039 public:
00040   bool operator() (const Polynomial& p1, const Polynomial& p2){
00041     return p1.lead()<p2.lead();
00042   }
00043 };
00044 
00045 const int SLIMGB_SIMPLEST=0;
00046 template<int variant> class SlimgbReduction{
00047 private:
00048   GroebnerStrategy* strat;
00049   std::priority_queue<Polynomial, std::vector<Polynomial>, LMLessCompare> to_reduce;
00050   public:
00051   std::vector<Polynomial> result;
00052 
00053   SlimgbReduction(GroebnerStrategy& strat){
00054     this->strat=&strat;
00055   }
00056   SlimgbReduction(){}
00057   void addPolynomial(const Polynomial& p);
00058   void reduce();
00059   //return zero at the end
00060   Polynomial nextResult();
00061 };
00062 template <int variant> void SlimgbReduction<variant>::addPolynomial(const Polynomial& p){
00063   if (!(p.isZero())){
00064     to_reduce.push(p);
00065   }
00066 }
00067 template <int variant> Polynomial SlimgbReduction<variant>::nextResult(){
00068   if (result.size()==0) return Polynomial();
00069   Polynomial res=result.back();
00070   result.pop_back();
00071   return res;
00072 }
00073 typedef SlimgbReduction<SLIMGB_SIMPLEST> slimgb_reduction_type;
00074 std::vector<Polynomial> parallel_reduce(std::vector<Polynomial> inp, GroebnerStrategy& strat, int average_steps, double delay_f);
00075 Polynomial red_tail(const ReductionStrategy& strat, Polynomial p);
00076 Polynomial red_tail_short(const ReductionStrategy& strat, Polynomial p);
00077 Polynomial nf3(const ReductionStrategy& strat, Polynomial p, Monomial rest_lead);
00078 Polynomial nf3_short(const ReductionStrategy& strat, Polynomial p);
00079 Polynomial ll_red_nf(const Polynomial& p,const BooleSet& reductors);
00080 
00081 Polynomial ll_red_nf_noredsb(const Polynomial& p,const BooleSet& reductors);
00082 Polynomial add_up_polynomials(const std::vector<Polynomial>& vec);
00083 Polynomial plug_1(const Polynomial& p, const MonomialSet& m_plus_ones);
00084 MonomialSet mod_mon_set(const MonomialSet& as, const MonomialSet &vs);
00085 std::vector<Polynomial> gauss_on_polys(const std::vector<Polynomial>& orig_system);
00086 Polynomial ll_red_nf_noredsb_single_recursive_call(const Polynomial& p,const BooleSet& reductors);
00087 Polynomial cheap_reductions(const ReductionStrategy& strat, Polynomial p);
00088 END_NAMESPACE_PBORIGB
00089 #endif