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.
[Math] computing the inverse of a special sparse matrix
inverselinear algebramatrices
Best Answer
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.
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.
For sparse matrices, Givens Rotation kicks ass.
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.