Name
Abstract | ||
|---|---|---|
We show how to multiply two n×n matrices S and T over semirings in the Congested Clique model, where n nodes communicate in a fully connected synchronous network using O(logn)-bit messages, within O(nz(S)1/3nz(T)1/3/n+1) rounds of communication, where nz(S) and nz(T) denote the number of non-zero elements in S and T, respectively. By leveraging the sparsity of the input matrices, our algorithm greatly reduces communication costs compared with general multiplication algorithms [Censor-Hillel et al. (2015) [9]], and thus improves upon the state-of-the-art for matrices with o(n2) non-zero elements. Moreover, our algorithm exhibits the additional strength of surpassing previous solutions also in the case where only one of the two matrices is such. Particularly, this allows to efficiently raise a sparse matrix to a power greater than 2. As applications, we show how to speed up the computation on non-dense graphs of 4-cycle counting and all-pairs-shortest-paths. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.tcs.2019.11.006 | Theoretical Computer Science |
Keywords | Field | DocType |
Distributed algorithms,Congested clique,Matrix multiplication,Triangle listing | Adjacency matrix,Discrete mathematics,Randomized algorithm,Combinatorics,Multiplication algorithm,Clique,Matrix (mathematics),Multiplication,Deterministic algorithm,Sparse matrix,Mathematics | Journal |
Volume | ISSN | Citations |
809 | 0304-3975 | 1 |
PageRank | References | Authors |
0.35 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Keren Censor-Hillel | 1 | 235 | 31.73 |
| Dean Leitersdorf | 2 | 9 | 2.17 |
| Elia Turner | 3 | 1 | 0.35 |