The input/output complexity of sparse matrix multiplication

DOI10.1007/978-3-662-44777-2_62MaRDI QIDQ2921459zbMATH OpenOpenAlexFDO

Authors Rasmus Pagh, Morten Stöckel

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.3551

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: We consider the problem of multiplying sparse matrices (over a semiring) where the number of non-zero entries is larger than main memory. In the classical paper of Hong and Kung (STOC '81) it was shown that to compute a product of dense $UimesU$ matrices, $Thetaleft(U^3/(BsqrtM)ight)$ I/Os are necessary and sufficient in the I/O model with internal memory size $M$ and memory block size $B$. In this paper we generalize the upper and lower bounds of Hong and Kung to the sparse case. Our bounds depend of the number $N=mathttnnz(A)+mathttnnz(C)$ of nonzero entries in $A$ and $C$, as well as the number $Z=mathttnnz(AC)$ of nonzero entries in $AC$. We show that $AC$ can be computed using $ildeOleft(fracNBminleft(sqrtfracZM,fracNMight)ight)$ I/Os, with high probability. This is tight (up to polylogarithmic factors) when only semiring operations are allowed, even for dense rectangular matrices: We show a lower bound of $Omegaleft(fracNBminleft(sqrtfracZM,fracNMight)ight)$ I/Os. While our lower bound uses fairly standard techniques, the upper bound makes use of ``compressed matrix multiplication sketches, which is new in the context of I/O-efficient algorithms, and a new matrix product size estimation technique that avoids the ``no cancellation assumption.

Recommendations

• The I/O Complexity of Sparse Matrix Dense Matrix Multiplication
• Fast Output-Sensitive Matrix Multiplication
• Optimal sparse matrix dense vector multiplication in the I/O-model
• Cache oblivious sparse matrix multiplication
• Algorithms – ESA 2004

Cited in

(14)

• The I/O complexity of Strassen's matrix multiplication with recomputation
• A note on the multiplication of sparse matrices
• Fast sparse matrix multiplication
• Fast Output-Sensitive Matrix Multiplication
• The I/O Complexity of Sparse Matrix Dense Matrix Multiplication
• Evaluating non-square sparse bilinear forms on multiple vector pairs in the I/O-model
• On optimizing multiplications of sparse matrices
• Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
• The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
• Algorithms – ESA 2004
• scientific article; zbMATH DE number 7650266 (Why is no real title available?)
• Turing machines with two-level memory: a deep look into the input/output complexity
• Optimal sparse matrix dense vector multiplication in the I/O-model
• Turing machines with two-level memory: new computational models for analyzing the input/output complexity

This page was built for publication: The input/output complexity of sparse matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921459)