Efficient Matching for Column Intersection Graphs

摘要

To improve the quality and efficiency of hypergraph-based matrix partitioners, we investigate high-qualityrnmatchings in column intersection graphs of large sparse binary matrices.We show that such algorithms haverna natural decomposition in an integer-weighted graph-matching function and a neighbor-finding functionrnand study the performance of 16 combinations of these functions. We improve upon the original matchingrnalgorithm of the Mondriaan matrix partitioner: by using PGA’, we improve the averagematching quality fromrn95.3% to 97.4% of the optimum value; by using our new neighbor-finding heuristic, we obtain comparablernquality and speedups of up to a factor of 19.6.