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

• We provide a method to compute the Fiedler vector of sparse graphs.
• We introduce preconditioning techniques to accelerate the convergence rate.
• Sparsity is considered in the whole computation process.
• The process is done in parallel with hybrid programming of MPI and OpenMP.
• The method is accurate, robust and efficient compared to novel schemes.

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.