Optimal sparse matrix dense vector multiplication in the I/O-model
Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob, Elias Vicari · 2007
We analyze the problem of sparse-matrix dense-vector multiplication (SpMV) in the I/O-model. The task of SpMV is to compute y := Ax, where A is a sparse N x N matrix and x and y are vectors. Here, sparsity is expressed by the parameter k that states that A has a total of at most kN nonzeros, i.e., an average number of k nonzeros per column. The extreme choices for parameter k are well studied special cases, namely for k=1 permuting and for k=N dense matrix-vector multiplication.