# Algorithm for Sparse-Matrix Inverse

I have a $50000\times 50000$ matrix $A$ sparse matrix containing only 5 non-zero elements in each row. Now the problem is that the diagonal elements and the constants (in $B$ matrix such that $AX=B$) get updated after every iteration. If I go by the usual Matlab function inv or via Gauss Elimination, it takes around 130 seconds for the solution to be computed for a single iteration and the number of iterations required by the problem is somewhat of the order 100-500 to compute the final solution $X$. Need some suggestions on this one if I am not wanting to use parallel computation.

• Inverting your sparse matrix will inevitably yield a dense one, so not a good plan. You can use an iterative method instead. Speaking of which, you haven't mentioned if your matrix is symmetric (positive definite) or not... Jun 19, 2013 at 14:57
• Do you update both A and B?
– Jan
Jun 19, 2013 at 15:36
• Welcome to SciComp.SE! Just to make sure: You have a matrix $A\in\mathbb{R}^{n\times n}$ and a matrix $B\in\mathbb{R}^{n\times m}$, and are interested in computing the matrix $X\in\mathbb{R}^{n\times n}$ such that $AX=B$ (that is, all you really want is $X$, and not the inverse $A^{-1}$), and you are using Matlab? In this case, have you tried X=A\B (never use inv for solving linear systems, that's not what it is for!), which is the most efficient "black-box" way of solving your problem in Matlab? Jun 19, 2013 at 17:05
• Also, an important information is the size of B (same size as A or much smaller)? Jun 19, 2013 at 17:07
• @clipper: Good point. I think without the help of the OP, there is little else we can suggest. I'm startled that none of our questions have gotten any answers -- does he no longer care about the question? Jun 20, 2013 at 6:52

You may use a sparse factorization algorithm, it means computing matrices $P$, $L$, $U$, such that $M = PLU$ where $P$ is a permutation matrix, $L$ a sparse lower triangular matrix and $U$ a sparse upper triangular matrix. The permutation matrix is there and computed in such a way that $L$ and $U$ remain reasonably sparse (without it it is not the case in general, as indicated in the other answer). Then when $M$ is factorized in this form, it is trivial to solve a linear system with an arbitrary rhs. If $M$ is symmetric definite, then there is a sparse cholesky factorization ($M = PLL^t$), if it is symmetric only, then it can be decomosed as $M = PLDL^t$, with $D$ a diagonal matrix.
There are several available implementations of sparse factorization: SuperLU, Choldmod, Mumps, TAUCS (depending on whether you need $LU$, $LL^t$ or $LDL^t$). There probably exists MATLAB bindings for most of them.