Please, help us to better know about our user community by answering the following short survey: https://forms.gle/wpyrxWi18ox9Z5ae9 Eigen  3.3.9 Catalogue of dense decompositions

This page presents a catalogue of the dense matrix decompositions offered by Eigen. For an introduction on linear solvers and decompositions, check this page . To get an overview of the true relative speed of the different decompositions, check this benchmark .

# 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

BDCSVD (divide & conquer) - One of the fastest SVD algorithms Excellent Yes Singular values/vectors, least squares Yes (and does least squares) Excellent

Blocked bidiagonalization

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

R-SVD

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:

• 1: There exist two variants of the LDLT algorithm. Eigen's one produces a pure diagonal D matrix, and therefore it cannot handle indefinite matrices, unlike Lapack's one which produces a block diagonal D matrix.
• 2: Eigenvalues, SVD and Schur decompositions rely on iterative algorithms. Their convergence speed depends on how well the eigenvalues are separated.
• 3: Our JacobiSVD is two-sided, making for proven and optimal precision for square matrices. For non-square matrices, we have to use a QR preconditioner first. The default choice, ColPivHouseholderQR, is already very reliable, but if you want it to be proven, use FullPivHouseholderQR instead.

# Terminology

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.