An efficient and accurate method to compute the Fiedler vector based on Householder deflation and inverse power iteration

• Autores: Wu Jian-ping, Song Jun-qiang, Zhang Wei-min
• Localización: Journal of computational and applied mathematics, ISSN 0377-0427, Vol. 269, Nº 1, 2014, págs. 101-108
• Idioma: inglés
• DOI: 10.1016/j.cam.2014.03.018
• Texto completo no disponible (Saber más ...)
• Resumen

  • The Fiedler vector of a graph plays a vital role in many applications. But it is usually very expensive in that it involves the solution of an eigenvalue problem. In this paper, we introduce the inverse power method incorporated with the Householder deflation to compute the Fiedler Vector. In the inverse power iterations, the coefficient matrix is formed implicitly, to take advantage of the sparsity. The linear systems encountered at each iteration must be symmetric positive definite, thus the conjugate gradient method is used. In addition, preconditioning techniques are introduced to reduce the computation cost. Any kind of preconditioning techniques with dropping can be used. For the graphs related to some of the sparse matrices downloaded from the UF Sparse Matrix Collection, the experiments are compared to the known novel schemes. The results show that the provided method is more accurate. While it is slower than MC73 sequentially, it has good parallel efficiency compared with TraceMin. In addition, it is insensitive to the selection of parameters, which is superior to the other two methods.