Linear algebra and decompositions

Catalogue of decompositions offered by Eigen

Generic information, not Eigen-specific

Eigen-specific

Decomposition Requirements on the matrix Speed Algorithm reliability and accuracy Rank-revealing Allows to compute (besides linear solving) Linear solver provided by Eigen Maturity of Eigen's implementation

Optimizations

PartialPivLU Invertible Fast Depends on condition number - - Yes Excellent

Blocking

FullPivLU - Slow Proven Yes - Yes Excellent

-

HouseholderQR - Fast Depends on condition number - Orthogonalization Yes Excellent

Blocking

ColPivHouseholderQR - Fast Good Yes Orthogonalization Yes Excellent

Soon: blocking

FullPivHouseholderQR - Slow Proven Yes Orthogonalization Yes Average

-

LLT Positive definite Very fast Depends on condition number - - Yes Excellent

Blocking
Soon: meta unroller

LDLT Positive or negative semidefinite1 Very fast Good - - Yes Excellent

Soon: blocking


Singular values and eigenvalues decompositions

JacobiSVD (two-sided) - Slow (but fast for small matrices) Excellent-Proven3 Yes Singular values/vectors, least squares Yes (and does least squares) Excellent

R-SVD

SelfAdjointEigenSolver Self-adjoint Fast-average2 Good Yes Eigenvalues/vectors - Good

Soon: specializations for 2x2 and 3x3

ComplexEigenSolver Square Slow-very slow2 Depends on condition number Yes Eigenvalues/vectors - Average

-

EigenSolver Square and real Average-slow2 Depends on condition number Yes Eigenvalues/vectors - Average

-

GeneralizedSelfAdjointEigenSolver Square Fast-average2 Depends on condition number - Generalized eigenvalues/vectors - Good

-


Helper decompositions

RealSchur Square and real Average-slow2 Depends on condition number Yes - - Average

-

ComplexSchur Square Slow-very slow2 Depends on condition number Yes - - Average

-

Tridiagonalization Self-adjoint Fast Good - - - Good

Soon: blocking

HessenbergDecomposition Square Average Good - - - Good

Soon: blocking

Notes:

Terminology

Selfadjoint
For a real matrix, selfadjoint is a synonym for symmetric. For a complex matrix, selfadjoint is a synonym for hermitian. More generally, a matrix $ A $ is selfadjoint if and only if it is equal to its adjoint $ A^* $. The adjoint is also called the conjugate transpose.
Positive/negative definite
A selfadjoint matrix $ A $ is positive definite if $ v^* A v > 0 $ for any non zero vector $ v $. In the same vein, it is negative definite if $ v^* A v < 0 $ for any non zero vector $ v $
Positive/negative semidefinite

A selfadjoint matrix $ A $ is positive semi-definite if $ v^* A v \ge 0 $ for any non zero vector $ v $. In the same vein, it is negative semi-definite if $ v^* A v \le 0 $ for any non zero vector $ v $

Blocking
Means the algorithm can work per block, whence guaranteeing a good scaling of the performance for large matrices.
Meta-unroller
Means the algorithm is automatically and explicitly unrolled for very small fixed size matrices.


libicr
Author(s): Robert Krug
autogenerated on Mon Jan 6 2014 11:34:09