# computing the inverse of a special sparse matrix

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.

-
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. –  Elmar Zander Mar 4 '13 at 10:24
@ElmarZander Yep, I need the inverse. –  Hugo Mar 4 '13 at 11:39
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. –  Elmar Zander Mar 4 '13 at 13:36