Solved

Calculate sparse inverse matrix in MATLAB

Posted on 2010-08-22
7
1,905 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 500 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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

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 …
This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
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.

737 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