Sparse matrix

A sparse matrix is a matrix in which the vast majority of elements are zero, stored in a compressed format that represents only the non-zero entries and their positions. The motivation is memory efficiency: a 10⁶ × 10⁶ matrix with 0.01% non-zero density would require 8 terabytes in dense format but only 800 megabytes in sparse format. Sparse matrices are the standard representation in scientific computing, graph algorithms, and machine learning.

The structural analogy between sparse matrices and spatial hashing is instructive. A dense matrix is like a uniform grid: every cell exists in memory, whether occupied or not. A sparse matrix is like a spatial hash: only occupied cells are stored, indexed by their coordinates. The compressed sparse row (CSR) format stores non-zero values in a flat array and uses auxiliary arrays to map matrix coordinates to positions in the value array. This is exactly the spatial hashing pattern — a hash function from (row, column) to a memory offset, with the "hash collision" resolved by sequential storage.

The performance implications are severe. Matrix-vector multiplication on a sparse matrix is memory-bound: the computation is trivial (multiply and add), but the irregular memory access pattern destroys cache locality. This is why sparse linear algebra libraries spend more effort on reordering and partitioning than on the arithmetic itself. The structure of the matrix is the algorithm.