“Know how to solve every problem that has been solved.” “What I cannot create, I do not understand.” — Richard Feynman

Linear algebra: which algorithm, when

Linear Algebra

Numerical linear algebra has roughly five questions you can ask of a matrix — solve a system, find eigenvalues, factor it, apply a function of it, or measure a property of it. For each question, the right algorithm depends mostly on what the matrix looks like (dense or sparse, symmetric or not, small or huge) and what part of the answer you actually need (one eigenvalue or all of them, full inverse or just a solve). The point of this page is to make those choices fast: tables of "you want to do X with a Y matrix, use Z," with links to the pages on this site where the algorithm itself lives.

The cardinal mistake in numerical linear algebra is reaching for a dense algorithm on a matrix that's secretly sparse, or running an iterative method on a problem small enough that a direct factorization would have finished by now. Most of the wins are about matching the algorithm to the structure you actually have. None of these algorithms is universally "the best" — they're each the best at one specific corner of the problem space.

1. Solving $A x = b$

Linear systems split by two questions: is the matrix dense or sparse, and does it have nice structure (symmetric? positive-definite?) that lets a specialized algorithm beat the generic one?

Matrix is...	You want...	Reach for
Small dense, no special structure	Exact solve	Gaussian elimination / LU factorization
Dense, symmetric positive-definite	Exact solve, faster than LU	Cholesky factorization (no page yet)
Dense, possibly rank-deficient / overdetermined	Least squares	Householder QR
Large sparse, SPD	Iterative solve	Conjugate gradient
Large sparse, symmetric indefinite	Iterative solve	MINRES (no page yet)
Large sparse, non-symmetric	Iterative solve	GMRES, BiCGStab (no pages yet); also see Arnoldi, which underlies GMRES

Rule of thumb on the dense/sparse divide: if the matrix has $n ≳ 1 0^{4}$ rows and is mostly zeros, it's worth treating as sparse — the $O (n^{3})$ cost of a direct method gets brutal fast, while sparse-matrix-vector products in an iterative method stay cheap. For dense matrices below that size, the direct methods are usually fine and don't have the convergence-rate uncertainty of the iterative ones.

2. Finding eigenvalues

Eigenvalues split by THREE questions: dense vs sparse, all eigenvalues vs a few of them, and which few — extremal (largest/smallest) or interior (near some target value).

Matrix is...	You want...	Reach for
Small dense, any structure	All eigenvalues	QR algorithm (no page yet); preceded by Householder tridiagonalization for symmetric / Hessenberg reduction for non-symmetric
Large sparse, symmetric / Hermitian	A few extremal eigenvalues	Lanczos iteration (or the implicitly restarted variant — ARPACK)
Large sparse, symmetric, want interior eigenvalues	Eigenvalues near a target $σ$	Shift-invert Lanczos (Lanczos on $(A - σ I)^{- 1}$ ), or the Davidson method for diagonally-dominant cases (typical in electronic structure)
Large sparse, non-symmetric	A few eigenvalues	Arnoldi iteration; or biorthogonal Lanczos when memory matters more than stability
Any size	Just the dominant eigenvector (e.g., PageRank)	Power iteration — the simplest possible thing
Symmetric, want a few interior eigenvalues, want preconditioning	Eigenvalues with a good preconditioner	LOBPCG (no page yet) — locally optimal block preconditioned CG for eigenvalues

The big practical fact: Lanczos converges to extremal eigenvalues first, outside-in. If you want the 500th eigenvalue, you don't run Lanczos and read off entry 500 — you shift-invert. If your matrix has a clear diagonal dominance, Davidson can be dramatically faster than Lanczos because it exploits the diagonal as a preconditioner.

3. Matrix factorizations

Factorizations are useful for two reasons: solving multiple systems with the same matrix (factor once, back-substitute many times), and exposing structure you want to read off (rank, principal components, conditioning). The choice depends on which kind of structure you want.

Factorization	What it gives you	When to use
LU = $P A = LU$	Solve $A x = b$ in two triangular sweeps	Default for dense non-symmetric solve. See Gaussian elimination.
Cholesky = $A = L L^{T}$	LU for SPD matrices, half the cost	Whenever the matrix is SPD. Pages: no Cholesky page yet.
QR = $A = QR$	$Q$ orthogonal, $R$ upper triangular	Least squares, rank-revealing, eigenvalue iteration kernel. See Householder QR.
SVD = $A = U Σ V^{T}$	Rank, pseudoinverse, low-rank approximation, principal components	Anywhere you need numerical rank or the "best" low-rank approximation in 2-norm. See SVD.
Schur = $A = QT Q^{*}$	Quasi-triangular $T$ with eigenvalues on the diagonal	Intermediate step for QR algorithm and matrix functions on small dense matrices. No page yet.

4. Matrix functions $f (A) b$

Often you don't want $f (A)$ itself — you want the vector $f (A) b$ . Examples: $e^{- i H t} ψ_{0}$ in quantum time propagation, $A^{- 1/2} ξ$ for sampling from a Gaussian, $lo g (det A)$ via $lo g (A) b$ trace estimators. Computing the full $f (A)$ matrix is wasteful when you only need its action on a vector.

Setting	Reach for
Small dense, want $f (A)$ itself	Schur-Parlett or scaling-and-squaring (for $exp$ ). Not covered on this site yet.
Large sparse, want $f (A) b$ for analytic $f$	Lanczos (Hermitian) or Arnoldi (non-Hermitian) approximation. The Krylov subspace gives $f (A) b \approx ∥ b ∥ Q_{m} f (T_{m}) e_{1}$ .
You want the resolvent $(z I - A)^{- 1} b$ for many $z$	Lanczos / Arnoldi continued-fraction expansion. See Liouville-Lanczos for a TDDFT application.
Specifically $(I - β A)^{- 1} b$ with SPD $A$	Conjugate gradient (it's just a shifted SPD solve).

5. Properties of a matrix

Often you don't want a factorization or a solve — you want a NUMBER. Is this matrix nearly singular? What's its effective rank? How much will my answer move if my input moves a little? These have their own toolkit.

You want to know...	Compute...
How well-conditioned is this system?	Condition number — ratio of largest to smallest singular value
Numerical rank	SVD; count singular values above a tolerance
Determinant (large, dense)	LU factorization, product of pivot diagonals
Determinant (large, sparse)	Cholesky if SPD, else stochastic trace estimation via Lanczos quadrature
Trace of a function of A (e.g., $tr f (A)$ )	Hutchinson-style stochastic trace + Lanczos quadrature

The decision flow, condensed

When in doubt, this is the order of questions to ask:

Is the matrix dense or sparse? Below $n \sim 1 0^{4}$ with no obvious sparsity pattern, dense direct methods. Above that, or with obvious zeros, iterative methods.
Is it symmetric (and/or positive-definite)? Every symmetric algorithm is faster than its non-symmetric counterpart by roughly 2×. Positive-definiteness unlocks Cholesky and CG.
Do you want all eigenvalues, or just some? "All" → direct (QR algorithm after tridiagonalization). "Some" → iterative (Lanczos / Arnoldi / Davidson). The two regimes have almost nothing in common algorithmically.
Which eigenvalues do you want? Extremal → bare Lanczos / Arnoldi. Interior → shift-invert or Davidson. Dominant only → power iteration.
Do you want $A^{- 1}$ or just $A^{- 1} b$ ? Almost always the latter. Don't form the inverse.

The single most common mistake — across both research code and production code — is forming a matrix explicitly when its action is all you need. $A^{- 1}$ for solving one system. The full Hessian when you only need its product with a vector. The full QR matrix when you only need the projection onto the column space. Iterative methods avoid all of these by keeping the matrix implicit. That implicitness is half the reason they scale.

What's still missing on this site

Algorithms that the tables above mention but don't have pages yet: Cholesky factorization, LU factorization (the proper version, not just Gaussian elimination as exposition), GMRES, MINRES, BiCG / BiCGStab, the QR algorithm itself, Schur decomposition, LOBPCG, and the scaling-and-squaring matrix exponential. These are the natural next pages for the linear algebra section.