Technical Report CS0339

Title: Sparse-Matrix Multiplication: a Simple and Efficient Parallel Algorithm
Authors: A Israeli and Y. Shiloach
Abstract: A parallel algorithm for multiplying sparse matrices is presented. It uses the PRAM (shared memory) model of parallel computation. Nothing is assumed on the particular distribution of nonzero elements in the matrices. Yet the algorithm is simple and efficient. Let N be the number of products of a nonzero element in one matrix with a nonzero element in the other, carried out by the regular matrix multiplication algorithm. Our algorithm runs on an N-PRAM (PRAM with N processors), in O(log N) time. A sequential (one processor) variation of this algorithm runs in o(N+|A|) time, where |A| is the numbe of nonzero elements in A.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1984
To the main CS technical reports page

Computer science department, Technion