19
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 7
    $\begingroup$ 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"? $\endgroup$
    – Yuval Filmus
    Dec 25 '12 at 19:17
  • $\begingroup$ i should have mentioned that i'm interested in work space. $\endgroup$
    – gil
    Dec 30 '12 at 13:40
  • $\begingroup$ 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). $\endgroup$
    – yo'
    Dec 30 '12 at 21:36
  • 1
    $\begingroup$ 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.) $\endgroup$
    – András Salamon
    Dec 31 '12 at 13:59
  • $\begingroup$ 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. $\endgroup$
    – gil
    Jan 3 '13 at 7:49
20
$\begingroup$

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)

Improve this answer
$\endgroup$
0
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.