a sparse direct solver

Most enormous matrices from real applications are sparse: out of millions of entries, only a handful per row are nonzero, because each unknown interacts with just a few others (think of a mesh where a grid point talks only to its neighbours). Storing or factoring such a matrix as if it were dense would be hopeless. A sparse direct solver is an elimination-based solver engineered to factor a sparse matrix while touching, storing, and computing on only the nonzeros.

It performs the same Gaussian elimination or Cholesky factorization as a dense solver, but on a compressed representation that records only the nonzero entries and their locations. The challenge is that elimination creates NEW nonzeros — called fill-in — where the original matrix had zeros, because subtracting one row from another can turn a zero into a nonzero. A sparse direct solver works hard to keep fill-in small, typically by first reordering the rows and columns (a symbolic analysis phase) so the factors L and U stay as sparse as possible, then doing the numeric factorization, then the cheap triangular solves. The total cost depends entirely on how much fill occurs — for a well-ordered 2D problem it can be near-linear, but for dense fill it degrades toward the cubic dense cost.

Sparse direct solvers (SuiteSparse, MUMPS, PARDISO, UMFPACK and friends) are the backbone of finite-element and circuit simulation, where they robustly deliver an accurate factorization that can be reused for many right-hand sides. Their great virtue over iterative methods is reliability: they give a backward-stable answer without needing a good preconditioner or worrying about convergence. Their limit is memory: for very large 3D problems fill-in can make the factors too big to store, and at that point iterative or multigrid methods take over. So the choice between sparse-direct and iterative is largely a question of how badly the problem fills in.