8

If I have already accurately known the eigenvalue spectrum (i.e. all eigenvalues) of a matrix, is there any efficient numerical algorithm to compute all the eigenvectors corresponding to these eigenvalues?

I guess with the information about eigenvalues, there should be some quicker way to compute eigenvectors of the matrix compared with simply diagonalize it without any information.

Geoff Oxberry
  • 30,394
  • 9
  • 64
  • 127
Enchantedland
  • 89
  • 1
  • I just had a thought, maybe eigen decomposition can be used ($PDP^{-1}=A$ thus $P=APD^{-1}$, where $P$ is a matrix containing an eigen vector in each column) I have no idea if this can be made into a converging method and if so whether it would converge faster than the already mentioned method. – fibonatic Mar 28 '15 at 04:22

1 Answers1

3

If you can invert the matrix, the simplest choice is shifted inverse iteration, which is just power iteration for $(\mu I - A)^{-1}$, where $\mu$ is some estimate of an eigenvalue whose eigenvector you want. Convergence speed depends on how close you set $\mu$ is to your desired eigenvalue and how close other eigenvalues are to $\mu$.

http://en.wikipedia.org/wiki/Inverse_iteration

Jesse Chan
  • 3,132
  • 1
  • 13
  • 17
  • 1
    Inverse power iteration is a good idea. I just want to point out that you don't even need to invert $A$, just solve the system $(\mu I - A) v^{n+1} = v^{n}$ with $v^0$ being some guess (e.g.: a vector with each component set to one). – Juan M. Bello-Rivas Mar 26 '15 at 02:12
  • 1
    Of course - one should (typically) never invert a matrix :). One thought that came to mind is that approximately solving the system with a known spectrum might be done cheaply using a matrix polynomial if the eigenvalues are clustered. – Jesse Chan Mar 26 '15 at 02:53
  • If you want all eigenvectors (or even a significant fraction, $O(n)$ of them, let's say), this method costs $O(n^4)$, because it needs $n$ different LU factorizations, while throwing away the eigenvalues and starting from scratch would cost $O(n^3)$. – Federico Poloni Mar 28 '15 at 08:39
  • @JuanM.Bello-Rivas Can you please tell me what is the name of the method? I.e., using $(\mu I-A)v^{n+1}=v^n$ to find eigenvectors. – Tan Jan 12 '22 at 17:17