Algorithms that find a good partition of highly unstructured graphs are critical in developing efficient algorithms for problems in many application areas such as task graph scheduling, parallel scientific computing, and storage of large databases on parallel disk systems. The objective is to partition the graph in k roughly parts such that the number of edges crossing them is minimized. In adaptive computations, dynamic adjustments to the mesh require repartitioning of the mesh to improve load balance. This re-partitioning also results in movement of data structures associated with graph vertices. Hence, a good re-partitioning algorithm should also minimize the movement of vertices (in addition to balancing the load and minimizing the cut of the resulting new partition).

This talk will present results of our work on serial and parallel multi-level algorithms for finding partitionings of large graphs in both static and adaptive settings. The multi-level schemes coarsen a large graph into a very small graph by repeatedly merging pairs of connected nodes, find a partition of the small graph, and then perform localized refinements of the partition while uncoarsening it. This multi-level paradigm is very fast and robust, and appears quite promising for solving other NP hard discrete optimization problems.

Joint work with George Karypis.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing