Sparse matrices
Sparse matrices: definitions, storage formats (triplet/COO, CSR, CSC, diagonal/band/block), operations (transpose, addition, SpMV), algorithms (fast transpose, CSR SpMV), complexities, examples with Python.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Sparse matrices appear whenever most entries of a matrix are zero, which is common in graphs, recommendation systems, NLP term–document matrices, finite element meshes, and network simulations. Efficient sparse representations save memory and speed up core operations like matrix–vector multiplication, which are used inside algorithms you learn across subjects (e.g., Dijkstra’s shortest path, PageRank, and iterative solvers).
Key ideas
- The density of a matrix is the fraction of entries that are nonzero: density p = t/(m·n), 0 ≤ p ≤ 1. The sparsity is 1 − p.
- A storage scheme for a sparse matrix is a data structure that stores only nonzero entries with enough index information to support desired operations (e.g., addition, transpose, multiplication).
Common storage schemes
Triplet (coordinate list, COO)
- Structure: a list of 3-tuples (row, col, value) for each nonzero. In many DS textbooks, a header triple (m, n, t) is stored at index 0, followed by t triples.
- Space: header + 3t elements. If each index and value are stored as fixed-size fields, space is O(t).
- Operations: Easy to construct and concatenate. Addition requires merging sorted triplets; transpose can be done by swapping row and col plus re-sorting, or by the fast-transpose algorithm.
- Diagram to draw and label: Draw a small 4×5 grid marking nonzeros with filled circles. Next to it, draw a three-column table labeled row, col, val. First row is m, n, t (header), followed by the list of triples in row-major order.
Compressed Sparse Row (CSR)
- Structure: three 1-D arrays: values (val), column indices (col_idx), and row pointer (row_ptr). For m×n with t nonzeros:
- val[0..t−1]: all nonzero values, grouped by row.
- col_idx[0..t−1]: column index for each value.
- row_ptr[0..m]: row_ptr[i] is the starting index in val/col_idx of row i; row_ptr[m] = t.
- Space: t values + t column indices + (m+1) row pointers ⇒ O(t + m).
- Strength: Fast matrix–vector multiplication (SpMV) and row slicing. Addition is possible by row-wise merging. Transpose requires conversion or building CSC.
- Diagram to draw and label: Draw arrays val, col_idx aligned horizontally. Below, draw row_ptr as tick marks showing where each row starts; label row_ptr[0], row_ptr[1], …, row_ptr[m].
- Structure: three 1-D arrays: values (val), column indices (col_idx), and row pointer (row_ptr). For m×n with t nonzeros:
Compressed Sparse Column (CSC)
- Same idea as CSR but compress by columns: values, row indices, and col_ptr[0..n]. Efficient for column operations and transposes of CSR.
Diagonal and band storage
- Diagonal storage: When all nonzeros lie on the main diagonal (or a small fixed set of diagonals), store only those diagonals in compact arrays. Space O(k·min(m, n)) for k diagonals if you store only the actual diagonal entries; if a padded banded layout is used, space is O(k·n).
- Band matrix: Nonzeros confined within a band around the main diagonal. Store only the band in a 2D array of size (lower_bw + upper_bw + 1) × n.
Block sparse
- Store nonzero blocks (submatrices) rather than individual entries when nonzeros cluster. Improves cache performance and reduces index overhead.
Exact statements and commonly asked derivations
- Statement (Space comparison): For an m×n dense matrix, storage is O(m·n). For triplet, storage is O(t). For CSR/CSC, storage is O(t + m) or O(t + n), respectively. For sufficiently sparse matrices (t ≪ m·n), sparse storage asymptotically saves memory.
- Derivation (When does sparse save space vs dense?):
- Dense needs m·n elements.
- CSR needs t (val) + t (col_idx) + (m+1) (row_ptr) elements. Ignoring constant-size metadata, CSR is smaller when 2t + (m+1) < m·n ⇒ t < (m·n − (m+1))/2. Similar inequality holds for CSC replacing m by n.
- Statement (Time complexity under standard assumptions: arrays are contiguous; indices are sorted):
- COO transpose by resorting: O(t log t).
- COO fast transpose (counting by column): O(n + t).
- COO addition when both are sorted by (row, col): O(tA + tB).
- CSR SpMV y = A·x: O(t) operations + O(m) to zero-init y.
- CSR addition C = A + B: O(tA + tB) with row-wise merge.
- CSR×dense-vector is usually faster than COO due to better locality.
Algorithms (what to write in exams)
COO Fast Transpose (assumes header and that triples are sorted by row):
- Count how many triples fall into each column of A: count[c].
- Compute starting positions for each column in B: start[c] = 1 + sum_{k=0}^{c−1} count[k]. Index 1 because index 0 holds header.
- For each triple (i, j, v) in A (from index 1..t), place (j, i, v) into B at index start[j], then increment start[j].
- Set B’s header (n, m, t). This runs in O(n + t) time and produces B sorted by row then column.
COO Addition (A and B same shape, sorted by (row, col)):
- Use two pointers i and j to traverse A and B.
- If positions match, sum values; emit only if sum ≠ 0.
- Else emit the lexicographically smaller triplet.
- Append the remainder. Complexity O(tA + tB).
CSR SpMV y = A·x (A is m×n):
- Initialize y[0..m−1] = 0.
- For each row i, for k from row_ptr[i] to row_ptr[i+1]−1: y[i] += val[k] · x[col_idx[k]]. Complexity O(t).
Edge cases and conventions
- Index origin: Many textbooks and C-style implementations use 0-based indices for rows/cols in code, but the triplet header position often uses 1-based counting in algorithm descriptions. Be consistent in your answer and code.
- Duplicates: COO may contain multiple entries for the same (row, col); merge them by summing before or during operations.
- Sorted order: Keep COO sorted by (row, col) for predictable merges.
- Empty rows/columns: In CSR, empty rows have row_ptr[i] = row_ptr[i+1]; in CSC, empty columns have col_ptr[j] = col_ptr[j+1].
Formulas
sparsity s = 1 − p— s: fraction of zeros (unitless), p as above; applies to any matrix.COO header = (m, n, t)— sizes and count; used in triplet representation.CSR = (val[0..t−1], col_idx[0..t−1], row_ptr[0..m])— arrays composing CSR; applies when storing row-compressed sparse matrices.CSC = (val[0..t−1], row_idx[0..t−1], col_ptr[0..n])— arrays composing CSC; applies to column-compressed storage.start[c] = 1 + sum_{k=0}^{c−1} count[k]— starting position for column c in fast transpose (COO with header at index 0); count[k] is number of A’s entries in column k.SpMV CSR: y[i] = sum_{k=row_ptr[i]}^{row_ptr[i+1]−1} val[k] · x[col_idx[k]]— y: result vector, i: row index; applies when multiplying CSR matrix A by dense vector x.Space dense = m·n, Space COO ≈ 3t (+ header), Space CSR ≈ 2t + (m+1)— element counts (unitless), comparing storage needs.
Worked examples
Example 1: Fast transpose of a sparse matrix in triplet (COO) form Problem: Given A (4×5) with nonzeros at (0,2)=3, (1,0)=22, (1,4)=17, (2,0)=7, (3,1)=5, store A in triplet with header and compute its transpose using fast transpose.
Python program:
# Triplet (COO) fast transpose with header at index 0
# Triples are 0-based (row, col), header = (m, n, t)
def fast_transpose(coo):
m, n, t = coo[0]
B = [(n, m, t)] + [(0, 0, 0)] * t
if t == 0:
return B
# Count entries per column in A
count = [0] * n
for i in range(1, t + 1):
_, c, _ = coo[i]
count[c] += 1
# Compute starting positions in B (index 1..t)
start = [0] * n
total = 1 # position after header
for c in range(n):
start[c] = total
total += count[c]
# Place transposed entries
for i in range(1, t + 1):
r, c, v = coo[i]
pos = start[c]
B[pos] = (c, r, v)
start[c] += 1
return B
# Build A in triplet (header + entries sorted by row, then col)
A = [
(4, 5, 5), # header: 4 rows, 5 cols, 5 nonzeros
(0, 2, 3),
(1, 0, 22),
(1, 4, 17),
(2, 0, 7),
(3, 1, 5),
]
B = fast_transpose(A)
print("A (triplet):")
for t in A:
print(t)
print("B = A^T (triplet):")
for t in B:
print(t)
Sample output:
A (triplet):
(4, 5, 5)
(0, 2, 3)
(1, 0, 22)
(1, 4, 17)
(2, 0, 7)
(3, 1, 5)
B = A^T (triplet):
(5, 4, 5)
(0, 1, 22)
(0, 2, 7)
(1, 3, 5)
(2, 0, 3)
(4, 1, 17)
Explanation check: B is 5×4 with nonzeros (row, col, val): (0,1,22), (0,2,7), (1,3,5), (2,0,3), (4,1,17). This matches transposed positions, sorted by row then col.
Example 2: CSR matrix–vector multiplication (SpMV) Problem: Store the 4×4 matrix below in CSR and compute y = A·x for x = [1, 2, 3, 4]^T. A = [10 0 0 0] [ 0 0 3 0] [ 2 0 0 0] [ 0 5 0 1]
Python program:
# Build CSR from a dense 2D list (0-based)
def dense_to_csr(dense):
m = len(dense)
n = len(dense[0]) if m > 0 else 0
val = []
col_idx = []
row_ptr = [0]
for i in range(m):
for j in range(n):
v = dense[i][j]
if v != 0:
val.append(v)
col_idx.append(j)
row_ptr.append(len(val))
return val, col_idx, row_ptr
def csr_spmv(val, col_idx, row_ptr, x):
m = len(row_ptr) - 1
y = [0] * m
for i in range(m):
start, end = row_ptr[i], row_ptr[i + 1]
acc = 0
for k in range(start, end):
acc += val[k] * x[col_idx[k]]
y[i] = acc
return y
A_dense = [
[10, 0, 0, 0],
[0, 0, 3, 0],
[2, 0, 0, 0],
[0, 5, 0, 1],
]
x = [1, 2, 3, 4]
val, col_idx, row_ptr = dense_to_csr(A_dense)
y = csr_spmv(val, col_idx, row_ptr, x)
print("val:", val)
print("col_idx:", col_idx)
print("row_ptr:", row_ptr)
print("y:", y)
Sample output:
val: [10, 3, 2, 5, 1]
col_idx: [0, 2, 0, 1, 3]
row_ptr: [0, 1, 2, 3, 5]
y: [10, 9, 2, 14]
Explanation check: y[0]=10·1=10; y[1]=3·3=9; y[2]=2·1=2; y[3]=5·2+1·4=14.
Example 3: Addition of two sparse matrices in triplet (COO) form Problem: Given A and B (both 3×3) in sorted triplet form, compute C = A + B. A nonzeros: (0,0,1), (0,2,2), (2,1,3) B nonzeros: (0,1,4), (1,2,5), (2,1,3), (2,2,6)
Python program:
# COO addition with header, merge by (row, col), discard zeros
def coo_add(A, B):
mA, nA, tA = A[0]
mB, nB, tB = B[0]
assert mA == mB and nA == nB
m, n = mA, nA
i, j = 1, 1
C = [(m, n, 0)]
while i <= tA and j <= tB:
rA, cA, vA = A[i]
rB, cB, vB = B[j]
if (rA, cA) == (rB, cB):
s = vA + vB
if s != 0:
C.append((rA, cA, s))
i += 1
j += 1
elif (rA, cA) < (rB, cB):
C.append((rA, cA, vA))
i += 1
else:
C.append((rB, cB, vB))
j += 1
while i <= tA:
C.append(A[i])
i += 1
while j <= tB:
C.append(B[j])
j += 1
# fix header count
C[0] = (m, n, len(C) - 1)
return C
A = [
(3, 3, 3),
(0, 0, 1),
(0, 2, 2),
(2, 1, 3),
]
B = [
(3, 3, 4),
(0, 1, 4),
(1, 2, 5),
(2, 1, 3),
(2, 2, 6),
]
C = coo_add(A, B)
print("C (triplet):")
for t in C:
print(t)
Sample output:
C (triplet):
(3, 3, 6)
(0, 0, 1)
(0, 1, 4)
(0, 2, 2)
(1, 2, 5)
(2, 1, 6)
(2, 2, 6)
Explanation check: At (2,1), values 3+3=6; all positions are lexicographically ordered.
Common mistakes
- Leaving COO unsorted and trying to merge/add — leads to O(t²) behavior and wrong duplicates handling.
- Not merging duplicates in COO (same (row, col) appears multiple times), so results are inflated.
- CSR row_ptr length off by one (must be m+1) or not setting row_ptr[m] = t.
- Using incorrect column indices in CSR (not sorted within row). Sorting isn’t mandatory, but some algorithms assume increasing col_idx for binary search or merges.
- Forgetting to drop zero results after addition, leaving unnecessary entries.
- For SpMV, using x of wrong length (must be n), or not zero-initializing y.
- For fast transpose, computing start[c] incorrectly (forgetting header shift or incorrect cumulative sums).
For your exam
- Short notes: Compare COO vs CSR vs CSC (space, operations, pros/cons). Mention typical complexities: COO fast transpose O(n + t), CSR SpMV O(t).
- Derivations: Space bounds and “when sparse is better than dense.” Show dense = m·n vs CSR = 2t + (m+1); derive inequality for t.
- Algorithms: Write steps for fast transpose, COO addition, CSR SpMV. Include edge cases and invariants (e.g., row_ptr[m] = t).
- Programs: Python/C to perform COO transpose/addition, CSR SpMV. Ensure input/output format is clear and sample output matches exactly.
- Diagrams: Draw a small sparse matrix, its triplet table, and CSR arrays with arrows labeling row_ptr boundaries.
- Full-marks answers usually include: clean definition, labeled diagram, algorithm with correct complexity, one small worked example with correct numbers, and clear statement of assumptions (indexing, sorted order, duplicate handling).
Quick check
- What are the three arrays in CSR and what does row_ptr[i] store?
- How does the fast transpose algorithm achieve O(n + t) time from a COO input?
- If a 10,000×10,000 matrix has density p = 0.0001, approximately how many nonzeros does it have, and is CSR storage likely beneficial?
Answers: 1) val, col_idx, row_ptr; row_ptr[i] is the starting index in val/col_idx for row i (with row_ptr[m] = t). 2) It counts entries per column, computes cumulative starting positions for each column, and writes each transposed triple directly to its final position in one pass. 3) t ≈ p·m·n = 0.0001·10^8 = 10,000 nonzeros; yes, CSR (≈ 2t + m+1 elements) is far smaller than dense (10^8 elements).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?