Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model
Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model
复制标题
拥塞团模型中的稀疏矩阵乘法和三角形列表
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Elia Turner
中科院分区：
文献类型：
--
作者：
K. Censor;Dean Leitersdorf;Elia Turner
我们将两个$n乘以n个$矩阵$S，T$在拥塞团模型的半环上，其中$n$完全连接节点在$O(nz(S)^{1/3} nz(T)^{1/3}/n + 1)$轮通信中使用$O(log n)$位消息同步通信，其中$nz(A)$表示矩阵$A$中的非零元素的数量。通过利用输入矩阵的稀疏性，与一般算法相比，我们的算法大大减少了通信[centor - hillel等人，PODC 2015]，改进了具有$o(n^2)$非零元素的矩阵的最新技术。当只有一个矩阵是稀疏的时候，我们的算法也表现出了超越先前解的额外强度。这允许有效地将稀疏矩阵提高到大于2的幂。作为应用，我们加快了稀疏图的4周期计数和APSP。
We multiply two $n imes n$ matrices $S,T$ over semirings in the Congested Clique model, where $n$ fully connected nodes communicate synchronously using $O(log n)$-bit messages, within $O(nz(S)^{1/3} nz(T)^{1/3}/n + 1)$ rounds of communication, where $nz(A)$ denotes the number of non-zero elements in a matrix $A$. By leveraging the sparsity of the input matrices, our algorithm greatly reduces communication compared with general algorithms [Censor-Hillel et al., PODC 2015], improving upon the state-of-the-art for matrices with $o(n^2)$ non-zero elements. Our algorithm exhibits the additional strength of surpassing previous solutions also when only one matrix is sparse. This allows efficiently raising a sparse matrix to a power greater than 2. As applications, we speed up 4-cycle counting and APSP in sparse graphs.
Our algorithmic contribution is a new emph{deterministic} method of restructuring the input matrices in a sparsity-aware manner, which assigns each node with element-wise multiplication tasks that are not necessarily consecutive but are balanced, yielding communication-efficient multiplication.
Moreover, this new deterministic method for restructuring matrices may be used to restructure the adjacency matrix of input graphs, enabling faster solutions for graph related problems. As an example, we present a new deterministic algorithm which solves the triangle listing problem in $O(m/n^{5/3} + 1)$ rounds, a complexity that was previously obtained by a emph{randomized} algorithm [Pandurangan et al., SPAA 2018] and matches the lower bound of $ ilde{Omega}(n^{1/3})$ when $m=n^2$ of [Izumi and Le Gall, PODC 2017, Pandurangan et al., SPAA 2018].
Our triangle listing algorithm implies triangle counting with the same complexity of $O(m/n^{5/3} + 1)$ rounds, which is a emph{cubic} improvement over the previous $O(m^2/n^3)$-round algorithm [Dolev et al., DISC 2012].
DOI：
10.1145/3210377.3210409
发表时间：
2016-02
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
通讯作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato