Lanczos Method: Calculating Smallest Eigenvalues

[Hassan2]

Having done with subspace iteration method, I think now I can understand and implement the Lanczos method. In fact the lanczos algorithm is simpler than the subspace, but it seems to me that the common Lanczos algorithms give the largest eigenvalues rather than smalles ones. That being true, does anyone have a reference for the case of calculating smallest eigenvalues?

Your help would be highly appreciated.

 

[AlephZero]

Just find the eignenvalues of the inverse of the matrix. The eigenvectors of the matrix and its inverse are the same.

You don't invert the matrix explicitly. Instead of multiplying a vector by the matrix to calculate $y = Ax$ you solve the equiations $Ay = x$. (You want to factorize $A = LL^T$ or $A = LDL^T$ before you start the iterations, or course).

If $A$ is singular, you can add a constant multiple of the unit matrix before you factorize it. If you are finding the eigenvalues $\lambda_i$ of $(A + cI)^{-1}$, the eigenvalues of $A$ are $1 / \lambda_i - c$.

If you are solving a generalized eigenproblem $Kx = \lambda Mx$, and K is singular, you add a multiple of $M$ to $K$ instead of a multiple of $I$.

 

[Hassan2]

Thanks. It works now, but there is a problem which I think is due to deviation from orthogonality: I have many instances of the same eigenvalue in the final list of eigenvalues. Or perhaps it's due the the numerical error introduced when solving the equation $Ax_{k+1}=x_{k}$ ( I use an iterative solver).

 

[AlephZero]

Thanks. It works now, but there is a problem which I think is due to deviation from orthogonality: I have many instances of the same eigenvalue in the final list of eigenvalues.

Remember my post when I said "you really really don't want to write your own Lanczos routine?" You are just start the adventure game of finding out why, if you keep trying!

Warning: I spent a long time on this several years ago, and gave up after several months because my code was never "100% reliable" on new problems.

If you read the literature, there are lots of ways that claim to fix this problem - but only if you can find a a paper that works for your matrices, AND you can understand it!

Have fun.

 

[Hassan2]

Yes I remember well. I think I should give up too. Perhaps the subspace iteration is enough for my purpose.

Thanks for the advice.