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:
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?
Best Answer
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.