KIOPS: a fast adaptive Krylov subspace solver for exponential integrators. (English) Zbl 1418.65074
J. Comput. Phys. 372, 236-255 (2018); corrigendum ibid. 441, Article ID 110443, 2 p. (2021).
Summary: This paper presents a new algorithm KIOPS for computing linear combinations of \(\varphi\)-functions that appear in exponential integrators. This algorithm is suitable for large-scale problems in computational physics where little or no information about the spectrum or norm of the Jacobian matrix is known a priori. We first show that such problems can be solved efficiently by computing a single exponential of a modified matrix. Then our approach is to compute an appropriate basis for the Krylov subspace using the incomplete orthogonalization procedure and project the matrix exponential on this subspace. We also present a novel adaptive procedure that significantly reduces the computational complexity of exponential integrators. Our numerical experiments demonstrate that KIOPS outperforms the current state-of-the-art adaptive Krylov algorithm phipm.
MSC:
| 65L04 | Numerical methods for stiff equations |
| 65F25 | Orthogonalization in numerical linear algebra |
| 65-04 | Software, source code, etc. for problems pertaining to numerical analysis |
Keywords:
adaptive Krylov subspace methods; incomplete orthogonalization; time integration; exponential integrators; \(\varphi\)-functions; matrix exponentialReferences:
| [1] | Minchev, B. V.; Wright, W. M., A Review of Exponential Integrators for First Order Semi-Linear Problems (2005), Department of Mathematics, Norwegian University of Science and Technology, Tech. Rep. 2/05 |
| [2] | Hochbruck, M.; Ostermann, A., Exponential integrators, Acta Numer., 19, 209-286 (2010) · Zbl 1242.65109 |
| [3] | Higham, N. J., Functions of Matrices: Theory and Computation (2008), SIAM · Zbl 1167.15001 |
| [4] | Moler, C.; Van Loan, C., Nineteen dubious ways to compute the exponential of a matrix, SIAM Rev., 20, 4, 801-836 (1978) · Zbl 0395.65012 |
| [5] | Moler, C.; Van Loan, C., Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev., 45, 1, 3-49 (2003) · Zbl 1030.65029 |
| [6] | 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 |
| [7] | Caliari, M.; Kandolf, P.; Ostermann, A.; Rainer, S., The Leja method revisited: backward error analysis for the matrix exponential, SIAM J. Sci. Comput., 38, 3, A1639-A1661 (2016) · Zbl 1339.65061 |
| [8] | Sidje, R. B., Expokit: a software package for computing matrix exponentials, ACM Trans. Math. Softw., 24, 1, 130-156 (1998) · Zbl 0917.65063 |
| [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] | 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, 10, 2293-2314 (2008) · Zbl 1153.65042 |
| [11] | 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 |
| [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] | Lopez, L.; Simoncini, V., Preserving geometric properties of the exponential matrix by block Krylov subspace methods, BIT Numer. Math., 46, 4, 813-830 (2006) · Zbl 1107.65039 |
| [14] | 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 |
| [15] | Kooij, G. L.; Botchev, M. A.; Geurts, B. J., A block Krylov subspace implementation of the time-parallel Paraexp method and its extension for nonlinear partial differential equations, J. Comput. Appl. Math., 316, 229-246 (2017) · Zbl 1375.65130 |
| [16] | Frommer, A.; Lund, K.; Szyld, D. B., Block Krylov subspace methods for functions of matrices, Electron. Trans. Numer. Anal., 47, 100-126 (2017) · Zbl 1372.65138 |
| [17] | Gander, M. J.; Güttel, S., PARAEXP: a parallel integrator for linear initial-value problems, SIAM J. Sci. Comput., 35, 2, C123-C142 (2013) · Zbl 1266.65123 |
| [18] | Moret, I.; Novati, P., RD-rational approximations of the matrix exponential, BIT Numer. Math., 44, 3, 595-615 (2004) · Zbl 1075.65062 |
| [19] | 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 |
| [20] | Moret, I., On RD-rational Krylov approximations to the core-functions of exponential integrators, Numer. Linear Algebra Appl., 14, 5, 445-457 (2007) · Zbl 1199.65235 |
| [21] | Niesen, J.; Wright, W. M., Algorithm 919: a Krylov subspace algorithm for evaluating the \(φ\)-functions appearing in exponential integrators, ACM Trans. Math. Softw., 38, 3, 22 (2012) · Zbl 1365.65185 |
| [22] | Niesen, J.; Wright, W. M., A Krylov subspace method for option pricing, SSRN, 1799124 (2011) |
| [23] | Tokman, M.; Loffeld, J.; Tranquilli, P., New adaptive exponential propagation iterative methods of Runge-Kutta type, SIAM J. Sci. Comput., 34, 5, A2650-A2669 (2012) · Zbl 1259.65121 |
| [24] | Clancy, C.; Pudykiewicz, J. A., On the use of exponential time integration methods in atmospheric models, Tellus, Ser. A Dyn. Meteorol. Oceanogr., 65, 1 (2013) |
| [25] | Clancy, C.; Pudykiewicz, J. A., A class of semi-implicit predictor-corrector schemes for the time integration of atmospheric models, J. Comput. Phys., 250, 665-684 (2013) · Zbl 1349.65205 |
| [26] | Gaudreault, S.; Pudykiewicz, J. A., An efficient exponential time integration method for the numerical solution of the shallow water equations on the sphere, J. Comput. Phys., 322, 827-848 (2016) · Zbl 1351.76106 |
| [27] | Arnoldi, W. E., The principle of minimized iterations in the solution of the matrix eigenvalue problem, Q. Appl. Math., 9, 1, 17-29 (1951) · Zbl 0042.12801 |
| [28] | Tokman, M., Efficient integration of large stiff systems of ODEs with exponential propagation iterative (EPI) methods, J. Comput. Phys., 213, 2, 748-776 (2006) · Zbl 1089.65063 |
| [29] | Saad, Y., Variations on Arnoldi’s method for computing eigenelements of large unsymmetric matrices, Linear Algebra Appl., 34, 269-295 (1980) · Zbl 0456.65017 |
| [30] | Saad, Y., The Lanczos biorthogonalization algorithm and other oblique projection methods for solving large unsymmetric systems, SIAM J. Numer. Anal., 19, 3, 485-506 (1982) · Zbl 0483.65022 |
| [31] | Koskela, A., Approximating the Matrix Exponential of an Advection-Diffusion Operator Using the Incomplete Orthogonalization Method, Numerical Mathematics and Advanced Applications—ENUMATH, vol. 2013, 345-353 (2015), Springer · Zbl 1328.65107 |
| [32] | Vo, H. D.; Sidje, R. B., Approximating the large sparse matrix exponential using incomplete orthogonalization and Krylov subspaces of variable dimension, Numer. Linear Algebra Appl., 24, 3, Article e2090 pp. (2017) · Zbl 1424.65063 |
| [33] | Rainwater, G.; Tokman, M., A new approach to constructing efficient stiffly accurate EPIRK methods, J. Comput. Phys., 323, 283-309 (2016) · Zbl 1415.65163 |
| [34] | Friesner, R. A.; Tuckerman, L. S.; Dornblaser, B. C.; Russo, T. V., A method for exponential propagation of large systems of stiff nonlinear differential equations, J. Sci. Comput., 4, 4, 327-354 (1989) |
| [35] | Beylkin, G.; Keiser, J. M.; Vozovoi, L., A new class of time discretization schemes for the solution of nonlinear PDEs, J. Comput. Phys., 147, 2, 362-387 (1998) · Zbl 0924.65089 |
| [36] | Gallopoulos, E.; Saad, Y., Efficient solution of parabolic equations by Krylov approximation methods, SIAM J. Sci. Stat. Comput., 13, 5, 1236-1264 (1992) · Zbl 0757.65101 |
| [37] | 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 |
| [38] | Cox, S. M.; Matthews, P. C., Exponential time differencing for stiff systems, J. Comput. Phys., 176, 2, 430-455 (2002) · Zbl 1005.65069 |
| [39] | Kassam, A.-K.; Trefethen, L. N., Fourth-order time-stepping for stiff PDEs, SIAM J. Sci. Comput., 26, 4, 1214-1233 (2005) · Zbl 1077.65105 |
| [40] | Krogstad, S., Generalized integrating factor methods for stiff PDEs, J. Comput. Phys., 203, 1, 72-88 (2005) · Zbl 1063.65097 |
| [41] | Hochbruck, M.; Ostermann, A., Exponential integrators of Rosenbrock-type, Oberwolfach Rep., 3, 1107-1110 (2006) |
| [42] | Einkemmer, L.; Tokman, M.; Loffeld, J., On the performance of exponential integrators for problems in magnetohydrodynamics, J. Comput. Phys., 330, 550-565 (2017) · Zbl 1378.76132 |
| [43] | Michels, D. L.; Luan, V. T.; Tokman, M., A stiffly accurate integrator for elastodynamic problems, ACM Trans. Graph., 36, 4, 116:1-116:14 (2017) |
| [44] | Tokman, M., A new class of exponential propagation iterative methods of Runge-Kutta type (EPIRK), J. Comput. Phys., 230, 24, 8762-8778 (2011) · Zbl 1370.65035 |
| [45] | Rainwater, G.; Tokman, M., Designing efficient exponential integrators with EPIRK framework, (AIP Conference Proceedings, vol. 1863 (2017), AIP Publishing), 020007 |
| [46] | 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 |
| [47] | Higham, N. J., The scaling and squaring method for the matrix exponential revisited, SIAM J. Matrix Anal. Appl., 26, 4, 1179-1193 (2005) · Zbl 1081.65037 |
| [48] | Kandolf, P.; Ostermann, A.; Rainer, S., A residual based error estimate for Leja interpolation of matrix functions, Linear Algebra Appl., 456, 157-173 (2014) · Zbl 1293.65075 |
| [49] | Luan, V. T.; Ostermann, A., Exponential Rosenbrock methods of order five—construction, analysis and numerical comparisons, J. Comput. Appl. Math., 255, 417-431 (2014) · Zbl 1291.65201 |
| [50] | Bates, P. W.; Brown, S.; Han, J., Numerical analysis for a nonlocal Allen-Cahn equation, Int. J. Numer. Anal. Model., 6, 1, 33-49 (2009) · Zbl 1165.65051 |
| [51] | Caliari, M.; Ostermann, A., Implementation of exponential Rosenbrock-type integrators, Appl. Numer. Math., 59, 3-4, 568-581 (2009) · Zbl 1160.65318 |
| [52] | Hairer, E.; Wanner, G., Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems (2004), Springer-Verlag: Springer-Verlag Berlin, Heidelberg |
| [53] | Lefever, R.; Nicolis, G., Chemical instabilities and sustained oscillations, J. Theor. Biol., 30, 2, 267-284 (1971) · Zbl 1170.92344 |
| [54] | Gray, P.; Scott, S., Autocatalytic reactions in the isothermal, continuous stirred tank reactor: oscillations and instabilities in the system \(A + 2 B \to 3 B; B \to C\), Chem. Eng. Sci., 39, 6, 1087-1097 (1984) |
| [55] | Hochbruck, M.; Ostermann, A., Explicit exponential Runge-Kutta methods for semilinear parabolic problems, SIAM J. Numer. Anal., 43, 3, 1069-1090 (2005) · Zbl 1093.65052 |
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.
