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.