Computer Science – Numerical Analysis
Scientific paper
2010-03-18
Computer Science
Numerical Analysis
Preprint of a paper submitted to ACM TOMS on March 15 2010
Scientific paper
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.
No associations
LandOfFree
A Highly Efficient Parallel Algorithm for Computing the Fiedler Vector does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Highly Efficient Parallel Algorithm for Computing the Fiedler Vector, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Highly Efficient Parallel Algorithm for Computing the Fiedler Vector will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-353733