Sparse matrix vector multiplication on distributed architectures: Lower bounds and average complexity results (Q1329416)

The author considers the problem of computing \(y= Ax\), where \(A\) is an \(n\times n\) sparse matrix with \(O(n)\) nonzero elements and proves that there exist some sparse matrices for which, on a local memory with \(p\) processors, this computations require \(O((n/p)\log^{1/2}p)\) time. The average complexity of this problem is analyzed, and the attention is focused on the case when the vectors \(x\) and \(y\) are partitioned among processors according to a fixed scheme independent of the matrix \(A\). It is shown that if \(A\) is non-singular, then the computation of \(y= Ax\) requires \(O((n/p)\log p)\) time with probability greater than 1/2.