×

A new investigation of the extended Krylov subspace method for matrix function evaluations. (English) Zbl 1240.65154

Summary: For large square matrices \(A\) and functions \(f\), the numerical approximation of the action of \(f(A)\) to a vector \(v\) has received considerable attention in the last two decades. In this paper, we investigate the extended Krylov subspace method, a technique that was recently proposed to approximate \(f(A)v\) for \(A\) symmetric. We provide a new theoretical analysis of the method, which improves the original result for \(A\) symmetric, and gives a new estimate for \(A\) nonsymmetric. Numerical experiments confirm that the new error estimates correctly capture the linear asymptotic convergence rate of the approximation. By using recent algorithmic improvements, we also show that the method is computationally competitive with respect to other enhancement techniques.

MSC:

65F60 Numerical computation of matrix exponential and similar matrix functions
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Higham, Matrix Functions-Theory and Applications (2008)
[2] Friesner, A method for exponential propagation of large systems of stiff nonlinear differential equations, Journal of Scientific Computing 4 pp 327– (1989)
[3] Puzynin, Magnus-factorized method for numerical solving the time-dependent Schrödinger equation, Computer Physics Communications 126 (1-2) pp 158– (2000) · Zbl 0962.65103
[4] Gallopoulos, Efficient solution of parabolic equations by Krylov approximation methods, SIAM Journal on Scientific and Statistical Computing 13 (5) pp 1236– (1992) · Zbl 0757.65101
[5] Gallopoulos, A parallel block cyclic reduction algorithm for the fast solution of elliptic equations, Parallel Computing 10 pp 143– (1989) · Zbl 0676.65098
[6] Hochbruck, Exponential Runge-Kutta methods for parabolic problems, Applied Numerical Mathematics 53 pp 323– (2005) · Zbl 1070.65099
[7] Hochbruck, Exponential integrators for quantum-classical molecular dynamics, BIT 39 (1) pp 620– (1999) · Zbl 0985.81002
[8] Hochbruck, Exponential integrators for large systems of differential equations, SIAM Journal on Scientific Computing 19 (5) pp 1552– (1998) · Zbl 0912.65058
[9] Borici, Computational methods for UV suppresses fermions, Journal of Computational Physics 189 pp 454– (2003)
[10] Nettesheim, Computational Molecular Dynamics: Challenges, Methods, Ideas pp 396– (1999) · Zbl 0970.81104 · doi:10.1007/978-3-642-58360-5_22
[11] van den Eshof, Numerical methods for the QCD overlap operator. I: sign-function and error bounds, Computer Physics Communications 146 (2) pp 203– (2002) · Zbl 1008.81508
[12] Druskin, New spectral Lanczos decomposition method for induction modeling in arbitrary 3-D geometry, Geophysics 64 (3) pp 701– (1999)
[13] Druskin, Two polynomial methods of calculating functions of symmetric matrices, U.S.S.R. Computational Mathematics and Mathematical Physics 29 pp 112– (1989) · Zbl 0719.65035
[14] Druskin, Krylov subspace approximation of eigenpairs and matrix functions in exact and computer arithmetic, Numerical Linear Algebra with Applications 2 (3) pp 205– (1995) · Zbl 0831.65042
[15] Knizhnerman, Calculation of functions of unsymmetric matrices using Arnoldi’s method, U.S.S.R. Computational Mathematics and Mathematical Physics 31 pp 1– (1991) · Zbl 0774.65021
[16] Saad, Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM Journal on Numerical Analysis 29 pp 209– (1992) · Zbl 0749.65030
[17] Bergamaschi, Efficient computation of the exponential operator for large, sparse, symmetric matrices, Numerical Linear Algebra with Applications 7 (1) pp 27– (2000) · Zbl 0983.65058
[18] Druskin, Extended Krylov subspaces: approximation of the matrix square root and related functions, SIAM Journal on Matrix Analysis and Applications 19 (3) pp 755– (1998) · Zbl 0912.65022
[19] Eiermann, A restarted Krylov subspace method for the evaluation of matrix functions, SIAM Journal on Numerical Analysis 44 (6) pp 2481– (2006) · Zbl 1129.65019
[20] Frommer, Stopping criteria for rational matrix functions of Hermitian and symmetric matrices, SIAM Journal on Scientific Computing 30 (3) pp 1387– (2008) · Zbl 1203.65079
[21] Ilic M, Simpson DP, Turner IW. A restarted Lanczos approximation to functions of a symmetric matrix. Technical Report 8011, Queensland University of Technology, Australia, 2007.
[22] Moret I. Rational Lanczos approximations to the matrix square root and related functions. Technical Report, Dipartimento di Matematica e Informatica, Università degli Studi di Trieste, Trieste, Italy, 2005. To appear in Numerical Linear Algebra with Applications.
[23] Moret, An interpolatory approximation of the matrix exponential based on Faber polynomials, Journal of Computational and Applied Mathematics 131 pp 361– (2001) · Zbl 0983.65057
[24] Moret, RD-rational approximations of the matrix exponential, BIT 44 (3) pp 595– (2004) · Zbl 1075.65062
[25] Popolizio, Acceleration techniques for approximating the matrix exponential operator, SIAM Journal on Matrix Analysis and Applications 30 (2) pp 657– (2008) · Zbl 1168.65021
[26] Trefethen, Talbot quadratures and rational approximations, BIT 46 (3) pp 653– (2006) · Zbl 1103.65030
[27] Simoncini, A new iterative method for solving large-scale Lyapunov matrix equations, SIAM Journal on Scientific Computing 29 (3) pp 1268– (2007) · Zbl 1146.65038
[28] Frommer A. Monotone convergence of the Lanczos approximations to matrix functions of Hermitian matrices. Technical Report, Fachbereich Universität, Wuppertal-D, 2008. · Zbl 1190.65063
[29] Popolizio M. Acceleration techniques for approximating the matrix exponential. Ph.D. Thesis, Università degli Studi di Bari, March 2008. · Zbl 1168.65021
[30] Alpak, An extended Krylov subspace method to simulate single-phase fluid flow phenomena in axisymmetric and anisotropic porous media, Journal of Petroleum Science and Engineering 40 pp 121– (2003)
[31] Nauts, New approach to many state quantum dynamics: the recursive residue generation method, Physical Review Letters 51 pp 2238– (1983)
[32] Tal-Ezer, Spectral methods in time for parabolic problems, SIAM Journal on Numerical Analysis 26 pp 1– (1989) · Zbl 0668.65090
[33] Horn, Topics in Matrix Analysis (1991) · Zbl 0729.15001 · doi:10.1017/CBO9780511840371
[34] Druskin, Using nonorthogonal Lanczos vectors in the computation of matrix functions, SIAM Journal on Scientific Computing 19 (1) pp 38– (1998) · Zbl 0912.65021
[35] van den Eshof, Preconditioning Lanczos approximations to the matrix exponential, SIAM Journal on Scientific Computing 27 (4) pp 1438– (2006) · Zbl 1105.65051
[36] Druskin, On monotonicity of the Lanczos approximation to the matrix exponential, Linear Algebra and its Applications 429 (7) pp 1679– (2008) · Zbl 1166.65017
[37] Druskin, Spectral approach to solving three-dimensional Maxwell’s diffusion equations in the time and frequency domains, Radio Science 29 (4) pp 937– (1994)
[38] Suetin, Analytical Methods and Special Functions (1998) · Zbl 0937.41009
[39] Crouzeix, Numerical range and numerical calculus in Hilbert space, Journal of Functional Analysis 244 pp 668– (2007) · Zbl 1116.47004
[40] Beckermann, Image numérique, GMRES et polynômes de Faber, Comptes Rendus Mathematique, Académie de Science Paris, Series I 340 pp 855– (2005) · Zbl 1076.47004 · doi:10.1016/j.crma.2005.04.027
[41] Beckermann B, Reichel L. Error estimation and evaluation of matrix functions via the Faber transform. Manuscript, December 2008. · Zbl 1204.65041
[42] Gustafson, Numerical Range: The Field of Values of Linear Operators and Matrices (1977)
[43] Higham NJ. The Matrix Computation Toolbox. Available from: http://www.ma.man.ac.uk/higham/mctoolbox.
[44] Driscoll, Algorithm 756: a MATLAB toolbox for Schwarz-Christoffel mapping, ACM Transactions on Mathematical Software 22 (2) pp 168– (1996) · Zbl 0884.30005
[45] Faber, The polynomial numerical hulls of Jordan blocks and related matrices, Linear Algebra and its Applications 374 pp 231– (2003) · Zbl 1044.15019
[46] Knizhnerman, Adaptation of the Lanczos and Arnoldi methods to the spectrum, or why the two Krylov subspace methods are powerful, Chebyshev Digest ( in Russian: Chebyshyovsky Sbornik) 3 (2) pp 141– (2002) · Zbl 1106.65030
[47] The MathWorks, Inc. MATLAB 7, September 2004.
[48] Diele, Error estimates for polynomial Krylov approximations to matrix functions, SIAM Journal on Matrix Analysis and Applications 30 (4) pp 1546– (2008) · Zbl 1176.65057
[49] Petrushev, Rational Approximation of Real Functions (1987)
[50] Matrix Market. A visual repository of test data for use in comparative studies of algorithms for numerical linear algebra, Mathematical and Computational Sciences Division, National Institute of Standards and Technology. Available Online at: http://math.nist.gov/MatrixMarket.
[51] Borici, Proceedings of the Third International Workshop on Numerical Analysis and Lattice QCD pp 201– (2005) · Zbl 1066.81001 · doi:10.1007/3-540-28504-0
[52] Simoncini, Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM Journal on Scientific Computing 25 (2) pp 454– (2003) · Zbl 1048.65032
[53] Lopez, Analysis of projection methods for rational function approximation to the matrix exponential, SIAM Journal on Numerical Analysis 44 (2) pp 613– (2006) · Zbl 1158.65031
[54] Sonneveld, IDR(s): a family of simple and fast algorithms for solving large nonsymmetric linear systems, SIAM Journal on Scientific Computing 31 (2) pp 1035– (2008) · Zbl 1190.65053
[55] Boyle J, Mihajlovic MD, Scott JA. HSL_MI20: an efficient AMG preconditioner. Technical Report RAL-TR-2007-021, Rutherford Appleton Laboratory, Chilton, England, 2007.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.