Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I am wondering how to find the eigenvalues of some sparse matrix in given interval [a, b] by iterative method. To my personal understanding, it is more obvious to use Krylov subspace method to find the extreme eigenvalues rather than the interior ones.

share|improve this question
    
Have you considered the answers provided here? –  Deathbreath Apr 11 '12 at 14:27
    
I'm curious... How large is your matrix? Do you need all interior eigenvalues, or ones closest to a particular value? –  Paul Apr 11 '12 at 15:05
    
@Paul This is just an on-goning research, the size will be billion by billion sparse matrices, and we only need a few eigenvalues in certain interval to do the modeling. –  Willowbrook Apr 11 '12 at 15:21
    
@Deathbreath Thank you for your reminder. I have considered those answers. –  Willowbrook Apr 11 '12 at 15:27
add comment

2 Answers

up vote 10 down vote accepted

The following strategy is called shift and invert and depends upon two important facts:

  1. $A-\tau I$ has the same spectrum as $A$, but shifted down by $\tau$, i.e., if $\lambda \in \sigma(A)$ then $\lambda-\tau \in \sigma(A-\tau I)$.
  2. Assuming that $A$ is invertible, the matrix $A^{-1}$ has a spectrum which is equal to the element-wise inverse of the spectrum of $A$, i.e., if $\lambda \in \sigma(A)$ then $1/\lambda \in \sigma(A^{-1})$.

Since $A-\frac{a+b}{2}I$ will have shifted the portion of $A$'s spectrum which is close to $\frac{a+b}{2}$ near the origin, the eigenvalues of $A$ near $\frac{a+b}{2}$ will be very large in $(A-\frac{a+b}{2}I)^{-1}$, and so it is reasonable to expect a Krylov algorithm to pick them up.

share|improve this answer
    
My question is by shift and invert method, we can amplify all the eigenvalues near a, which of course will include the unwanted ones originally less than a, and then how to filter out those eigenvalues. The other question is how to use the other endpoint b in the interation. –  Willowbrook Apr 11 '12 at 15:25
1  
It's possible to filter out certain eigenvalues by using polynomial filters. For an accessible overview of this technique see Sorensen: "Numerical methods for large eigenvalue problems" in Acta Numerica journals.cambridge.org/action/… –  Reid.Atcheson Apr 11 '12 at 23:30
    
@Willowbrook: Shifting by $c=(a+b)/2$ as recommended uses bouth end points, and moves the eigenvalues in [a,b] to the absolute largest ones in the transformed problem. So if you can factor your matrix, this is the way to proceed. If you can't factor the matrix, you'd add some info about the sttructure and origin of your matrix, so that one can make useful suggestions. –  Arnold Neumaier Apr 14 '12 at 19:22
add comment

May be you know that ressource already, but it may be useful anyway... http://www-users.cs.umn.edu/~saad/eig_book_2ndEd.pdf regards, Tom

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.