Fast computation of the matrix exponential for a Toeplitz matrix
From MaRDI portal
Abstract: The computation of the matrix exponential is a ubiquitous operation in numerical mathematics, and for a general, unstructured matrix it can be computed in 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.
Recommendations
- On the exponential of semi-infinite quasi-Toeplitz matrices
- Shift-invert Lanczos method for the symmetric positive semidefinite Toeplitz matrix exponential.
- Fast exponential time integration scheme for option pricing with jumps.
- Incremental computation of block triangular matrix exponentials with application to option pricing
- Shift-invert Arnoldi approximation to the Toeplitz matrix exponential
Cites work
- \texttt{smt}: A Matlab toolbox for structured matrices
- A fast solver for linear systems with displacement structure
- A Fast Stable Solver for Nonsymmetric Toeplitz and Quasi-Toeplitz Systems of Linear Equations
- A Look-Ahead Block Schur Algorithm for Toeplitz-Like Matrices
- A Spectral Order Method for Inverting Sectorial Laplace Transforms
- A superfast structured solver for Toeplitz linear systems via randomized sampling
- Algebraic methods for Toeplitz-like matrices and operators
- Computations with Gohberg-Semencul-type formulas for Toeplitz matrices
- Computing the exponential of large block-triangular block-Toeplitz matrices encountered in fluid queues
- Decreasing the Displacement Rank of a Matrix
- Displacement Structure: Theory and Applications
- Efficient solution of a partial integro-differential equation in finance
- Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
- Finite difference methods in financial engineering. A partial differential approach. With CD-ROM
- Functions of Matrices
- Generalized Displacement Structure for Block-Toeplitz, Toeplitz-Block, and Toeplitz-Derived Matrices
- scientific article; zbMATH DE number 4051976 (Why is no real title available?)
- scientific article; zbMATH DE number 1350351 (Why is no real title available?)
- scientific article; zbMATH DE number 778080 (Why is no real title available?)
- On Krylov Subspace Approximations to the Matrix Exponential Operator
- Option pricing when underlying stock returns are discontinuous
- Preconditioned Lanczos Methods for the Minimum Eigenvalue of a Symmetric Positive Definite Toeplitz Matrix
- Rational Krylov approximation of matrix functions: numerical methods and optimal pole selection
- Scaled and squared subdiagonal Padé approximation for the matrix exponential
- Shift-invert Arnoldi approximation to the Toeplitz matrix exponential
- Stable and Efficient Algorithms for Structured Systems of Linear Equations
- Structured matrices in mathematics, computer science, and engineering I. Proceedings of an AMS-IMS-SIAM joint summer research conference, University of Colorado, Boulder, CO, USA, June 27--July 1, 1999
- Templates for the Solution of Algebraic Eigenvalue Problems
- The exponentially convergent trapezoidal rule
- The scaling and squaring method for the matrix exponential revisited
Cited in
(20)- Circulant preconditioners for analytic functions of Toeplitz matrices
- On the exponential of semi-infinite quasi-Toeplitz matrices
- Fast transforms of Toeplitz matrices
- \(O(n\log^ 2n)\) determinant computation of a Toeplitz matrix and fast variance estimation
- Band-times-circulant preconditioners for non-symmetric Toeplitz systems
- On the rational approximation of Markov functions, with applications to the computation of Markov functions of Toeplitz matrices
- Incremental computation of block triangular matrix exponentials with application to option pricing
- Optimality of the Paterson-Stockmeyer method for evaluating matrix polynomials and rational matrix functions
- Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox
- Computing the exponential of large block-triangular block-Toeplitz matrices encountered in fluid queues
- Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes
- High-performance computation of the exponential of a large sparse matrix
- Divide-and-conquer methods for functions of matrices with banded or hierarchical low-rank structure
- Efficient Computation of the Matrix Exponential by Generalized Polar Decompositions
- Matrix Structures and Matrix Functions
- Speeding Up Krylov Subspace Methods for Computing \(\boldsymbol{{f}(A){b}}\) via Randomization
- Fast matrix exponential-based quasi-boundary value methods for inverse space-dependent source problems
- Consensus-based distributed solution algorithms for linear equations with block Toeplitz structures
- Tensor product factorization-based numerical algorithms for the inverses of generalized banded Toeplitz matrices
- Some acceleration techniques for calculating the eigenvalues of normal Toeplitz matrices
This page was built for publication: Fast computation of the matrix exponential for a Toeplitz matrix
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3130420)
