Sparse Matrix
A matrix where the overwhelming majority of entries are zero, stored by listing only the non-zero entries (value + coordinates) instead of allocating every cell — trading O(1) direct access for large space savings.
A dense matrix allocates every cell, O(rows × cols) space regardless of content. A sparse matrix instead stores only the non-zero entries — common representations include a coordinate list (row, col, value) triples, or the more compact CSR/CSC (compressed sparse row/column) formats used in real numerical libraries.
The trade-off is direct access: a dense matrix reads any cell in O(1) by index arithmetic; a sparse matrix must search its non-zero entries for a given (row, col), which is slower unless entries are indexed (e.g. by row) — the workspace here uses a simple per-row list for that reason.
Sparse representations shine when non-zero density is low (a graph's adjacency matrix for a sparse graph, a large but mostly-empty scientific simulation grid) — the space savings can be the difference between fitting in memory and not, and matrix-vector multiplication only does work proportional to the non-zero count, not rows × cols.
Operations
| Operation | Complexity |
|---|---|
| get(row, col) | O(entries in row) |
| set(row, col, v) | O(entries in row) |
| space | O(non-zero entries) |
| matrix-vector multiply | O(non-zero entries) |
Where it's used
Large graph adjacency matrices, scientific/numerical computing (finite element methods), recommendation-system rating matrices, any matrix that is mostly empty.