If your matrix is diagonalizable, say A = PDP^-1$A = PDP^-1$, then exp(A) = P exp(D) P^-1$\exp(A) = P \exp(D) P^-1$. If your matrix is not diagonalizable and you need the more general JordonJordan 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.
You could calculate Exp(A)$\exp(A)$ directly by its Taylor series. Then the problem becomes how to efficiently calculate powers of A$A$. Maybe you could take advantage of your particular sparsity structure to calculate these powers.