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!

  • $\begingroup$ I guess, analogously to the answer you are referring to, you assume a write-only, one-way tape for the output? $\endgroup$ May 14 '15 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 '15 at 0:08

Your Answer

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

Browse other questions tagged or ask your own question.