For which classes of matrix can the matrix exponential be easily computed? 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.
 A: 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}$$ 
A: 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
