Compute smallest eigenvectors of a matrix

Question

It appears that matlab's eigs is giving me bad approximations of the smallest eigenvectors of a matrix.

I assume I can use some slower methods which would also be more accurate...

I am looking to find the 2nd smallest eigenvector of a lapalcian matrix (known as the "fiedler" vector). I know of course that the smallest eigenvector of a laplacian matrix is the constant vector.

Any suggestions for a more accurate method?

P.S In all the above, when I say "smallest eigenvector" I mean the eigenvector associated with the eigenvalue of smallest magnitude.

Answer 1

There is a straightforward way to exploit your a priori knowledge of the smallest eigenpair: you could simply project out the component of the current eigenvector estimate in the direction of the constant vector in each iteration of, say, inverse iteration. You should then expect the iterate to converge to the eigenvector corresponding to the second smallest eigenvalue, your desired Fiedler vector.

Depending on the connectivity of your graph, you may or may not want to run a sparse-direct factorization before inverse iteration in order to accelerate the applications of $A^{-1}$. Once the inverse iteration approach is working, you could also consider replacing it with a Krylov algorithm, which takes a little more work to code but should converge faster.

Answer 2

You can take the eigenvalue approximation computed by Matlab as the shift $\sigma$ in inverse iteration. If you accumulate the residual to high accuracy, you get in this way full accuracy of the eigenvector, using techniques such as that of

Ogita, Rump and Oishi, Accurate sum and dot product with applications, http://oishi.info.waseda.ac.jp/~oishi/papers/OgRuOi05.pdf

An exception is the case where the eigenvalue is close to defective; then you need to use a subspace method applied with $(A-\sigma I)^{-1}$ as the matrix.

Answer 3

You can get the full eigendecomposition with eig(full(A))