Why It Matters
What is a Sparse Matrix
Sparsity Pattern
The sparsity pattern describes which entries are non-zero. Visualizing sparsity patterns reveals structure that affects format choice and algorithm performance.
Sparse Matrix Formats
CSR (Compressed Sparse Row)
Matrix: CSR Representation:
+ + values = [1, 2, 3, 4, 5, 6]
| 1 0 0 2 0 | col_idx = [0, 3, 1, 2, 3, 4]
| 0 3 0 0 0 | row_ptr = [0, 2, 3, 5, 6]
| 0 0 4 5 0 |
| 0 0 0 0 6 | Row 0: values[0:2] = [1, 2]
+ + Row 1: values[2:3] = [3]
Row 2: values[3:5] = [4, 5]
Row 3: values[5:6] = [6]
Best for: Row slicing, matrix-vector multiplication, arithmetic operations Worst for: Column slicing, inserting new non-zeros
CSC (Compressed Sparse Column)
Matrix: CSC Representation:
+ + values = [1, 3, 2, 4, 5, 6]
| 1 0 0 2 0 | row_idx = [0, 1, 0, 2, 2, 3]
| 0 3 0 0 0 | col_ptr = [0, 2, 3, 4, 6, 6]
| 0 0 4 5 0 |
| 0 0 0 0 6 | Col 0: values[0:2] = [1, 3] (rows 0,1)
+ + Col 1: values[2:3] = [3] (row 1)
Col 2: values[3:4] = [4] (row 2)
Col 3: values[4:6] = [2, 5] (rows 0,2)
Col 4: values[6:6] = [] (no non-zeros)
Best for: Column slicing, solving , feature-based operations Worst for: Row slicing, inserting new non-zeros
COO (Coordinate)
Matrix: COO Representation:
+ + row = [0, 0, 1, 2, 2, 3]
| 1 0 0 2 0 | col = [0, 3, 1, 2, 3, 4]
| 0 3 0 0 0 | values = [1, 2, 3, 4, 5, 6]
| 0 0 4 5 0 |
| 0 0 0 0 6 | Each triple: (row[i], col[i], values[i])
+ + = (0,0,1), (0,3,2), (1,1,3), ...
Best for: Construction, incremental building, format conversion input Worst for: Arithmetic, slicing (convert to CSR/CSC first)
LIL (List of Lists)
Matrix: LIL Representation:
+ + data = [[1, 2], [3], [4, 5], [6]]
| 1 0 0 2 0 | rows = [[0, 3], [1], [2, 3], [4]]
| 0 3 0 0 0 |
| 0 0 4 5 0 | Row 0: data[0]=[1,2], rows[0]=[0,3]
| 0 0 0 0 6 | Row 1: data[1]=[3], rows[1]=[1]
+ + Row 2: data[2]=[4,5], rows[2]=[2,3]
Row 3: data[3]=[6], rows[3]=[4]
Best for: Incremental construction, row-wise modifications Worst for: Arithmetic, column slicing (convert to CSR/CSC)
DOK (Dictionary of Keys)
Matrix: DOK Representation:
+ + {(0,0): 1, (0,3): 2,
| 1 0 0 2 0 | (1,1): 3, (2,2): 4,
| 0 3 0 0 0 | (2,3): 5, (3,4): 6}
| 0 0 4 5 0 |
| 0 0 0 0 6 | Lookup: dok[(0,3)] -> 2
+ + Insert: dok[(4,4)] = 7
Best for: Element-wise access during construction, sparse matrix assembly Worst for: Arithmetic, slicing (convert to CSR/CSC)
Format Comparison
| Format | Construction | Row Slice | Col Slice | MatVec | Arithmetic | Memory |
|---|---|---|---|---|---|---|
| CSR | O(nnz) | O(1) | O(m) | O(nnz) | O(nnz) | Low |
| CSC | O(nnz) | O(n) | O(1) | O(nnz) | O(nnz) | Low |
| COO | O(1) | O(nnz) | O(nnz) | O(nnz) | O(nnz) | Medium |
| LIL | O(1) | O(nnz) | O(nnz) | O(nnz) | O(nnz) | High |
| DOK | O(1) | O(nnz) | O(nnz) | O(nnz) | O(nnz) | High |
Format Conversions
Converting between formats involves tradeoffs in speed, memory, and operations supported.
from scipy import sparse
import numpy as np
# Build incrementally with LIL, convert to CSR for computation
lil = sparse.lil_matrix((10000, 10000))
lil[0, 0] = 1
lil[1, 2] = 3
lil[5, 7] = -2
csr = lil.tocsr() # Convert for efficient operations
# COO construction from data
row = np.array([0, 1, 2, 0])
col = np.array([0, 1, 2, 2])
val = np.array([1.0, 2.0, 3.0, 4.0])
coo = sparse.coo_matrix((val, (row, col)), shape=(3, 3))
csr = coo.tocsr() # Convert for arithmetic
# CSR <-> CSC conversion
csc = csr.tocsc()
csr_back = csc.tocsr()
Conversion cost hierarchy:
LIL/DOK -> CSR/CSC: O(nnz Γ log(nnz)) [sorting]
COO -> CSR/CSC: O(nnz) [linear scan]
CSR <-> CSC: O(nnz) [transpose]
CSR/CSC -> Dense: O(m Γ n) [always expensive]
Sparse Matrix Operations
Matrix-Vector Multiplication
from scipy import sparse
import numpy as np
A = sparse.random(100000, 100000, density=0.001, format='csr')
x = np.random.randn(100000)
y = A @ x # O(nnz) matrix-vector multiply
print(f"nnz: {A.nnz}, time proportional to {A.nnz} operations")
Matrix Addition
A = sparse.random(1000, 1000, density=0.01, format='csr')
B = sparse.random(1000, 1000, density=0.01, format='csr')
C = A + B # Element-wise addition, sparsity decreases
D = A - B # Element-wise subtraction
E = 2.0 * A # Scalar multiplication
Note: Sum of two sparse matrices has sparsity min(sparsity(A), sparsity(B)). Non-zeros may increase significantly.
Matrix Multiplication
A = sparse.random(1000, 1000, density=0.01, format='csr')
B = sparse.random(1000, 1000, density=0.01, format='csr')
C = A @ B # Sparse Γ Sparse
print(f"Input nnz: {A.nnz}, {B.nnz}, Output nnz: {C.nnz}")
Transpose
A = sparse.random(1000, 500, density=0.01, format='csr')
AT = A.T # O(nnz) operation, swaps CSR <-> CSC internally
AAT = A @ A.T # Symmetric result
Element Access
# DOK: O(1) lookup
dok = sparse.dok_matrix((10000, 10000))
dok[123, 456] = 7.0
val = dok[123, 456] # O(1)
# CSR: O(log(nnz_row)) via binary search within row
csr = dok.tocsr()
val = csr[123, 456] # Slower than DOK for single lookups
# Dense slice: convert small block
block = csr[100:200, 100:200].toarray()
Sparse vs Dense
Key insight: GPUs prefer dense matrices for regular memory access patterns. Sparse matrices on GPUs (cuSPARSE) can be faster but require specialized kernels. For very large sparse matrices, CPU sparse operations often beat GPU dense operations due to memory constraints.
Common Sparsity Patterns
D = sparse.diags([1, 2, 3, 4]) # 4x4 diagonal
D_inv = sparse.diags([1/x for x in [1, 2, 3, 4]]) # O(n) inversion
# Tridiagonal matrix (bandwidth = 1)
main_diag = np.ones(100) * 2
off_diag = np.ones(99) * -1
A = sparse.diags([off_diag, main_diag, off_diag], [-1, 0, 1])
# Storage: 299 values vs 10000 dense
blocks = [sparse.random(100, 100, density=0.1) for _ in range(10)]
A = sparse.block_diag(blocks) # 1000x1000 matrix, 10 independent blocks
A = sparse.random(1000, 1000, density=0.01, format='csr')
# Expected nnz = 1000 * 1000 * 0.01 = 10000
Python Implementation
Construction Patterns
from scipy import sparse
import numpy as np
# Pattern 1: From dense array
dense = np.array([[1, 0, 2], [0, 0, 0], [3, 0, 4]])
csr = sparse.csr_matrix(dense)
# Pattern 2: COO from data
row, col, val = [0, 2, 0], [0, 2, 2], [1.0, 4.0, 2.0]
coo = sparse.coo_matrix((val, (row, col)), shape=(3, 3))
# Pattern 3: Diagonal
D = sparse.diags([1, 2, 3])
# Pattern 4: Random
R = sparse.random(100, 100, density=0.1, format='csr',
random_state=42)
# Pattern 5: Identity
I = sparse.eye(1000, format='csr')
# Pattern 6: Kronecker product
A = sparse.random(10, 10, density=0.3)
B = sparse.random(10, 10, density=0.3)
C = sparse.kron(A, B) # 100x100 sparse matrix
Sparse Linear Algebra
from scipy.sparse import linalg
A = sparse.csr_matrix([[4, 1], [1, 3]])
b = np.array([1, 2])
# Direct solve (small sparse systems)
x = linalg.spsolve(A, b)
# Iterative solve (large sparse systems)
x_iter, info = linalg.bicgstab(A, b, maxiter=1000, tol=1e-10)
# Eigenvalues
vals, vecs = linalg.eigs(A, k=2, which='LM')
# Singular values
U, s, Vt = linalg.svds(A, k=2)
# Norm
norm_A = linalg.norm(A, ord='fro')
Practical Example: Sparse Gradient Descent
from scipy import sparse
import numpy as np
# Feature matrix: 1M samples, 100K features, 0.1% density
X = sparse.random(1000000, 100000, density=0.001, format='csr')
y = np.random.randn(1000000)
w = np.random.randn(100000)
# Gradient: X.T @ (X @ w - y)
residual = X @ w - y # O(nnz) sparse matvec
gradient = X.T @ residual # O(nnz) sparse transpose matvec
w -= 0.01 * gradient # O(n) dense update
# Memory: X is ~1.2GB sparse, would be 80GB dense
Applications in AI/ML
Recommendation Systems
from scipy.sparse.linalg import svds
# Sparse user-item matrix (1M users, 10K items)
R = sparse.random(1000000, 10000, density=0.001, format='csr')
# Truncated SVD for latent factors
U, sigma, Vt = svds(R, k=50) # k=50 latent dimensions
# U: user embeddings, Vt: item embeddings
NLP: Term-Document Matrices
from sklearn.feature_extraction.text import TfidfVectorizer
documents = ["the cat sat on the mat", "the dog ran in the park"]
vectorizer = TfidfVectorizer()
X = vectorizer.fit_transform(documents) # Sparse matrix
print(f"Shape: {X.shape}, nnz: {X.nnz}")
Graph Neural Networks
import torch
from torch_geometric.utils import dense_to_sparse
# Dense adjacency (small graph)
A_dense = torch.tensor([[0, 1, 0], [1, 0, 1], [0, 1, 0]], dtype=torch.float)
edge_index, edge_weight = dense_to_sparse(A_dense)
# edge_index: [[0,1,1,2], [1,0,2,1]] β sparse COO-like format
Transformer Sparse Attention
# Local attention pattern (window size = 256)
def local_attention_mask(seq_len, window=256):
mask = torch.zeros(seq_len, seq_len, dtype=torch.bool)
for i in range(seq_len):
start = max(0, i - window // 2)
end = min(seq_len, i + window // 2)
mask[i, start:end] = True
return mask # ~99% sparse for long sequences
# Sparse attention in PyTorch
from torch.nn.functional import scaled_dot_product_attention
# Use is_causal or custom attn_mask for sparsity
Common Mistakes
| Mistake | Why It's Wrong | Correct Approach |
|---|---|---|
Using .toarray() for large matrices | Defeats purpose of sparsity β allocates O(mΓn) memory | Keep as sparse, use sparse operations |
| Converting CSR <-> CSC repeatedly | Each conversion is O(nnz) and creates new arrays | Pick the right format once, stick with it |
| Adding dense to sparse | Result is dense, losing all benefits | Use sparse + sparse, or convert sparse to dense only when necessary |
Using A[i,j] in loops on CSR | Each access is O(log(nnz_row)) β slow in loops | Use DOK for random access, vectorize operations |
| Ignoring fill-in in sparse solvers | Matrix multiplication can create new non-zeros | Monitor nnz growth, use iterative methods for large systems |
| Assuming GPU acceleration helps | Sparse operations on GPUs have high overhead for small nnz | Profile: GPU sparse beats CPU sparse only for very large matrices |
| Using float64 for integer indices | Wastes memory, slower operations | Use int32 for indices (saves 50% over int64) |
| Building large sparse matrices with append | List appends cause O(n) copies | Use COO lists or LIL, convert once at the end |
Interview Questions
Q1: Why are sparse matrices important in machine learning?
Answer: Most real-world datasets produce sparse matrices: NLP term-document matrices (99.9% sparse), recommendation systems (99.95% sparse), graph adjacency matrices (99.999% sparse). Storing and computing with dense representations wastes memory and compute. Sparse formats store only non-zeros, reducing memory from O(mn) to O(nnz) and computation from O(mn) to O(nnz).
Q2: When would you choose CSR over CSC?
Answer: CSR for row-oriented operations: row slicing, matrix-vector multiplication (), row-wise normalization. CSC for column-oriented operations: column slicing, solving , feature normalization. CSR and CSC are dual β CSR is optimal when operations access rows, CSC when accessing columns.
Q3: What is the time complexity of sparse matrix-vector multiplication?
Answer: O(nnz), where nnz is the number of non-zero entries. For CSR, each row computes by iterating over non-zeros in that row. Total work is proportional to nnz, which is optimal since every non-zero must be accessed at least once.
Q4: How does sparse matrix multiplication differ from dense?
Answer: Dense multiplication is . Sparse multiplication is more complex: the output nnz is unpredictable. For CSR Γ CSR, the algorithm iterates over non-zeros of A and B, finding shared indices via merge or hash. Complexity is worst case. The output can be much denser than either input ("fill-in").
Q5: Describe the conversion path from construction to computation.
Answer: Build with COO (append triples in any order) or LIL (row-wise insertion), then convert to CSR or CSC for computation. Conversion is O(nnz). Never build directly in CSR/CSC β they don't support efficient insertion. The pipeline: COO/LIL -> CSR/CSC -> compute -> COO/LIL for modifications.
Q6: What is fill-in and why does it matter?
Answer: Fill-in occurs when operations on sparse matrices produce denser results. Examples: doubles non-zeros; can create non-zeros; sparse LU decomposition creates non-zeros in zero positions. Fill-in reduces the effectiveness of sparse representations and increases computation time.
Q7: How would you handle a sparse matrix on a GPU?
Answer: Use cuSPARSE (NVIDIA) or equivalent. Key considerations: (1) Only beneficial for very large matrices (nnz > 1M), (2) CSR/CSC formats are supported, (3) Sparse operations on GPUs have higher per-operation overhead than CPU, so batch operations help, (4) Mixed sparse-dense operations (sparse Γ dense) benefit most from GPU acceleration.
Practice Problems
Problem 1: Memory Savings
Problem 2: Sparsity After Operations
Problem 3: Format Selection
Problem 4: Sparse Eigenvalues
Quick Reference
| Aspect | Detail |
|---|---|
| Dense storage | bytes (float64) |
| CSR storage | bytes |
| CSC storage | bytes |
| COO storage | bytes |
| MatVec complexity | |
| Sparse Γ Sparse | |
| Sparsity definition | |
| Sparse threshold | β₯ 90% zeros |
| Break-even nnz | for CSR vs dense |
| Best construction format | COO (random) or LIL (row-wise) |
| Best computation format | CSR (rows) or CSC (columns) |
| Best random access format | DOK |
| Python library | scipy.sparse |
| GPU support | cuSPARSE, PyTorch sparse |
Cross-References
- Matrix Decompositions β SVD, eigenvalue decomposition for sparse matrices
- Linear Algebra Matrices β Dense operations as baseline for comparison
- Linear Algebra Basics β Vectors, matrices, and basic operations
- Linear Algebra Determinants β Rank, determinant, conditioning
- Eigenvalues and Eigenvectors β Sparse eigenvalue computation
- Calculus Optimization β Gradient methods using sparse Jacobians
- Probability Distributions β Sparse covariance matrices
- Discrete Graphs β Adjacency matrices and sparse graph operations