HARP - A DYNAMIC SPECTRAL PARTITIONER

Partitioning unstructured graphs is central to the parallel solution o f computational science and engineering problems. Spectral partitioner s, such as recursive spectral bisection (RSB), have proven effective i n generating high-quality partitions of realistically sized meshes. Th e major problem which hindered their widespread use was their long exe cution 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 framew ork JOVE which dynamically balances the computational loads of distrib uted-memory machines with a global view. The underlying principle of H ARP 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 oth er spectral partitioners, while maintaining the solution quality of th e proven RSB method. These results indicate that graph partitioning ca n now be truly embedded in dynamically changing real-world application s. (C) 1998 Academic Press.