?
Solved

Calculate sparse inverse matrix in MATLAB

Posted on 2010-08-22
7
Medium Priority
?
1,950 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
7 Comments
 

Author Comment

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

Expert Comment

by:d-glitch
ID: 33495480
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
ID: 33495687
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:tadsyoung
ID: 33495721
"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
ID: 33495868
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 2000 total points
ID: 33496582
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
ID: 33496680
Thanks, this was really helpful.
0

Featured Post

Get 15 Days FREE Full-Featured Trial

Benefit from a mission critical IT monitoring with Monitis Premium or get it FREE for your entry level monitoring needs.
-Over 200,000 users
-More than 300,000 websites monitored
-Used in 197 countries
-Recommended by 98% of users

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Having just graduated from college and entered the workforce, I don’t find myself always using the tools and programs I grew accustomed to over the past four years. However, there is one program I continually find myself reverting back to…R.   So …
If you haven’t already, I encourage you to read the first article (http://www.experts-exchange.com/articles/18680/An-Introduction-to-R-Programming-and-R-Studio.html) in my series to gain a basic foundation of R and R Studio.  You will also find the …
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

777 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