7
$\begingroup$

We have diagonal matrices $A = \mbox{diag} (\lambda_1, \ldots, \lambda_n)$ for which matrix exponential has simple form $e^A = \mbox{diag} (e^{\lambda_1}, \ldots, e^{\lambda_n})$, and it can be computed with $\mathcal{O}(n)$ time complexity.

There are general algorithms for computing matrix exponential for general matrix, such as Pade Approximation, but they work cubic time in size of a square matrix.

I'm interested in finding classes of square matrices for which matrix exponential can be computed not harder than $\mathcal{O}(n^2)$ complexity. Is there any structured matrices that has this property?

Any literature/articles suggestions will be appreciated.

$\endgroup$

2 Answers 2

9
$\begingroup$

Nilpotent matrices

For example, if $\mathrm A \neq \mathrm O_n$ and $\mathrm A^2 = \mathrm O_n$, then $\mathrm A^k = \mathrm O_n$ for all $k \geq 2$ and

$$\exp(\mathrm A) = \mathrm I_n + \mathrm A + \dfrac{1}{2!} \mathrm A^2 + \dfrac{1}{3!} \mathrm A^3 + \dfrac{1}{4!} \mathrm A^4 + \cdots = \mathrm I_n + \mathrm A$$


Idempotent matrices

For example, if $\mathrm A^2 = \mathrm A$, then $\mathrm A^k = \mathrm A$ for all $k \geq 1$ and

$$\begin{array}{rl} \exp(\mathrm A) &= \mathrm I_n + \mathrm A + \dfrac{1}{2!} \mathrm A^2 + \dfrac{1}{3!} \mathrm A^3 + \dfrac{1}{4!} \mathrm A^4 + \cdots\\\\ &= \mathrm I_n + \left(1 + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \cdots \right) \mathrm A\\\\ &= \mathrm I_n + (e - 1) \mathrm A\end{array}$$

Projection matrices are idempotent.


Involutory matrices

If $\mathrm A$ is involutory, then $\mathrm A^2 = \mathrm I_n$ and, thus,

$$\mathrm A^k = \begin{cases} \mathrm I_n & \text{if } k \text{ is even}\\\\ \mathrm A & \text{if } k \text{ is odd}\end{cases}$$

Hence,

$$\begin{array}{rl} \exp(\mathrm A) &= \mathrm I_n + \mathrm A + \dfrac{1}{2!} \mathrm A^2 + \dfrac{1}{3!} \mathrm A^3 + \dfrac{1}{4!} \mathrm A^4 + \cdots\\\\ &= \mathrm I_n + \mathrm A + \dfrac{1}{2!} \mathrm I_n + \dfrac{1}{3!} \mathrm A + \dfrac{1}{4!} \mathrm I_n + \cdots\\\\ &= \left(1 + \frac{1}{2!} + \frac{1}{4!} + \cdots \right) \mathrm I_n + \left(1 + \frac{1}{3!} + \frac{1}{5!} + \cdots \right) \mathrm A\\\\ &= \cosh (1) \, \mathrm I_n + \sinh (1) \, \mathrm A\end{array}$$

$\endgroup$
11
  • 2
    $\begingroup$ Another particularly interesting case is $\mathrm A^2=-\mathrm I$, so that $e^{\mathrm A}=\cos(1) \mathrm I + \sin(1)\mathrm A$. $\endgroup$
    – lisyarus
    Commented Aug 1, 2016 at 12:44
  • 2
    $\begingroup$ All these examples could be summed up in : If you know the characteristic polynomial, then you are in business. If you don't know the characteristic polynomial, you are in trouble, because it costs n^3 to compute it $\endgroup$
    – user145413
    Commented Aug 1, 2016 at 12:51
  • $\begingroup$ @lisyarus Do such matrices have a name? $\endgroup$ Commented Aug 1, 2016 at 13:00
  • $\begingroup$ @username Not necessarily. I don't need to know the characteristic polynomial of a projection matrix to know it is idempotent. Some matrices are given to us, others are constructed by us. $\endgroup$ Commented Aug 1, 2016 at 13:01
  • 2
    $\begingroup$ @RodrigodeAzevedo I'd say that the minimal polynomial can be of help, since it provides a way to express $A^n$ in terms of lower powers of $A$, and leads to a recurrence relation in the coefficients of $e^A$. $\endgroup$
    – lisyarus
    Commented Aug 1, 2016 at 13:11
4
$\begingroup$

Circulant matrices should be able to be exponentiated in less than $n^2$ time. You can diagonalize them via the FFT and then exponentiate the diagonal matrix.

EDIT: I believe strongly non-singular Toeplitz matrices can have their exponentiation well approximated quickly enough by combining the results of

http://www.sciencedirect.com/science/article/pii/0024379589907179

and

http://www.cis.umac.mo/~fsthws/newpapers/abstract/ps091108.pdf

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .