Dense linear problems and decompositions » Catalogue of dense decompositions module

Contents

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

DecompositionRequirements on the matrixSpeedAlgorithm reliability and accuracyRank-revealingAllows to compute (besides linear solving)Linear solver provided by EigenMaturity of Eigen's implementation

Optimizations

PartialPivLUInvertibleFastDepends on condition number--YesExcellent

Blocking, Implicit MT

FullPivLU-SlowProvenYes-YesExcellent

-

HouseholderQR-FastDepends on condition number-OrthogonalizationYesExcellent

Blocking

ColPivHouseholderQR-FastGoodYesOrthogonalizationYesExcellent

Soon: blocking

FullPivHouseholderQR-SlowProvenYesOrthogonalizationYesAverage

-

LLTPositive definiteVery fastDepends on condition number--YesExcellent

Blocking

LDLTPositive or negative semidefiniteVery fastGood--YesExcellent

Soon: blocking


Singular values and eigenvalues decompositions

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

Blocked bidiagonalization

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

R-SVD

SelfAdjointEigenSolverSelf-adjointFast-averageGoodYesEigenvalues/vectors-Excellent

Closed forms for 2x2 and 3x3

ComplexEigenSolverSquareSlow-very slowDepends on condition numberYesEigenvalues/vectors-Average

-

EigenSolverSquare and realAverage-slowDepends on condition numberYesEigenvalues/vectors-Average

-

GeneralizedSelfAdjointEigenSolverSquareFast-averageDepends on condition number-Generalized eigenvalues/vectors-Good

-


Helper decompositions

RealSchurSquare and realAverage-slowDepends on condition numberYes--Average

-

ComplexSchurSquareSlow-very slowDepends on condition numberYes--Average

-

TridiagonalizationSelf-adjointFastGood---Good

Soon: blocking

HessenbergDecompositionSquareAverageGood---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.
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 $

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 $

Means the algorithm can work per block, whence guaranteeing a good scaling of the performance for large matrices.
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 routines.
Means the algorithm is explicitly parallelized to take advantage of multicore processors via OpenMP.
Means the algorithm is automatically and explicitly unrolled for very small fixed size matrices.