# Calculate sparse inverse matrix in MATLAB

I have a large square n x n matrix where n = 1,000,000. I need to calculate the inverse of this matrix. This would take a long time to do directly.  However, the inverse matrix is very sparse.  I know which elements of the inverse matrix are non-zero, and each row (and column) only has 100 non-zero entries.
So I thought I could directly calculate each of these 100,000,000 elements of the inverse matrix. Therefore I need MATLAB code to calculate individual elements of an inverse matrix in a much faster way than simply taking the inverse and checking the individual elements.

That is, given a matrix M, find element (i,j) of inv(M) quickly and directly using MATLAB. The answer must be much faster to calculate than simply taking the inverse and checking the appropriate elements.
###### Who is Participating?

Commented:
Yes.  If you know that your inverse is sparse, the problem is easy.  Let's call your original matrix A, and the inverse matrix B = A^(-1).  We know that B * A = I (the identity matrix).

Every row of your inverse matrix has at most 100 non-zero elements.  Imagine that we labelled these elements x_1, x_2, ..., x_100.

We know that the dot product of any row of B and any column of A is the corresponding element in the identity matrix I.

This gives us a linear equation in x_1, ..., x_100.

Grab 100 columns of A, and do this.  Now, you have 100 linear equations in x_1, ..., x_100.  If they are not linearly independent, just grab more columns of A until you have 100 linearly independent equations.  (There's a theorem that guarantees that this will work with extremely high probability unless the original matrix is singular.)

You now have a 100x100 linear system of equations.  Solve using your favourite method.

Do this for each row.

Hope this helps!

(Bonus: You can make this go a bit faster using the following trick.  First, observe that you can do this with columns instead of rows, using A * B = I instead.  You know where all the non-zero elements are, so pick the row or column that has the fewest unknown non-zero elements to solve for.  Now that you know a few of the non-zero elements, the number of unknown non-zero elements is a little bit lower, so find again the row or column that *now* has the fewest unknowns, and solve that one.  Repeat until they're all done.)
0

Author Commented:
C or C++ code I could compile into a MEX file would also be okay.
0

Commented:
What is the context of this question?
What is the data and where are you getting it?
What sort of job/project/assignment is this?

Isn't this functionality built into MATLAB already?

http://www.mathworks.com/access/helpdesk/help/techdoc/math/f6-19352.html#f6-41044
0

Author Commented:
This is an attempt to make a research project work faster. The input matrix is a covariance matrix, and I am trying to obtain the inverse covariance matrix. Matlab can, of course, take the inverse of a matrix.  But because my matrix is so large, and has special properties (i.e. the output matrix is sparse) I thought there must surely be a better way to do it.

This is how the input matrix (cov) is created, and how it is used (out):

``````for j=1:size(x,1);
covpart(:,:,j)=gaussians(j)*(distance_vector(:,j)*distance_vector(:,j)');
end
cov=sum(covpart,3);

out=exp(-.5*(distance_vector'/cov)*distance_vector);
``````
0

Author Commented:
"distance_vector" in line 6 is a different variable than any of the distance vectors in line 2.  Sorry for the confusion there.
0

Commented:
Can you transform your matrix into a Block diagonal matrix?
http://en.wikipedia.org/wiki/Block_matrix#Block_diagonal_matrices

or a band matrix?
http://en.wikipedia.org/wiki/Band_matrix#Band_storage

Free C/C++ Sources for Numerical Computation
http://cliodhna.cop.uop.edu/~hetrick/c-sources.html

A matlab paper on sparse matrix:
http://www.mathworks.com/access/helpdesk/help/pdf_doc/otherdocs/simax.pdf
0

Author Commented: