A Graph Based Davidson Algorithm for the Graph Partitioning Problem

M. Holzrichter and S. Oliveira
Department of Computer Science
University of Iowa
Ames, IA


The problem of partitioning a graph such that the number of edges incident to vertices in different partitions is minimized, arises in many contexts. Some examples include its recursive application for minimizing fill-in in matrix factorizations and load-balancing for parallel algorithms. Spectral graph partitioning algorithms partition a graph using the eigenvector associated with the second smallest eigenvalue (Fiedler value) of a matrix called the {\em graph Laplacian}. The focus of this paper is the use graph theory to compute this eigenvector more quickly.

Specifically we design a multigrid preconditioner coupled with the Davidson algorithm which works well for finding the Fiedler vector. This multigrid preconditioner uses ideas of graph coarsening, such as heavy edge matching, in its development. We anticipate that similar ideas can be used when developing Multigrid Algorithms for other unstructured problems.

Contributed August 6, 1999.