I have a symmetric positive-definite sparse matrix of size 150k X 150k.
I use the Power Iteration Method to find the largest eigenvalue.
I learnt from this post in math.stackexchange.com that if the matrix is positive definite, then by using the shift $B = A – \lambda_{max} I$ and then applying Power Iteration Method to B, I can find the smallest eigenvalue.
EDIT:: It is not numerically stable
However, my question is, if I can apply the same method to calculate eigenvalues between the smallest and largest eigenvalues, placed at regular intervals, by using the same method.
(I need to calculate eigenvalues closest to 300 regularly selected values between the smallest and largest eigenvalue).
If the interval is $ s = (\lambda_{max} – \lambda_{min})/301 $, then will applying Power Iteration Method on $ C = A – sI$ give me the eigenvalue closest to $(\lambda_{max} – s)$?
( 301, since $ \lambda_{min} + 301*s = \lambda_{max}$, so I get 300 eigenvalues between $\lambda_{min}$ and $\lambda_{max}$)
I don't want to use Inverse Power Iteration Method because the matrix is too large and the inverse of such a large sparse matrix may or may not be sparse and would be computationally inefficient too.
Best Answer
Shifted power iteration — while theoretically possible — is not very useful since it converges to the eigenvalue farthest away from s.
But, by using the Inverse or Shifted Inverse power iteration algorithm will yield the eigenvalue closest to s. This means by picking appropriate shifts µ, any one eigenvalue of A can be found.
Initialize v(0) with an arbitrary vector such that $||v^{(0)}||_{2} = 1$
for k = 1, 2, . . .
Solve $Aw = v^{(k−1)}$ for $w$
$v(k) = w/||w||_{2}$
$λ(k) = [v^{(k)}]^{T}Av^{(k)}$
end
Inverse of A need not be calculated. Instead for each iteration the eigenvector can be calculated by solving a system of linear equations, which is $Aw = v^{(k-1)}$
Same applies for Shifted Inverse Power Iteration.
So, Inverse Power Iteration doesn't require to calculate inverse of the matrix after all.