PolynomialSolver< _Scalar, _Deg > Class Template Reference

---

Detailed Description

template<typename _Scalar, int _Deg>
class PolynomialSolver< _Scalar, _Deg >

A polynomial solver.

Computes the complex roots of a real polynomial.

Parameters:

_Scalar	the scalar type, i.e., the type of the polynomial coefficients
_Deg	the degree of the polynomial, can be a compile time value or Dynamic. Notice that the number of polynomial coefficients is _Deg+1.

This class implements a polynomial solver and provides convenient methods such as

• real roots,
• greatest, smallest complex roots,
• real roots with greatest, smallest absolute real value.
• greatest, smallest real roots.

WARNING: this polynomial solver is experimental, part of the unsuported Eigen modules.

Currently a QR algorithm is used to compute the eigenvalues of the companion matrix of the polynomial to compute its roots. This supposes that the complex moduli of the roots are all distinct: e.g. there should be no multiple roots or conjugate roots for instance. With 32bit (float) floating types this problem shows up frequently. However, almost always, correct accuracy is reached even in these cases for 64bit (double) floating types and small polynomial degree (<20).

Definition at line 342 of file Polynomials.

Inheritance diagram for PolynomialSolver< _Scalar, _Deg >:

List of all members.

Public Types
typedef PolynomialSolverBase < _Scalar, _Deg >	PS_Base
typedef Matrix< Scalar, _Deg, _Deg >	CompanionMatrixType
typedef EigenSolver < CompanionMatrixType >	EigenSolverType
typedef _Scalar	Scalar
typedef NumTraits< Scalar >::Real	RealScalar
typedef std::complex< RealScalar >	RootType
typedef Matrix< RootType, _Deg, 1 >	RootsType
typedef DenseIndex	Index
Public Member Functions
template<typename OtherPolynomial >
void	compute (const OtherPolynomial &poly)
	Computes the complex roots of a new polynomial.
template<typename OtherPolynomial >
	PolynomialSolver (const OtherPolynomial &poly)
	PolynomialSolver ()
const RootsType &	roots () const
template<typename Stl_back_insertion_sequence >
void	realRoots (Stl_back_insertion_sequence &bi_seq, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
	Clear and fills the back insertion sequence with the real roots of the polynomial i.e.
const RootType &	greatestRoot () const
const RootType &	smallestRoot () const
const RealScalar &	absGreatestRealRoot (bool &hasArealRoot, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
const RealScalar &	absSmallestRealRoot (bool &hasArealRoot, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
const RealScalar &	greatestRealRoot (bool &hasArealRoot, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
const RealScalar &	smallestRealRoot (bool &hasArealRoot, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
Protected Member Functions
template<typename OtherPolynomial >
void	setPolynomial (const OtherPolynomial &poly)
template<typename squaredNormBinaryPredicate >
const RootType &	selectComplexRoot_withRespectToNorm (squaredNormBinaryPredicate &pred) const
template<typename squaredRealPartBinaryPredicate >
const RealScalar &	selectRealRoot_withRespectToAbsRealPart (squaredRealPartBinaryPredicate &pred, bool &hasArealRoot, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
template<typename RealPartBinaryPredicate >
const RealScalar &	selectRealRoot_withRespectToRealPart (RealPartBinaryPredicate &pred, bool &hasArealRoot, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
Protected Attributes
EigenSolverType	m_eigenSolver
RootsType	m_roots

---

Member Typedef Documentation

template<typename _Scalar , int _Deg>

typedef Matrix<Scalar,_Deg,_Deg> PolynomialSolver< _Scalar, _Deg >::CompanionMatrixType

Definition at line 350 of file Polynomials.

template<typename _Scalar , int _Deg>

typedef EigenSolver<CompanionMatrixType> PolynomialSolver< _Scalar, _Deg >::EigenSolverType

Definition at line 351 of file Polynomials.

template<typename _Scalar, int _Deg>

typedef DenseIndex PolynomialSolverBase< _Scalar, _Deg >::Index [inherited]

Definition at line 53 of file Polynomials.

template<typename _Scalar , int _Deg>

typedef PolynomialSolverBase<_Scalar,_Deg> PolynomialSolver< _Scalar, _Deg >::PS_Base

Definition at line 347 of file Polynomials.

template<typename _Scalar, int _Deg>

typedef NumTraits<Scalar>::Real PolynomialSolverBase< _Scalar, _Deg >::RealScalar [inherited]

Definition at line 49 of file Polynomials.

template<typename _Scalar, int _Deg>

typedef Matrix<RootType,_Deg,1> PolynomialSolverBase< _Scalar, _Deg >::RootsType [inherited]

Definition at line 51 of file Polynomials.

template<typename _Scalar, int _Deg>

typedef std::complex<RealScalar> PolynomialSolverBase< _Scalar, _Deg >::RootType [inherited]

Definition at line 50 of file Polynomials.

template<typename _Scalar, int _Deg>

typedef _Scalar PolynomialSolverBase< _Scalar, _Deg >::Scalar [inherited]

Definition at line 48 of file Polynomials.

---

Constructor & Destructor Documentation

template<typename _Scalar , int _Deg>

template<typename OtherPolynomial >

PolynomialSolver< _Scalar, _Deg >::PolynomialSolver

(

const OtherPolynomial &

poly

)

[inline]

Definition at line 367 of file Polynomials.

template<typename _Scalar , int _Deg>

PolynomialSolver< _Scalar, _Deg >::PolynomialSolver

(

)

[inline]

Definition at line 370 of file Polynomials.

---

Member Function Documentation

template<typename _Scalar, int _Deg>

const RealScalar& PolynomialSolverBase< _Scalar, _Deg >::absGreatestRealRoot	(	bool &	hasArealRoot,
		const RealScalar &	absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()
	)		const [inline, inherited]

Returns:

a real root with greatest absolute magnitude. A real root is defined as the real part of a complex root with absolute imaginary part smallest than absImaginaryThreshold. absImaginaryThreshold takes the dummy_precision associated with the _Scalar template parameter of the PolynomialSolver class as the default value. If no real root is found the boolean hasArealRoot is set to false and the real part of the root with smallest absolute imaginary part is returned instead.

Parameters:

[out]	hasArealRoot	: boolean true if a real root is found according to the absImaginaryThreshold criterion, false otherwise.
[in]	absImaginaryThreshold	: threshold on the absolute imaginary part to decide whether or not a root is real.

Definition at line 223 of file Polynomials.

template<typename _Scalar, int _Deg>

const RealScalar& PolynomialSolverBase< _Scalar, _Deg >::absSmallestRealRoot	(	bool &	hasArealRoot,
		const RealScalar &	absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()
	)		const [inline, inherited]

Returns:

a real root with smallest absolute magnitude. A real root is defined as the real part of a complex root with absolute imaginary part smallest than absImaginaryThreshold. absImaginaryThreshold takes the dummy_precision associated with the _Scalar template parameter of the PolynomialSolver class as the default value. If no real root is found the boolean hasArealRoot is set to false and the real part of the root with smallest absolute imaginary part is returned instead.

Parameters:

[out]	hasArealRoot	: boolean true if a real root is found according to the absImaginaryThreshold criterion, false otherwise.
[in]	absImaginaryThreshold	: threshold on the absolute imaginary part to decide whether or not a root is real.

Definition at line 246 of file Polynomials.

template<typename _Scalar , int _Deg>

template<typename OtherPolynomial >

void PolynomialSolver< _Scalar, _Deg >::compute

(

const OtherPolynomial &

poly

)

[inline]

Computes the complex roots of a new polynomial.

Definition at line 356 of file Polynomials.

template<typename _Scalar, int _Deg>

const RealScalar& PolynomialSolverBase< _Scalar, _Deg >::greatestRealRoot	(	bool &	hasArealRoot,
		const RealScalar &	absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()
	)		const [inline, inherited]

Returns:

the real root with greatest value. A real root is defined as the real part of a complex root with absolute imaginary part smallest than absImaginaryThreshold. absImaginaryThreshold takes the dummy_precision associated with the _Scalar template parameter of the PolynomialSolver class as the default value. If no real root is found the boolean hasArealRoot is set to false and the real part of the root with smallest absolute imaginary part is returned instead.

Parameters:

[out]	hasArealRoot	: boolean true if a real root is found according to the absImaginaryThreshold criterion, false otherwise.
[in]	absImaginaryThreshold	: threshold on the absolute imaginary part to decide whether or not a root is real.

Definition at line 269 of file Polynomials.

template<typename _Scalar, int _Deg>

const RootType& PolynomialSolverBase< _Scalar, _Deg >::greatestRoot

(

)

const [inline, inherited]

Returns:

the complex root with greatest norm.

Definition at line 113 of file Polynomials.

template<typename _Scalar, int _Deg>

template<typename Stl_back_insertion_sequence >

void PolynomialSolverBase< _Scalar, _Deg >::realRoots	(	Stl_back_insertion_sequence &	bi_seq,
		const RealScalar &	absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()
	)		const [inline, inherited]

Clear and fills the back insertion sequence with the real roots of the polynomial i.e.

the real part of the complex roots that have an imaginary part which absolute value is smaller than absImaginaryThreshold. absImaginaryThreshold takes the dummy_precision associated with the _Scalar template parameter of the PolynomialSolver class as the default value.

Parameters:

[out]	bi_seq	: the back insertion sequence (stl concept)
[in]	absImaginaryThreshold	: the maximum bound of the imaginary part of a complex number that is considered as real.

Definition at line 83 of file Polynomials.

template<typename _Scalar, int _Deg>

const RootsType& PolynomialSolverBase< _Scalar, _Deg >::roots

(

)

const [inline, inherited]

Returns:

the complex roots of the polynomial

Definition at line 69 of file Polynomials.

template<typename _Scalar, int _Deg>

template<typename squaredNormBinaryPredicate >

const RootType& PolynomialSolverBase< _Scalar, _Deg >::selectComplexRoot_withRespectToNorm

(

squaredNormBinaryPredicate &

pred

)

const [inline, protected, inherited]

Definition at line 96 of file Polynomials.

template<typename _Scalar, int _Deg>

template<typename squaredRealPartBinaryPredicate >

const RealScalar& PolynomialSolverBase< _Scalar, _Deg >::selectRealRoot_withRespectToAbsRealPart	(	squaredRealPartBinaryPredicate &	pred,
		bool &	hasArealRoot,
		const RealScalar &	absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()
	)		const [inline, protected, inherited]

Definition at line 130 of file Polynomials.

template<typename _Scalar, int _Deg>

template<typename RealPartBinaryPredicate >

const RealScalar& PolynomialSolverBase< _Scalar, _Deg >::selectRealRoot_withRespectToRealPart	(	RealPartBinaryPredicate &	pred,
		bool &	hasArealRoot,
		const RealScalar &	absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()
	)		const [inline, protected, inherited]

Definition at line 170 of file Polynomials.

template<typename _Scalar, int _Deg>

template<typename OtherPolynomial >

void PolynomialSolverBase< _Scalar, _Deg >::setPolynomial

(

const OtherPolynomial &

poly

)

[inline, protected, inherited]

Definition at line 57 of file Polynomials.

template<typename _Scalar, int _Deg>

const RealScalar& PolynomialSolverBase< _Scalar, _Deg >::smallestRealRoot	(	bool &	hasArealRoot,
		const RealScalar &	absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()
	)		const [inline, inherited]

Returns:

the real root with smallest value. A real root is defined as the real part of a complex root with absolute imaginary part smallest than absImaginaryThreshold. absImaginaryThreshold takes the dummy_precision associated with the _Scalar template parameter of the PolynomialSolver class as the default value. If no real root is found the boolean hasArealRoot is set to false and the real part of the root with smallest absolute imaginary part is returned instead.

Parameters:

[out]	hasArealRoot	: boolean true if a real root is found according to the absImaginaryThreshold criterion, false otherwise.
[in]	absImaginaryThreshold	: threshold on the absolute imaginary part to decide whether or not a root is real.

Definition at line 292 of file Polynomials.

template<typename _Scalar, int _Deg>

const RootType& PolynomialSolverBase< _Scalar, _Deg >::smallestRoot

(

)

const [inline, inherited]

Returns:

the complex root with smallest norm.

Definition at line 122 of file Polynomials.

---

Member Data Documentation

template<typename _Scalar , int _Deg>

EigenSolverType PolynomialSolver< _Scalar, _Deg >::m_eigenSolver [protected]

Definition at line 374 of file Polynomials.

template<typename _Scalar, int _Deg>

RootsType PolynomialSolverBase< _Scalar, _Deg >::m_roots [protected, inherited]

Definition at line 301 of file Polynomials.