Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model

Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob, and Elias Vicari

In Theory of Computing Systems, Special issue of SPAA'07, volume 47(4), pages 934-962, 2010.

Abstract

We study the problem of sparse-matrix dense-vector multiplication (SpMV) in external memory. The task of SpMV is to compute y:=Ax, where A is a sparse Nx N matrix and x is a vector. We express sparsity by a parameter k, and for each choice of k consider the class of matrices where the number of nonzero entries is kN, i.e., where the average number of nonzero entries per column is k.

We investigate what is the external worst-case complexity, i.e., the best possible upper bound on the number of I/Os, as a function of k and N. We determine this complexity up to a constant factor for all meaningful choices of these parameters. Our model of computation for the lower bound is a combination of the I/O-models of Aggarwal and Vitter, and of Hong and Kung.

We study variants of the problem, differing in the memory layout of A. If A is stored in column major layout, we prove that SpMV has I/O complexity Θ(min{kN/B·max{1,logM/B (N/max{k,M})},kN}) for kN1-ε and any constant 0 < ε < 1. If the algorithm can choose the memory layout, the I/O complexity reduces to Θ(min{kN/B·max{1,logM/B (N/(kM))},kN}) for kN1/3. In contrast, if the algorithm must be able to handle an arbitrary layout of the matrix, the I/O complexity is Θ(min{kN/B·max{1,logM/B (N/M)},kN}) for kN/2.

In the cache oblivious setting we prove that with tall cache assumption MB1+ε, the I/O complexity is O(kN/B·max{1,logM/B (N/max{k,M})}) for A in column major layout.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2010. All rights reserved.

Online version

tocs10.pdf (313 Kb)

DOI

10.1007/s00224-010-9285-4

BIBTEX entry

@article{tocs10,
  author = "Michael A. Bender and Gerth St{\o}lting Brodal and Rolf Fagerberg and Riko Jacob and Elias Vicari",
  doi = "10.1007/s00224-010-9285-4",
  issn = "1432-4350",
  journal = "Theory of Computing Systems, Special issue of SPAA'07",
  number = "4",
  pages = "934-962",
  publisher = "Springer {V}erlag, Berlin",
  title = "Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model",
  volume = "47",
  year = "2010"
}

Other versions