An inexact shift-and-invert Arnoldi algorithm for Toeplitz matrix exponential.
From MaRDI portal
Abstract: We revisit the shift-and-invert Arnoldi method proposed in [S. Lee, H. Pang, and H. Sun. {it Shift-invert Arnoldi approximation to the Toeplitz matrix exponential}, SIAM J. Sci. Comput., 32: 774--792, 2010] for numerical approximation to the product of Toeplitz matrix exponential with a vector. In this approach, one has to solve two large scale Toeplitz linear systems in advance. However, if the desired accuracy is high, the cost will be prohibitive. Therefore, it is interesting to investigate how to solve the Toeplitz systems inexactly in this method. The contribution of this paper is in three regards. First, we give a new stability analysis on the Gohberg-Semencul formula (GSF) and define the GSF condition number of a Toeplitz matrix. It is shown that, when the size of the Toeplitz matrix is large, our result is sharper than the one given in [M. Gutknecht and M. Hochbruck. {it The stability of inversion formulas for Toeplitz matrices}, Linear Algebra Appl., 223/224: 307--324, 1995]. Second, we establish a relation between the error of Toeplitz systems and the residual of Toeplitz matrix exponential. We show that if the GSF condition number of the Toeplitz matrix is medium sized, then the Toeplitz systems can be solved in a low accuracy. Third, based on this relationship, we present a practical stopping criterion for relaxing the accuracy of the Toeplitz systems, and propose an inexact shift-and-invert Arnoldi algorithm for the Toeplitz matrix exponential problem. Numerical experiments illustrate the numerical behavior of the new algorithm, and show the effectiveness of our theoretical results.
Recommendations
- Shift-invert Arnoldi approximation to the Toeplitz matrix exponential
- Shift-invert Lanczos method for the symmetric positive semidefinite Toeplitz matrix exponential.
- An inexact shift-and-invert Arnoldi algorithm for large non-Hermitian generalised Toeplitz eigenproblems
- Double-shift-invert Arnoldi method for computing the matrix exponential
- A shift and invert reorthogonalization Arnoldi algorithm for solving the chemical master equation
Cites work
- 2-norm error bounds and estimates for Lanczos approximations to linear systems and rational matrix functions
- A Block Algorithm for Matrix 1-Norm Estimation, with an Application to 1-Norm Pseudospectra
- Accuracy and Stability of Numerical Algorithms
- An Estimate for the Condition Number of a Matrix
- An inexact shift-and-invert Arnoldi algorithm for large non-Hermitian generalised Toeplitz eigenproblems
- An Introduction to Iterative Toeplitz Solvers
- An Optimal Circulant Preconditioner for Toeplitz Systems
- Analysis of Some Krylov Subspace Approximations to the Matrix Exponential Operator
- Condition Estimates
- Conjugate Gradient Methods for Toeplitz Systems
- Exponential time integration and Chebychev discretisation schemes for fast pricing of options
- Fast Preconditioned Conjugate Gradient Algorithms for Wiener–Hopf Integral Equations
- Functions of Matrices
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- scientific article; zbMATH DE number 2118874 (Why is no real title available?)
- Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
- On a method for solving an integral equation in the displacement contact problem.
- Option pricing when underlying stock returns are discontinuous
- Preconditioning Lanczos Approximations to the Matrix Exponential
- RD-rational approximations of the matrix exponential
- Residual, restarting, and Richardson iteration for the matrix exponential
- Shift-invert Arnoldi approximation to the Toeplitz matrix exponential
- Shift-invert Lanczos method for the symmetric positive semidefinite Toeplitz matrix exponential.
- The stability of inversion formulas for Toeplitz matrices
Cited in
(13)- A shifted block FOM algorithm with deflated restarting for matrix exponential computations
- On the exponential of semi-infinite quasi-Toeplitz matrices
- A Gohberg-Semencul type formula for the inverse of conjugate-Toeplitz matrix and applications
- Double-shift-invert Arnoldi method for computing the matrix exponential
- A shift and invert reorthogonalization Arnoldi algorithm for solving the chemical master equation
- Inexact rational Krylov method for evolution equations
- A note on the structured perturbation analysis for the inversion formula of Toeplitz matrices
- The stability of formulae of the Gohberg-Semencul-Trench type for Moore-Penrose and group inverses of Toeplitz matrices
- Shift-invert Lanczos method for the symmetric positive semidefinite Toeplitz matrix exponential.
- Shift-invert Arnoldi approximation to the Toeplitz matrix exponential
- An inexact shift-and-invert Arnoldi algorithm for large non-Hermitian generalised Toeplitz eigenproblems
- A note on the paper ``A note on inversion of Toeplitz matrices by X.-G. Lv and T.-Z. Huang
- Inexact shift-invert Arnoldi method for evolution equations
This page was built for publication: An inexact shift-and-invert Arnoldi algorithm for Toeplitz matrix exponential.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3466267)
