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
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Thursday, March 13, 2014 - 3:52:05 PM
Last modification on : Tuesday, December 7, 2021 - 3:46:06 PM
Long-term archiving on: : Friday, June 13, 2014 - 11:51:27 AM


Files produced by the author(s)




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



Record views


Files downloads