Sparse Linear Solvers
Sparse solvers exploit the many zeros in discretization matrices to solve large linear systems in time and memory far below dense methods.
Exploiting the zeros
Discretizing a PDE produces a matrix that is sparse: each unknown couples only to a few neighbors, so the vast majority of entries are zero. A dense solver would waste enormous time and memory on those zeros. Sparse linear solvers store and operate on only the nonzero entries, reducing both memory and arithmetic from cubic to a small multiple of the number of unknowns for favorable problems.
Sparse solvers fall into two broad families, direct and iterative, each with distinct strengths, and the right choice depends on the matrix structure, size, and how many right-hand sides must be solved.
Direct methods
Sparse direct solvers compute an LU or Cholesky factorization while trying to preserve sparsity. The obstacle is fill-in: factorization introduces new nonzeros where the original had zeros. Fill-reducing orderings (nested dissection, minimum degree) reorder the unknowns to keep fill low. Direct methods are robust, insensitive to conditioning, and efficient when the same matrix is reused for many right-hand sides, but their memory grows quickly for three-dimensional problems.
Iterative methods
Iterative solvers (Krylov methods with preconditioning) use only matrix-vector products and keep memory proportional to the number of unknowns, scaling to very large three-dimensional systems where direct methods run out of memory. Their convergence depends on conditioning, so they rely on effective preconditioners. Hybrid approaches use a sparse direct solve on subdomains within an iterative or domain-decomposition framework.
- Store and compute only on nonzero entries
- Direct: robust, reusable, but fill-in limits 3D scale
- Iterative: memory-lean and scalable, needs preconditioning
- Fill-reducing orderings control direct-solver cost
Large fusion simulations mix both: sparse direct solvers on subproblems and preconditioned Krylov methods for the global implicit systems that arise in transport and MHD modeling.