SPARSE-MATRIX VECTOR MULTIPLICATION ON DISTRIBUTED ARCHITECTURES - LOWER BOUNDS AND AVERAGE COMPLEXITY RESULTS

Authors
MANZINI G
Citation
G. Manzini, SPARSE-MATRIX VECTOR MULTIPLICATION ON DISTRIBUTED ARCHITECTURES - LOWER BOUNDS AND AVERAGE COMPLEXITY RESULTS, Information processing letters, 50(5), 1994, pp. 231-238
Citations number
6
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
50
Issue
5
Year of publication
1994
Pages
231 - 238
Database
ISI
SICI code
0020-0190(1994)50:5<231:SVMODA>2.0.ZU;2-T
Abstract
In this paper we consider the problem of computing y = Ax where A is a n n X n sparse matrix with THETA(n) nonzero elements. We prove that, u nder reasonable assumptions, on a local memory machine with p processo rs this computation requires OMEGA((n/p) log p) time. We also study th e average complexity of this problem: we prove that for an important c lass of algorithms the computation of y = Ax requires OMEGA((n/p) log p) time with probability greater than 1/2.