Hendrickson, Bruce; Leland, Robert An improved spectral graph partitioning algorithm for mapping parallel computations. (English) Zbl 0816.68093 SIAM J. Sci. Comput. 16, No. 2, 452-469 (1995). Summary: 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 in 1 ReviewCited in 97 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 65Y05 Parallel numerical computation Keywords:load balancing; distributed memory parallel computer PDFBibTeX XMLCite \textit{B. Hendrickson} and \textit{R. Leland}, SIAM J. Sci. Comput. 16, No. 2, 452--469 (1995; Zbl 0816.68093) Full Text: DOI Link