Optimizing Sparse Matrix Vector Multiplication Using Diagonal Storage Matrix Format

摘要

Sparse matrix vector multiplication (SpMV) is used in many scientific computations. The main bottleneck of this algorithm is memory bandwidth and many methods reduce memory bandwidth usage by compressing the index array. The matrices from finite difference modeling applications often have several dense diagonals and sparse diagonals. For these matrices, the index array can be deleted by using diagonal storage format (DIA) to store dense diagonals and DIA & CSR mixed algorithm. In this paper we propose two improved sparse matrix storage format based on DIA format and the corresponding SpMV algorithms. We present the performance results on two platforms, which show that our method can reduce the memory usage for a wide range of sparse matrices and achieve speedup up to 1.87.