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.


Year:
2016-07
Publisher:
Écublens, MATHICSE
Note:
MATHICSE Technical Report Nr. 23 .2016 July 2016
Laboratories:




 Record created 2019-10-11, last modified 2019-12-05

Version 1:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)