Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Inverse of Large Sparse Matrix

Subject: Inverse of Large Sparse Matrix

From: Elia

Date: 24 Feb, 2007 14:21:23

Message: 1 of 4

Hi All,

I need find the inverse of a very large sparse martix.
The size of the matrix is near 16000^2.
The problem ofcourse is that Matlab yields : "Out of memory" ,when I
use B=inv(A);
I know that there are some clever algorithms to exploit the fact that
the matrix is sparse and most of its values are zeros and to find the
inverse in some other way without exceeding the limit of memory but I
dont know how.
I tired to use the operator '\' but it didnt work either.

If somebody knows how to do it , please help .

Thanks,
Elia.

Subject: Inverse of Large Sparse Matrix

From: Tim Davis

Date: 15 Jul, 2007 18:52:52

Message: 2 of 4

The solution to your problem is not attempt to solve it ...

"Never" invert a matrix, particularly a large sparse one.

See http://blogs.mathworks.com/loren/2007/05/16/purpose-of-inv/ and the comments there for more details.

Subject: Inverse of Large Sparse Matrix

From: Rajesh Karan

Date: 4 Mar, 2012 08:50:14

Message: 3 of 4

Dear Prof Davis:

I was following various posts on sparse matix inversion, and everywhere I found similar answer: "never try to invert a sparse matrix". What I think, most of the people who have answered "how to invert large sparse matrix" see the problem in the context of engineering problem and finding the solution of type "Ax=By" arising from PDE. My problem is different. Let me pose my problem as follows.

What I am trying to do is to compue Greens function for quantum many-body system. The imaginary frequency Greens function (G) I am looking at, can be brought into block-diagonal form [:=b, total Nb] for every frequency[:=w, total Nw] => G(w,b). Each block is a function of momentum: Kx,Ky (max Nx,Ny repectively).

Nw,Nb,Nx,Ny are all integers: typical values: Nw=N=2000, Nb=B=10; Nx=X=400; Ny=Y=400

for every w: 0 to N; for every block b:0,B; for every x:0 to X; for every y:0 toY; I have a sparse matrix: E(w,b,x,y)(:,:) whose size is say 1000x1000, sparcity:~16 per Row/Col. Define another diagonal matrix of size 1000x1000 and call it W. The matrix "E" cannot be brought into block diagonal form.

My problem is to integrate a function of "E" for given x and y in the following way:
Define Z: Z is much less than X, and Y: say 28. Then define WmEinv = Invert(W- E) and gather ZxZ submatix (based on some algorithm) and call it F. Integrate "F" over x and y. This way we have formed a matrix G(w,b): Integrate[ (W,E(w,b,x,y)(:,:)) -> F(w,b)(:,:) , over{x,y}] for given w and b. It is therefore I need to understand how to do inversion of sparse matrix. Yours is just a random post, I picked up after searching on google, and my search hit was maximum for this page. I looked at your adress to find out whether it is active or not and I found you are a professor and you have written books on sparse matrix. Therefore you are the best person I can pose the problem. What I need to understand is: do you think there is still some hope by not inverting the large sparse matrix and doing the computation I want?

Thank you for your attention.
Best regards.
Rajesh Karan.
rajesh.feb02@gmail.com


"Tim Davis" <davis@cise.ufl.edu> wrote in message <f7dqe3$mmc$1@fred.mathworks.com>...
> The solution to your problem is not attempt to solve it ...
>
> "Never" invert a matrix, particularly a large sparse one.
>
> See http://blogs.mathworks.com/loren/2007/05/16/purpose-of-inv/ and the comments there for more details.

Subject: Inverse of Large Sparse Matrix

From: Roger Stafford

Date: 4 Mar, 2012 20:48:12

Message: 4 of 4

"Rajesh Karan" wrote in message <jivac6$rj0$1@newscl01ah.mathworks.com>...
> Dear Prof Davis:
>
> I was following various posts on sparse matix inversion, and everywhere I found similar answer: "never try to invert a sparse matrix". What I think, most of the people who have answered "how to invert large sparse matrix" see the problem in the context of engineering problem and finding the solution of type "Ax=By" arising from PDE. My problem is different. Let me pose my problem as follows.
>
> What I am trying to do is to compue Greens function for quantum many-body system. The imaginary frequency Greens function (G) I am looking at, can be brought into block-diagonal form [:=b, total Nb] for every frequency[:=w, total Nw] => G(w,b). Each block is a function of momentum: Kx,Ky (max Nx,Ny repectively).
>
> Nw,Nb,Nx,Ny are all integers: typical values: Nw=N=2000, Nb=B=10; Nx=X=400; Ny=Y=400
>
> for every w: 0 to N; for every block b:0,B; for every x:0 to X; for every y:0 toY; I have a sparse matrix: E(w,b,x,y)(:,:) whose size is say 1000x1000, sparcity:~16 per Row/Col. Define another diagonal matrix of size 1000x1000 and call it W. The matrix "E" cannot be brought into block diagonal form.
>
> My problem is to integrate a function of "E" for given x and y in the following way:
> Define Z: Z is much less than X, and Y: say 28. Then define WmEinv = Invert(W- E) and gather ZxZ submatix (based on some algorithm) and call it F. Integrate "F" over x and y. This way we have formed a matrix G(w,b): Integrate[ (W,E(w,b,x,y)(:,:)) -> F(w,b)(:,:) , over{x,y}] for given w and b. It is therefore I need to understand how to do inversion of sparse matrix. Yours is just a random post, I picked up after searching on google, and my search hit was maximum for this page. I looked at your adress to find out whether it is active or not and I found you are a professor and you have written books on sparse matrix. Therefore you are the best person I can pose the problem. What I need to understand is: do you think there is still some hope by not inverting the large sparse matrix and doing the computation I want?
>
> Thank you for your attention.
> Best regards.
> Rajesh Karan.
> rajesh.feb02@gmail.com
- - - - - - - -
  One serious difficulty with inverting a sparse matrix is that its inverse may no longer have a high percentage of zeros, which is normally the reason for using the sparse format for arrays. For large matrices this can therefore lead to exceeding the computer's memory capacity just to store the inverse, rather than being a problem with the algorithm used to find it.

  A second reason for possibly avoiding the 'inv' function is that a full inverse may not really be needed for the task at hand. Taking the inverse of a large square matrix is a computationally intense undertaking and there may be shorter ways of accomplishing the same goal. For example, solving for an array X in

  A*X = B

may be accomplished more efficiently with X = A\B than X = inv(A)*B if B has fewer columns than rows.

  I know of no other reasons than these two for avoiding the use of the 'inv' function. It is a perfectly decent operation to use under the proper circumstances. Note that inv(A) is equivalent to A\eye(n), (with A an n by n square matrix,) so it is not likely to be less efficient than using '\' for cases where the number of columns in B is as great as or greater than the number of rows.

  If you feel you really need a full inverse and have enough memory to store it, then in my opinion you should not be afraid to use matlab's 'inv' function. I suspect that the reason people often say to "never" use it is the frequency with which it is used improperly. Users will often call on it to solve a single set of n linear equations in n unknowns because that is what they were taught in linear algebra, but this is far less efficient than using matlab's matrix division algorithm.

Roger Stafford

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us