### Static and Dynamic Graph Partitioning. A comparative study of existing algorithms

### Ulrich Elsner

#####
ISBN 978-3-89722-923-5

212 pages, year of publication: 2002

price: 40.50 €

Many interesting tasks occurring in real life can be formulated as a graph
partitioning problem. Examples include the distribution of unstructured
data to parallel processors, the optimal design of electronic circuits and
applications in geographic information services. In all these cases, the
number of vertices can reach into millions. Solving a problem of that
size with an algorithm with exponential running time is, for all practical
purposes, not viable. But graph partitioning is, even in its simplest
form, NP-complete. This fact strongly implies that any algorithm that can
solve the problem has a worst-case running time that is exponential in the
number of vertices. Thus there nearly certainly is no algorithm that is
always fundamentally faster than trying all possible combinations.

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.