Optimizing Sparse Matrix-Vector Multiplication on GPUs using the Mathematics of Arrays

We present a Mathematics of Arrays (MoA) and ψ-calculus derivation of the memory-optimal operational normal form for ELLPACK sparse matrix-vector multiplication (SpMV) on GPUs. Under the standard row-parallel schedule, MoA shows that column-major ELLPACK is the unique axis permutation that places the lane-varying index innermost at linearization, thereby producing unit-stride streams for the value and index arrays and maximizing coalesced loads (Proposition 1). The derivation is explicitly schedule-aware and predicts the dual result that, for k-parallel kernels with intra-warp reduction in the padded column index, row-major becomes optimal by the same criterion. We further obtain a reshape-permute refinement (SELL-C with C equal to wavefront width) that bounds padding by slice-local maxima while preserving unit stride across lanes, and we identify a correctness-preserving row permutation that reduces the dispersion of vector gathers. These transformations are semantics-preserving in MoA and directly target the reduction of memory reads on AMD Instinct MI300X-class devices. The analysis provides a principled path to multiplicative speedups in language-model and biomolecular AI workloads, with immediate consequences for cost, energy, and reproducibility.