Graph Partitioning

A direct outcome of our graph partitioning research is the development of the METIS family of multilevel partitioning programs and libraries. This includes computationally efficient and highly effective tools for partitioning very large graphs on serial and parallel computers as well as tools for partitioning hypergraphs, especially those corresponding to netlists of VLSI circuits.

In addition, some ideas inspired from the multilevel optimization algorithms developed for graph partitioning found their way on two other research projects. The first is the work on MGridGen, a tool to generate a sequence of coarse grids for geometric multigrid-based precoditioners. The second is the work on CLUTO, our data clustering tool, which contains effective graph-partitioning based clustering algorithms. In fact, the quality of the partitionings produced by CLUTO are in general better than those produced by the serial graph partitioning algorithm in METIS.

All of these tools are available for download from our Software page.