This paper introduces a storage format for sparse matrices, called   compressed sparse blocks (CSB)  , which allows both  Ax  and  A , x  to be computed efficiently in parallel, where  A  is an  n × n  sparse matrix with  nnz e 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 the same as that for the more-standard compressed-sparse-rows (CSR) format, for which computing  Ax  in parallel is easy but  A , x  is difficult. Benchmark results indicate that on one processor, the CSB algorithms for  Ax  and  A , x  run just as fast as the CSR algorithm for  Ax , but the CSB algorithms also scale up linearly with processors until limited by off-chip memory bandwidth.
['Aydin Buluç', 'Jeremy T. Fineman', 'Matteo Frigo', 'John R. Gilbert', 'Charles E. Leiserson']
Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks