×

Computable upper error bounds for Krylov approximations to matrix exponentials and associated \(\varphi\)-functions. (English) Zbl 1432.65053

Summary: An a posteriori estimate for the error of a standard Krylov approximation to the matrix exponential is derived. The estimate is based on the defect (residual) of the Krylov approximation and is proven to constitute a rigorous upper bound on the error, in contrast to existing asymptotical approximations. It can be computed economically in the underlying Krylov space. In view of time-stepping applications, assuming that the given matrix is scaled by a time step, it is shown that the bound is asymptotically correct (with an order related to the dimension of the Krylov space) for the time step tending to zero. This means that the deviation of the error estimate from the true error tends to zero faster than the error itself. Furthermore, this result is extended to Krylov approximations of \(\varphi\)-functions and to improved versions of such approximations. The accuracy of the derived bounds is demonstrated by examples and compared with different variants known from the literature, which are also investigated more closely. Alternative error bounds are tested on examples, in particular a version based on the concept of effective order. For the case where the matrix exponential is used in time integration algorithms, a step size selection strategy is proposed and illustrated by experiments.

MSC:

65F60 Numerical computation of matrix exponential and similar matrix functions
15A16 Matrix exponential and similar functions of matrices
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Afanasjew, M.; Eiermann, M.; Ernst, O.; Güttel, S., Implementation of a restarted Krylov subspace method for the evaluation of matrix functions, Linear Algebra Appl., 429, 10, 2293-2314 (2008) · Zbl 1153.65042 · doi:10.1016/j.laa.2008.06.029
[2] Al-Mohy, Ah; Higham, Nj, Computing the action of the matrix exponential, with an application to exponential integrators, SIAM J. Sci. Comput., 33, 2, 488-511 (2011) · Zbl 1234.65028 · doi:10.1137/100788860
[3] Auzinger, W.; Koch, O.; Thalhammer, M., Defect-based local error estimators for splitting methods, with application to Schrödinger equations, Part II: higher-order methods for linear problems, J. Comput. Appl. Math., 255, 384-403 (2013) · Zbl 1291.65282 · doi:10.1016/j.cam.2013.04.043
[4] Beckermann, B.; Reichel, L., Error estimation and evaluation of matrix functions via the Faber transform, SIAM J. Numer. Anal., 47, 3849-3883 (2009) · Zbl 1204.65041 · doi:10.1137/080741744
[5] Blanes, S.; Moan, Pc, Fourth- and sixth-order commutator-free Magnus integrators for linear and non-linear dynamical systems, Appl. Numer. Math., 56, 1519-1537 (2005) · Zbl 1103.65129 · doi:10.1016/j.apnum.2005.11.004
[6] Blanes, S.; Casas, F.; Oteo, Ja; Ros, J., The Magnus expansion and some of its applications, Phys. Rep., 470, 151-238 (2008) · doi:10.1016/j.physrep.2008.11.001
[7] Botchev, M.; Grimm, V.; Hochbruck, M., Residual, restarting and Richardson iteration for the matrix exponential, SIAM J. Sci. Comput., 35, A1376-A1397 (2013) · Zbl 1278.65052 · doi:10.1137/110820191
[8] Braconnier, T.; Langlois, P.; Rioual, J., The influence of orthogonality on the Arnoldi method, Linear Algebra Appl., 309, 1, 307-323 (2000) · Zbl 0948.65034 · doi:10.1016/S0024-3795(99)00100-7
[9] Celledoni, E.; Moret, I., A Krylov projection method for systems of ODEs, Appl. Numer. Math., 24, 365-378 (1997) · Zbl 0885.65073 · doi:10.1016/S0168-9274(97)00033-0
[10] Druskin, V.; Knizhnerman, L., Two polynomial methods of calculating functions of symmetric matrices, Zh. Vychisl. Mat. Mat. Fiz., 29, 6, 112-121 (1989) · Zbl 0719.65035
[11] Druskin, V.; Knizhnerman, L., Error bounds in the simple Lanczos procedure for computing functions of symmetric matrices and eigenvalues, Comput. Math. Math. Phys., 31, 7, 20-30 (1992) · Zbl 0786.65031
[12] Druskin, V.; Knizhnerman, L., Krylov subspace approximation of eigenpairs and matrix functions in exact and computer arithmetic, Numer. Linear Algebra Appl., 2, 3, 205-217 (1995) · Zbl 0831.65042 · doi:10.1002/nla.1680020303
[13] Druskin, V.; Greenbaum, A.; Knizhnerman, L., Using nonorthogonal Lanczos vectors in the computation of matrix functions, SIAM J. Sci. Comput., 19, 38-54 (1998) · Zbl 0912.65021 · doi:10.1137/S1064827596303661
[14] Eiermann, M.; Ernst, O., A restarted Krylov subspace method for the evaluation of matrix functions, SIAM J. Numer. Anal., 44, 2481-2504 (2006) · Zbl 1129.65019 · doi:10.1137/050633846
[15] Eiermann, M.; Ernst, O.; Güttel, S., Deflated restarting for matrix functions, SIAM J. Matrix Anal. Appl., 32, 2, 621-641 (2011) · Zbl 1264.65070 · doi:10.1137/090774665
[16] Frommer, A.; Güttel, S.; Schweitzer, M., Efficient and stable Arnoldi restarts for matrix functions based on quadrature, SIAM J. Matrix Anal. Appl., 35, 2, 661-683 (2014) · Zbl 1309.65050 · doi:10.1137/13093491X
[17] Gallopoulos, E.; Saad, Y., Efficient solution of parabolic equations by Krylov approximation methods, SIAM J. Sci. Statist. Comput., 13, 1236-1264 (1992) · Zbl 0757.65101 · doi:10.1137/0913071
[18] Golub, Gh; Van Loan, Cf, Matrix Computations (1989), Baltimore: The John Hopkins University Press, Baltimore · Zbl 0733.65016
[19] Greenbaum, A., Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl., 113, 7-63 (1989) · Zbl 0662.65032 · doi:10.1016/0024-3795(89)90285-1
[20] Gustafsson, K., Control theoretic techniques for stepsize selection in explicit Runge-Kutta methods, ACM Trans. Math. Softw., 17, 533-554 (1991) · Zbl 0900.65256 · doi:10.1145/210232.210242
[21] Held, K., Electronic structure calculations using dynamical mean field theory, Adv. Phys., 56, 829-926 (2007) · doi:10.1080/00018730701619647
[22] Higham, N., Accuracy and Stability of Numerical Algorithms (2002), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 1011.65010
[23] Higham, N., Functions of Matrices: Theory and Computations (2008), Philadelphia: SIAM, Philadelphia · Zbl 1167.15001
[24] Hochbruck, M.; Lubich, C., On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 34, 1911-1925 (1997) · Zbl 0888.65032 · doi:10.1137/S0036142995280572
[25] Hochbruck, M.; Lubich, C.; Selhofer, H., Exponential integrators for large systems of differential equations, SIAM J. Sci. Comput., 19, 1552-1574 (1998) · Zbl 0912.65058 · doi:10.1137/S1064827595295337
[26] Hochbruck, M.; Ostermann, A., Exponential integrators, Acta Numer., 19, 209-286 (2010) · Zbl 1242.65109 · doi:10.1017/S0962492910000048
[27] Horn, Ra; Johnson, Cr, Matrix Analysis (1985), Cambridge: Cambridge University Press, Cambridge · Zbl 0576.15001
[28] Hubbard, J., Electron correlations in narrow energy bands, Proc. R. Soc. Lond. A, 276, 238-257 (1963) · doi:10.1098/rspa.1963.0204
[29] Jafari, S.: Introduction to Hubbard model and exact diagonalization. Iran. J. Phys. Res. 8 (2008). Available from http://ijpr.iut.ac.ir/article-1-279-en.pdf
[30] Jia, Z.; Lv, H., A posteriori error estimates of Krylov subspace approximations to matrix functions, Numer. Algorithms, 69, 1-28 (2015) · Zbl 1331.65069 · doi:10.1007/s11075-014-9878-0
[31] Lubich, C., From Quantum to Classical Molecular Dynamics: Reduced Models and Numerical Analysis, Zurich Lectures in Advanced Mathematics (2008), Zurich: European Mathematical Society, Zurich · Zbl 1160.81001
[32] Mahan, Gd, Many-Particle Physics: Physics of Solids and Liquids (1993), New York: Plenum Press, New York
[33] Mohankumar, N.; Auerbach, Sm, On time-step bounds in unitary quantum evolution using the Lanczos method, Comput. Phys. Commun., 175, 473-481 (2006) · Zbl 1196.81112 · doi:10.1016/j.cpc.2006.07.005
[34] Mohankumar, N.; Carrington, T., A new approach for determining the time step when propagating with the Lanczos algorithm, Comput. Phys. Commun., 181, 1859-1861 (2010) · Zbl 1217.65135 · doi:10.1016/j.cpc.2010.07.020
[35] Moler, C.; Van Loan, Cf, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev., 45, 1, 3-49 (2003) · Zbl 1030.65029 · doi:10.1137/S00361445024180
[36] Moret, I.; Novati, P., An interpolatory approximation of the matrix exponential based on Faber polynomials, J. Comput. Appl. Math., 131, 1, 361-380 (2001) · Zbl 0983.65057 · doi:10.1016/S0377-0427(00)00261-2
[37] Moret, I.; Novati, P., RD rational approximations of matrix exponentials, BIT, 44, 595-615 (2004) · Zbl 1075.65062 · doi:10.1023/B:BITN.0000046805.27551.3b
[38] Musco, C., Musco, C., Sidford, A.: Stability of the Lanczos method for matrix function approximation. In: Czumaj, A. (ed.), Proceeding SODA ’18—Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1605-1624 (2018). Preprint available from arXiv:1708.07788 · Zbl 1406.65032
[39] Niesen, J.; Wright, W., Algorithm 919: a Krylov subspace algorithm for evaluating the \(\varphi \)-functions appearing in exponential integrators, ACM Trans. Math. Softw., 38, 22 (2012) · Zbl 1365.65185 · doi:10.1145/2168773.2168781
[40] Paige, C., Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix, IMA J. Appl. Math., 18, 3, 341-349 (1976) · Zbl 0347.65018 · doi:10.1093/imamat/18.3.341
[41] Paige, C., Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem, Linear Algebra Appl., 34, 235-258 (1980) · Zbl 0471.65017 · doi:10.1016/0024-3795(80)90167-6
[42] Park, Tj; Light, Jc, Unitary quantum time evolution by iterative Lanczos reduction, J. Chem. Phys., 85, 5870-5876 (1986) · doi:10.1063/1.451548
[43] Parlett, B., The Symmetric Eigenvalue Problem (1998), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 0885.65039
[44] Pavarini, E.; Koch, E.; Van Den Brink, J.; Sawatzky, G., Quantum Materials: Experiments and Theory (2016), Jülich: Forschungszentrum Jülich, Jülich
[45] Saad, Y., Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 29, 1, 209-228 (1992) · Zbl 0749.65030 · doi:10.1137/0729014
[46] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Philadelphia: SIAM, Philadelphia · Zbl 1002.65042
[47] Sidje, R., Expokit: a software package for computing matrix exponentials, ACM Trans. Math. Softw., 24, 1, 130-156 (1998) · Zbl 0917.65063 · doi:10.1145/285861.285868
[48] Stewart, De; Leyk, Ts, Error estimates for Krylov subspace approximations of matrix exponentials, J. Comput. Appl. Math., 72, 359-369 (1996) · Zbl 0859.65040 · doi:10.1016/0377-0427(96)00006-4
[49] Van Den Eshof, J.; Hochbruck, M., Preconditioning Lanczos approximations to the matrix exponential, SIAM J. Sci. Comput., 27, 1438-1457 (2006) · Zbl 1105.65051 · doi:10.1137/040605461
[50] Wang, H.; Ye, Q., Error bounds for the Krylov subspace methods for computations of matrix exponentials, SIAM J. Matrix Anal. Appl., 38, 1, 155-187 (2017) · Zbl 1365.65136 · doi:10.1137/16M1063733
[51] Zemke, J.: Krylov Subspace Methods in Finite Precision: A Unified Approach. Ph.D. Thesis, Technische Universität Hamburg (2003) · Zbl 1196.65018
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.