Three Storage Formats for Sparse Matrices on GPGPUs∗

The multiplication of a sparse matrix by a dense vector is a center-piece of scientific computing applications: it is the essential kernel for the solution of sparse linear systems and sparse eigenvalue problems by iterative methods. The efficient implementation of the sparse matrix-vector multiplication is therefore crucial and has been the subject of an immense amount of research, with interest renewed with every major new trend in high performance computing architectures. The intro-duction of General Purpose Graphics Programming Units (GPGPUs) is no exception, and many articles have been devoted to this problem. In this report we propose three novel matrix formats, ELL-G and HLL which derive from ELL, and HDIA for matrices having mostly a diagonal sparsity pattern. We compare the performance of the pro-posed formats to that of state-of-the-art formats (i.e., HYB and ELL-RT) with experiments run on different GPU platforms and test matri-ces coming from various application domains. ∗This Technical Report has been issued as a Research Report for early dissemination of its contents. No part of its text nor any illustration can be reproduced without writte