Polynomial< T, NumberTraits > Class Template Reference

#include <Polynomial.h>

List of all members.

Public Types

typedef Polynomial< T, NumberTraits > poly_type
 Shortcut for a polynomial type.
typedef T number_type
 Type of the coefficients of the polynomial.
typedef NumberTraits traits_type
 Associated AlgebraicTraits type to the type of polynomial coefficients.
typedef traits_type::scalar_type scalar_type
 A scalar type.
typedef Complex< scalar_type > complex_type
 Complex number type, roots of polynomials with real coefficients can be complex.

Public Member Functions

 Polynomial ()
 Polynomial (unsigned int nSize)
 Polynomial (const poly_type &other)
 ~Polynomial ()
poly_type & operator= (const poly_type &other)
unsigned int size () const
unsigned int capacity () const
int degree () const
 operator number_type * () const
number_type operator() (const number_type &arg) const
poly_type zero () const
poly_type one () const
poly_type & minus ()
poly_type operator- () const
poly_type & operator+= (const poly_type &rhs)
poly_type operator+ (const poly_type &rhs) const
poly_type & operator-= (const poly_type &rhs)
poly_type operator- (const poly_type &rhs) const
poly_type & operator *= (const poly_type &rhs)
poly_type operator * (const poly_type &rhs) const
poly_type & operator+= (const number_type &rhs)
poly_type operator+ (const number_type &rhs) const
poly_type & operator-= (const number_type &rhs)
poly_type operator- (const number_type &rhs) const
poly_type & operator *= (const number_type &rhs)
poly_type operator * (const number_type &rhs) const
bool operator== (const poly_type &rhs) const
bool operator!= (const poly_type &rhs) const
bool operator< (const poly_type &rhs) const
number_type getNorm () const
number_type evaluate (const number_type &arg) const
void display (std::ostream &os=std::cout) const
number_type syntheticDivision (const number_type &value)
void polyDiv (const poly_type &other, poly_type &quotient, poly_type &reminder)
poly_type & toMonicForm ()
poly_type & fromRoots (const std::vector< number_type > &roots)
poly_type & monomialMultiplication (const number_type &value)
int roots (std::vector< Complex< scalar_type > > &roots, bool polish=true)
void load (std::istream &is)
void save (std::ostream &os) const

Static Public Member Functions

static void gcd (poly_type p1, poly_type p2, poly_type &result)
static void lcm (const poly_type &p1, const poly_type &p2, poly_type &result)

Friends

poly_type operator+ (const number_type &lhs, const poly_type &rhs)
poly_type operator- (const number_type &lhs, const poly_type &rhs)
poly_type operator * (const number_type &lhs, const poly_type &rhs)
std::ostream & operator<< (std::ostream &os, const poly_type &p)
std::istream & operator>> (std::istream &is, poly_type &p)

Detailed Description

template<class T, typename NumberTraits = AlgebraicTraits< T >>
class Polynomial< T, NumberTraits >

A polynomial Is represented as a set of coefficients stored in an array. The first template parameter represents the type of coefficients and the second template parameter of the Polynomial class represents the traits class associated to the first template parameter and is by default AlgebraicTraits<T>

Definition at line 31 of file Polynomial.h.

Constructor & Destructor Documentation

template<class T, typename NumberTraits = AlgebraicTraits< T >>
Polynomial< T, NumberTraits >::Polynomial (  )  [inline]

Default constructor

Definition at line 48 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
Polynomial< T, NumberTraits >::Polynomial ( unsigned int  nSize  )  [inline, explicit]

Constructor

Parameters:
nSize Number of polynomial coefficients to allocate memory for

Definition at line 57 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
Polynomial< T, NumberTraits >::Polynomial ( const poly_type &  other  )  [inline]

Copy constructor

Parameters:
other Polynomial to copy

Definition at line 65 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
Polynomial< T, NumberTraits >::~Polynomial (  )  [inline]

Destructor

Definition at line 89 of file Polynomial.h.

Member Function Documentation

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type& Polynomial< T, NumberTraits >::operator= ( const poly_type &  other  )  [inline]

Assignment operator

Parameters:
other Polynomial to copy
Returns:
Refference to this polynomial.

Definition at line 98 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
unsigned int Polynomial< T, NumberTraits >::size (  )  const [inline]

Get the number of the coefficients of the polynomial

Returns:
number of polynomial coeficients, excluding zero leading coefficients

Definition at line 137 of file Polynomial.h.

Referenced by Polynomial< T, NumberTraits >::evaluate(), Polynomial< T, NumberTraits >::getNorm(), AlgebraicTraits< RationalFunction< ScalarType, AlgebraicTraits< ScalarType > > >::is_zero(), AlgebraicTraits< Polynomial< ScalarType, AlgebraicTraits< ScalarType > > >::is_zero(), Polynomial< T, NumberTraits >::monomialMultiplication(), RationalFunction< T, NumberTraits >::normalize(), Polynomial< T, NumberTraits >::operator *=(), Polynomial< T, NumberTraits >::operator+=(), Polynomial< T, NumberTraits >::operator-=(), Polynomial< T, NumberTraits >::operator=(), Polynomial< T, NumberTraits >::operator==(), Polynomial< T, NumberTraits >::polyDiv(), Polynomial< T, NumberTraits >::Polynomial(), RationalFunction< T, NumberTraits >::RationalFunction(), Polynomial< T, NumberTraits >::roots(), Polynomial< T, NumberTraits >::syntheticDivision(), and Polynomial< T, NumberTraits >::toMonicForm().

Here is the caller graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
unsigned int Polynomial< T, NumberTraits >::capacity (  )  const [inline]

Get the count of coefficients the polynomial has allocated memory

Definition at line 144 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
int Polynomial< T, NumberTraits >::degree (  )  const [inline]

Return the degree of the polynomial

Remarks:
This function returns size() - 1

Definition at line 152 of file Polynomial.h.

Referenced by AlgebraicTraits< Polynomial< ScalarType, AlgebraicTraits< ScalarType > > >::degree(), Polynomial< T, NumberTraits >::polyDiv(), and Polynomial< T, NumberTraits >::roots().

Here is the caller graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
Polynomial< T, NumberTraits >::operator number_type * (  )  const [inline]

Casting operator to number type.

Remarks:
This operator is used to access polynomial coefficients using normal C pointer indexing syntax (e.g. poly[0] = 3.14). The leading coefficients are at lower indexes. e.g. poly[0] is the most significant (or leading) coefficient and poly[poly.size() - 1] is the least significant coefficient

Definition at line 164 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
number_type Polynomial< T, NumberTraits >::operator() ( const number_type &  arg  )  const [inline]

Function call operator.

Parameters:
arg Point in which to evaluate the polynomial
See also:
evaluate()
Returns:
The value of the polynomial at the given point
Remarks:
Evaluates the polynomial at the supplied argument

Definition at line 177 of file Polynomial.h.

References Polynomial< T, NumberTraits >::evaluate().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type Polynomial< T, NumberTraits >::zero (  )  const [inline]

Create the null polynomial.

Returns:
A polynomial having the same degree equal to zero and its only coefficient equal to zero.

Definition at line 186 of file Polynomial.h.

Referenced by Polynomial< T, NumberTraits >::operator *=(), Polynomial< T, NumberTraits >::polyDiv(), and Polynomial< T, NumberTraits >::roots().

Here is the caller graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type Polynomial< T, NumberTraits >::one (  )  const [inline]

Create the identity polynomial with regard to polynomial multiplication.

Returns:
A polynomial having the degree equal to zero and its only coefficient equal to one.

Definition at line 198 of file Polynomial.h.

Referenced by Polynomial< T, NumberTraits >::fromRoots().

Here is the caller graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type& Polynomial< T, NumberTraits >::minus (  )  [inline]

Return inverts this polynomial with regard to polynomial addition.

Returns:
a refference to this polynomial after modification

Definition at line 209 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type Polynomial< T, NumberTraits >::operator- (  )  const [inline]

Unary minus operator.

Returns:
zero minus this polynomial

Definition at line 221 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type& Polynomial< T, NumberTraits >::operator+= ( const poly_type &  rhs  )  [inline]

Addition assignment

Precondition:
Neither this nor rhs can not be empty polynomials.
Parameters:
rhs Right hand side operand
Returns:
Refference to this polynomial after the addition

Definition at line 238 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type Polynomial< T, NumberTraits >::operator+ ( const poly_type &  rhs  )  const [inline]

Addition operator

Parameters:
rhs Right hand side operand
Returns:
The result of the addition

Definition at line 282 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type& Polynomial< T, NumberTraits >::operator-= ( const poly_type &  rhs  )  [inline]

Subtraction assignment

Parameters:
rhs right hand side operand
Returns:
Refference to this polynomial after the subtraction

Definition at line 291 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type Polynomial< T, NumberTraits >::operator- ( const poly_type &  rhs  )  const [inline]

Subtraction operator

Parameters:
rhs right hand side operand
Returns:
The result of the subtraction

Definition at line 335 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type& Polynomial< T, NumberTraits >::operator *= ( const poly_type &  rhs  )  [inline]

Multiplication assignment

Parameters:
rhs right hand side operand
Returns:
Refference to this polynomial after the multiplication

Definition at line 344 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size(), and Polynomial< T, NumberTraits >::zero().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type Polynomial< T, NumberTraits >::operator * ( const poly_type &  rhs  )  const [inline]

Polynomial multiplication operator

Parameters:
rhs right hand side operand
Returns:
The result of the multiplication

Definition at line 397 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type& Polynomial< T, NumberTraits >::operator+= ( const number_type &  rhs  )  [inline]

Addition assignment

Parameters:
rhs right hand side operand
Returns:
Refference to this polynomial after the addition

Definition at line 406 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type Polynomial< T, NumberTraits >::operator+ ( const number_type &  rhs  )  const [inline]

Addition operator

Parameters:
rhs right hand side operand
Returns:
The result of the addition

Definition at line 423 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type& Polynomial< T, NumberTraits >::operator-= ( const number_type &  rhs  )  [inline]

Subtraction assignment

Parameters:
rhs right hand side operand
Returns:
Refference to this polynomial after the subtraction

Definition at line 432 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type Polynomial< T, NumberTraits >::operator- ( const number_type &  rhs  )  const [inline]

Subtraction operator

Parameters:
rhs right hand side operand
Returns:
The result of the subtraction

Definition at line 449 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type& Polynomial< T, NumberTraits >::operator *= ( const number_type &  rhs  )  [inline]

Multiplication assignment

Parameters:
rhs right hand side operand
Returns:
Refference to this polynomial after the multiplication

Definition at line 458 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type Polynomial< T, NumberTraits >::operator * ( const number_type &  rhs  )  const [inline]

Multiplication operator

Parameters:
rhs right hand side operand
Returns:
The result of the multiplication

Definition at line 478 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
bool Polynomial< T, NumberTraits >::operator== ( const poly_type &  rhs  )  const [inline]

Equality operator

Parameters:
rhs right hand side operand
Returns:
true if this polynomial is equal to the right hand side polynomial and false otherwise

Definition at line 521 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
bool Polynomial< T, NumberTraits >::operator!= ( const poly_type &  rhs  )  const [inline]

Inequality operator

Parameters:
rhs right hand side operand
Returns:
true if this polynomial is different to the right hand side polynomial and false otherwise

Definition at line 544 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
bool Polynomial< T, NumberTraits >::operator< ( const poly_type &  rhs  )  const [inline]

Comparison operator

Parameters:
rhs right hand side polynomial
Returns:
true if the norm of this polynomial is less than the norm of the right hand side polynomial and false otherwise

Definition at line 554 of file Polynomial.h.

References Polynomial< T, NumberTraits >::getNorm().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
number_type Polynomial< T, NumberTraits >::getNorm (  )  const [inline]

Compute a norm for this polynomial

Returns:
the value of the polynomial at the point one

Definition at line 577 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Referenced by AlgebraicTraits< Polynomial< ScalarType, AlgebraicTraits< ScalarType > > >::norm(), and Polynomial< T, NumberTraits >::operator<().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
number_type Polynomial< T, NumberTraits >::evaluate ( const number_type &  arg  )  const [inline]

Evaluate this polynomial at a given point

Parameters:
arg The point in which to evaluate the polynomial
Returns:
the value of the polynomial at point given as argument

Definition at line 600 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Referenced by Polynomial< T, NumberTraits >::operator()().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
void Polynomial< T, NumberTraits >::display ( std::ostream &  os = std::cout  )  const [inline]

Display this polynomial to a stream

Parameters:
os The output stream

Definition at line 625 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
number_type Polynomial< T, NumberTraits >::syntheticDivision ( const number_type &  value  )  [inline]

Performs synthetic division, i.e. divide this polynomial by the polynomial (x - value). The reminder in this case is a number.

Parameters:
value the free term of the polynomial (x - a)
Returns:
The remainder of the division.

Definition at line 646 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
void Polynomial< T, NumberTraits >::polyDiv ( const poly_type &  other,
poly_type &  quotient,
poly_type &  reminder 
) [inline]

Performs polynomial division (long division).

Precondition:
The algebraic structure formed by the polynomial coefficients must be at least a field. This function will throw an exception if polynomial coefficients are from an integral domain or general ring.
Parameters:
other the divisor
quotient [out] refference to a polynomial that will hold the quotient of the division
reminder [out] refference to a polynomial that will hold the reminder of the division
Remarks:
This polynomial is the dividend.
Todo:
Implement division algorithm for polynomials with coefficients from an integral domain.

Definition at line 683 of file Polynomial.h.

References Polynomial< T, NumberTraits >::degree(), Polynomial< T, NumberTraits >::resize(), Polynomial< T, NumberTraits >::size(), Polynomial< T, NumberTraits >::trimZeros(), and Polynomial< T, NumberTraits >::zero().

Referenced by Polynomial< T, NumberTraits >::gcd(), Polynomial< T, NumberTraits >::lcm(), RationalFunction< T, NumberTraits >::operator *=(), RationalFunction< T, NumberTraits >::operator+=(), RationalFunction< T, NumberTraits >::operator-=(), and RationalFunction< T, NumberTraits >::operator/=().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type& Polynomial< T, NumberTraits >::toMonicForm (  )  [inline]

Bring this polynomial to monic form.

Precondition:
Polynomial coefficients must at least be from a field, or else an exception will be thrown.
Returns:
Refference to this polynomial after the transformation
Remarks:
divide all coefficients by the leading coefficient (of X^n).

Definition at line 745 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Referenced by Polynomial< T, NumberTraits >::gcd(), and Polynomial< T, NumberTraits >::lcm().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
static void Polynomial< T, NumberTraits >::gcd ( poly_type  p1,
poly_type  p2,
poly_type &  result 
) [inline, static]

Compute the greatest common divisor of two polynomials.

Precondition:
Polynomial coefficients must at least be from a field, or else an exception will be thrown from the division algorithm.
Parameters:
p1 first polynomial
p2 second polynomial
result [out] refference to a polynomial that will contain the greatest common divisor.
Remarks:
Uses Euclid's algorithm.

Definition at line 781 of file Polynomial.h.

References Polynomial< T, NumberTraits >::polyDiv(), and Polynomial< T, NumberTraits >::toMonicForm().

Referenced by Polynomial< T, NumberTraits >::lcm(), RationalFunction< T, NumberTraits >::normalize(), RationalFunction< T, NumberTraits >::operator *=(), RationalFunction< T, NumberTraits >::operator+=(), RationalFunction< T, NumberTraits >::operator-=(), and RationalFunction< T, NumberTraits >::operator/=().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
static void Polynomial< T, NumberTraits >::lcm ( const poly_type &  p1,
const poly_type &  p2,
poly_type &  result 
) [inline, static]

Compute the least common multiple of two polynomials

Precondition:
Polynomial coefficients must at least be from a field, or else an exception will be thrown from the division algorithm.
Parameters:
p1 first polynomial
p2 second polynomial
result [out] refference to a polynomial that will contain the least common multiple.
Remarks:
Uses the formula: lcm(p1, p2) = (p1 * p2) / gcd(p1, p2)

Definition at line 806 of file Polynomial.h.

References Polynomial< T, NumberTraits >::gcd(), Polynomial< T, NumberTraits >::polyDiv(), and Polynomial< T, NumberTraits >::toMonicForm().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type& Polynomial< T, NumberTraits >::fromRoots ( const std::vector< number_type > &  roots  )  [inline]

Creates this polynomial given its roots

Precondition:
This polynomial must be empty.
Parameters:
roots A vector containing the roots
Returns:
A refference to this polynomial.

Definition at line 820 of file Polynomial.h.

References AlgebraicTraits< T >::one(), and Polynomial< T, NumberTraits >::one().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type& Polynomial< T, NumberTraits >::monomialMultiplication ( const number_type &  value  )  [inline]

Multiply this polynomial by the monomial (X - value)

Precondition:
This polynomial can not be empty.
Parameters:
value The free term of the multiplicand polynomial
Returns:
A refference to this polynomial.
Remarks:
This is a rather slow function so better avoid it.

Definition at line 860 of file Polynomial.h.

References Polynomial< T, NumberTraits >::size().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
int Polynomial< T, NumberTraits >::roots ( std::vector< Complex< scalar_type > > &  roots,
bool  polish = true 
) [inline]

Find all complex roots of this polynomial

Precondition:
This polynomial can not be empty.
Parameters:
[out] roots The vector to receive the roots.
polish Should we perform root polishing?
Returns:
A refference to this polynomial.
Remarks:
Unfortunately the precision of this function is very poor. It uses laguer() routine repeatedly followed by a polynomial deflation by the found root

Definition at line 895 of file Polynomial.h.

References Polynomial< T, NumberTraits >::degree(), Polynomial< T, NumberTraits >::size(), AlgebraicTraits< T >::zero(), and Polynomial< T, NumberTraits >::zero().

Here is the call graph for this function:

template<class T, typename NumberTraits = AlgebraicTraits< T >>
void Polynomial< T, NumberTraits >::load ( std::istream &  is  )  [inline]

Load this from a stream

Parameters:
is stream to load from

Definition at line 979 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
void Polynomial< T, NumberTraits >::save ( std::ostream &  os  )  const [inline]

Save this to a stream

Parameters:
os stream to save to

Definition at line 1001 of file Polynomial.h.

Friends And Related Function Documentation

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type operator+ ( const number_type &  lhs,
const poly_type &  rhs 
) [friend]

Addition with a scalar

Parameters:
lhs left hand side operand
rhs right hand side operand
Returns:
the result of the operation

Definition at line 489 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type operator- ( const number_type &  lhs,
const poly_type &  rhs 
) [friend]

Subtraction with a scalar

Parameters:
lhs left hand side operand
rhs right hand side operand
Returns:
the result of the operation

Definition at line 500 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
poly_type operator * ( const number_type &  lhs,
const poly_type &  rhs 
) [friend]

Multiplication with a scalar

Parameters:
lhs left hand side operand
rhs right hand side operand
Returns:
the result of the operation

Definition at line 511 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
std::ostream& operator<< ( std::ostream &  os,
const poly_type &  p 
) [friend]

std::ostream insertion operator

Definition at line 953 of file Polynomial.h.

template<class T, typename NumberTraits = AlgebraicTraits< T >>
std::istream& operator>> ( std::istream &  is,
poly_type &  p 
) [friend]

std::istream extraction operator

Definition at line 964 of file Polynomial.h.

The documentation for this class was generated from the following file:
Math-Objects Library Docs  Generated by: doxygen