Efficiently computing $e^{tX}$ for many different values of $t$

Question

Given an anti-Hermitian and sparse matrix $X$, I am using Python (NumPy and SciPy) to compute the matrix exponential $f(t) := e^{tX}$ for  many values of $t$. The method I am currently using is to essentially compute the exponent with the following function:
X = SomeSparseMatrix
def f(t):
    return scipy.sparse.linalg.expm(t * X)

I'm wondering if there is a way to make this faster. For example, if I compute this function once to obtain $e^X$, can I obtain $e^{tX}$ from $e^X$ without having to recompute the exponent?

rpm2718 · Accepted Answer

An anti-Hermitian matrix is diagonalizable, with orthogonal eigenvectors (ref). Hence you can write $X = PDP^{-1}$, where $D$ is a diagonal matrix. Therefore the exponential can be calculated as $e^X=Pe^DP^{-1}$, and $e^{tX} = Pe^{tD}P^{-1}$.
If $d_1$, $d_2$, etc.... are the diagonal elements of $D$, then for each value of $t_i in t$, $e^{t_iD}$ is just a diagonal matrix with elements $e^{t_id_1}$, $e^{t_id_2}$, etc....Now your calculation of the exponential for each value $t_i$ is just reduced to $N$ scalar exponentiations for an $Ntimes N$ matrix $X$.
You still have the task of diagonalizing $X$,but you only have to do it once. If $t$ has $M$ elements, then you also have $2M$ matrix multiplications to do.
So you would be trading $M$ matrix exponentiations for one diagonalization of $X$, as well as $Ncdot M$ scalar exponentiations, and $2M$ matrix multiplications. I don't know what the complexity of matrix exponentiation is, but I think this is likely to be a good trade.
As Daniel Shapero points out in his comment above, if you only need the action of $e^{tX}v$ for some vector $v$ and don't really need the matrix, then you can often save a whole lot of time. That savings is easy to realize with this approach, since $e^{tX}v = Pe^{tD}P^{-1}v=Pe^{tD}(P^{-1}v)$. You only do the $P^{-1}v$ calculation once, and the $Pe^{tD}$ calculations can be done faster than an ordinary matrix multiplication since $e^{t_iD}$ is a diagonal matrix. In this case, the diagonalization is the only thing that scales as $N^3$ (or maybe a bit less, depending on the implementation of the diagonalization), and it is done just once, not once per each point in $t$.

Efficiently computing $e^{tX}$ for many different values of $t$

One Answer

Add your own answers!

Ask a Question