TRACEMIN-Fiedler: a parallel algorithm for computing the Fiedler vector. 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. 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).
Keywords for this software
References in zbMATH (referenced in 5 articles , 1 standard article )
Showing results 1 to 5 of 5.
- Zhu, Yao; Sameh, Ahmed H.: $\textPSPIKE+$: A family of parallel hybrid sparse linear system solvers (2017)
- Wu, Jian-ping; Song, Jun-qiang; Zhang, Wei-min: An efficient and accurate method to compute the Fiedler vector based on Householder deflation and inverse power iteration (2014)
- Manguoglu, Murat; Cox, Eric; Saied, Faisal; Sameh, Ahmed: TRACEMIN-Fiedler: a parallel algorithm for computing the Fiedler vector (2011)
- Taylor, Alan; Vass, J.Keith; Higham, Desmond J.: Discovering bipartite substructure in directed networks (2011)
- Manguoglu, Murat; Koyutürk, Mehmet; Sameh, Ahmed H.; Grama, Ananth: Weighted matrix ordering and parallel banded preconditioners for iterative linear system solvers (2010)