polynomial.h 3.97 KB
Newer Older
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/* Copyright (C) 2016 tinygb
 * Written by <pierre-jean.spaenlehauer@inria.fr>
 *
 * ========LICENCE========
 * This file is part of tinygb.
 *
 * FFLAS-FFPACK is free software: you can redistribute it and/or modify
 * 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
19
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
20 21 22 23
 * ========LICENCE========
 *
 */

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

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

#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
38
std::ostream& operator<<(std::ostream &o, const polynomial<T> &p);
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
39

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

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

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

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

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

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

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

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

SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
120 121 122
  /// @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
123
  bool topred(const polynomial &g);
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
124 125 126 127

  /// @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
128
  bool istopred(const polynomial &g) const;
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
129 130 131 132

  /// @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
133 134 135 136 137 138 139 140 141
  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
142 143 144 145

  /// @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
146 147 148 149 150 151 152

  //human readable formatting
  friend std::ostream& operator<< <T>(std::ostream&, const polynomial<T>&);
};

#include "polynomial.tpp"
#endif