HARP: A Dynamic Spectral Partitioner

Partitioning unstructured graphs is central to the parallel solution of computational science and engineering problems. Spectral partitioners, such as recursive spectral bisection (RSB), have proven effective in generating high-quality partitions of realistically sized meshes. The major problem which hindered their widespread use was their long execution times. This paper presents a new inertial spectral partitioner called HARP. The main objective of the proposed approach is to quickly partition the meshes at runtime for the dynamic load balancing framework JOVE which dynamically balances the computational loads of distributed-memory machines with a global view. The underlying principle of HARP is to find the eigenvectors of the unpartitioned vertices and then project them onto the eigenvectors of the original mesh. Results for various meshes ranging in size from 1000 to 100,000 vertices indicate that HARP can indeed partition meshes rapidly at runtime. Experimental results show that our largest mesh can be partitioned sequentially in only a few seconds on an SP-2, which is several times faster than other spectral partitioners, while maintaining the solution quality of the proven RSB method. These results indicate that graph partitioning can now be truly embedded in dynamically changing real-world applications.