Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model

Authors Keren Censor-Hillel, Dean Leitersdorf, Elia Turner



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.4.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Author Details

Keren Censor-Hillel
  • Department of Computer Science, Technion, Israel
Dean Leitersdorf
  • Department of Computer Science, Technion, Israel
Elia Turner
  • Department of Computer Science, Technion, Israel

Cite AsGet BibTex

Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner. Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.OPODIS.2018.4

Abstract

We show how to multiply two n x n matrices S and T over semirings in the Congested Clique model, where n nodes communicate in a fully connected synchronous network using O(log{n})-bit messages, within O(nz(S)^{1/3} nz(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., PODC 2015], and thus improves upon the state-of-the-art for matrices with o(n^2) 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. Our algorithmic contribution is a new 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 guarantee a balanced element distribution, providing for communication-efficient multiplication. Moreover, this new deterministic method for restructuring matrices may be used to restructure the adjacency matrix of input graphs, enabling faster deterministic solutions for graph related problems. As an example, we present a new sparsity aware, deterministic algorithm which solves the triangle listing problem in O(m/n^{5/3} + 1) rounds, a complexity that was previously obtained by a randomized algorithm [Pandurangan et al., SPAA 2018], and that matches the known lower bound of Omega~(n^{1/3}) when m=n^2 of [Izumi and Le Gall, PODC 2017, Pandurangan et al., SPAA 2018]. Naturally, our triangle listing algorithm also implies triangle counting within the same complexity of O(m/n^{5/3} + 1) rounds, which is (possibly more than) a cubic improvement over the previously known deterministic O(m^2/n^3)-round algorithm [Dolev et al., DISC 2012].

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Distributed algorithms
Keywords
  • congested clique
  • matrix multiplication
  • triangle listing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Rasmus Resen Amossen and Rasmus Pagh. Faster join-projects and sparse matrix multiplications. In The 12th International Conference on Database Theory (ICDT), pages 121-126, 2009. Google Scholar
  2. Ariful Azad, Grey Ballard, Aydin Buluç, James Demmel, Laura Grigori, Oded Schwartz, Sivan Toledo, and Samuel Williams. Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication. SIAM J. Scientific Computing, 38(6), 2016. Google Scholar
  3. Grey Ballard, Aydin Buluç, James Demmel, Laura Grigori, Benjamin Lipshitz, Oded Schwartz, and Sivan Toledo. Communication optimal parallel multiplication of sparse random matrices. In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, (SPAA), pages 222-231, 2013. Google Scholar
  4. Grey Ballard, Alex Druinsky, Nicholas Knight, and Oded Schwartz. Hypergraph Partitioning for Sparse Matrix-Matrix Multiplication. TOPC, 3(3):18:1-18:34, 2016. Google Scholar
  5. Aydin Buluç and John R. Gilbert. The Combinatorial BLAS: design, implementation, and applications. IJHPCA, 25(4):496-509, 2011. Google Scholar
  6. Aydin Buluç and John R. Gilbert. Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments. SIAM J. Scientific Computing, 34(4), 2012. Google Scholar
  7. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic Methods in the Congested Clique. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 143-152, 2015. Google Scholar
  8. Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner. Sparse Matrix Multiplication in the Congested Clique model, 2018. URL: http://arxiv.org/abs/arXiv:1802.04789.
  9. Don Coppersmith and Shmuel Winograd. Matrix Multiplication via Arithmetic Progressions. J. Symb. Comput., 9(3):251-280, 1990. Google Scholar
  10. Danny Dolev, Christoph Lenzen, and Shir Peled. "Tri, Tri Again": Finding Triangles and Small Subgraphs in a Distributed Setting - (Extended Abstract). In Proceedings of the 26th International Symposium on Distributed Computing (DISC), pages 195-209, 2012. Google Scholar
  11. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 367-376, 2014. Google Scholar
  12. François Le Gall. Faster Algorithms for Rectangular Matrix Multiplication. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 514-523, 2012. Google Scholar
  13. François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 296-303, 2014. Google Scholar
  14. François Le Gall. Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems. In Proceedings of the 30th International Symposium on Distributed Computing (DISC), pages 57-70, 2016. Google Scholar
  15. Francois Le Gall and Florent Urrutia. Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1029-1046, 2018. Google Scholar
  16. Taisuke Izumi and François Le Gall. Triangle Finding and Listing in CONGEST Networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 381-389, 2017. Google Scholar
  17. Haim Kaplan, Micha Sharir, and Elad Verbin. Colored intersection searching via sparse rectangular matrix multiplication. In Proceedings of the 22nd ACM Symposium on Computational Geometry (SocG), pages 52-60, 2006. Google Scholar
  18. Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. Distributed Computation of Large-scale Graph Problems. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 391-410, 2015. Google Scholar
  19. Penporn Koanantakool, Ariful Azad, Aydin Buluç, Dmitriy Morozov, Sang-Yun Oh, Leonid Oliker, and Katherine A. Yelick. Communication-Avoiding Parallel Sparse-Dense Matrix-Matrix Multiplication. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 842-853, 2016. Google Scholar
  20. Alfio Lazzaro, Joost VandeVondele, Jürg Hutter, and Ole Schütt. Increasing the Efficiency of Sparse Matrix-Matrix Multiplication with a 2.5D Algorithm and One-Sided MPI. CoRR, abs/1705.10218, 2017. Google Scholar
  21. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In The ACM Symposium on Principles of Distributed Computing (PODC), pages 42-50, 2013. Google Scholar
  22. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In The 46th ACM Symposium on Theory of Computing (STOC), pages 565-573, 2014. Google Scholar
  23. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. On the Distributed Complexity of Large-Scale Graph Computations. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 405-414, 2018. Google Scholar
  24. Edgar Solomonik, Maciej Besta, Flavio Vella, and Torsten Hoefler. Scaling betweenness centrality using communication-efficient sparse matrix multiplication. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 47:1-47:14, 2017. Google Scholar
  25. Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13(4):354-356, 1969. Google Scholar
  26. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In The 44th ACM Symposium on Theory of Computing (STOC), pages 887-898, 2012. Google Scholar
  27. Raphael Yuster and Uri Zwick. Fast sparse matrix multiplication. ACM Trans. Algorithms, 1(1):2-13, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail