Sparse Direct Solvers
Factorization-based solvers that exploit sparsity to solve linear systems exactly, trading memory for robustness against iterative failure.
Factorization for sparse matrices
A sparse direct solver computes an LU or Cholesky factorization of a sparse matrix, then solves the system by forward and back substitution. Unlike iterative solvers, it delivers the solution in a fixed, predictable number of operations and does not depend on spectral properties or preconditioner quality. This robustness makes it the safe choice for ill-conditioned systems and for problems solved repeatedly with the same matrix but many right-hand sides.
The fill-in problem
The central challenge is fill-in: entries that are zero in the original matrix become nonzero during factorization. Uncontrolled fill can turn a sparse matrix into a nearly dense factor, exhausting memory. The amount of fill depends dramatically on the ordering of the unknowns, so sparse direct solvers spend a symbolic analysis phase choosing an ordering that minimizes fill before any numbers are touched.
- Symbolic phase: analyze the sparsity pattern and choose an ordering
- Numeric factorization: compute the actual L and U (or Cholesky) factors
- Solve phase: forward and back substitution, cheap and reusable per right-hand side
Supernodes and the frontal approach
Modern sparse solvers group columns with similar structure into supernodes so that dense-matrix kernels (BLAS level 3) can be used, extracting high performance from cache and vector units. Multifrontal and supernodal methods organize the factorization as a tree of dense sub-factorizations, which also exposes parallelism across independent branches.
When to use direct vs iterative
Direct solvers excel for two-dimensional problems, for moderately sized three-dimensional ones, and whenever an iterative method struggles to converge. For very large three-dimensional problems the fill-in becomes prohibitive, and multigrid or preconditioned Krylov methods win. The two families also combine: a sparse direct solve on subdomains sits inside domain decomposition preconditioners. Ordering quality, discussed under nested dissection, is decisive for their efficiency.