Sparse Matrix Multiplication in the Low-Bandwidth Model
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
10
Series
SPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 435-444
Abstract
We study matrix multiplication in the low-bandwidth model: There are n computers, and we need to compute the product of two n × n matrices. Initially computer i knows row i of each input matrix. In one communication round each computer can send and receive one O(logn)-bit message. Eventually computer i has to output row i of the product matrix. We seek to understand the complexity of this problem in the uniformly sparse case: each row and column of each input matrix has at most d non-zeros and in the product matrix we only need to know the values of at most d elements in each row or column. This is exactly the setting that we have, e.g., when we apply matrix multiplication for triangle detection in graphs of maximum degree d. We focus on the supported setting: the structure of the matrices is known in advance; only the numerical values of nonzero elements are unknown. There is a trivial algorithm that solves the problem in O(d2) rounds, but for a large d, better algorithms are known to exist; in the moderately dense regime the problem can be solved inO(dn1/3) communication rounds, and for very large d, the dominant solution is the fast matrix multiplication algorithm using O(n1.158) communication rounds (for matrix multiplication over fields and rings supporting fast matrix multiplication). In this work we show that it is possible to overcome quadratic barrier for all values of d: we present an algorithm that solves the problem in O(d1.907) rounds for fields and rings supporting fast matrix multiplication and O(d1.927) rounds for semirings, independent of n.Description
Funding Information: We are grateful to the anonymous reviewers for their helpful feedback on the previous versions of this work. This work was supported in part by the Academy of Finland, Grant 321901. Publisher Copyright: © 2022 ACM.
Other note
Citation
Gupta, C, Hirvonen, J, Korhonen, J H, Studený, J & Suomela, J 2022, Sparse Matrix Multiplication in the Low-Bandwidth Model. in SPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, pp. 435-444, Annual ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, Pennsylvania, United States, 11/07/2022. https://doi.org/10.1145/3490148.3538575