Given a high-dimensional symmetric postive-definite matrix with only the main diagonal and several other diagonal (say, 1st, 5th and 100th) above and below the main diagonal to be non-zero and all other elements in the matrix are zero, is there an efficient way to compute the inverse of this type of matrix? It seems matlab can compute the inverse very fast.

  • 1
    $\begingroup$ Are you sure you really want to have the inverse instead of solving a linear system? The inverse is usually dense, even if the original matrix is sparse, and if your system is really high-dimensional the inverse will probably not fit into memory. $\endgroup$ – Elmar Zander Mar 4 '13 at 10:24
  • $\begingroup$ @ElmarZander Yep, I need the inverse. $\endgroup$ – Hugo Mar 4 '13 at 11:39
  • $\begingroup$ Matlab has a well optimised BLAS inside, so it's pretty fast as long as the matrices are of moderate size. However, what you need scales as $O(n^3)$ (or $O(n^{\log_2(7)})$ at best) and it makes no big difference, whether you use Cholesky or LU, since you just have a factor of 2 between them, but the same asymptotic complexity. Sparsity and "spd"-ness won't buy you anything, if you need the inverse--only when you're solving linear systems. $\endgroup$ – Elmar Zander Mar 4 '13 at 13:36

First high-dimensional means a large matrix (but still two dimensional), right? Like an m-by-m matrix instead of an m-by-m-by-m tensor? There are three ways I can think of on top of my head.

  1. For tridiagonal matrices Thomas' Algorithm is good. But in this case we have a perturbed tridiagonal matrix so we can use Thomas plus Sherman-Morrison Formula.

  2. For sparse matrices, Givens Rotation kicks ass.

  3. For positive definite, Cholesky Decomposition is the algorithm of choice.

These can be used to (like Gaussian elimination) to factor the matrix in question into triangular matrices which can then be easily inverted. No doubt there are others or even hybrid methods not listed here. I am sure MATLAB has some criteria (for example the sparsity percentage) to decide which algorithm would work the fastest and then goes ahead and applies it.


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.