0

I want to check the space complexity of

  • matrix inversion,

  • matrix adjoint and

  • matrix determinant.

Most of the literature mention the time complexity (for the inversion there are $O(n^3)$ solutions and for the determinant $O(n^4)$ and $O(n^3)$). But I haven't been able to find literature where mentions the space complexity for these three operations.

Do you guys know any good references covering the space complexity of some algorithms for these operations ?

Thank you.

liwuen
  • 330
  • 2
  • 17
  • You can use Gaussian elimination (assuming there are no precision issues) to find both an inversion and a determinant, and it requires O(n^3) time and O(n^2) space. Since the output for inversion requires O(n^2) space, it's space-optimal for this operation. –  Jul 06 '20 at 03:57
  • some special matrices (like orthonormal rotational and homogenuous transform matrices) can be inverted in-place so `O(1)` space using transposing of rotation part of matrix and correcting the rest by simple `matrix*vector` multiplication. However standard approach complexity heavily depends on the implementation. – Spektre Jul 06 '20 at 07:08
  • @Spektre neither transpose nor matrix multiplication are O(1) – dmuir Jul 06 '20 at 07:18
  • @dmuir transpose is `O(1)` space its done inplace so the result is already allocated. but youre right `matrix*vector` is `O(m)` space where `m` is dimensionality of the space the matrix represent usually `m=n-1` where `n` is size of square matrix. here example [`matrix_inv`](https://stackoverflow.com/a/42293434/2521214) for 4x4 3D matrix – Spektre Jul 06 '20 at 07:21

0 Answers0