Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

Abstract

Recently, a number of researchers have investigated a class of graph partitioning algorithms that reduce the size of the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partition for the original graph [4, 26]. From the early work it was clear that multilevel techniques held great promise; however, it was not known if they can be made to consistently produce high quality partitions for graphs arising in a wide range of application domains. We investigate the effectiveness of many different choices for all three phases: coarsening, partition of the coarsest graph, and refinement. In particular, we present a new coarsening heuristic (called heavyedge

heuristic) for which the size of the partition of the coarse graph is within a small factor of the size of the final partition obtained after multilevel refinement. We also present a much faster variation of the Kernighan-Lin

algorithm for refining during uncoarsening. We test our scheme on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation. Our experiments show that our scheme produces partitions that are consistently better than those produced by spectral partitioning schemes in substantially smaller time. Also, when our scheme is used to compute fill reducing orderings for sparse matrices, it produces orderings that have substantially smaller fill than the widely used multiple minimum degree algorithm.

Keywords: Graph Partitioning, Multilevel Partitioning Methods, Spectral Partitioning Methods, Fill Reducing Ordering, Kernighan-Lin Heuristic, Parallel Sparse Matrix Algorithms.

1 Introduction

Graph partitioning is an important problem that has extensive applications in many areas, including scientific computing,

VLSI design, and task scheduling. The problem is to partition the vertices of a graph in p roughly equal parts,

such that the number of edges connecting vertices in different parts is minimized. For example, the solution of a sparse

system of linear equations Ax D b via iterative methods on a parallel computer gives rise to a graph partitioning problem.

A key step in each iteration of these methods is the multiplication of a sparse matrix and a (dense) vector. A good

partition of the graph corresponding to matrix A can significantly reduce the amount of communication in parallel

sparse matrix-vector multiplication [32]. If parallel direct methods are used to solve a sparse system of equations, then

a graph partitioning algorithm can be used to compute a fill reducing ordering that lead to high degree of concurrency

in the factorization phase [32, 12]. The multiple minimum degree ordering used almost exclusively in serial direct

methods is not suitable for parallel direct methods, as it provides very little concurrency in the parallel factorization

phase.

The graph partitioning problem is NP-complete. However, many algorithms have been developed that find a reasonably

good partition. Spectral partitioning methods are known to produce good partitions for a wide class of problems,

and they are used quite extensively [47, 46, 24]. However, these methods are very expensive since they require the

computation of the eigenvector corresponding to the second smallest eigenvalue (Fiedler vector). Execution time of

Abstract

Recently, a number of researchers have investigated a class of graph partitioning algorithms that reduce the size of the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partition for the original graph [4, 26]. From the early work it was clear that multilevel techniques held great promise; however, it was not known if they can be made to consistently produce high quality partitions for graphs arising in a wide range of application domains. We investigate the effectiveness of many different choices for all three phases: coarsening, partition of the coarsest graph, and refinement. In particular, we present a new coarsening heuristic (called heavyedge

heuristic) for which the size of the partition of the coarse graph is within a small factor of the size of the final partition obtained after multilevel refinement. We also present a much faster variation of the Kernighan-Lin

algorithm for refining during uncoarsening. We test our scheme on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation. Our experiments show that our scheme produces partitions that are consistently better than those produced by spectral partitioning schemes in substantially smaller time. Also, when our scheme is used to compute fill reducing orderings for sparse matrices, it produces orderings that have substantially smaller fill than the widely used multiple minimum degree algorithm.

Keywords: Graph Partitioning, Multilevel Partitioning Methods, Spectral Partitioning Methods, Fill Reducing Ordering, Kernighan-Lin Heuristic, Parallel Sparse Matrix Algorithms.

1 Introduction

Graph partitioning is an important problem that has extensive applications in many areas, including scientific computing,

VLSI design, and task scheduling. The problem is to partition the vertices of a graph in p roughly equal parts,

such that the number of edges connecting vertices in different parts is minimized. For example, the solution of a sparse

system of linear equations Ax D b via iterative methods on a parallel computer gives rise to a graph partitioning problem.

A key step in each iteration of these methods is the multiplication of a sparse matrix and a (dense) vector. A good

partition of the graph corresponding to matrix A can significantly reduce the amount of communication in parallel

sparse matrix-vector multiplication [32]. If parallel direct methods are used to solve a sparse system of equations, then

a graph partitioning algorithm can be used to compute a fill reducing ordering that lead to high degree of concurrency

in the factorization phase [32, 12]. The multiple minimum degree ordering used almost exclusively in serial direct

methods is not suitable for parallel direct methods, as it provides very little concurrency in the parallel factorization

phase.

The graph partitioning problem is NP-complete. However, many algorithms have been developed that find a reasonably

good partition. Spectral partitioning methods are known to produce good partitions for a wide class of problems,

and they are used quite extensively [47, 46, 24]. However, these methods are very expensive since they require the

computation of the eigenvector corresponding to the second smallest eigenvalue (Fiedler vector). Execution time of

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил