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.

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)'); endcov=sum(covpart,3); out=exp(-.5*(distance_vector'/cov)*distance_vector);

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:

Thanks, this was really helpful.

0

Featured Post

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!