Skip to Main content Skip to Navigation
Journal articles

Lower bounds for sparse matrix vector multiplication on hypercubic networks

Abstract : In this paper we consider the problem of computing on a local memory machine the product y = Ax,where A is a random n×n sparse matrix with Θ (n) nonzero elements. To study the average case communication cost of this problem, we introduce four different probability measures on the set of sparse matrices. We prove that on most local memory machines with p processors, this computation requires Ω ((n/p) \log p) time on the average. We prove that the same lower bound also holds, in the worst case, for matrices with only 2n or 3n nonzero elements.
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958901
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 3:52:05 PM
Last modification on : Thursday, May 2, 2019 - 2:30:10 PM
Long-term archiving on: : Friday, June 13, 2014 - 11:51:27 AM

File

dm020103.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00958901, version 1

Collections

Citation

Giovanni Manzini. Lower bounds for sparse matrix vector multiplication on hypercubic networks. Discrete Mathematics and Theoretical Computer Science, DMTCS, 1998, 2, pp.35-47. ⟨hal-00958901⟩

Share

Metrics

Record views

184

Files downloads

863