Eigen::LookAheadLevinson< Scalar_ > Class Template Reference

#include <contrib/Eigen/src/StructuredMatrices/LookAheadLevinson.h>

Detailed Description

template<typename Scalar_>
class Eigen::LookAheadLevinson< Scalar_ >

Look-ahead Levinson direct solver for general Toeplitz systems.

Solves T*x = b for a square Toeplitz matrix T in O(n^2) operations. This is an implementation of the look-ahead Levinson algorithm of T. F. Chan and P. C. Hansen, which extends the classical Levinson recursion to remain (weakly) numerically stable for general — including indefinite and ill-conditioned — Toeplitz matrices. When the recursion would otherwise break down at a near-singular leading principal submatrix, the algorithm "looks ahead" and takes a block step (up to maxBlockSize) over it. As a by-product it produces an estimate of the matrix condition number (conditionEstimate).

The class derives from SolverBase and follows the usual decomposition style; transposed and adjoint systems reuse the factorization of T through the persymmetry \( T^T = E T E \) (with E the exchange matrix), so all three solves below cost the same:

LookAheadLevinson<double> levinson(T);      // or levinson.compute(T);
VectorXd x = levinson.solve(b);              // solve T   * x = b
VectorXd y = levinson.transpose().solve(b);  // solve T^T * y = b
VectorXd z = levinson.adjoint().solve(b);    // solve T^H * z = b

Template Parameters

Scalar_

the scalar type, real or complex.

References:

• T. F. Chan and P. C. Hansen, "A look-ahead Levinson algorithm for general Toeplitz systems," IEEE Trans. Signal Process., 40(5):1079-1090, 1992.
• T. F. Chan and P. C. Hansen, "A look-ahead Levinson algorithm for indefinite Toeplitz systems," SIAM J. Matrix Anal. Appl., 13(2):490-506, 1992.

See also

class Toeplitz

Inheritance diagram for Eigen::LookAheadLevinson< Scalar_ >:

Public Member Functions
template<int Rows_, int Cols_>
LookAheadLevinson &	compute (const Toeplitz< Scalar, Rows_, Cols_ > &T)
RealScalar	conditionEstimate () const
ComputationInfo	info () const
	LookAheadLevinson ()
template<int Rows_, int Cols_>
	LookAheadLevinson (const Toeplitz< Scalar, Rows_, Cols_ > &T)
Index	maxBlockSize () const
LookAheadLevinson &	setMaxBlockSize (Index p)
template<typename Rhs>
const Solve< LookAheadLevinson, Rhs >	solve (const MatrixBase< Rhs > &b) const

Constructor & Destructor Documentation

LookAheadLevinson() [1/2]

template<typename Scalar_>

Eigen::LookAheadLevinson< Scalar_ >::LookAheadLevinson ( )

inline

Default constructor; call compute before solve.

LookAheadLevinson() [2/2]

template<typename Scalar_>

template<int Rows_, int Cols_>

Eigen::LookAheadLevinson< Scalar_ >::LookAheadLevinson ( const Toeplitz< Scalar, Rows_, Cols_ > & T )

inlineexplicit

Constructs and factorizes from the Toeplitz matrix T, which may have fixed or dynamic dimensions.

Member Function Documentation

compute()

template<typename Scalar_>

template<int Rows_, int Cols_>

LookAheadLevinson & Eigen::LookAheadLevinson< Scalar_ >::compute

(

const Toeplitz< Scalar, Rows_, Cols_ > &

T

)

Factorizes the square Toeplitz matrix T.

See also

solve

conditionEstimate()

template<typename Scalar_>

RealScalar Eigen::LookAheadLevinson< Scalar_ >::conditionEstimate ( ) const

inline

Returns

an estimate of the 2-norm condition number of T, available after compute (the "algorithm condition number" of Chan and Hansen).

info()

template<typename Scalar_>

ComputationInfo Eigen::LookAheadLevinson< Scalar_ >::info ( ) const

inline

Returns

Success if the algorithm could skip all ill-conditioned leading submatrices within the look-ahead range, NumericalIssue otherwise.

maxBlockSize()

template<typename Scalar_>

Index Eigen::LookAheadLevinson< Scalar_ >::maxBlockSize ( ) const

inline

Returns

the maximum look-ahead block size \( p_{\max} \).

See also

setMaxBlockSize

setMaxBlockSize()

template<typename Scalar_>

LookAheadLevinson & Eigen::LookAheadLevinson< Scalar_ >::setMaxBlockSize ( Index p )

inline

Sets the maximum look-ahead block size \( p_{\max} \) (default 4). The solver is numerically stable as long as T has no more than p-1 consecutive ill-conditioned leading principal submatrices. Must be called before compute.

solve()

template<typename Scalar_>

template<typename Rhs>

const Solve< LookAheadLevinson, Rhs > Eigen::LookAheadLevinson< Scalar_ >::solve ( const MatrixBase< Rhs > & b ) const

inline

Returns

the solution x of T*x = b, as a lazily evaluated expression. Supports multiple right-hand sides. The transposed and adjoint systems are solved at the same cost, and with the same factorization, through transpose().solve(b) and adjoint().solve(b).

Precondition

compute has been called.

---

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

• /builds/libeigen/eigen/contrib/Eigen/src/StructuredMatrices/LookAheadLevinson.h