TR#: | CS0339 |

Class: | CS |

Title: | Sparse-Matrix Multiplication: a Simple and Efficient Parallel Algorithm |

Authors: | A Israeli and Y. Shiloach |

CS0339.pdf | |

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. |

Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1984/CS/CS0339), 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