This paper introduces a storage format for sparse matrices, called compressed sparse blocks (CSB), which allows both Ax and A T x to be computed efficiently in parallel, where A is an n × n sparse matrix with nnz ≥ n nonzeros and x is a dense n-vector. Our algorithms use Θ(nnz) work (serial running time) and Θ( √ n lg n) span (critical-path length), yielding a parallelism of Θ(nnz / √ n lg n), which is amply high for virtually any large matrix. The storage requirement for CSB is esssentially the same as that for the morestandard compressed-sparse-rows (CSR) format, for which computing Ax in parallel is easy but A T x is difficult. Benchmark results indicate that on one processor, the CSB algorithms for Ax and A T x run just as fast as the CSR algorithm for Ax, but the CSB algorithms also scale up linearly with processors until limited by offchip memory bandwidth.
More recently, Buluç et al. REF have presented a block structure that allows efficient computation of both Ax and A T x in parallel.
Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks
SPAA '09
Computer Science