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.
tadsyoungAsked:
Who is Participating?
 
QCDConnect With a Mentor 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
 
tadsyoungAuthor Commented:
C or C++ code I could compile into a MEX file would also be okay.
0
 
d-glitchCommented:
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
Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
tadsyoungAuthor 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);

Open in new window

0
 
tadsyoungAuthor 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
 
phoffricCommented:
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
 
tadsyoungAuthor Commented:
Thanks, this was really helpful.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.