An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
Bruce Hendrickson, Robert W. Leland · SIAM Journal on Scientific Computing · 1995
Efficient use of a distributed memory parallel computer requires that the computational load be balanced across processors in a way that minimizes interprocessor communication. A new domain mapping algorithm is presented that extends recent work in which ideas from spectral graph theory have been applied to this problem. The generalization of spectral graph bisection involves a novel use of multiple eigenvectors to allow for division of a computation into four or eight parts at each stage of a recursive decomposition. The resulting method is suitable for scientific computations like irregular finite elements or differences performed on hypercube or mesh architecture machines. Experimental results confirm that the new method provides better decompositions arrived at more economically and robustly than with previous spectral methods. This algorithm allows for arbitrary nonnegative weights on both vertices and edges to model inhomogeneous computation and communication. A new spectral lower bound for graph bisection is also presented.
Cited by 480 works. doi:10.1137/0916028
Authors
References
- An Efficient Heuristic Procedure for Partitioning Graphs
- Some simplified NP-complete graph problems
- Algebraic connectivity of graphs
- Partitioning Sparse Matrices with Eigenvectors of Graphs
- The Symmetric Eigenvalue Problem.
- Lower Bounds for the Partitioning of Graphs
- A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory
- Numerical Methods for Unconstrained Optimization and Nonlinear Equations.
- A unified geometric approach to graph separators
- An algorithm for quadrisection and its application to standard cell placement