|
"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
|
Feed for this Thread