AN IMPROVED SPECTRAL GRAPH PARTITIONING ALGORITHM FOR MAPPING PARALLEL COMPUTATIONS

Efficient use of a distributed memory parallel computer requires that the computational load be balanced across processors in a way that min imizes 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 spect ral graph bisection involves a novel use of multiple eigenvectors to a llow for division of a computation into four or eight parts at each st age 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 re sults confirm that the new method provides better decompositions arriv ed at more economically and robustly than with previous spectral metho ds. This algorithm allows for arbitrary nonnegative weights on both ve rtices and edges to model inhomogeneous computation and communication. A new spectral lower bound for graph bisection is also presented.