Processor-efficient sparse matrix-vector multiplication (Q1767967)

The authors consider the matrix-vector multiplication for sparse matrices which is the kernel of many numerical algorithms. After some preliminaries, a new measure of matrix sparsity called staircase width is introduced and some basic facts about this measure are formulated, proved and compared with other measure of sparsity like the stripe width and bandwidth using the University of Florida sparse matrix collection that have arisen in a variety of real applications. The staircase width of a matrix is never larger than the bandwidth or the stripe width. Usually, it is significantly smaller. Next, the generalized sparse matrix-vector multiplication algorithm for systolic arrays is introduced and analyzed together with the discussion about its correctness. Finally, some interesting results concerning the performance of the algorithm are presented. Summarizing, it is an interesting paper worth to be read.