<p>Recently, Ta-Shma [STOC 2013], has shown that spectral approximation of matrices, can be carried out in quantum logspace.  As such, spectral approximation is in DSPACE($log^2$) with random coins, and I believe that actually can be done in $NC^2$ with random coins, because it just amounts to iterated matrix multiplication.</p>

CC BY-SA 3.0
2013-07-01T15:02:12.807Z
2013-07-01T15:02:12.807Z
Lior Eldar
<p>The decision versions of many common problems in linear algebra over the integers (or rationals)
are in the class $\mathsf{DET}$, see the paper </p>

<p>Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Structure and Importance of Logspace-MOD Class. Mathematical Systems Theory 25(3): 223-237 (1992)</p>

<p>$\mathsf{DET}$ is contained in $\mathsf{DSPACE}(\log^2)$.</p>

<p>Computing the eigenvalues is a little more delicate:</p>

<p>1) In $\mathsf{DSPACE}(\log^2)$, one can compute the coefficients
of the characteristic polynomial.</p>

<p>2) Then you can use the parallel algorithm by Reif and Neff
to compute approximations to the eigenvalues. The algorithm runs on
a CREW-PRAM in logarithmic time with polynomially many processors, 
so it can be simulated with poly-logarithmic space. 
(It is not explicitely stated in the paper, but their PRAM should to be
log-space uniform.) 
The space used is
 polylogarithmic in the size of
the input matrix and the precision $p$. Precision $p$ means that
you get approximations up to an additive error of $2^{-p}$.</p>

<p>This is a concatenation of functions computable in poly-logarithmic space.
(Output tapes are write only and oneway.)</p>

<p>C. Andrew Neff, John H. Reif: An Efficient Algorithm for the Complex Roots Problem. J. Complexity 12(2): 81-115 (1996)</p>

CC BY-SA 3.0
2013-01-07T11:17:40.983Z
2013-01-08T10:52:03.763Z
2013-01-08T10:52:03.763Z
Markus Bläser
<p>I am looking for a survey paper or a book covering results 
about the space complexity of common linear algebra operations
such as matrix rank, eigenvalues calculation, etc.
I stress the "space complexity" part meaning work space complexity, 
rather than time complexity since it is easier to trace time results. 
I appreciate any reference in the matter.</p>

<p>Thanks.</p>

CC BY-SA 3.0
2012-12-25T19:17:10.740Z
My guess is that the complexity is always at most linear (e.g. $O(nm)$ for an $n\times m$ matrix). Are you interested in "total space" or in "work space"?
Yuval Filmus
CC BY-SA 3.0
2012-12-30T13:40:52.770Z
i should have mentioned that i'm interested in work space.
gil
CC BY-SA 3.0
2012-12-30T21:36:33.570Z
I'm sure it's $\mathcal O(n^2)$ for an $n\times n$ matrix. The basic reason is that I know two useful methods how to compute them and both are quadratic in space. First is computing the characteristic polynomial (quadratic) and finding the roots. Second is using some approximation methods which all need to store a modified matrix (but I cannot elaborate on this, it's been a while since I was studying numerical linear algebra).
yo'
CC BY-SA 3.0
2012-12-31T13:59:45.557Z
To expand on the point made by @Yuval Filmus, space complexity is quite sensitive to the specific computation model.  In particular, since the output is linear size, one could play tricks by using the output tape as workspace unless the model clearly specifies a write-only output tape.  To avoid such issues, I would be tempted to rephrase as decision problems (e.g. given as input three matrices, check if the third is the product of the first two).  Could you specify the model you had in mind?  (Also, I am not aware of books about space complexity, and didn't find any useful surveys either.)
András Salamon
CC BY-SA 3.0
2013-01-03T07:49:26.630Z
in regard to @AndrásSalamon , so a decision version that is useful for me needs can be : is the k'th eigenvalue in bigger then q. for integer k and rational q. Thanks.
gil
<linear-algebra><space-complexity>
What is the space complexity of calculating Eigenvalues?
gil
# What is the space complexity of calculating Eigenvalues?

(Asked by: username_0 on 2012-12-25)

I am looking for a survey paper or a book covering results
about the space complexity of common linear algebra operations
such as matrix rank, eigenvalues calculation, etc.
I stress the "space complexity" part meaning work space complexity,
rather than time complexity since it is easier to trace time results.
I appreciate any reference in the matter.

Thanks.

**Tags:** linear-algebra, space-complexity
> **Comments:**
> **username_1**: My guess is that the complexity is always at most linear (e.g. $O(nm)$ for an $n\times m$ matrix). Are you interested in "total space" or in "work space"?  
> **username_0**: i should have mentioned that i'm interested in work space.  
> **username_2**: I'm sure it's $\mathcal O(n^2)$ for an $n\times n$ matrix. The basic reason is that I know two useful methods how to compute them and both are quadratic in space. First is computing the characteristic polynomial (quadratic) and finding the roots. Second is using some approximation methods which all need to store a modified matrix (but I cannot elaborate on this, it's been a while since I was studying numerical linear algebra).  
> **username_3**: To expand on the point made by @Yuval Filmus, space complexity is quite sensitive to the specific computation model.  In particular, since the output is linear size, one could play tricks by using the output tape as workspace unless the model clearly specifies a write-only output tape.  To avoid such issues, I would be tempted to rephrase as decision problems (e.g. given as input three matrices, check if the third is the product of the first two).  Could you specify the model you had in mind?  (Also, I am not aware of books about space complexity, and didn't find any useful surveys either.)  
> **username_0**: in regard to @AndrásSalamon , so a decision version that is useful for me needs can be : is the k'th eigenvalue in bigger then q. for integer k and rational q. Thanks.  

---

## 2 answers

### Answer by username_5 on 2013-01-07. Score: 20 | Accepted answer

The decision versions of many common problems in linear algebra over the integers (or rationals)
are in the class $\mathsf{DET}$, see the paper

Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Structure and Importance of Logspace-MOD Class. Mathematical Systems Theory 25(3): 223-237 (1992)

$\mathsf{DET}$ is contained in $\mathsf{DSPACE}(\log^2)$.

Computing the eigenvalues is a little more delicate:

1) In $\mathsf{DSPACE}(\log^2)$, one can compute the coefficients
of the characteristic polynomial.

2) Then you can use the parallel algorithm by Reif and Neff
to compute approximations to the eigenvalues. The algorithm runs on
a CREW-PRAM in logarithmic time with polynomially many processors,
so it can be simulated with poly-logarithmic space.
(It is not explicitely stated in the paper, but their PRAM should to be
log-space uniform.)
The space used is
polylogarithmic in the size of
the input matrix and the precision $p$. Precision $p$ means that
you get approximations up to an additive error of $2^{-p}$.

This is a concatenation of functions computable in poly-logarithmic space.
(Output tapes are write only and oneway.)

C. Andrew Neff, John H. Reif: An Efficient Algorithm for the Complex Roots Problem. J. Complexity 12(2): 81-115 (1996)


---

### Answer by username_4 on 2013-07-01. Score: 4

Recently, Ta-Shma [STOC 2013], has shown that spectral approximation of matrices, can be carried out in quantum logspace. As such, spectral approximation is in DSPACE($log^2$) with random coins, and I believe that actually can be done in $NC^2$ with random coins, because it just amounts to iterated matrix multiplication.


---

