article · 2010

Highly Parallel Sparse Matrix-Matrix Multiplication

John, R. Gilbert

Cited by 0Abstract and details only

Abstract

Abstract. Generalized sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high performance graph algorithms as well as for some linear solvers, such as algebraic multi-grid. Here we show that SpGEMM also yields efficient algorithms for general sparse-matrix indexing in distributed memory, provided that the underlying SpGEMM implementation is sufficiently flexible and scalable. We demonstrate that our parallel SpGEMM methods, which use two-dimensional block data distributions with serial hypersparse kernels, are indeed highly flexible, scalable, and memory-efficient in the general case. This algorithm is the first to yield increasing speedup on an unbounded number of processors; our experiments show scaling up to thousands of processors in a variety of test scenarios. Key words. parallel computing, numerical linear algebra, sparse matrix-matrix multiplication, SpGEMM, sparse matrix indexing, sparse matrix assignment, two-dimensional data decomposition, hypersparsity, graph algorithms, sparse SUMMA, subgraph extraction, graph contraction, graph batch update

Cite this paper

APA 7

John, & Gilbert, R. (2010). Highly Parallel Sparse Matrix-Matrix Multiplication.

MLA 9

John, , and R. Gilbert. “Highly Parallel Sparse Matrix-Matrix Multiplication.” 2010.

Chicago

John, and R. Gilbert. 2010. “Highly Parallel Sparse Matrix-Matrix Multiplication.”

Harvard

John and Gilbert, R. (2010) ‘Highly Parallel Sparse Matrix-Matrix Multiplication’.

BibTeX

@article{john2010highly,
  title = {{Highly Parallel Sparse Matrix-Matrix Multiplication}},
  author = {John and Gilbert, R.},
  year = {2010}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.