×

ART: adaptive residual-time restarting for Krylov subspace matrix exponential evaluations. (English) Zbl 1427.65060

Summary: In this paper a new restarting method for Krylov subspace matrix exponential evaluations is proposed. Since our restarting technique essentially employs the residual, some convergence results for the residual are given. We also discuss how the restart length can be adjusted after each restart cycle, which leads to an adaptive restarting procedure. Numerical tests arepresented to compare our restarting with three other restarting methods. Some of the algorithms described in this paper are a part of the Octave/Matlab package expmARPACK available at http://team.kiam.ru/botchev/expm/.

MSC:

65F60 Numerical computation of matrix exponential and similar matrix functions
65F99 Numerical linear algebra
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65L05 Numerical methods for initial value problems involving ordinary differential equations
35Q61 Maxwell equations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Moret, I.; Novati, P., An interpolatory approximation of the matrix exponential based on Faber polynomials, J. Comput. Appl. Math., 131, 1-2, 361-380 (2001) · Zbl 0983.65057
[2] Tal-Ezer, H., Polynomial approximation of functions of matrices and applications, J. Sci. Comput., 4, 1, 25-60 (1989) · Zbl 0684.65040
[3] De Raedt, H.; Michielsen, K.; Kole, J. S.; Figge, M. T., One-step finite-difference time-domain algorithm to solve the Maxwell equations, Phys. Rev. E, 67, Article 056706 pp. (2003)
[4] Sommeijer, B. P.; Shampine, L. F.; Verwer, J. G., RKC: An explicit solver for parabolic PDEs, J. Comput. Appl. Math., 88, 315-326 (1998) · Zbl 0910.65067
[5] Lebedev, V. I., Explicit difference schemes for solving stiff systems of ODEs and PDEs with complex spectrum, Russian J. Numer. Anal. Math. Modelling, 13, 2, 107-116 (1998) · Zbl 0914.65087
[6] Botchev, M. A.; Sleijpen, G. L.G.; van der Vorst, H. A., Stability control for approximate implicit time stepping schemes with minimum residual iterations, Appl. Numer. Math., 31, 3, 239-253 (1999) · Zbl 0941.65074
[7] Al-Mohy, A. H.; Higham, N. J., 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
[8] Eiermann, M.; Ernst, O. G., A restarted Krylov subspace method for the evaluation of matrix functions, SIAM J. Numer. Anal., 44, 2481-2504 (2006) · Zbl 1129.65019
[9] Tal-Ezer, H., On restart and error estimation for Krylov approximation of \(w = f(A) v\), SIAM J. Sci. Comput., 29, 6, 2426-2441 (2007) · Zbl 1154.65320
[10] Sidje, R. B., Expokit. A software package for computing matrix exponentials, ACM Trans. Math. Software, 24, 1, 130-156 (1998), www.maths.uq.edu.au/expokit/ · Zbl 0917.65063
[11] Celledoni, E.; Moret, I., A Krylov projection method for systems of ODEs, Appl. Numer. Math., 24, 2-3, 365-378 (1997) · Zbl 0885.65073
[12] Botchev, M. A.; Grimm, V.; Hochbruck, M., Residual, restarting and Richardson iteration for the matrix exponential, SIAM J. Sci. Comput., 35, 3, A1376-A1397 (2013) · Zbl 1278.65052
[13] Niehoff, J., Projektionsverfahren Zur Approximation Von Matrixfunktionen Mit Anwendungen Auf Die Implementierung Exponentieller Integratoren (2006), Mathematisch-Naturwissenschaftlichen Fakultät der Heinrich-Heine-Universität Düsseldorf, (Ph.D. thesis)
[14] Hochbruck, M.; Lubich, C.; Selhofer, H., Exponential integrators for large systems of differential equations, SIAM J. Sci. Comput., 19, 5, 1552-1574 (1998) · Zbl 0912.65058
[15] 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
[16] Afanasjew, M.; Eiermann, M.; Ernst, O. G.; Güttel, S., Implementation of a restarted Krylov subspace method for the evaluation of matrix functions, Linear Algebra Appl., 429, 2293-2314 (2008) · Zbl 1153.65042
[17] Güttel, S., Rational Krylov Methods for Operator Functions (2010), Technischen Universität Bergakademie Freiberg, www.guettel.com
[18] Eiermann, M.; Ernst, O. G.; Güttel, S., Deflated restarting for matrix functions, SIAM J. Matrix Anal. Appl., 32, 2, 621-641 (2011) · Zbl 1264.65070
[19] Güttel, S.; Frommer, A.; 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
[20] T. Jawecki, W. Auzinger, O. Koch, Computable strict upper bounds for Krylov approximations to a class of matrix exponentials and \(\phi \)-functions. arXiv preprint arXiv:1809.03369, 2018. https://arxiv.org/pdf/1809.03369. · Zbl 1432.65053
[21] Hundsdorfer, W.; Verwer, J. G., Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations (2003), Springer Verlag · Zbl 1030.65100
[22] Dekker, K.; Verwer, J. G., Stability of Runge-Kutta Methods for Stiff Non-Linear Differential Equations (1984), Elsevier Science Publishers: Elsevier Science Publishers North-Holland · Zbl 0571.65057
[23] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore and London · Zbl 0865.65009
[24] Parlett, B. N., The Symmetric Eigenvalue Problem (1998), SIAM · Zbl 0885.65039
[25] van der Vorst, H. A., Iterative Krylov Methods for Large Linear Systems (2003), Cambridge University Press · Zbl 1023.65027
[26] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM, Available from http://www-users.cs.umn.edu/saad/books.html · Zbl 1002.65042
[27] van der Vorst, H. A., An iterative solution method for solving \(f(A) x = b\), using krylov subspace information obtained for the symmetric positive definite matrix \(A\), J. Comput. Appl. Math., 18, 249-263 (1987) · Zbl 0621.65022
[28] Druskin, V. L.; Knizhnerman, L. A., Two polynomial methods of calculating functions of symmetric matrices, U.S.S.R. Comput. Maths Math. Phys., 29, 6, 112-121 (1989) · Zbl 0719.65035
[29] Knizhnerman, L. A., Calculation of functions of unsymmetric matrices using Arnoldi’s method, U.S.S.R. Comput. Maths Math. Phys., 31, 1, 1-9 (1991) · Zbl 0774.65021
[30] Hochbruck, M.; Lubich, C., On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 34, 5, 1911-1925 (1997) · Zbl 0888.65032
[31] Druskin, V. L.; Greenbaum, A.; Knizhnerman, L. A., Using nonorthogonal Lanczos vectors in the computation of matrix functions, SIAM J. Sci. Comput., 19, 1, 38-54 (1998) · Zbl 0912.65021
[32] Beckermann, B.; Reichel, L., Error estimation and evaluation of matrix functions via the Faber transform, SIAM J. Num. Anal., 47, 3849-3883 (2009) · Zbl 1204.65041
[33] Suetin, P. K., Series of Faber Polynomials (1998), CRC Press · Zbl 0936.30027
[34] Beckermann, B., Image numérique, GMRES et polynômes de Faber, C. R. Acad. Sci. Paris I, 340, 11, 855-860 (2005) · Zbl 1076.47004
[35] Hochbruck, M.; Ostermann, A., Exponential integrators, Acta Numer., 19, 209-286 (2010) · Zbl 1242.65109
[36] Moret, I.; Novati, P., RD rational approximations of the matrix exponential, BIT, 44, 595-615 (2004) · Zbl 1075.65062
[37] van den Eshof, J.; Hochbruck, M., Preconditioning Lanczos approximations to the matrix exponential, SIAM J. Sci. Comput., 27, 4, 1438-1457 (2006) · Zbl 1105.65051
[38] Göckler, T.; Grimm, V., Uniform approximation of \(\varphi \)-functions in exponential integrators by a rational Krylov subspace method with simple poles, SIAM J. Matrix Anal. Appl., 35, 4, 1467-1489 (2014) · Zbl 1416.65192
[39] Krukier, L. A., Implicit difference schemes and an iterative method for solving them for a certain class of systems of quasi-linear equations, Sov. Math., 23, 7, 43-55 (1979), Translation from Izv. Vyssh. Uchebn. Zaved., Mat. 1979, No. 7(206), 41-52 (1979) · Zbl 0476.65067
[40] Taflove, A.; Hagness, S. C., Computational Electrodynamics: The Finite-Difference Time-Domain Method (2005), Artech House Inc: Artech House Inc Boston, MA
[41] Kole, J. S.; Figge, M. T.; De Raedt, H., Unconditionally stable algorithms to solve the time-dependent Maxwell equations, Phys. Rev. E, 64, Article 066705 pp. (2001)
[42] Berenger, J., A perfectly matched layer for the absorption of electromagnetic waves, J. Comput. Phys., 114, 185-200 (1994) · Zbl 0814.65129
[43] S.G. Johnson, Notes on perfectly matched layers (PMLs). math.mit.edu/stevenj/18.369/pml.pdf, 2010.
[44] Botchev, M. A., Krylov subspace exponential time domain solution of Maxwell’s equations in photonic crystal modeling, J. Comput. Appl. Math., 293, 24-30 (2016) · Zbl 1322.65056
[45] Verwer, J. G.; Botchev, M. A., Unconditionally stable integration of Maxwell’s equations, Linear Algebra Appl., 431, 3-4, 300-317 (2009) · Zbl 1170.78004
[46] Botchev, M. A., A block Krylov subspace time-exact solution method for linear ordinary differential equation systems, Numer. Linear Algebra Appl., 20, 4, 557-574 (2013) · Zbl 1313.65181
[47] Hochbruck, M.; Lubich, C., A gautschi-type method for oscillatory second-order differential equations, Numer. Math., 83, 403-426 (1999) · Zbl 0937.65077
[48] Botchev, M. A.; Harutyunyan, D.; van der Vegt, J. J.W., The Gautschi time stepping scheme for edge finite element discretizations of the Maxwell equations, J. Comput. Phys., 216, 654-686 (2006) · Zbl 1136.78328
[49] Grimm, V.; Hochbruck, M., Rational approximation to trigonometric operators, BIT, 48, 2, 215-229 (2008) · Zbl 1148.65075
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.