Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model
We study the problem of sparse-matrix dense-vector multiplication (SpMV) in external memory. The task of SpMV is to compute y :=Ax, where A is a sparse N x N matrix and x is a vector. We express sparsity by a parameter k, and for each choice of k consider the class of matrices where the number of nonzero entries is kN, i.e., where the average number of nonzero entries per column is k. We investigate what is the external worst-case complexity, i.e., the best possible upper bound on the number of I/Os, as a function of k, N and the parameters M (memory size) and B (track size) of the I/O-model. We determine this complexity up to a constant factor for all meaningful choices of these parameters, as long as k  = B(1+epsilon), the I/O complexity is O(kN/B max{1, log(M/B) N/max{k, M}}) for A in column major layout.
sparse matrix dense vector multiplication i/o-model external memory algorithms lower bound