CODEWITHSUNDEEP
performancematlabmatrixlinear-algebrasparse-matrix
rajan sthapit
rajan sthapit

Reputation: 4364

Memory and time issues when dividing two matrices

I have two sparse matrices in matlab

M1 of size 9thousandx1.8million and M2 of size 1.8millionx1.8million.

Now I need to calculate the expression

M1/M2

and it took me like an hour. Is it normal? Is there any efficient way in matlab so that I can overcome this time issue. I mean it's a lot and if I make number of iterations then it will keep on taking 1 hour. Any suggestion?

Upvotes: 4

Views: 113

Answers (1)

Chris A.
Chris A.

Reputation: 6887

A quick back-of-the-envelope calculation based on assuming some iterative method like conjugate gradient or Kaczmarz method is used, and plugging in the sizes makes me believe that an hour isn't bad.

Because of the tridiagonality the matrix that's being "inverted" (if not explicitly), both of those methods are going to take a number of instructions near "some near-unity scalar factor" times ~9000 times 1.8e6 times "the number of iterations required for convergence". The product of the two things in quotes is probably around 50 (minimum) to around 1000 (maximum). I didn't cherry pick these to make your math work, these are about what I'd expect from having done these. If you assume about 1e9 instructions per second (which doesn't account much for memory access etc.) you get around 13 minutes to around 4.5 hours.

Thus, it seems in the right range for an algorithm that's exploiting sparsity.

Might be able to exploit it better yourself if you know the structure, but probably not by much.

Note, this isn't to say that 13 minutes is achievable.

Edit: One side note, I'm not sure what's being used, but I assumed iterative methods. It's also possible that direct methods are used (like explained here). These methods can be very efficient for sparse systems if you exploit the sparsity right. It's very possible that Matlab is using these by default, but it's worth investigating what Matlab is doing in your case.

In my limited experience, iterative methods were usually preferred over direct methods as the size of the systems get large (yours is large.) Our linear systems worked out to be block tridiagonal as well, as they often do in image processing.

Upvotes: 4

Related Questions