SpMV

SpMV, or sparse matrix–vector multiplication, is the operation of computing y = A x where A is a sparse (mostly zero) matrix and x and y are dense vectors. It is a fundamental kernel in scientific and engineering computations, used in iterative solvers, eigenvalue calculations, and graph algorithms, where large sparse matrices arise from discretizations of physical problems or from network representations.

Several storage formats are used to store sparse matrices efficiently. The compressed sparse row (CSR) format stores nonzero values, their column indices, and pointers to the start of each row. The compressed sparse column (CSC) format is the columnwise counterpart. Coordinate (COO) format stores triplets (row, column, value) for each nonzero. For performance on modern architectures, block and hybrid formats such as block CSR (BSR), ELLPACK (ELL), and HYB combine ideas to improve memory access and vectorization, especially on GPUs.

Performance of SpMV is typically bounded by memory bandwidth rather than arithmetic throughput, since the number of floating-point operations is proportional to the number of nonzeros while the matrix data and vector operands must be fetched from memory. The irregular sparsity pattern leads to noncontiguous accesses to the input vector x and to scattered writes to y, making performance sensitive to storage format and data layout.

Parallelism is achieved by assigning work across rows or nonzeros. CSR supports row-wise parallelism on CPUs, while GPU implementations often use HYB or ELL/CSR hybrids to improve memory coalescing. Load balancing can be challenging for matrices with highly variable row lengths, and matrix repartitioning or reordering is sometimes applied to improve locality and convergence in iterative methods. In distributed settings, SpMV is typically implemented as part of a larger parallel sparse linear algebra routine using MPI or similar.

SpMV is a building block for iterative solvers such as Conjugate Gradient, GMRES, and Jacobi methods, often with a preconditioner. It also appears in time-stepping schemes, spectral computations, and graph-processing algorithms where A encodes connections or transitions. Variants like Block SpMV exploit block structure in certain matrices to improve throughput.