TITLE: A Graph Based Davidson Algorithm for the Graph Partitioning Problem
Authors: M. Holzrichter and S. Oliveira.

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.

*This paper has appeared in

International Journal of Foundations of Computer Science 10(2):225-247, 
June 1999. (Special Issue on Graph Algorithms and Applications).

*A brief description of the algorithm is also in:

Lecture Notes in Computer Science no. 1586, IPPP--SPDP workshops, Parallel
and distributed Processing Proceedings, pp. 978--985,  Eds. J. Rolim et al,  
Springer, April 1999.