Solved

Calculate sparse inverse matrix in MATLAB

Posted on 2010-08-22
7
1,866 Views
Last Modified: 2016-03-02
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.
0
Comment
Question by:tadsyoung
7 Comments
 

Author Comment

by:tadsyoung
Comment Utility
C or C++ code I could compile into a MEX file would also be okay.
0
 
LVL 27

Expert Comment

by:d-glitch
Comment Utility
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 Comment

by:tadsyoung
Comment Utility
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
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 

Author Comment

by:tadsyoung
Comment Utility
"distance_vector" in line 6 is a different variable than any of the distance vectors in line 2.  Sorry for the confusion there.
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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
 
LVL 4

Accepted Solution

by:
QCD earned 500 total points
Comment Utility
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 Closing Comment

by:tadsyoung
Comment Utility
Thanks, this was really helpful.
0

Featured Post

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
When we want to run, execute or repeat a statement multiple times, a loop is necessary. This article covers the two types of loops in Python: the while loop and the for loop.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now