JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Choosing, Updating, and Scaling Factorizations

The payoff: a decision map across every factorization, plus the moves that make them practical at scale — blocking, the Schur complement, sparse fill-in, and rank-one updates.

A decision map

You now have a toolbox; the skill is matching tool to matrix. Choosing the right factorization starts with one question: what structure does A have? Symmetry, definiteness, sparsity, and whether you need eigenvalues or just a solve all push you toward a different decomposition. Get this right and you can be an order of magnitude faster and more accurate than a one-size-fits-all solver.

  1. Symmetric positive definite? Use Cholesky — fastest and most stable.
  2. Symmetric but indefinite? Use LDL^T — keeps symmetry, no square roots.
  3. General square solve? Use LU with partial pivoting.
  4. Least squares / tall-thin / accuracy-critical? Use QR via Householder.
  5. Need eigenvalues? Use Schur (symmetric -> spectral); need geometry/conditioning -> SVD or polar.

Blocking and the Schur complement

Real matrices are huge, and the same factorizations apply to blocks as to scalars. Partition A = [A, B; C, D] and eliminate the top-left block: the bottom-right gets replaced by the Schur complement S = D - C A^-1 B. This block factorization is the engine behind cache-efficient LAPACK kernels, domain decomposition in PDE solvers, and the marginalization step in Gaussian inference — the Schur complement is literally the covariance of one block conditioned on the other.

[ A  B ]   =   [ I        0 ] [ A   0 ] [ I   A^-1 B ]
[ C  D ]       [ C A^-1   I ] [ 0   S ] [ 0      I   ]

# S = D - C A^-1 B   is the Schur complement of A.
# det([A B; C D]) = det(A) * det(S).
# block-LU = recurse the same idea on A and on S.
Block LU: eliminating the A block leaves the Schur complement S in the corner.

Sparsity and fill-in

Most large matrices are mostly zeros. Naively factoring them is a disaster: elimination creates new nonzeros where A had zeros — fill-in — that can turn a 99%-empty matrix into a dense, memory-busting L. The cure is reordering: permute rows and columns (e.g. approximate minimum degree, nested dissection) so elimination introduces as little fill as possible. A good ordering is often the difference between a problem fitting in memory and not.

Updating instead of refactoring

The final payoff is the reason factorizations dominate computation: when A changes a little, you don't start over. A low-rank update modifies an existing factorization in O(n^2) instead of refactoring from scratch in O(n^3). If A changes by a rank-one bump A + u v^T, the Sherman-Morrison-Woodbury formula gives the new inverse — and the new solution — directly from the old factorization plus a single extra solve.

Sherman-Morrison (rank-one update of the inverse):

(A + u v^T)^-1  =  A^-1  -  (A^-1 u)(v^T A^-1) / (1 + v^T A^-1 u)

# You already have A = LU, so A^-1 u and v^T A^-1 are two cheap solves.
# No O(n^3) refactor. Woodbury is the same idea for a rank-k update U V^T.
# Used in: recursive least squares, Kalman filters, quasi-Newton (BFGS).
Sherman-Morrison-Woodbury: patch a factorization in O(n^2) when A gets a low-rank bump.

That is the whole arc of this track: a matrix is rarely just a grid of numbers. Factor it — by its symmetry, its sparsity, its geometry — and you reveal exactly the structure you need: a fast solve, an eigenvalue, a rotation, a conditioning bound. The factorization you choose is the lens through which the matrix tells you what it is. Pick the lens deliberately, and you understand both the problem and the machine that solves it.