6
$\begingroup$

By the answer to this question, computing the eigenvalues of a matrix to within $2^{-n}$ precision can be done in polylogarithmic space. Is it also possible to compute the eigenvectors of a matrix to within precision $2^{-n}$ in polylogarithmic space?

We can try to find the eigenvectors from the eigenvalues, but since we only have the eigenvalues up to precision $2^{-n}$, this seems to lead to a host of numerical stability issues (in particular, if there are two nearby eigenvalues, small perturbations in the matrix can lead to large perturbations in the eigenvectors).

Any references are appreciated!

Improve this question
$\endgroup$
2
  • $\begingroup$ I guess, analogously to the answer you are referring to, you assume a write-only, one-way tape for the output? $\endgroup$
    – Sasho Nikolov
    May 14, 2015 at 23:40
  • $\begingroup$ Yes (along with a read-only input tape and a read-write work tape of polylog(n) size). $\endgroup$
    – jschnei
    May 15, 2015 at 0:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy