Fast spectral methods for ratio cut partitioning and clustering

Abstract

The ratio cut partitioning objective function successfully embodies both the traditional min-cut and equipartition goals of partitioning. Fiduccia-Mattheyses style ratio cut heuristics have achieved cost savings averaging over 39% for circuit partitioning and over 50% for hardware simulation applications. The authors show a theoretical correspondence between the optimal ratio cut partition cost and the second smallest eigenvalue of a particular netlist-derived matrix, and present fast Lanczos-based methods for computing heuristic ratio cuts from the eigenvector of this second eigenvalue. Results are better than those of previous methods, e.g. by an average of 17% for the Primary MCNC benchmarks. An efficient clustering method, also based on the second eigenvector, is very successful on the 'difficult' input classes in the CAD (computer-aided design) literature. Extensions and directions for future work are also considered.