  The computation of the matrix exponential is a ubiquitous operation in
numerical mathematics, and for a general, unstructured $n\times n$ matrix it
can be computed in $\mathcal{O}(n^3)$ operations. An interesting problem arises
if the input matrix is a Toeplitz matrix, for example as the result of
discretizing integral equations with a time invariant kernel. In this case it
is not obvious how to take advantage of the Toeplitz structure, as the
exponential of a Toeplitz matrix is, in general, not a Toeplitz matrix itself.
The main contribution of this work are fast algorithms for the computation of
the Toeplitz matrix exponential. The algorithms have provable quadratic
complexity if the spectrum is real, or sectorial, or more generally, if the
imaginary parts of the rightmost eigenvalues do not vary too much. They may be
efficient even outside these spectral constraints. They are based on the
scaling and squaring framework, and their analysis connects classical results
from rational approximation theory to matrices of low displacement rank. As an
example, the developed methods are applied to Merton's jump-diffusion model for
option pricing.
