Practical applications of the graph partitioning problem usually do not require the absolute minimum number of edges cut but are satisfied with a nearly optimal solution. However, in most cases this approximate solution should be found fast. Hence there is a need for fast heuristics.
There are many heuristics for graph partitioning that employ quite different approaches, promising different combinations of speed and quality. This book evaluates these algorithms and examines the influence of the algorithm, the implementation and even randon number generator on the speed and quality of partitions.
To achieve high performance on parallel computers when working with sparse matrices, it is essential that the data are distributed to the processors in a reasonable way. We demonstrate that using a good quality graph partitioning method can lead to a doubling of performance compared to simple distribution.
In a number of scientific and engineering applications the amount of data will change dynamically during the course of the calculation. For example, an adaptive Finite Element program may refine parts of its mesh. To maintain high performance on parallel computers one then needs to periodically redistribute the data in order to maintain both, a good balance and a low interprocessor communication. The redistribution should require as little communication as possible. These somewhat contradictory tasks can be formulated as a dynamic graph partitioning problem.
Different approaches to dynamic graph partitioning emphasize either the reduction of data transfered during the redistribution phase or the quality of the resulting new partition. They concentrate on optimizing the one measure and treat the respective other measure only as a secondary goal. We tested the different approaches in many different scenarios and evaluated their performance.