MATRIX INVERSION TAKING FOREVER TO RUN

I have a matrix(size 200*200) which I want to keep multiplying with 10 lakhs different input vectors. Furthermore, some elements in the matrix are random and to capture their statistical behaviour, 300 monte carlo sims need to be done for each of the input vector. Now this is taking a lot of time for even 2^5 codes. If extrapolated, it will take forever for the original case. I have profiled the code, and ofcourse the inversion is most demanding. I tried generating Mex file, but it doesn't help. Though increasing the number of workers in the parallel tool box helps, but still not significantly.

Is there any intelligent way of doing this? Thanks in advance.

[Bruno Luong]

In my computer (5-6 year old) it takes 4 seconds to solve 300*2^5 systems of 200 x 200 linear equations

>> A=rand(200); b=rand(200,1);
>> tic; for i=1:300*2^5, x=A\b; end, toc
Elapsed time is 3.785910 seconds.

Yeah not instantaneous but far from forever.

[YOGENDRA SINGH BHANDARI]

Sure, just that generation of A and B in my case is slightly different.

[Bruno Luong]

I simply don't believe.

For random matrix such as mine, MATLAB "\" use direct method must use the most generic factorization method, and it's not profit any advantage more than your matrix, whatever it is.

Answer 1

[Steven Lord]

In general, you should not invert matrices. I suspect you're trying to work symbolically in which case you absolutely should not try to invert symbolic matrices, especially ones that large.

maxN = 7;
lengthOfExpression = zeros(1, maxN);
timeToCompute = zeros(1, maxN);
for n = 1:maxN
    syms('x', [n n]);
    tic
    A = inv(x);
    timeToCompute(n) = toc;
    lengthOfExpression(n) = strlength(char(A));
end
lengthOfExpression

You can see that the length of the expression representing the inverse grows pretty quickly. The time required to compute the inverse starts off small but at the last data point it rises sharply. You can try extending the problem size to maxN = 8 if you have the desire and the time. Extrapolation can be tricky, especially when trying to extrapolate the behavior of n = 200 from data with n = 7, but even looking at the general trend shows that storing and computing your inverse may run up against the storage capacity of the universe and its lifespan.

If you're solving a system of equations, use the backslash operator (\) instead and/or substitute values in for your symbolic variables before trying to solve the system if possible.

[YOGENDRA SINGH BHANDARI]

I am using the backslash operator, and the matrix is not symbolic. As I told the matrix happens to be random and to capture the statisitical behaviour, in the testbench I am passing 300 different values of the matrix for each input vector.

[Steven Lord]

Can you show a small sample of code that generates and uses these matrices and tell us how this differs from "the original case" that you've extrapolated will take "forever"?

I agree with the expectation Bruno Luong stated in a comment, that solving a 200-by-200 system of equations even tens or hundreds of thousands of times shouldn't take that long. Maybe if your machine has almost no memory free and so needs to swap every time it does a calculation, but if your machine is that memory constrained everything about it should be crawling not just MATLAB.

[Aurea94]

If my matrix is symbolic and I cannot substitute the variables before solving. Is there a way in which I can spped the calculus of the inverse?

[Walter Roberson]

@Aurea94

Let me show an example:

N = 6

N = 6

syms A B C D
M = sym(magic(N));
M(1,1) = A^2+3*C; M(2,3) = B*tan(D-5); M(3, 5) = exp(-C); M(4,2) = D*(D-1)*(D-2);
temp = solve(C^3+B*C^2-2*C+5, C, 'maxdegree', 3);
M(5,6) = temp(2);
M

M = 

rank(M)

ans = 6

tic; Minv = inv(M); toc

Elapsed time is 11.597662 seconds.

syms prox [N N]
tic; proxinv = inv(prox); proxinv = subs(proxinv, prox, M); toc

Elapsed time is 2.803145 seconds.

So when the matrix is complicated enough then you can get a fair bit ahead by taking inv() of a representative matrix the same size and substituting in the corresponding coefficients of the original matrix afterwards. In this case we take the inverse of a generic 6 x 6 matrix of just symbolic variable names, which gives us the general form for inverses of 6 x 6 matrix; then we substitute in the specific terms.