Fast spectral methods for ratio cut partitioning and clustering

摘要: Partitioning of circuit netlists in VLSI design is considered. It shown that the second smallest eigenvalue a matrix derived from netlist gives provably good approximation optimal ratio cut partition cost. also demonstrated fast Lanczos-type methods for sparse symmetric problem are robust basis computing heuristic cuts based on eigenvector this eigenvalue. Effective clustering an immediate by-product computation and very successful difficult input classes proposed CAD literature. The intersection graph representation considered, as partitioning, spectral partitioning proposed. heuristics were tested industry benchmark suites, results terms both solution quality runtime. Several types algorithmic speedups directions future work discussed. >