Sparse Matrix Vector

Sparse Matrix-Vector Multiplication (SpMV) is the operation y = A×x where A is a sparse matrix — a fundamental kernel in scientific computing, graph algorithms, and machine learning where most matrix elements are zero and storing them explicitly wastes memory and compute.

Why Sparsity Matters

• Dense 10K×10K matrix: 100M elements, 800MB (float). Most entries may be zero.
• Sparse: Store only non-zeros (NNZ). 1% density → 1M elements, 8MB.
• SpMV compute: Only operate on non-zeros → NNZ operations vs. N² for dense.

Sparse Storage Formats

CSR (Compressed Sparse Row) — Most Common:

A = [1 0 2]   row_ptr = [0, 2, 3, 5]
    [0 3 0]   col_idx  = [0, 2, 1, 0, 2]
    [4 0 5]   values   = [1, 2, 3, 4, 5]

• `row_ptr[i]` to `row_ptr[i+1]`: Indices of row i's non-zeros in col_idx/values.
• Efficient row-wise access (good for row-parallel SpMV).

COO (Coordinate Format):
- Triplet (row, col, val) for each non-zero. Simple but unordered.
- Used for construction, then converted to CSR/CSC.

ELL (ELLPACK):
- Fixed number of elements per row (padded to max). GPU-friendly (coalesced access).
- Wastes memory if row lengths vary widely.

CSC (Compressed Sparse Column):
- Column-wise CSR — efficient for column operations.

GPU SpMV

• CSR SpMV: Each thread/warp handles one row → irregular memory access, poor coalescing.
• ELL: Each thread handles one element position → coalesced access.
• SELL-C-σ: Sliced ELL with row sorting for better load balance.
• cuSPARSE: NVIDIA library with optimized SpMV for all major formats.

Applications

• FEM/FDM solvers: Stiffness/mass matrices in structural, fluid simulations.
• PageRank: Web graph adjacency matrix × rank vector.
• Recommender systems: User-item interaction matrix.
• Sparse neural networks: Pruned weight matrices for efficient inference.

SpMV performance is memory-bandwidth limited — the ratio of NNZ to unique memory accesses determines efficiency, and format selection based on matrix structure (regular, irregular, banded) is the primary optimization lever.