Brief Announcement: Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity
Chetan Gupta, Janne H. Korhonen, Jan Studený, Jukka Suomela, Hossein Vahidi · 2024
In prior work, Gupta et al. (SPAA 2022) presented a distributed algorithm for multiplying sparse n x n matrices, using n computers. They assumed that the input matrices are uniformly sparse---there are at most d non-zeros in each row and column---and the task is to compute a uniformly sparse part of the product matrix. Initially each computer knows one row of each input matrix, and eventually each computer needs to know one row of the product matrix. In each communication round each computer can send and receive one O(łog n)-bit message. Their algorithm solves this task in O(d^1.907 ) rounds, while the trivial bound is O(d^2).