Block-Row Sparse Matrix-Vector Multiplication on SIMD Machines

TitleBlock-Row Sparse Matrix-Vector Multiplication on SIMD Machines
Publication TypeConference Paper
Year of Publication1995
AuthorsKapadia, N, Fortes, JAB
Conference Name1995 International Conference on Parallel Processing
Date Published08/1995
AbstractThe irregular nature of the data structures required to efficiently store arbitrary sparse matrices and the architectural constraints of a SIMD computer make it difficult to design an algorithm that can efficiently multiply an arbitrary sparse matrix by a vector. A new "block-row" algorithm is proposed. It allows the "regularity" of a data structure with a row-major mapping to be varied by changing a parameter (the "blocksize"); a heuristic to find a very good approximation of the optimal blocksize is also described. The block-row algorithm has been implemented on a 16,384 processor MasPar MP-1, and, for the matrices studied, the algorithm was found to be faster than any of the other algorithms considered. 1. INTRODUCTION This paper presents a new block-row algorithm for matrix-vector multiplication which was primarily developed for the large unstructured sparse matrices arising from a scattering-matrix approach to device simulation [1],[3]. The algorithm has been implemented on a 16...