polynomial.h 4.07 KB
Newer Older
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
1
/* Written by <pierre-jean.spaenlehauer@inria.fr>
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
2 3 4 5
 *
 * ========LICENCE========
 * This file is part of tinygb.
 *
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
6
 * tinygb is free software: you can redistribute it and/or modify
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
7 8 9 10 11 12 13 14 15 16 17
 * it under the terms of the  GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 3 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
18
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
19 20 21 22
 * ========LICENCE========
 *
 */

SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
23 24 25
/// @file
/// @brief Polynomials in sparse representation

SPAENLEHAUER Pierre-Jean's avatar
TODOs  
SPAENLEHAUER Pierre-Jean committed
26 27
#ifndef __POLYNOMIAL_H__
#define __POLYNOMIAL_H__
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
28 29 30 31 32 33 34 35 36

#include <list>
#include "param.h"
#include "monomial.h"

template<class T>
class polynomial;

template<class T>
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
37
std::ostream& operator<<(std::ostream &o, const polynomial<T> &p);
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
38

SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
39 40
/// @class
/// @brief Class for manipulating polynomials in sparse representation
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
41
template<class T>
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
42
class polynomial 
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
43 44 45 46
{
  void combine_LM();
  std::list<std::pair<monomial,T> > vp;

SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
47 48
  public:
  /// @brief default constructor, construct the zero polynomial
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
49
  polynomial() 
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
50 51 52
    {
      vp = std::list<std::pair<monomial,T> >();
    }
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
53
  
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
54
  /// @brief constructor from an ordered list of pairs
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
55 56
  polynomial(std::list<std::pair<monomial,T> > _vp) : vp(_vp){}

SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
57
  /// @brief get the list of terms
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
58 59 60 61 62
  const std::list<std::pair<monomial,T> >& get_vp() const 
  {
    return vp;
  }

SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
63
  /// @brief orders the list of terms and merges terms with same monomials.
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
64 65
  void normalize();  
  
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
66
  /// @brief set the polynomial to 0
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
67 68 69 70 71
  void clear() 
  {
    vp.clear();
  }
  
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
72 73 74
  /// @brief adds a term
  /// @param m monomial part of the term
  /// @param e field element
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
75 76 77 78
  void insert(monomial m, T e) 
  {
    vp.push_back(std::pair<monomial, T>(m,e));
  }
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
79 80
 
  /// @brief get the leading monomial
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
81 82 83 84 85 86
  const monomial& LM() const 
  {
    assert(!vp.back().second.is_zero());
    return vp.back().first;
  }

SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
87
  /// @brief get the leading coefficient
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
88 89 90 91 92
  const T& LC() const 
  {
    return vp.back().second;
  }

SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
93
  /// @brief scales the polynomial so that the leading coefficient is 1.
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
94 95 96 97 98 99
  void set_monic();
  unsigned size() const 
  {
    return vp.size();
  }
  
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
100
  /// @brief tests if a normalized polynomial is zero.
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
101 102 103 104 105
  bool is_zero() const 
  {
    return vp.empty();
  }

SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
106 107
  /// @brief computes the degree, only works for degree orderings
  /// @returns the sum of the exponents
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
108 109
  unsigned degree() const 
  {
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
110
    //@todo extends for non-degree orderings
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
111 112 113 114
    return LM().degree();
  }

#ifdef BILIN
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
115
  /// @brief special degree for the selection of critpairs for bilinear systems
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
116 117 118
  unsigned degree_bilin() const;
#endif

SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
119 120 121
  /// @brief top-reduce by a polynomial
  /// @param g reductor
  /// @returns a boolean indicating if the polynomial was topreduced
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
122
  bool topred(const polynomial &g);
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
123 124 125 126

  /// @brief check if top-reducible by another polynomial
  /// @param g reductor
  /// @returns a boolean indicating if the polynomial was topreduced
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
127
  bool istopred(const polynomial &g) const;
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
128 129 130 131

  /// @brief get the coefficient of a given monomial
  /// @param m monomial whose coefficient is returned
  /// @returns the corresponding coefficient
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
132 133 134 135 136 137 138 139 140
  T coeff(const monomial& m) const;

  /****************************************/

  polynomial<T> operator*(const monomial&) const;
  void operator+=(const polynomial<T>&);
  void operator-=(const polynomial<T>&);
  void operator*=(const T&);
  void operator/=(const T&);
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
141 142 143 144

  /// @brief prints the list of pairs coeff/monomial
  /// @param out output stream
  void print(std::ostream& out) const;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
145

146 147 148 149
  /// @brief compares leading monomials.
  /// @param P polynomial to be compared to.
  inline bool operator<(const polynomial<T>& P) const;

SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
150 151 152 153 154 155
  //human readable formatting
  friend std::ostream& operator<< <T>(std::ostream&, const polynomial<T>&);
};

#include "polynomial.tpp"
#endif