4
$\begingroup$

I have a 7000x7000 sparse matrix (scipy), which I want to exponentiate. I've tried using scipy.sparse.linalg.expm, which works quite well for smaller matrices (takes a few seconds for a 1000x1000 matrix) but it takes too long time to compute for the matrix in question. Is there a way to optimise this or work around the time complexity of this algorithm (apparently O(n^2))? For background, I've tried the same with R package {expm} with similar results, so it's apparently more about the algorithmic approach to the problem rather than the specific software used. Do you have any ideas?

$\endgroup$
  • 2
    $\begingroup$ Do you need the matrix exponential itself or is a vector-matrix multiplication what you are trying to perform in the end? If the second is the case, Krylov-methods might offer what you are looking for. $\endgroup$ – mdot Feb 16 '17 at 0:34
  • 1
    $\begingroup$ Agree with max. It depends on your final goals. If you need matrix-vector product, there should be a choice of fast iterative algorithms that can help you in that. If you need the actual matrix exponential, the answer will depend if you can allow for an approximation to the matrix exponential. Then, you would also have some options (HSS, H-matrices), though I doubt those type of things are readily available in Python or R. $\endgroup$ – Anton Menshov Feb 16 '17 at 0:50
  • 1
    $\begingroup$ The complexity of standard expm implementations is $O(n^3)$, not $n^2$. $\endgroup$ – Federico Poloni Feb 19 '17 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.