Sparse matrix vector multiplication on distributed architectures: Lower bounds and average complexity results

Giovanni Manzini

doi:10.1016/0020-0190(94)00046-8

Sparse matrix vector multiplication on distributed architectures: Lower bounds and average complexity results

Giovanni Manzini

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper we consider the problem of computing y = Ax where A is an n x n sparse matrix with Θ(n) nonzero elements. We prove that, under reasonable assumptions, on a local memory machine with p processors this computation requires Ω((n/p) log p) time. We also study the average complexity of this problem: we prove that for an important class of algorithms the computation of y = Ax requires Ω((n/p) log p) time with probability greater than 1 2.

Original language	English
Pages (from-to)	231-238
Number of pages	8
Journal	Information Processing Letters
Volume	50
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(94)00046-8
Publication status	Published - 10 Jun 1994
Externally published	Yes

Keywords

Average complexity
Distributed architectures
Parallel algorithms
Sparse matrices
Worst-case behavior

Access to Document

10.1016/0020-0190(94)00046-8

Cite this

@article{4a6efc6a2b2549ecb3f9647e82502006,

title = "Sparse matrix vector multiplication on distributed architectures: Lower bounds and average complexity results",

abstract = "In this paper we consider the problem of computing y = Ax where A is an n x n sparse matrix with Θ(n) nonzero elements. We prove that, under reasonable assumptions, on a local memory machine with p processors this computation requires Ω((n/p) log p) time. We also study the average complexity of this problem: we prove that for an important class of algorithms the computation of y = Ax requires Ω((n/p) log p) time with probability greater than 1 2.",

keywords = "Average complexity, Distributed architectures, Parallel algorithms, Sparse matrices, Worst-case behavior",

author = "Giovanni Manzini",

year = "1994",

month = jun,

day = "10",

doi = "10.1016/0020-0190(94)00046-8",

language = "English",

volume = "50",

pages = "231--238",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Sparse matrix vector multiplication on distributed architectures

T2 - Lower bounds and average complexity results

AU - Manzini, Giovanni

PY - 1994/6/10

Y1 - 1994/6/10

N2 - In this paper we consider the problem of computing y = Ax where A is an n x n sparse matrix with Θ(n) nonzero elements. We prove that, under reasonable assumptions, on a local memory machine with p processors this computation requires Ω((n/p) log p) time. We also study the average complexity of this problem: we prove that for an important class of algorithms the computation of y = Ax requires Ω((n/p) log p) time with probability greater than 1 2.

AB - In this paper we consider the problem of computing y = Ax where A is an n x n sparse matrix with Θ(n) nonzero elements. We prove that, under reasonable assumptions, on a local memory machine with p processors this computation requires Ω((n/p) log p) time. We also study the average complexity of this problem: we prove that for an important class of algorithms the computation of y = Ax requires Ω((n/p) log p) time with probability greater than 1 2.

KW - Average complexity

KW - Distributed architectures

KW - Parallel algorithms

KW - Sparse matrices

KW - Worst-case behavior

UR - https://www.scopus.com/pages/publications/0028446382

U2 - 10.1016/0020-0190(94)00046-8

DO - 10.1016/0020-0190(94)00046-8

M3 - Article

SN - 0020-0190

VL - 50

SP - 231

EP - 238

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Sparse matrix vector multiplication on distributed architectures: Lower bounds and average complexity results

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this