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	Good4	-	-	Yes	Excellent	Blocking, Implicit MT
FullPivLU	-	Slow (no blocking)	Good4	Yes	Rank, kernel, image	Yes	Excellent	-
HouseholderQR	-	Fast	Good4	-	Orthogonalization, least squares for overdetermined systems	Yes (and does least squares)	Excellent	Blocking
ColPivHouseholderQR	-	Fast	Good4	Yes	Orthogonalization, least squares for overdetermined systems	Yes (and does least squares)	Excellent	-
RandColPivHouseholderQR	-	Fast (large matrices)	Good4	Yes	Orthogonalization, least squares for overdetermined systems	Yes (and does least squares)	Good	Blocking, randomized pivot selection
FullPivHouseholderQR	-	Slow (no blocking)	Good4	Yes	Orthogonalization, least squares for overdetermined systems	Yes (and does least squares)	Average	-
CompleteOrthogonalDecomposition	-	Fast	Good4	Yes	Orthogonalization, minimum-norm least squares, pseudo-inverse	Yes (and does least squares)	Excellent	-
RandCompleteOrthogonalDecomposition	-	Fast (large matrices)	Good4	Yes	Orthogonalization, minimum-norm least squares, pseudo-inverse	Yes (and does least squares)	Good	Blocking, randomized pivot selection
LLT	Positive definite	Very fast	Good5	-	-	Yes	Excellent	Blocking
LDLT	Positive or negative semidefinite1	Very fast	Good	-	-	Yes	Excellent	-
BunchKaufman	Self-adjoint (possibly indefinite)	Very fast	Good	-	Inertia	Yes	Good	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)	High relative accuracy3	Yes	Singular values/vectors, least squares	Yes (and does least squares)	Excellent	R-SVD
SelfAdjointEigenSolver	Self-adjoint	Fast-average2	Good	-	Eigenvalues/vectors	-	Excellent	Closed forms for 2x2 and 3x3
TridiagonalEigenSolver	Symmetric tridiagonal	Fast	Good	-	Eigenvalues/vectors, subsets of the spectrum	-	Good	Vectorization, Explicit MT
ComplexEigenSolver	Square	Slow-very slow2	Depends on condition number	-	Eigenvalues/vectors	-	Average	-
EigenSolver	Square and real	Average-slow2	Depends on condition number	-	Eigenvalues/vectors	-	Average	-
GeneralizedSelfAdjointEigenSolver	Square	Fast-average2	Depends on condition number	-	Generalized eigenvalues/vectors	-	Good	-
GeneralizedEigenSolver	Square and real	Slow-very slow2	Depends on condition number	-	Generalized eigenvalues/vectors	-	Average	-
Helper decompositions
RealSchur	Square and real	Average-slow2	Depends on condition number	-	-	-	Average	-
ComplexSchur	Square	Slow-very slow2	Depends on condition number	-	-	-	Average	-
RealQZ	Square and real (pair of matrices)	Average-slow2	Depends on condition number	-	Generalized eigenvalues of a pencil	-	Average	-
ComplexQZ	Square (pair of matrices)	Slow-very slow2	Depends on condition number	-	Generalized eigenvalues of a pencil	-	Average	-
Tridiagonalization	Self-adjoint	Fast	Good	-	-	-	Good	-
HessenbergDecomposition	Square	Average	Good	-	-	-	Good	-

Notes:

• 1: There exist two variants of the LDLT algorithm. Eigen's LDLT produces a pure diagonal D matrix and therefore cannot handle indefinite matrices; it uses symmetric pivoting, which keeps the factorization stable when pivots are tiny or zero. The other variant, which produces the block-diagonal D needed for indefinite self-adjoint matrices, is provided by the BunchKaufman class.
• 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, which buys high relative accuracy on square matrices: where a bidiagonalizing algorithm only computes each singular value accurately relative to the largest one, Jacobi computes it accurately relative to itself, so that tiny singular values are still meaningful. That property is conditional rather than absolute – the relative error is governed by the condition number of the matrix obtained by scaling its columns to unit norm, so a matrix that stays ill-conditioned under any such scaling loses it (J. Demmel and K. Veselic, "Jacobi's method is more accurate than QR", SIAM J. Matrix Anal. Appl. 13 (1992), pp. 1204-1245). For non-square matrices, we have to use a QR preconditioner first; PreconditionSquareMatrix applies it to square matrices too. Householder QR is backward stable with or without pivoting, so this choice is about rank revelation rather than about the accuracy of the factorization itself: the default ColPivHouseholderQRPreconditioner reveals rank reliably in practice but without a guarantee, FullPivHouseholderQRPreconditioner inspects the whole trailing submatrix at a substantially higher cost, and HouseholderQRPreconditioner and NoQRPreconditioner do not pivot at all. See the guidance below on complete pivoting.
• 4: These factorizations are all backward stable, but pivoting buys something different in each. For LU the backward error bound is proportional to the growth factor: partial pivoting bounds it only by \( 2^{n-1} \), whereas complete pivoting admits a far smaller bound that grows only slightly faster than polynomially in n. That partial-pivoting worst case is not observed on real matrices, however, and partial pivoting is more than sufficient in practice. Householder QR is backward stable irrespective of pivoting, with a bound that involves no growth factor at all; there, pivoting serves rank revelation rather than stability, and what separates column from complete pivoting is how reliably the trailing diagonal of R exposes a rank deficiency. Since complete pivoting also rules out the cache-friendly blocked algorithms, LAPACK and Eigen both treat partial and column pivoting as the defaults for LU and QR; see the guidance below. This is a judgement about those two factorizations rather than about complete pivoting in general: LAPACK does provide a complete-pivoting Cholesky (pstrf) for positive semidefinite matrices, where the pivoting also determines the rank.
• 5: Cholesky needs no pivoting for stability: on a positive definite matrix the growth factor is bounded by 1, so the unpivoted factorization is backward stable as it stands. What conditioning governs is instead whether it completes: on a matrix that is positive definite but nearly singular, rounding can drive a computed pivot to zero or below, and Eigen reports that through info() rather than returning a meaningless factor. Use LDLT, or a rank-revealing decomposition, for such matrices.

Practical guidance

The following recommendations apply to the most common use cases:

• Symmetric positive definite systems: Use LLT. It is the fastest solver and has excellent numerical properties for this class of problems. For semidefinite or nearly singular symmetric systems, use LDLT.
• Symmetric indefinite systems: Use BunchKaufman. It extends the Cholesky family to indefinite self-adjoint matrices with a backward-stable pivoting strategy at LDLT-like speed, and also reveals the inertia of the matrix.
• General invertible systems: Use PartialPivLU. It uses cache-friendly blocking and implicit multi-threading, making it the fastest general-purpose solver. Partial pivoting is sufficient for virtually all practical problems.
• Least squares (over- or under-determined systems): Use CompleteOrthogonalDecomposition as the default. Like the SVD, it robustly computes the minimum-norm solution for rank-deficient and under-determined problems, but at QR-like speed. Use BDCSVD when you also need singular values or vectors, not just the least squares solution.
• Large least squares problems: Use RandCompleteOrthogonalDecomposition. It produces the same kind of factorization as CompleteOrthogonalDecomposition, but chooses pivots from a small random sketch so that nearly all of the work happens in level-3 BLAS kernels rather than in the memory-bound column scan of classical column pivoting. The pivot-quality difference is empirically minor. On small matrices the sketch overhead dominates, so prefer the non-randomized class there.
• Pseudo-inverse: CompleteOrthogonalDecomposition and RandCompleteOrthogonalDecomposition are the only decompositions that provide pseudoInverse() directly. Prefer solve() over multiplying by an explicitly formed pseudo-inverse.
• Full-rank least squares (overdetermined systems): When the matrix is known to be full rank, HouseholderQR is the fastest option. For very tall and skinny well-conditioned matrices, solving via the normal equations with LLT can be faster still.
• FullPivLU and FullPivHouseholderQR use complete pivoting, which rules out the cache-friendly blocked algorithms and so makes them substantially slower than their partial- and column-pivoting counterparts, increasingly so as the matrix grows. What complete pivoting buys – a smaller growth factor for LU, a more reliable rank decision for QR – rarely repays that cost on its own, so PartialPivLU and ColPivHouseholderQR are the right default. LAPACK reflects the same trade-off for LU and QR: it exposes no complete-pivoting driver for either, standardizing instead on partial-pivoting LU (getrf) and column-pivoted QR (geqp3, geqp3rk). Complete-pivoting LU survives there only as the auxiliary routine getc2, called by the generalized Sylvester solver, and complete pivoting has no QR counterpart at all.
• When complete pivoting is worth it: rank determination. Column pivoting is reliable in practice but not guaranteed (Kahan's matrix is the standard example of a nearly rank-deficient matrix whose column-pivoted QR exposes no small trailing diagonal entry), whereas complete pivoting inspects the whole trailing submatrix at each step. If your application depends on getting the rank right, FullPivLU or FullPivHouseholderQR is a defensible choice, and the argument is strongest for small matrices, where the lost blocking costs comparatively little. When rank is the whole point and the cost is acceptable, BDCSVD remains the most reliable answer, since the singular values let you choose the threshold yourself.

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 algorithm itself is not parallelized, but that it relies on parallelized matrix-matrix product routines.

Explicit Multi Threading (MT)

Means the algorithm is explicitly 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.