A sparse matrix is a matrix in which the overwhelming majority of entries are zero, allowing specialised storage formats and algorithms that operate only on the non-zero elements. By storing and computing with structure rather than dense arrays, sparse representations dramatically reduce memory and arithmetic for large-scale linear algebra. They are foundational to optimisation problems such as bundle adjustment, graph algorithms and finite-element simulation where connectivity is local.
Overview
- Sparse matrices exploit a simple observation: when most entries of a large matrix are zero, storing and multiplying every entry wastes memory and time. Compressed formats record only the non-zeros and their positions, and sparse solvers exploit the resulting structure so that problems with millions of unknowns become tractable on commodity hardware.
- It is modelled as a subclass of Linear Algebra within the spatial-computing domain.
- The benefit of sparsity is realised only when both storage and algorithms respect it. A matrix that is mathematically sparse but stored densely confers no advantage; compressed formats such as compressed sparse row record only non-zeros and their indices, and sparse solvers are written to skip the zeros entirely, so cost scales with the number of non-zeros rather than the square of the dimension.
- Sparsity often reflects locality in the underlying problem: a finite-element mesh connects each node only to its neighbours, a social graph connects each person only to their contacts, and a bundle-adjustment system links each observation only to the camera and point it involves. Recognising and exploiting this block and band structure is the key to scaling.
Key aspects
- Storage formats: compressed sparse row, compressed sparse column and coordinate lists trade off access patterns.
- Fill-in: factorisation can introduce new non-zeros, so ordering heuristics minimise fill.
- Block structure: bundle adjustment exploits the sparse block-arrow structure of its normal equations for fast solves.
- Operations: sparse matrix-vector products scale with the non-zero count rather than the dense size.
Applications
- Solving the normal equations in bundle adjustment and large-scale optimisation.
- Representing graph connectivity as adjacency matrices for graph algorithms.
- Discretised partial differential equations in finite-element and finite-difference simulation.
Considerations
- Direct factorisation can suffer fill-in, where zeros become non-zero, so reordering heuristics are applied to preserve sparsity.
- Iterative solvers such as conjugate gradients avoid fill-in and suit very large sparse systems but require good preconditioning.
- Choice of storage format should match the dominant access pattern, since row-oriented and column-oriented formats favour different operations.