direct vs iterative solvers

There are two philosophies for solving Ax = b. A direct method factors A once — into LU, or QR, or Cholesky — and then solves by cheap forward and back substitution. In exact arithmetic it produces the answer in a finite, predictable number of steps. An iterative method instead starts from a guess and refines it repeatedly, generating x0, x1, x2, ... that (you hope) converge to the solution, stopping when the residual b - A x_k is small enough.

Direct methods are robust and accurate: they need no tuning, they handle one factorization for many right-hand sides, and a backward-stable factorization gives a backward-stable solve. Their weakness is cost and memory. Factoring a dense n-by-n matrix costs O(n^3) work and O(n^2) storage, and for sparse matrices the factors can fill in — zeros becoming nonzeros — and blow up the memory.

Iterative methods win exactly where direct methods strain: very large, sparse, or structured systems. Each iteration usually costs only one matrix-vector product, which for a sparse matrix is proportional to the number of nonzeros, not to n^2. They never need to store a factorization. The price is uncertainty: convergence depends on the matrix's spectrum and conditioning, and may be slow or require a good preconditioner to be practical.

The honest summary is that size and structure decide. For modest dense systems (up to a few thousand unknowns), use a direct solver and stop worrying. For the giant sparse systems from discretized PDEs or graphs, where n can be in the millions, a direct factorization is impossible and iterative Krylov methods with preconditioning are the only realistic option.