Sign in to follow this  
duhroach

Given EigenValues, find EigenVectors for huge matrix

Recommended Posts

duhroach    225
I'm computing the EigenValues of a huge matrix (100x100) using the Shifted QR Algorithm. From here, I'm a little confused about where I can derive the EigenVectors from. I know that I can solve for the nullspace of (A-cI)*X=0 to get them, but that requires a large amount of row-reduction operations, which doesn't do too well with a matrix my size. Is there another algorithm out there that, given the EigenValues of a matrix, I can derive the EigenVectors (corrosponding to the eigenvalues) w/o the mass of row operations? Thanks, ~Main

Share this post


Link to post
Share on other sites
duhroach    225
Well, 100x100 is large when you're considering reducing it using Row operations, No?

I've calculated the EigenValues using the Shifted QR Algorithm, Once your system has come to convergence, the eigenvalues are located across the diagonal of your last computed matrix (or, in certain cases, by deriving the characteristic equations for minors of your final matrix)

~Main

Share this post


Link to post
Share on other sites
TheAdmiral    1122
If you've gone to all the work of (nearly) factorising the matrix, you should at least try to recycle the results. I doubt this is the best way to do it, but:

A = QR
Ax = λix
QRx = λix
Rx = λiQTx

The vector on the right can be calculated directly, then the system can be solved by back-substitution. This takes O(n2) work, which trounces row-reduction.

Admiral

Share this post


Link to post
Share on other sites
Dave Eberly    1173
Quote:
Original post by duhroach
From here, I'm a little confused about where I can derive the EigenVectors from.
I know that I can solve for the nullspace of (A-cI)*X=0 to get them, but that requires a large amount of row-reduction operations, which doesn't do too well with a matrix my size.

Is there another algorithm out there that, given the EigenValues of a matrix, I can derive the EigenVectors (corrosponding to the eigenvalues) w/o the mass of row operations?


The row-reductions you propose work well with contrived examples in Linear Algebra books. In practice, it does not work well when you have a fixed-precision floating-point arithmetic system. Instead, you need to use a QR algorithm as proposed by TheAdmiral. The classical text on such approaches is "Matrix Computations" by Golub and van Loan.

Share this post


Link to post
Share on other sites
TheAdmiral    1122
Quote:
Original post by alvaro
I've never used this method myself, but at the end of the wikipedia article on the QR algorithm there is a decription of how to get the eigenvectors. I don't know if the product of those matrices is numerically stable, but that's the first thing I would try.

If I understand the sentence correctly, that method only works for symmetric matrices. In this case, the eigenvectors are, approximately, the columns of the last Qk computed. I don't see how this could be generalised though.

Admiral

Share this post


Link to post
Share on other sites
duhroach    225
Quote:

The vector on the right can be calculated directly, then the system can be solved by back-substitution

Hmm.. that's interesting. I'll try that and post results..

Quote:

If I understand the sentence correctly, that method only works for symmetric matrices. In this case, the eigenvectors are, approximately, the columns of the last Qk computed. I don't see how this could be generalised though.


That's correct, that's only for symmetric matricies.

I've read somewhere that you can plug in eigen values to the "Power Method" To get the vectors. Although this seems a bit backwards, as in the power method generates eigenvalues from eigenVectors.

~Main

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this