×

Krylov approximation of linear ODEs with polynomial parameterization. (English) Zbl 1338.65183

Summary: We propose a new numerical method to solve linear ordinary differential equations (ODEs) of the type \(\tfrac{\partial u}{\partial t}(t,\varepsilon) = A(\varepsilon) \, u(t,\varepsilon)\), where \(A:\mathbb{C}\to\mathbb{C}^{n\times n}\) is a matrix polynomial with large and sparse matrix coefficients. The algorithm computes an explicit parameterization of approximations of \(u(t,\varepsilon)\) such that approximations for many different values of \(\varepsilon\) and \(t\) can be obtained with a very small additional computational effort. The derivation of the algorithm is based on a reformulation of the parameterization as a linear parameter-free ordinary differential equation and on approximating the product of the matrix exponential and a vector with a Krylov method. The Krylov approximation is generated with Arnoldi’s method and the structure of the coefficient matrix turns out to be independent of the truncation parameter so that it can also be interpreted as Arnoldi’s method applied to an infinite dimensional matrix. We prove the superlinear convergence of the algorithm and provide a posteriori error estimates to be used as termination criteria. The behavior of the algorithm is illustrated with examples stemming from spatial discretizations of partial differential equations.

MSC:

65L05 Numerical methods for initial value problems involving ordinary differential equations
34A30 Linear ordinary differential equations and systems
65L20 Stability and convergence of numerical methods for ordinary differential equations
65L70 Error bounds for numerical methods for ordinary differential equations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. H. Al-Mohy and N. J. Higham, {\it Computing the action of the matrix exponential, with an application to exponential integrators}, SIAM J. Sci. Comput., 33 (2011), pp. 488-511. · Zbl 1234.65028
[2] P. Benner, S. Gugercin, and K. Willcox, {\it A Survey of Model Reduction Methods for Parametric Systems}, Technical report, Max Planck Institute, Magdeburg, 2013. · Zbl 1339.37089
[3] T. Betcke, {\it Optimal scaling of generalized and polynomial eigenvalue problems}, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 1320-1338. · Zbl 1176.65038
[4] S. Blanes, F. Casas, J. Oteo, and J. Ros, {\it The Magnus expansion and some of its applications}, Phys. Rep., 470 (2009), pp. 151-238.
[5] H. G. Bock, S. Körkel, and J. P. Schlöder, {\it Parameter estimation and optimum experimental design for differential equation models}, in Model Based Parameter Estimation, H. G. Bock, T. Carraro, W. Jäger, S. Körkel, R. Rannacher, and J. Schlöder, eds., Springer, New York, 2013, pp. 1-30. · Zbl 1269.65014
[6] R. Eid, {\it Time Domain Model Reduction by Moment Matching}, Ph.D. thesis, TU München, 2008.
[7] M. Eiermann and O. G. Ernst, {\it A restarted Krylov subspace method for the evaluation of matrix functions}, SIAM J. Numer. Anal., 44 (2006), pp. 2481-2504. · Zbl 1129.65019
[8] H.-Y. Fan, W.-W. Lin, and P. V. Dooren, {\it Normwise scaling of second order polynomial matrices}, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 252-256. · Zbl 1088.15010
[9] E. Gallopoulos and Y. Saad, {\it Efficient solution of parabolic equations by Krylov approximation methods}, SIAM J. Sci. Statist. Comput., 13 (1992), pp. 1236-1264. · Zbl 0757.65101
[10] N. J. Higham, {\it Functions of Matrices: Theory and Computation}, SIAM, Philadelphia, 2008. · Zbl 1167.15001
[11] N. J. Higham and S. D. Relton, {\it Higher order Fréchet derivatives of matrix functions and the level-2 condition number}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 1019-1037. · Zbl 1308.65066
[12] M. Hochbruck and C. Lubich, {\it On Krylov subspace approximations to the matrix exponential operator}, SIAM J. Numer. Anal., 34 (1997), pp. 1911-1925. · Zbl 0888.65032
[13] M. Hochbruck, C. Lubich, and H. Selhofer, {\it Exponential integrators for large systems of differential equations}, SIAM J. Sci. Comput., 19 (1998), pp. 1552-1574. · Zbl 0912.65058
[14] M. Hochbruck and A. Ostermann, {\it Exponential integrators}, Acta Numer., 19 (2010), pp. 209-286. · Zbl 1242.65109
[15] R. Horn and C. Johnson, {\it Topics in Matrix Analysis}, Cambridge University Press, Cambridge, UK, 1991. · Zbl 0729.15001
[16] E. Jarlebring, W. Michiels, and K. Meerbergen, {\it A linear eigenvalue algorithm for the nonlinear eigenvalue problem}, Numer. Math., 122 (2012), pp. 169-195. · Zbl 1256.65043
[17] A. Koskela and E. Jarlebring, {\it The Infinite Arnoldi Exponential Integrator for Linear Inhomogeneous ODEs}, Technical report, KTH Royal Institute of Technology, 2015, http://arxiv.org/abs/1507.07507.
[18] P. Lietaert and K. Meerbergen, {\it Interpolatory Model order Reduction by Tensor Krylov Methods}, Technicl report, KU Leuven, 2015.
[19] R. Mathias, {\it A chain rule for matrix functions and applications}, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 610-620. · Zbl 0867.15014
[20] I. Najfeld and T. F. Havel, {\it Derivatives of the matrix exponential and their computation}, Adv. Appl. Math., 16 (1995), pp. 321-375. · Zbl 0839.15004
[21] S. D. Relton, {\it Algorithms for Matrix Functions and their Fréchet Derivatives and Condition Numbers}, Ph.D. thesis, University of Manchester, 2014.
[22] Y. Saad, {\it Analysis of some Krylov subspace approximations to the matrix exponential operator}, SIAM J. Numer. Anal., 29 (1992), pp. 209-228. · Zbl 0749.65030
[23] B. A. Schmitt and E. Kostina, {\it Peer two-step methods with embedded sensitivity approximation for parameter-dependent ODEs}, SIAM J. Numer. Anal., 50 (2012), pp. 2182-2207. · Zbl 1275.65040
[24] R. B. Sidje, {\it Expokit: A software package for computing matrix exponentials}, ACM Trans. Math. Software, 24 (1998), pp. 130-156. · Zbl 0917.65063
[25] L. N. Trefethen and M. Embree, {\it Spectra and Pseudospectra. The Behavior of Nonnormal Matrices and Operators}, Princeton University Press, Princeton, NJ, 2005. · Zbl 1085.15009
[26] Y. Yue and K. Meerbergen, {\it Using Krylov-Padé model order reduction for accelerating design optimization of structures and vibrations in the frequency domain}, Internat. J. Numer. Methods Engrg., 90 (2012), pp. 1207-1232. · Zbl 1242.74222
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.