Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am implementing an algorithm to calculate eigenvalues and eigenvectors of a symmetric matrix in a GPU. In order to calculate the eigenvalues I first reduced the matrix to the tridiagonal form using Householder transformations. Now I want to use those eigenvalues to calculate the corresponding eigenvectors through inverse iteration.

I was reading about inverse iteration here and I noticed that in step 4 I must invert a matrix or, alternatively, solve a set of linear equations:

inverse iteration

As noted here this is much easier to do with tridiagonal matrices. I already have the reduction, but its eigenvectors are not the same of the original matrix. So my question is, what do I have to do to get the eigenvectors of the original matrix?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

If you first decomposed your matrix $\mathbf A$ as

$$\mathbf A=\mathbf P\mathbf T\mathbf P^\top$$

where $\mathbf P$ is orthogonal and $\mathbf T$ is tridiagonal, and afterwards you managed to find a (partial) eigendecomposition of $\mathbf T$ as

$$\mathbf T=\mathbf Q\mathbf \Lambda\mathbf Q^\top$$

where $\mathbf Q$ is the orthonormal matrix of eigenvectors and $\mathbf \Lambda$ is diagonal, then $\mathbf A$ has the eigendecomposition

$$\mathbf A=(\mathbf P\mathbf Q)\mathbf \Lambda(\mathbf P\mathbf Q)^\top$$

Put another way, if you have a vector $\mathbf v$ and a scalar $\lambda$ satisfying

$$\mathbf T\mathbf v=\lambda\mathbf v$$

then

$$\begin{align*}(\mathbf P^\top\mathbf A\mathbf P)\mathbf v&=\lambda\mathbf v\\\mathbf P^\top\mathbf A\mathbf P\mathbf v&=\lambda\mathbf v\\\mathbf A\cdot(\mathbf P\mathbf v)&=\lambda(\mathbf P\mathbf v)\end{align*}$$

In short, you need to multiply the eigenvectors of your tridiagonal matrix $\mathbf T$ with the orthogonal matrix $\mathbf P$ you obtained from the tridiagonal decomposition of $\mathbf A$ to obtain eigenvectors of $\mathbf A$.


If you'll indulge me a tiny aside: at least for getting a few eigenvectors of a symmetric matrix, one can do better than inverse iteration by using a method that is, well, a carefully modified inverse iteration. Try searching for "MRRR algorithm" in your favorite search engine for details.

share|improve this answer
    
Thank you for the for the suggestion. I'll do some research. –  nmat Oct 14 '11 at 22:09
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.