MATHICSE Technical Report : Fast computation of the matrix exponential for a Toeplitz matrix

The computation of the matrix exponential is a ubiquitous operation in numerical mathematics, and for a general, unstructured n×n matrix it can be computed in O(n3) 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 is an algorithm of quadratic complexity for the computation of the Toeplitz matrix exponential. It is based on the scaling and squaring framework, and 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.