Jump to content
  • Advertisement
Sign in to follow this  
FluxCapacitor

QR algorithm and multiple eigenvalues

This topic is 3889 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi; I'm trying to write an eigensolver for (real) symmetric/tridiagonal matrices using the QR method. While I have the basic algorithm working, I'm unclear on how to deal with the case where not all eigenvalues have distinct absolute values (i.e. some eigenvalue has multiplicity > 1 or some eigenvalue pair are negations of each other). From what I've read (although the only proof I've seen of the algorithm dealt solely with the simple case), while most of the matrix will converge to be diagonal, the multiple eigenvalues will congregate into block matrices along the diagonal (each of size p x p, where p is the multiplicity of the corresponding eigenvalue). Then my understanding is that one must somehow detect this occurrence and split out the block matrix and recursively run the QR algorithm on it. Can anyone elaborate on how to go about performing the detection step, or point me to some (preferably free, online) resources dealing with the topic? Also, once one finds the eigenvalues hidden in these smaller matrices, how does one go about finding the corresponding eigenvectors? Currently I just read off the eigenvectors from the columns of Q, but this method would seem to break in the presence of the block matrices. Thanks!

Share this post


Link to post
Share on other sites
Advertisement
The last question is easier. Once you have an eigenvalue lambda, you know (by definition) that

M * v = lambda * v,

where M is your matrix and v is the eigenvector you seek. That can be rewritten as

(M-I*lambda)*v = 0

So just subtract lambda from all the diagonal elements of the matrix and try to find vectors that are mapped to 0. The solutions of that linear system of equations are all the eigenvectors for the given eigenvalue.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!