<p>By the answer to <a href="https://cstheory.stackexchange.com/questions/14856/what-is-the-space-complexity-of-calculating-eigenvalues/14996#14996">this question</a>, 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? </p>

<p>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). </p>

<p>Any references are appreciated!</p>

CC BY-SA 3.0
2015-05-14T23:40:48.320Z
I guess, analogously to the answer you are referring to, you assume a write-only, one-way tape for the output?
Sasho Nikolov
CC BY-SA 3.0
2015-05-15T00:08:28.820Z
Yes (along with a read-only input tape and a read-write work tape of polylog(n) size).
jschnei
<linear-algebra><space-bounded><logspace>
What is the space complexity of computing the eigenvectors of a matrix?
jschnei
# What is the space complexity of computing the eigenvectors of a matrix?

(Asked by: username_0 on 2015-05-14)

By the answer to [this question](https://cstheory.stackexchange.com/questions/14856/what-is-the-space-complexity-of-calculating-eigenvalues/14996#14996), 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!

**Tags:** linear-algebra, space-bounded, logspace
> **Comments:**
> **username_1**: I guess, analogously to the answer you are referring to, you assume a write-only, one-way tape for the output?  
> **username_0**: Yes (along with a read-only input tape and a read-write work tape of polylog(n) size).  

---

## 0 answers

