Eigen::PolynomialSolver< Scalar_, Deg_ > Class Template Reference

#include <contrib/Eigen/src/Polynomials/PolynomialSolver.h>

Detailed Description

template<typename Scalar_, int Deg_>
class Eigen::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 contrib Eigen modules.

The eigenvalues of the balanced companion matrix of the polynomial give first approximations of the roots. Ehrlich-Aberth iterations on the polynomial itself target a residual within the rounding error of evaluation, with a finite sweep limit and an initial-estimate fallback for unfinished iterates whose residual increased. The roots of a real polynomial are returned as real numbers or exact conjugate pairs. A root of multiplicity \( m \) can only be located to about \( \varepsilon^{1/m} \).

Inheritance diagram for Eigen::PolynomialSolver< Scalar_, Deg_ >:

Public Member Functions
template<typename OtherPolynomial>
void	compute (const OtherPolynomial &poly)
Public Member Functions inherited from Eigen::PolynomialSolverBase< Scalar_, Deg_ >
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 RootType &	greatestRoot () const
template<typename Stl_back_insertion_sequence>
void	realRoots (Stl_back_insertion_sequence &bi_seq, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
const RootsType &	roots () const
const RealScalar &	smallestRealRoot (bool &hasArealRoot, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
const RootType &	smallestRoot () const

Protected Member Functions
template<typename OtherPolynomial>
void	cleanUpRoots (const OtherPolynomial &poly)
template<typename OtherPolynomial>
void	refineRoots (const OtherPolynomial &poly)

Member Function Documentation

cleanUpRoots()

template<typename Scalar_, int Deg_>

template<typename OtherPolynomial>

void Eigen::PolynomialSolver< Scalar_, Deg_ >::cleanUpRoots ( const OtherPolynomial & poly )

inlineprotected

Restores the structure the in-place iteration keeps only to within rounding. The roots of a real polynomial are real or conjugate pairs: two iterates closer to each other's conjugate than to the real axis become exactly conjugate, and an iterate left without a partner becomes real. Residual-based snapping of the remaining roots requires an imaginary part at most sqrt(eps) times the real part and a finite rounding bound.

compute()

template<typename Scalar_, int Deg_>

template<typename OtherPolynomial>

void Eigen::PolynomialSolver< Scalar_, Deg_ >::compute ( const OtherPolynomial & poly )

inline

Computes the complex roots of a new polynomial.

refineRoots()

template<typename Scalar_, int Deg_>

template<typename OtherPolynomial>

void Eigen::PolynomialSolver< Scalar_, Deg_ >::refineRoots ( const OtherPolynomial & poly )

inlineprotected

Refines the eigenvalue estimates in m_roots by Ehrlich-Aberth iterations (Ehrlich 1967; Aberth 1973), \( z_i \leftarrow z_i - w_i / (1 - w_i \sum_{j \ne i} (z_i - z_j)^{-1}) \) with \( w_i = p(z_i) / p'(z_i) \). The iteration is cubic for simple roots, and the sum keeps the iterates apart, so every root is refined at once without deflation. Updates use the latest estimates; real starting values receive an epsilon-sized imaginary perturbation so they can reach nonreal roots. At the sweep limit, unfinished estimates are compared with their initial polynomial residuals. A root is final once \( |p(z_i)| \) is within the rounding bound of its evaluation, so that \( z_i \) is an exact root of a polynomial that close to \( p \) (the stopping rule of Bini 1996), or once its Newton correction is below one ulp.

---

The documentation for this class was generated from the following file:

• /builds/libeigen/eigen/contrib/Eigen/src/Polynomials/PolynomialSolver.h