On Krylov Subspace Approximations to the Matrix Exponential Operator
Open accessThe DOI matches its Crossref record; 29 of the 30 references it cites were found in a registry or an index, and 1 are not checked yet.
Abstract
Krylov subspace methods for approximating the action of matrix exponentials are analyzed in this paper. We derive error bounds via a functional calculus of Arnoldi and Lanczos methods that reduces the study of Krylov subspace approximations of functions of matrices to that of linear systems of equations. As a side result, we obtain error bounds for Galerkin-type Krylov methods for linear equations, namely, the biconjugate gradient method and the full orthogonalization method. For Krylov approximations to matrix exponentials, we show superlinear error decay from relatively small iteration numbers onwards, depending on the geometry of the numerical range, the spectrum, or the pseudospectrum. The convergence to exp$(\tau A)v$ is faster than that of corresponding Krylov methods for the solution of linear equations $(I-\tau A)x=v$, which usually arise in the numerical solution of stiff ordinary differential equations (ODEs). We therefore propose a new class of time integration methods for large systems of nonlinear differential equations which use Krylov approximations to the exponential function of the Jacobian instead of solving linear or nonlinear systems of equations in every time step.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Analogous to the eigenvalue problem in DMRG, both Eqs. ( 7) and ( 8) can be integrated using a Lanczos scheme [28] in order to keep the computational cost at O(D 3 ).”
From Unifying time evolution and optimization with matrix product states (2016) · cites this paper as [28]
Citations
Cites
Solving Ordinary Differential Equations II
Hairer, E., & Wanner, G. (1996) · Springer Series in Computational Mathematics · doi:10.1007/978-3-642-05221-7 · Cited by 4,342
Solving Ordinary Differential Equations II
Hairer, E., & Wanner, G. (1991) · Springer Series in Computational Mathematics · doi:10.1007/978-3-662-09947-6 · Cited by 1,456
Theory of Functions of a Complex Variable
Markushevich, A. I., Silverman, R. A., & Gillis, J. (1966) · Physics Today · doi:10.1063/1.3048359 · Cited by 1,211
Unitary quantum time evolution by iterative Lanczos reduction
Park, T. J., & Light, J. C. (1986) · The Journal of Chemical Physics · doi:10.1063/1.451548 · Cited by 888
Uniform Numerical Methods for Problems with Initial and Boundary Layers.
Berger, A. E., Doolan, E. P., Miller, J. J. H., & Schilders, W. H. A. (1982) · Mathematics of Computation · doi:10.2307/2007353 · Cited by 754
Analysis of Some Krylov Subspace Approximations to the Matrix Exponential Operator
Saad, Y. (1992) · SIAM Journal on Numerical Analysis · doi:10.1137/0729014 · Cited by 670
Numerical Ranges of Operators on Normed Spaces and of Elements of Normed Algebras
Bonsall, F. F., & Duncan, J. (1971) · Cambridge University Press eBooks · doi:10.1017/cbo9781107359895 · Cited by 614
Propagation Methods for Quantum Molecular Dynamics
Kosloff, R. (1994) · Annual Review of Physical Chemistry · doi:10.1146/annurev.pc.45.100194.001045 · Cited by 602
Krylov subspace methods for solving large unsymmetric linear systems
Saad, Y. (1981) · Mathematics of Computation · doi:10.1090/s0025-5718-1981-0616364-6 · Cited by 449
Generalized Runge-Kutta Processes for Stable Systems with Large Lipschitz Constants
Lawson, J. D. (1967) · SIAM Journal on Numerical Analysis · doi:10.1137/0704033 · Cited by 328
Efficient Solution of Parabolic Equations by Krylov Approximation Methods
Gallopoulos, E., & Saad, Y. (1992) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0913071 · Cited by 320
An Implementation of the Look-Ahead Lanczos Algorithm for Non-Hermitian Matrices
Freund, R. W., Gutknecht, M. H., & Nachtigal, N. M. (1993) · SIAM Journal on Scientific Computing · doi:10.1137/0914009 · Cited by 304
New Approach to Many-State Quantum Dynamics: The Recursive-Residue-Generation Method
Nauts, A., & Wyatt, R. E. (1983) · Physical Review Letters · doi:10.1103/physrevlett.51.2238 · Cited by 267
Convergence of Iterations for Linear Equations
Nevanlinna, O. (1993) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-8547-8 · Cited by 257
Spectral Methods in Time for Hyperbolic Equations
Tal-Ezer, H. (1986) · SIAM Journal on Numerical Analysis · doi:10.1137/0723002 · Cited by 183
Matrix-Free Methods for Stiff Systems of ODE’s
Brown, P. N., & Hindmarsh, A. C. (1986) · SIAM Journal on Numerical Analysis · doi:10.1137/0723039 · Cited by 175
Two polynomial methods of calculating functions of symmetric matrices
Druskin, V. L., & Knizhnerman, L. A. (1989) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/s0041-5553(89)80020-5 · Cited by 172
Van Der Vorst, H. A. (1987) · Journal of Computational and Applied Mathematics · doi:10.1016/0377-0427(87)90020-3 · Cited by 167
Spectral Methods in Time for Parabolic Problems
Tal‐Ezer, H. (1989) · SIAM Journal on Numerical Analysis · doi:10.1137/0726001 · Cited by 143
A method for exponential propagation of large systems of stiff nonlinear differential equations
Friesner, R. A., Tuckerman, L. S., Dornblaser, B. C., & Russo, T. (1989) · Journal of Scientific Computing · doi:10.1007/bf01060992 · Cited by 116
Iterative Solution of Linear Equations in ODE Codes
Gear, C. W., & Saad, Y. (1983) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0904040 · Cited by 115
Krylov subspace approximation of eigenpairs and matrix functions in exact and computer arithmetic
Druskin, V. L., & Knizhnerman, L. (1995) · Numerical Linear Algebra with Applications · doi:10.1002/nla.1680020303 · Cited by 113
On faber polynomials and faber expansions
K�vari, T., & Pommerenke, C. (1967) · Mathematische Zeitschrift · doi:10.1007/bf01112450 · Cited by 87
Linear-implizite Runge-Kutta-Methoden und ihre Anwendung
Strehmel, K., & Weiner, R. (1992) · Teubner-Texte zur Mathematik · doi:10.1007/978-3-663-10673-9 · Cited by 79
Polynomial approximation of functions of matrices and applications
Tal‐Ezer, H. (1989) · Journal of Scientific Computing · doi:10.1007/bf01061265 · Cited by 47
On semiiterative methods generated by Faber polynomials
Eiermann, M. (1989) · Numerische Mathematik · doi:10.1007/bf01409782 · Cited by 45
Matrix-free W-methods using a multiple Arnoldi iteration
Schmitt, B. A., & Weiner, R. (1995) · Applied Numerical Mathematics · doi:10.1016/0168-9274(95)00060-8 · Cited by 34
Error Analysis of Krylov Methods In a Nutshell
Hochbruck, M., & Lubich, C. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827595290450 · Cited by 31
Self-citationNumerical ranges and stability estimates
Spijker, M. N. (1993) · Applied Numerical Mathematics · doi:10.1016/0168-9274(93)90146-i · Cited by 28
A Convergence Analysis for Nonsymmetric Lanczos Algorithms
Ye, Q. (1991) · Mathematics of Computation · doi:10.1090/s0025-5718-1991-1068826-4 · Cited by 25
Research works printed but not linked: 5
- A. Friedli, Verallgemeinerte Runge‐Kutta Verfahren zur Lösung steifer Differentialgleichungen , in Lecture Notes in Mathematics 631, Springer‐Verlag, Berlin, 1978, pp. 35–50. · doi:10.1007/bfb0067462
- Hochbruck M., 1997, SIAM J. Sci. Comput., 18
- Knizhnerman L. A., 1991, Comput. Math. and Math. Phys., 31, 1
- Knizhnerman L. A., 1992, Comput. Math. and Math. Phys., 32, 1199
- D. R. Taylor, Analysis of the look‐ahead Lanczos algorithm , Ph.D. thesis, University of California at Berkeley, Berkeley, CA, 1982.
Cited by
Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
Moler, C., & Van Loan, C. (2003) · SIAM Review · doi:10.1137/s00361445024180 · Cited by 2,357
Continuous-time Monte Carlo methods for quantum impurity models
Gull, E., Millis, A. J., Lichtenstein, A. I., Rubtsov, A. N., Troyer, M., & Werner, P. (2011) · Reviews of Modern Physics · doi:10.1103/revmodphys.83.349 · Cited by 1,546
“(Hochbruck and Lubich, 1997) it has been shown rigorously that these Krylov space algorithms converge rapidly as a function of Niter, typically reaching convergence for very small iteration numbers p ≪ Ndim, although the number of iterations depends on the time interval τ .”
BackgroundThe Magnus expansion and some of its applications
Blanes, S., Casas, F., Oteo, J. A., & Ros, J. (2009) · Physics Reports · doi:10.1016/j.physrep.2008.11.001 · Cited by 1,157
“More details are contained in the references [103,105,106].”
BackgroundResultHochbruck, M., & Ostermann, A. (2010) · Acta Numerica · doi:10.1017/s0962492910000048 · Cited by 1,061
Self-citationUnifying time evolution and optimization with matrix product states
Haegeman, J., Lubich, C., Oseledets, I., Vandereycken, B., & Verstraete, F. (2016) · Physical Review B · doi:10.1103/physrevb.94.165116 · Cited by 804
Self-citation
Metadata
- Authors
- Hochbruck, M., & Lubich, C.
- Affiliations
- University of Tübingen (DE)
- Venue
- SIAM Journal on Numerical Analysis
- Published
- 1997-10
- Volume
- 34
- Issue
- 5
- Pages
- 1911-1925
- ISSN
- 0036-1429 (ISSN-L)
- 1095-7170
- OpenAlex
- W1984347942
- Cited by
- 795
- References
- 30
- Citations by year
- 2026: 27 · 2025: 23 · 2024: 19 · 2023: 23 · 2022: 23 · 2021: 37 · 2020: 42 · 2019: 41 · 2018: 46 · 2017: 41 · 2016: 42 · 2015: 32 · 2014: 44 · 2013: 44 · 2012: 30
- FWCI
- 14.18
- Type
- journal article
- Language
- en
- Open access
- green
- doi.org
- Licence
- other-oa
- Locations
- SIAM Journal on Numerical Analysis (publishedVersion)
- Repository KITopen (Karlsruhe Institute of Technology) (publishedVersion)
- KITopen (other-oa)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Mathematics › Numerical Analysis › Numerical Solvers for Ordinary Differential Equations
- Physical Sciences › Engineering › Computational Mechanics › Advanced Numerical Methods in Computational Mathematics
- Keywords
- matrix exponential, Krylov subspace methods, Arnoldi method, Lanczos method, functional calculus, error bounds, biconjugate gradient method, numerical range, pseudospectra, superlinear convergence, stiff ordinary differential equations, time integration methods, nonlinear differential equations, Jacobian matrix
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.