Skip to content

Eigenvalues and Eigenvectors

MTL5 provides a dense eigen suite in namespace mtl (headers under include/mtl/operation/) and a set of matrix-free iterative eigensolvers in namespace mtl::itl (headers under include/mtl/itl/eigen/). This page covers the routines available today and how to choose between them.

Use the dense suite for small/medium matrices where you want the whole spectrum; use the iterative solvers for large or matrix-free operators where you want a few eigenpairs and can only apply A * x.

Answer four questions:

  1. Dense or sparse/large? Small/medium and you want all (or most) eigenvalues → the dense suite below. Large, sparse, or matrix-free and you want a few → the iterative (mtl::itl) or sparse (mtl::sparse) solvers.
  2. Symmetric or general? Symmetric → the *_symmetric dense routines or itl::lanczos; general (non-symmetric) → eigenvalue/eigen or itl::arnoldi (expect complex eigenvalues).
  3. Values only, or values + vectors? Value-only routines are cheaper; the eigen* routines and the iterative solvers also return eigenvectors.
  4. Which eigenvalues? All → dense. Largest → iterative directly on the operator. Smallest / interior / nearest a target sigma → sparse::sparse_eigs_shift_invert.
FunctionMatrixOutputBackend
eigenvalue(A)general (non-symmetric)eigenvalues only, dense_vector<complex>LAPACK geev if available, else C++ Francis QR
eigen(A)general (non-symmetric)eigenvalues and right eigenvectors (complex)LAPACK geev if available, else C++ QR + inverse iteration
schur(A)general, real{Q, T}: A = Q T Qᵀ, T quasi-triangularLAPACK gees if available, else C++ Francis QR
rsf2csf(Q, T)a real Schur form{U, R}: A = U R Uᴴ, R upper triangular (complex)pure C++
eigenvalue_symmetric(A)symmetriceigenvalues, ascendingLAPACK syev if available, else C++
eigenvalue_symmetric_generic(A)symmetriceigenvalues, ascendingpure C++
eigen_symmetric(A)symmetriceigenvalues and eigenvectorspure C++
eigen_symmetric_jacobi(A)symmetric, real, smalleigenvalues and eigenvectors, with small eigenvalues relatively accuratepure C++

The LAPACK geev fast path for the general problem engages when built with -DMTL5_WITH_LAPACK=ON and the matrix is a column-major dense2D<float/double> (mirroring the symmetric syev dispatch). Row-major matrices and custom number types use the in-house path, which is always available and numerically identical up to sign/phase conventions.

All routines take an optional tol and max_iter; the pure-C++ paths also work with custom number types (posits, LNS, …) since they do not depend on LAPACK.

For the symmetric routines, tol defaults to the machine epsilon of the eigenvalue type (#565). A subdiagonal entry e between diagonal entries d₀ and d₁ is dropped once |e| ≤ tol·√|d₀|·√|d₁|, LAPACK dsteqr’s test, which scales with the smaller of the two eigenvalues it separates. A larger tol trades accuracy for fewer iterations. Passing 1e-10 gives the earlier default tolerance, though not the earlier results, since the deflation test also changed.

Tridiagonal QR is accurate to about ε‖A‖ in every eigenvalue, so an eigenvalue much smaller than ‖A‖ carries a large relative error, and so does its eigenvector when the gap is small. A normal matrix AᵀA with badly scaled columns is the common case: measured on 9 × 9 and 12 × 12 null-vector problems with columns scaled across 10⁶, the eigenvector of the smallest eigenvalue is off by about 1e-6 rad, while with unscaled columns it is accurate to 1e-15.

#include <mtl/mat/dense2D.hpp>
#include <mtl/operation/eigenvalue.hpp>
mtl::mat::dense2D<double> A(4, 4);
// ... fill A ...
// Eigenvalues only.
auto lambda = mtl::eigenvalue(A); // dense_vector<complex<double>>
// Eigenvalues and right eigenvectors.
auto [eigs, V] = mtl::eigen(A); // structured binding
// Column k of V is the right eigenvector for eigs(k): A * V(:,k) = eigs(k) * V(:,k)

eigen returns a struct { eigenvalues, eigenvectors } (structured-bindable), mirroring eigen_symmetric. Eigenvalue and eigenvector are paired by column. Eigenvectors are returned with unit 2-norm and a canonical phase (the largest-magnitude entry is rotated to be real and positive), so results are deterministic. Real and complex-conjugate eigenpairs are handled uniformly in complex arithmetic.

eigen computes the spectrum with the tested general QR path (eigenvalue, Hessenberg reduction followed by Francis QR iteration), then recovers each eigenvector by inverse iteration on A - lambda_k * I. A partial-pivot complex LU with a pivot floor keeps the (near-singular) system solvable — which is exactly the regime inverse iteration exploits.

eigen’s accuracy is bounded by the eigenvalues that eigenvalue produces: inverse iteration recovers the eigenvector of the true eigenvalue nearest each computed lambda_k. eigenvalue uses a Francis double-shift QR, so complex spectra of strongly non-normal matrices (e.g. companion / Forsythe matrices) are resolved accurately, and the eigenvectors follow to near machine precision. When LAPACK is available and the matrix qualifies, both routines dispatch to geev instead (see the table above).

#include <mtl/operation/schur.hpp>
auto [Q, T] = mtl::schur(A); // A = Q T Q^T, Q orthogonal
auto [U, R] = mtl::rsf2csf(Q, T); // A = U R U^H, R upper triangular, complex

Every square matrix is unitarily similar to an upper triangular one, whose diagonal holds the eigenvalues (Schur, 1909). For a real matrix with complex eigenvalues that form is complex. The real Schur form keeps real arithmetic instead: T is block upper triangular, a 1×1 block for each real eigenvalue and a 2×2 block for each complex-conjugate pair. A defective matrix has no full set of eigenvectors, and a nearly defective one has an ill-conditioned set; the Schur vectors are always an orthonormal basis, computed stably. That is why the Schur form, not the eigendecomposition, is what algorithms for matrix functions (sqrtm, logm; issue #650), Sylvester and Lyapunov equations and invariant subspaces are built on.

The 2×2 blocks are in LAPACK’s standard form, [a b; c a] with b·c < 0, whose eigenvalues are a ± i·sqrt(-b·c). A 2×2 block with real eigenvalues is always split into two 1×1 blocks, so a nonzero subdiagonal entry of T means a complex pair. rsf2csf (named after MATLAB’s function) turns the real form into the complex triangular one by a complex rotation of each block, with the eigenvalue of positive imaginary part first.

schur reduces A to Hessenberg form by Householder reflections, forms their product Q (hessenberg_extract_Q, LAPACK’s orghr), and runs the same Francis double-shift QR iteration as eigenvalue, but in its EISPACK hqr2 form: every transformation is applied to all of T and accumulated into Q, not only to the block still being reduced. Each 2×2 block is put into standard form by a port of LAPACK dlanv2. The iteration is shared with eigenvalue (detail/francis_qr.hpp), whose results are unchanged by the sharing.

Two choices differ from eigenvalue:

  • Deflation at the element type’s own epsilon, machine_epsilon<T>(), with LAPACK’s safe-minimum floor when numeric_limits gives a meaningful one. eigenvalue’s default tol of 1e-10 is kept for compatibility.
  • Power-of-two scaling of A to max |aᵢⱼ| in [½, 1] before the iteration, undone on T at the end. The EISPACK iteration forms products of two matrix entries, which overflow or underflow for entries near 1e200 or 1e-200; scaled, such matrices converge with the same accuracy as unscaled ones. In a binary floating-point type the scaling is exact.

The result is backward stable: on the test families (random, nonnormal, graded, companion, cyclic permutation, Jordan, triangular, diagonal; n ≤ 16), the measured ‖A − Q T Qᵀ‖_F / ‖A‖_F and ‖QᵀQ − I‖_F are at most 3.2 n ε for float, double and long double, at any scale.

With -DMTL5_WITH_LAPACK=ON, dense2D<float> and dense2D<double> (either orientation) dispatch to gees. A non-void Accumulator (schur<double>(A)) forces the in-house path, and is forwarded to the Hessenberg reduction and the formation of Q.

The in-house path uses only + − × ÷, comparisons, and abs and sqrt found by argument-dependent lookup, and reads epsilon from the type’s numeric_limits, which every MTL5 element type has (#838). Measured against Universal’s number systems on the same families (worst case, in units of n ε of each type; Universal is not an MTL5 dependency, so this was a one-off run, not part of MTL5’s test suite):

Type‖A − Q T Qᵀ‖ / ‖A‖‖QᵀQ − I‖Note
bfloat161.32.2
cfloat<16,5> (half)1.62.1entries beyond 65504 are rejected as infinite
cfloat<32,8>2.12.9
posit<16,1>2.13.3
posit<32,2>7.46.5
posit<64,3>6166Universal’s sqrt here is accurate to double, about 39 ε
takum<32>2.74.3
lns<32,22>3.63.6
dd4.15.2
qd0.060.08below 1: Universal’s epsilon() for qd is conservative
fixpnt<32,16>up to 3·10⁴up to 2·10⁴some matrices do not converge

A posit’s precision is greatest near 1, which the scaling to [½, 1] exploits. The scaled-back T has the precision of its own magnitude, so a posit matrix whose entries are far from 1 sees a larger relative error (62 n ε for posit<32,2> on graded matrices scaled by 10⁶). Fixed-point types are not supported: their precision is absolute, not relative, so the deflation test and the normalized reflectors lose their meaning for small entries.

schur takes a real element type. The complex Schur form of a complex matrix, and rsf2csf for types other than float, double and long double (which needs a complex type for them, such as Universal’s complex<T>), are later work in issue #650.

For symmetric matrices, prefer the symmetric routines — they exploit real spectra and orthogonal eigenvectors, and eigenvalue_symmetric transparently dispatches to LAPACK syev (heev for complex) when built with -DMTL5_WITH_LAPACK=ON and the matrix is a dense2D of float, double or their complex types, in either orientation. A 0x0 matrix returns an empty vector without calling LAPACK. If syev or heev returns a non-zero info, eigenvalue_symmetric throws std::runtime_error (#849), as the in-house iteration does when it runs out of iterations (#853). A NaN or Inf in the matrix throws std::invalid_argument before any work, on every path and for every size (#853), as it does for eigenvalue, eigen, eigen_symmetric, eigen_symmetric_jacobi, schur and svd. The eigenvalue routines also reject a non-square matrix the same way; svd takes rectangular ones. Before #853 a NaN or Inf usually made syev report non-convergence, but a 1x1 [Inf] came back as {Inf}.

#include <mtl/operation/eigenvalue_symmetric.hpp>
auto s = mtl::eigenvalue_symmetric(S); // ascending eigenvalues
auto [eigs, Q] = mtl::eigen_symmetric(S); // A = Q * diag(eigs) * Q^T

eigenvalue_symmetric_generic is the LAPACK-free reference path (Householder tridiagonalization + implicit-QR with Wilkinson shifts); eigenvalue_symmetric calls it when LAPACK is unavailable or the type does not qualify. Call it directly to exercise the pure-C++ algorithm regardless of build flags, or for custom number types.

Small matrices and small eigenvalues: Jacobi

Section titled “Small matrices and small eigenvalues: Jacobi”

eigen_symmetric_jacobi(A) is a two-sided cyclic Jacobi solver (#564). It returns the same {eigenvalues, eigenvectors} as eigen_symmetric, eigenvalues ascending:

#include <mtl/operation/eigenvalue_symmetric_jacobi.hpp>
auto [eigs, V] = mtl::eigen_symmetric_jacobi(S); // A = V * diag(eigs) * V^T

Tridiagonal QR is accurate to about ε‖A‖ in every eigenvalue. An eigenvalue much smaller than ‖A‖ therefore has a large relative error, and so does its eigenvector when the gap to the next eigenvalue is small. For a positive (semi)definite matrix, Jacobi computes small eigenvalues and their eigenvectors to high relative accuracy (Demmel & Veselić, 1992). The typical case is the null vector of a normal matrix AᵀA whose columns are badly scaled, as in the 8-point algorithm, DLT pose estimation, and plane or line fits. Measured on 200 random null-vector problems per size, with the columns scaled across 10⁶:

Neigen_symmetriceigen_symmetric_jacobi
96.6e-7 rad4.9e-15 rad
121.9e-6 rad5.4e-15 rad

On graded positive definite matrices with eigenvalues spanning 8 to 24 decades, Jacobi’s worst relative eigenvalue error was 6.6e-16. eigen_symmetric’s was between 2e-13 and 8e-11.

How it works:

  • It sweeps the off-diagonal pairs row by row and rotates each one to zero with the stable rotation θ = (a_qq − a_pp)/(2a_pq), t = sign(θ)/(|θ| + √(θ² + 1)).
  • It skips a pair once |a_pq| ≤ tol·√|a_pp|·√|a_qq|, and stops after a sweep that rotates nothing. tol defaults to machine ε, and max_sweeps caps the sweeps (default 60).
  • The per-pair test is what keeps the relative accuracy. A stop on off-diagonal mass ≤ ε²‖A‖²_F can leave a tiny entry that couples two small eigenvalues: diag(1, 1e-10, 2e-10) with a₁₂ = 1.5e-16 would come back 2.25e-12 relatively wrong.
  • No entry is ever squared, so matrices scaled from 1e+300 down to subnormal values converge.
  • Random normal matrices of size 9 and 12 converge in under 20 sweeps.

Jacobi costs more than tridiagonal QR. The eig-small suite of benchmarks/bench_all (bench_all --suite eig-small) measured the following medians in µs, from two runs of a Release build on a shared x86-64 machine, so the ranges are noisy:

neigen_symmetriceigen_symmetric_jacobisvd
30.550.590.99
61.1–1.81.7–3.36.3–6.5
94.1–5.111–1214–23
167.7–8.029–3169–82

Use Jacobi for small matrices whose small eigenvalues or null vectors matter, and eigen_symmetric (or LAPACK) for larger matrices and when only absolute accuracy is needed. It takes real element types only, custom reals such as posits included; a complex Hermitian matrix is rejected at compile time.

Null vectors: null_vector and the V-only svd

Section titled “Null vectors: null_vector and the V-only svd”

A null-space problem needs only the right singular vector of A’s smallest singular value, which is the last column of V. The full svd(A, U, S, V) also builds an m × m U. At m = 400 that makes it take about 0.24 s, almost all of it spent completing U to a full basis. Two calls skip U entirely (#566):

#include <mtl/operation/svd.hpp>
mtl::vec::dense_vector<double> s; // singular values, descending, length min(m, n)
mtl::mat::dense2D<double> V; // n x n right singular vectors
mtl::svd(A, s, V); // never forms U
auto x = mtl::null_vector(A); // unit x minimizing ||A x||: V's last column
  • Tall A (m > n): A is first reduced by Householder QR, A = QR, and one-sided Jacobi then runs on the n × n triangle R. R has the same singular values and right singular vectors as A, so each sweep costs O(n³) instead of O(mn²).
  • Accuracy: Householder QR is backward stable column by column, so it keeps Jacobi’s relative accuracy when A’s columns are badly scaled. Measured against the full svd on 10 × 3 up to 400 × 12 matrices, with rows or columns scaled across 10⁸, the singular values agree to 1.3e-15 relative and the columns of V to the same.
  • Square or wide A (m ≤ n): Jacobi runs on A itself, and S and V match the full svd bit for bit.
  • Backend: both calls always use the generic C++ path. LAPACK’s gesdd, which the full svd uses, has no V-only mode.

A null vector of a tall 2k × 9 or 2k × 12 system can be found four ways. The null-vector suite of benchmarks/bench_all measured these medians in µs, in a Release build. The two AᵀA columns include the time to form AᵀA.

m × Nnull_vector(A)svd(A)eigen_symmetric(AᵀA)eigen_symmetric_jacobi(AᵀA)
16 × 96.6133.56.6
64 × 99.74484.89.1
400 × 927238,5901518
16 × 1213186.515
400 × 1246238,8242736

The full svd’s time at m = 400 is almost all spent completing U to a full m × m basis. At m = 400, null_vector spends most of its time in the QR.

The AᵀA routes are faster, but forming AᵀA squares A’s condition number. The null vector’s error then grows with 1/gap² instead of 1/gap, where the gap is the second-smallest singular value relative to the largest. Measured in float on 36 × 9 matrices with an exact null vector (50 trials each), as the mean angle:

second-smallest σnull_vector(A)eigen_symmetric_jacobi(AᵀA)
1e-12.4e-71.6e-6
1e-21.3e-61.9e-4
1e-31.3e-52.0e-2

In double the same loss is ε·κ², so it rarely matters for these sizes, but it does in float or in a narrow custom type such as a posit.

When the left singular vectors are needed too, as in least squares, a pseudoinverse or PCA, a tall A rarely needs all m of them. The thin overload returns k = min(m, n) of each:

mtl::mat::dense2D<double> U, V; // U: m x k, V: n x k, orthonormal columns
mtl::vec::dense_vector<double> s; // k singular values, descending
mtl::svd(A, U, s, V); // A = U * diag(s) * V^T
  • Tall A (m > n), generic path: the same QR and Jacobi on R as the V-only svd, then U = Q [U_R; 0], formed by applying the n stored Householder reflectors to R’s left singular vectors. That is O(mn²), with no m × m basis to complete.
  • Square or wide A (m ≤ n): U, s and the k columns of V match the first k of the full svd bit for bit.
  • Zero singular values: U’s columns for them are completed to an orthonormal set, as in the full svd.
  • Backend: with LAPACK, a dense2D<float/double> goes to gesdd in its thin mode, as the full svd goes to gesdd in its full mode.

Measured with the null-vector suite, in µs:

m × nthin svdfull svd
64 × 913459
400 × 949238,000
400 × 1285238,000

For large matrices where a full dense factorization is infeasible, use the Krylov eigensolvers in mtl::itl. They operate through the LinearOperator concept — only A * x is required — so they apply to dense2D, compressed2D, and user-supplied matrix-free operators alike.

FunctionOperatorReturns
itl::power_iteration(A, v0)any (real dominant)dominant eigenpair (eigenpair<T>)
itl::lanczos(A, v0, k, which)symmetrick extremal Ritz pairs (ritz_pairs<T>)
itl::arnoldi(A, v0, k, which)generalk Ritz pairs (ritz_pairs<complex<T>>)

which is an itl::eigen_which selector — largest_magnitude, smallest_magnitude, largest_algebraic, smallest_algebraic. The optional subspace argument sets the Krylov dimension (default: a modest multiple of k, capped at n); a larger subspace converges more eigenpairs to tighter residuals. Each solver projects onto its Krylov subspace and solves the small projected problem (tridiagonal for Lanczos, Hessenberg for Arnoldi) with the dense routines above — so accuracy of the projected solve rides on the same code.

#include <mtl/itl/eigen/eigensolvers.hpp>
// Dominant eigenpair of a symmetric/SPD operator.
auto p = mtl::itl::power_iteration(A, v0);
// p.value, p.vector, p.converged
// The 5 largest eigenpairs of a large symmetric operator (matrix-free ok).
auto r = mtl::itl::lanczos(A, v0, 5, mtl::itl::eigen_which::largest_algebraic);
// r.values (dense_vector), r.vectors (columns), r.converged
// A few eigenpairs of a nonsymmetric operator (complex Ritz values).
auto g = mtl::itl::arnoldi(A, v0, 4, mtl::itl::eigen_which::largest_magnitude);

These are single-shot (non-restarted) builds with full reorthogonalization — robust and simple. Implicit/thick restarting is a planned follow-up.

For sparse matrices (compressed2D), mtl::sparse builds on the iterative solvers above:

FunctionReturns
sparse::sparse_eigs(A, k, which)k eigenpairs by Arnoldi applied directly to the sparse operator (best for largest-magnitude)
sparse::sparse_eigs_shift_invert(A, sigma, k)k eigenpairs nearest sigma (interior / smallest)

Largest-magnitude eigenvalues come from running Arnoldi directly on A (a sparse matrix is already a LinearOperator). Interior or smallest eigenvalues use shift-invert: (A - sigma*I) is factored once with the sparse LU direct solver, and its inverse is applied inside Arnoldi. An eigenpair (theta, y) of (A - sigma*I)^{-1} maps to (lambda, y) of A with lambda = sigma + 1/theta and the same eigenvector, so “nearest sigma” becomes “largest |theta|” — which Arnoldi converges to quickly.

#include <mtl/sparse/eigen/shift_invert.hpp>
// The 4 eigenvalues of A closest to sigma = 2.5, with eigenvectors.
auto near = mtl::sparse::sparse_eigs_shift_invert(A, 2.5, 4);
// near.values (complex, = sigma + 1/theta), near.vectors, near.converged
// The reusable operator, if you want to drive the Krylov solver yourself:
mtl::sparse::shift_invert_operator<double> op(A, 2.5); // factor once
auto y = op * x; // apply (A - 2.5 I)^{-1}

The factorization is computed once and applied on every Arnoldi step; tiny pivots are perturbed so a shift landing (near-)exactly on an eigenvalue stays solvable. Generalized problems A x = lambda B x are a future extension.

The examples/phase06_eigenvalue_svd/ directory has runnable programs:

  • vibrating_string.cpp — eigenvalues of discrete 1D/2D Laplacians as vibration modes; uses eigenvalue_symmetric and contrasts it with the general eigenvalue on a non-symmetric perturbation.
  • pca_svd.cpp — relates the SVD to the symmetric eigenproblem (singular values = |eigenvalues| for a symmetric matrix).

Every pure-C++ path (eigenvalue, eigen, schur, eigenvalue_symmetric_generic, eigen_symmetric, and the iterative solvers) works with custom scalar types such as posits and LNS — they depend only on standard arithmetic and mtl primitives, not on LAPACK. LAPACK dispatch is a float/double-only accelerator that is bypassed automatically for other types.