PolyBoRi
|
00001 /* 00002 * groebner_alg.h 00003 * PolyBoRi 00004 * 00005 * Created by Michael Brickenstein on 20.04.06. 00006 * Copyright 2006 The PolyBoRi Team. See LICENSE file. 00007 * 00008 */ 00009 00010 #ifndef PBORI_GB_ALG_H 00011 #define PBORI_GB_ALG_H 00012 00013 00014 #include "PairStatusSet.h" 00015 #include "PairManager.h" 00016 #include "MonomialHasher.h" 00017 #include "ReductionStrategy.h" 00018 #include "GroebnerStrategy.h" 00019 #include "LessWeightedLengthInStrat.h" 00020 #include "LargerDegreeComparer.h" 00021 #include "LessWeightedLengthInStratModified.h" 00022 #include "LessEcartThenLessWeightedLengthInStrat.h" 00023 #include "LessUsedTailVariablesThenLessWeightedLengthInStrat.h" 00024 #include "LessCombinedManySizesInStrat.h" 00025 00026 #include <polybori.h> 00027 #include "groebner_defs.h" 00028 #include "pairs.h" 00029 #include <boost/dynamic_bitset.hpp> 00030 #include <vector> 00031 #include <string> 00032 #include <algorithm> 00033 #include <utility> 00034 #include <iostream> 00035 #include "cache_manager.h" 00036 #include "polynomial_properties.h" 00037 00038 00039 BEGIN_NAMESPACE_PBORIGB 00040 00041 #define LL_RED_FOR_GROEBNER 1 00042 Polynomial map_every_x_to_x_plus_one(Polynomial p); 00043 00044 MonomialSet mod_var_set(const MonomialSet& as, const MonomialSet& vs); 00045 void groebner(GroebnerStrategy& strat); 00046 Polynomial reduce_by_binom(const Polynomial& p, const Polynomial& binom); 00047 Polynomial reduce_by_monom(const Polynomial& p, const Monomial& m); 00048 Polynomial reduce_complete(const Polynomial& p, const Polynomial& reductor); 00049 00050 00051 00052 00053 00054 Polynomial mult_fast_sim(const std::vector<Polynomial>& vec, 00055 const BoolePolyRing& ring); 00056 std::vector<Polynomial> full_implication_gb(const Polynomial & p,CacheManager& cache,GroebnerStrategy& strat); 00057 Polynomial reduce_complete(const Polynomial &p, const PolyEntry& reductor, wlen_type &len); 00058 MonomialSet recursively_insert(MonomialSet::navigator p, idx_type idx, MonomialSet mset); 00059 00060 00061 00062 00063 inline Polynomial 00064 cancel_monomial_in_tail(const Polynomial& p, const Monomial & m){ 00065 Monomial lm=p.lead(); 00066 00067 Polynomial res=reduce_by_monom(p,m); 00068 if ((!res.isZero()) && (res.lead()==lm)){ 00069 return res; 00070 } else { 00071 return res+lm; 00072 } 00073 /*Polynomial tail=p-lm; 00074 Monomial used_var=tail.usedVariables(); 00075 00076 if (used_var.reducibleBy(m)){ 00077 tail=Polynomial(BooleSet(tail).diff(m.multiples(used_var))); 00078 00079 } 00080 return tail+lm;*/ 00081 } 00082 00083 inline Polynomial 00084 reduce_by_binom(const Polynomial& p, const Polynomial& binom){ 00085 PBORI_ASSERT(binom.length()==2); 00086 00087 Monomial bin_lead=binom.lead(); 00088 Monomial bin_last=*(++(binom.orderedBegin())); 00089 00090 MonomialSet dividing_terms=((MonomialSet)p).multiplesOf(bin_lead); 00091 00092 Monomial b_p_gcd=bin_last.GCD(bin_lead); 00093 00094 Monomial divide_by=bin_lead/b_p_gcd; 00095 Monomial multiply_by=bin_last/b_p_gcd; 00096 00097 Polynomial rewritten=((Polynomial) dividing_terms)/divide_by; 00098 return p-dividing_terms+rewritten*multiply_by; 00099 00100 } 00101 00102 00103 inline Polynomial 00104 reduce_by_binom_in_tail (const Polynomial& p, const Polynomial& binom){ 00105 PBORI_ASSERT(binom.length()==2); 00106 Monomial lm=p.lead(); 00107 return lm+reduce_by_binom(p-lm,binom); 00108 } 00109 00110 00111 END_NAMESPACE_PBORIGB 00112 00113 #endif 00114