On Two-Dimensional Sparse Matrix Partitioning: Models, Methods, and a Recipe

By Ümit V. Çatalyürek, Cevdet Aykanat, Bora Uçar. 2010

130 citations recorded by the source corpus.

We consider two-dimensional partitioning of general sparse matrices for parallel sparse matrix-vector multiply operation. We present three hypergraph-partitioning-based methods, each having unique advantages. The first one treats the nonzeros of the matrix individually and hence produces fine-grain partitions. The other two produce coarser partitions, where one of them imposes a limit on the number of messages sent and received by a single processor, and the other trades that limit for a lower communication volume. We also present a thorough experimental evaluation of the proposed two-dimensional partitioning methods together with the hypergraph-based one-dimensional partitioning methods, using an extensive set of public domain matrices. Furthermore, for the users of these partitioning methods, we present a partitioning recipe that chooses one of the partitioning methods according to some matrix characteristics.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. M. Franklin
2. Reynold Xin
3. Ion Stoica
4. Ankur Dave
5. Joseph E. Gonzalez
6. Daniel Crankshaw

In Computer Networks and Communications

1. Ion Stoica
2. Joseph E. Gonzalez
3. M. Franklin
4. Reynold Xin
5. Haibo Chen
6. Ankur Dave
7. Binyu Zang
8. Mosharaf Chowdhury

In Electrical and Electronic Engineering

1. M. Franklin
2. Reynold Xin
3. Ion Stoica
4. Joseph E. Gonzalez

Citations in the corpus

• GraphX: a resilient distributed graph system on Spark (2013, methodology): “Finally, we extract and print the maximum PageRank value from the resulting Graph.”
• PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs (2019, methodology): “It follows the classic 2D partitioning [9, 89] to restrict the locations of edges within a small subset of machines to approximate an optimal partitioning.”
• GraphX: Graph Processing in a Distributed Dataflow Framework (2014, methodology): “We plot the mean and standard deviation for multiple trials of each experiment.”