For which classes of matrix can the matrix exponential be easily computed?

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}$$

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