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, Implicit MT

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

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

Closed forms 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.
Implicit Multi Threading (MT)
Means the algorithm can take advantage of multicore processors via OpenMP. "Implicit" means the algortihm itself is not parallelized, but that it relies on parallelized matrix-matrix product rountines.
Explicit Multi Threading (MT)
Means the algorithm is explicitely parallelized to take advantage of multicore processors via OpenMP.
Meta-unroller
Means the algorithm is automatically and explicitly unrolled for very small fixed size matrices.