Graph partitioning and hypergraph partitioning have been used extensively in applications ranging from very-large-scale integration (VLSI) to portioning of data in parallel and distributed applications. Hypergraph and graph partitioning problems are nondeterministic polynomial-time (NP)-complete. Hence, many heuristics as well as effective software packages have been developed in the past. These software packages include Mondriaan, PaToH, and Zoltan. The package Zoltan is used with a cluster of Linux workstations. A strategy that is often used in these packages for constructing hypergraph partitioning is to do a coarse-grained partitioning, followed by a fine-grained partitioning. Coarse-grained partitioning focuses on the merging of the columns based on a matching of the columns, and the matching is based on the inner products of the columns. Fine-grained partitioning uses the well-known heuristic of Kernighan and Lin with an improvement suggested by Fiduccia and Mattheyses.

This paper presents an algorithm that incrementally constructs the inner products of columns and generates the matchings. This overcomes one of the disadvantages of constructing an A^T A matrix, which could be dense (even if the original matrix A is sparse). The two steps involved in this process are a graph-matching function and a neighborhood function. The authors propose and use many different heuristics for computing both of these functions. For matching the heuristics used are the path-growing algorithm (PGA), the global paths algorithm (GPA), and the random order matching augmentation algorithm. For a neighborhood function, they propose and use heuristics such as FindHeavyUnmatchedNeighbors (FHUN), the stairway heuristic implementation of the FHUN, and StairwayM (a combination of stairway and Mondriaan).

This well-written paper tests these heuristics on large matrix data (with rows and columns varying from thousands to millions). The authors explain how the matching quality improves (from 95.3 percent to 97.4 percent), as well as the speed-up (to a factor of 19.6).