Sparse Matrix

Updated 01 Oct 2026

•
What it is
- •
  a matrix with sufficiently few nonzero entreis that storing and computing with those entries is advantageous
•
Representation
- •
  compressed sparse row format stores nonzero values, their column indices, and row pointers
•
Computation
- •
  sparse matrix-vector multiplication typically costs $O(\mathrm{nnz})$ , where $\mathrm{nnz}$ is the number of stored nonzeros
- •
  an iterative solve takes roughly this cost per iteration, plus method-specific work
- •
  direct factorization can introduce fill-in: entries that were initially zero become nonzero in the factors
•
Caution
- •
  "Sparse" does not automatically mean every solver runs in $O(n)$ time
•
Related
- •
  Thomas Algorithm
- •
  Conjugate Gradient Method

Linked references 4