An improved spectral load balancing method

Abstract

We describe an algorithm for the static load balancing of scientific computations that generalizes and improves upon spectral bisection. Through a novel use of multiple eigenvectors, our new spectral algorithm can divide a computation into 4 or 8 pieces at once. This leads to balanced partitions that have lower communication overhead and are less expensive to compute than those of spectral bisection. In addition, our approach automatically works to minimize message contention on a hypercube or mesh architecture.