Exponential of large matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T07:16:02Z http://mathoverflow.net/feeds/question/26261 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26261/exponential-of-large-matrices Exponential of large matrices Xodarap 2010-05-28T13:18:00Z 2011-06-23T05:24:42Z <p>I want to make a diffusion kernel, which involves $e^{\beta A}$, where A is a large matrix (25k by 25k). It is an adjacency matrix, so it's symmetric and very sparse.</p> <p>Does anyone have a recommendation of a tool to solve this? I use the term "tool" loosely - if you know that transforming it in this way first or whatever is useful then I'd like to know that.</p> http://mathoverflow.net/questions/26261/exponential-of-large-matrices/26275#26275 Answer by John D. Cook for Exponential of large matrices John D. Cook 2010-05-28T15:20:16Z 2010-05-28T15:20:16Z <p>If your matrix is diagonalizable, say A = PDP^-1, then exp(A) = P exp(D) P^-1. If your matrix is not diagonalizable and you need the more general Jordon Canonical Form, this approach may not work. JCF is not suitable for numerical computation since it forming the JCF is a discontinuous process: arbitrarily close matrices can map to canonical forms that differ by an integer in one entry.</p> <p>You could calculate Exp(A) directly by its Taylor series. Then the problem becomes how to efficiently calculate powers of A. Maybe you could take advantage of your particular sparsity structure to calculate these powers.</p> http://mathoverflow.net/questions/26261/exponential-of-large-matrices/26323#26323 Answer by Xodarap for Exponential of large matrices Xodarap 2010-05-28T23:39:47Z 2010-05-28T23:39:47Z <p>I am going with a hack - since the kernel "diffuses" relatively quickly, I just take only the neighbourhood around the two vertices that I want. This gives me a much reduced adjacency matrix which I can then raise e to without difficulty. </p> <p>I'm not familiar enough with the kernel function though to know how severely this is screwing up my results, and it's imperfect at best, so I'm still interested if anyone has a better idea.</p> http://mathoverflow.net/questions/26261/exponential-of-large-matrices/26371#26371 Answer by Chris Godsil for Exponential of large matrices Chris Godsil 2010-05-29T17:58:46Z 2010-05-29T17:58:46Z <p>This is not an answer, but it's too long for a comment. First, you need advice from a numerical analyst, not me. Computing matrix exponentials is a well-studied problem with a large literature. For one example, the recent book by Higham "Functions of matrices. Theory and computation" devotes a chapter to it. Matlab has a builtin routine for it.</p> <p>The trick will be to take advantage of the sparseness, which almost certainly rules out an approach based on diagonalization. Taylor series are not likely to help---try computing $\exp(100)$ using the series expansion about $0$.</p> <p>Also, just because you can write down the problem you want to solve using a matrix exponential, does not guarantee this is the best way to solve it. (To give a crude example, the solution to the linear system $Ax=b$ is $A^{-1}b$, but no-one in their right mind solves linear systems by computing inverses.)</p> http://mathoverflow.net/questions/26261/exponential-of-large-matrices/68483#68483 Answer by Glynne for Exponential of large matrices Glynne 2011-06-22T05:24:11Z 2011-06-22T05:24:11Z <p>Suprised that no one mentioned Expokit, <a href="http://www.maths.uq.edu.au/expokit/" rel="nofollow">http://www.maths.uq.edu.au/expokit/</a> It does exactly what was requested, and is available in several different implementations (including Matlab).</p> http://mathoverflow.net/questions/26261/exponential-of-large-matrices/68535#68535 Answer by Federico Poloni for Exponential of large matrices Federico Poloni 2011-06-22T16:48:35Z 2011-06-22T16:48:35Z <p>The book by Higham and the "nineteen dubious ways" paper deal with the dense case only. For the sparse case, the best way to go is using an algorithm that computes the so-called <em>action</em>, i.e., the map $v \mapsto \exp(A)v$. See e.g. Al-Mohy, <a href="http://epubs.siam.org/sisc/resource/1/sjoce3/v33/i2/p488_s1?isAuthorized=no" rel="nofollow">http://epubs.siam.org/sisc/resource/1/sjoce3/v33/i2/p488_s1?isAuthorized=no</a>.</p> <p>The matrix $\exp(A)$ itself is full and unstructured, and generally you do not want to use it. If you really need it, though, check out a series of papers by Benzi and coauthors: they show that the off-diagonal elements of many matrix functions decay exponentially, and thus your matrix might be "nearly banded".</p> http://mathoverflow.net/questions/26261/exponential-of-large-matrices/68587#68587 Answer by Nilima Nigam for Exponential of large matrices Nilima Nigam 2011-06-23T05:24:42Z 2011-06-23T05:24:42Z <p>I've asked for some clarification in a comment. In the meanwhile, if you're looking for software, I'll assume you've tried PETSc or Trilinos already? Here's a link to the freeware by Jiri Pittner, which links to BLAS routines as well: <a href="http://www.pittnerovi.com/la/" rel="nofollow">http://www.pittnerovi.com/la/</a></p> <p>Here's a site from INRIA <a href="http://verdandi.gforge.inria.fr/doc/linear_algebra_libraries.pdf" rel="nofollow">http://verdandi.gforge.inria.fr/doc/linear_algebra_libraries.pdf</a></p>