Spectral graph partitioning has been shown to provide provably bounded bisections for planar graphs and well-formed meshes. However their reliance on the eigenvectors of large sparse matrices has limited their performance, and therefore their applicability, in practice. Common approaches to compute eigenvectors of graph Laplacians rely upon generic Lanczos methods for sparse symmetric matrices. As such these methods require a large number of iterations to achieve sufficient accuracy in the Fiedler vector for the spectral methods to be effective. We show that by coupling bandwidth rich architectures, such as GPUs, with advanced eigensolvers that the performance of spectral methods can be improved substantially compared to previous implementations. Our approach focuses on optimized SpMV operations targeting graph Laplacians.
In addition to creating an initial partition many schemes seek to improve the quality through iterative updating methods, such as Kernighan-Lin. Though effective these methods are not readily amenable to the fine-grained parallelism exposed by GPUs because of interdependence between consecutive updates. To address quality improvement we utilize a flow based approach to augment the computed partitions. By relying on efficient breadth-first search this approach effectively improves the partition quality while exposing abundant fine-grained parallelism.