A Highly Efficient Parallel Algorithm for Computing the Fiedler Vector. (arXiv:1003.3689v1 [cs.NA])

A Highly Efficient Parallel Algorithm for Computing the Fiedler Vector. (arXiv:1003.3689v1 [cs.NA]): "

The eigenvector corresponding to the second smallest eigenvalue of the
Laplacian of a graph, known as the Fiedler vector, has a number of applications
in areas that include matrix reordering, graph partitioning, protein analysis,
data mining, machine learning, and web search. The computation of the Fiedler
vector has been regarded as an expensive process as it involves solving a large
eigenvalue problem. We present a novel and efficient parallel algorithm for
computing the Fiedler vector of large graphs based on the Trace Minimization
algorithm (Sameh, et.al). We compare the parallel performance of our method
with a multilevel scheme, designed specifically for computing the Fiedler
vector, which is implemented in routine MC73\_Fiedler of the Harwell Subroutine
Library (HSL). In addition, we compare the quality of the Fiedler vector for
the application of weighted matrix reordering and provide a metric for
measuring the quality of reordering.

"