×

A block Krylov subspace time-exact solution method for linear ordinary differential equation systems. (English) Zbl 1313.65181

This work deals with a time-exact method for solving large systems of ordinary differential equations (ODEs) of the form \(y' = -A y + g(t)\) or \(y'' = -A y + g(t)\). Such systems arise for example in application of method of lines in time to a space discretized partial differential equations. The presented method consists of two steps. First a piecewise polynomial approximation of the source term is introduced and constructed with the help of the truncated singular value decomposition. In the second step an efficient restarted residual-based block Krylov subspace method is used to solve the approximate ODE by computing the approximation to the matrix exponential function.
Three numerical examples are included, two-dimensional convection diffusion problem, two-dimensional wave equation and three-dimensional system of Maxwell’s equations. Presented algorithms are implemented in MATLAB and compared with exiting methods, for example with the EXPOKIT [R. B. Sidje, ACM Trans. Math. Softw. 24, No. 1, 130–156 (1998; Zbl 0917.65063)], to demonstrate its efficiency.

MSC:

65L05 Numerical methods for initial value problems involving ordinary differential equations
65F60 Numerical computation of matrix exponential and similar matrix functions
65F10 Iterative numerical methods for linear systems
65M20 Method of lines for initial value and initial-boundary value problems involving PDEs
35K20 Initial-boundary value problems for second-order parabolic equations
34A30 Linear ordinary differential equations and systems
35L05 Wave equation
35Q61 Maxwell equations

Citations:

Zbl 0917.65063
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Borzì, Computational Optimization of Systems Governed by Partial Differential Equations (2011) · Zbl 1240.90001
[2] He, Transition to the ultimate state of turbulent Rayleigh-Bénard convection, Physical Review Letters 108 (024502) (2012)
[3] Hochbruck, Exponential integrators, Acta Numerica 19 pp 209– (2010) · Zbl 1242.65109
[4] Minchev BV Wright WM A review of exponential integrators for first order semi-linear problems Technical Report 2/05 2005 http://www.ii.uib.no/ borko/pub/N2-2005.pdf
[5] Niesen, Algorithm 919: a Krylov subspace algorithm for evaluating the -functions appearing in exponential integrators, ACM Transactions on Mathematical Software 38 (3) pp 22:1– (2012) · Zbl 1365.65185
[6] Botchev, The Gautschi time stepping scheme for edge finite element discretizations of the Maxwell equations, Journal of Computational Physics 216 pp 654– (2006) · Zbl 1136.78328
[7] Analysis, Modeling and Simulation of Multiscale Problems (2006) · Zbl 1105.35002
[8] Lubich, From Quantum to Classical Molecular Dynamics: Reduced Models and Numerical Analysis (2008) · Zbl 1160.81001
[9] Hout, A contour integral method for the Black-Scholes and Heston equations, SIAM Journal on Scientific Computing 33 (2) pp 763– (2011) · Zbl 1233.65067
[10] Vorst, An iterative solution method for solving f(A)x = b, using Krylov subspace information obtained for the symmetric positive definite matrix A, Journal of Computational and Applied Mathematics 18 pp 249– (1987) · Zbl 0621.65022
[11] Druskin, Two polynomial methods of calculating functions of symmetric matrices, USSR Computational Mathematics and Mathematical Physics 29 (6) pp 112– (1989) · Zbl 0719.65035
[12] Tal-Ezer, Spectral methods in time for parabolic problems, SIAM Journal on Numerical Analysis 26 (1) pp 1– (1989) · Zbl 0668.65090
[13] Druskin, Krylov subspace approximations of eigenpairs and matrix functions in exact and computer arithmetic, Numerical Linear Algebra with Applications 2 pp 205– (1995) · Zbl 0831.65042
[14] Hochbruck, On Krylov subspace approximations to the matrix exponential operator, SIAM Journal on Numerical Analysis 34 (5) pp 1911– (1997) · Zbl 0888.65032
[15] Druskin, Using nonorthogonal Lanczos vectors in the computation of matrix functions, SIAM Journal on Scientific Computing 19 (1) pp 38– (1998) · Zbl 0912.65021
[16] Eshof, Preconditioning Lanczos approximations to the matrix exponential, SIAM Journal on Scientific Computing 27 (4) pp 1438– (2006) · Zbl 1105.65051
[17] Tal-Ezer, On restart and error estimation for Krylov approximation of w = f(A)v, SIAM Journal on Scientific Computing 29 (6) pp 2426– (2007) · Zbl 1154.65320
[18] Hochbruck, Approximation of matrix operators applied to multiple vectors, Mathematics and Computers in Simulation 79 (4) pp 1270– (2008) · Zbl 1189.65077
[19] Eiermann, Deflated restarting for matrix functions, SIAM Journal on Matrix Analysis and Applications 32 (2) pp 621– (2011) · Zbl 1264.65070
[20] Al-Mohy, Computing the action of the matrix exponential, with an application to exponential integrators, SIAM Journal on Scientific Computing 33 (2) pp 488– (2011) · Zbl 1234.65028
[21] De Raedt, One-step finite-difference time-domain algorithm to solve the Maxwell equations, Physical Review E 67 pp 056 706– (2003) · Zbl 1368.78162
[22] Tóth, Implicit and semi-implicit schemes in the versatile advection code: numerical tests, Astronomy and Astrophysics 332 pp 1159– (1998)
[23] Verwer, Unconditionally stable integration of Maxwell’s equations, Linear Algebra and its Applications 431 (3-4) pp 300– (2009) · Zbl 1170.78004
[24] Tal-Ezer, Highly Accurate Solution for Time-dependent PDE’s (2011)
[25] Gelber AV Shurina EP Epov MI An application of finite element method for solving the problem of modeling non-stationary electromagnetic fields of defectoscope International Conference on Computational Mathematics. Part I, II 2002 427 431
[26] Golub, Matrix Computations, 3. ed. (1996)
[27] Botchev, An SVD-approach to Jacobi-Davidson solution of nonlinear Helmholtz eigenvalue problems, Linear Algebra and its Applications 431 pp 427– (2009) · Zbl 1166.65022
[28] Enright, Continuous numerical methods for ODEs with defect control, Journal of Computational and Applied Mathematics 125 (1-2) pp 159– (2000) · Zbl 0982.65078
[29] Shampine, Solving ODEs and DDEs with residual control, Applied Numerical Mathematics 52 (1) pp 113– (2005) · Zbl 1063.65061
[30] Kierzenka, A BVP solver that controls residual and error, Journal of Numerical Analysis, Industrial and Applied Mathematics 3 (1-2) pp 27– (2008)
[31] Celledoni, A Krylov projection method for systems of ODEs, Applied Numerical Mathematics 24 (2-3) pp 365– (1997) · Zbl 0885.65073
[32] Botchev, Residual, Restarting and Richardson Iteration for the Matrix Exponential (2010)
[33] Vorst, Iterative Krylov Methods for Large Linear Systems (2003)
[34] Saad, Iterative Methods for Sparse Linear Systems, 2. ed. (2003) · Zbl 1031.65046
[35] Moret, RD rational approximations of the matrix exponential, BIT Numerical Mathematics 44 pp 595– (2004) · Zbl 1075.65062
[36] Hochbruck, A Gautschi-type method for oscillatory second-order differential equations, Numerische Mathematik 83 pp 403– (1999) · Zbl 0937.65077
[37] Grimm, On error bounds for the Gautschi-type exponential integrator applied to oscillatory second-order differential equations, Numerische Mathematik 100 pp 71– (2005) · Zbl 1074.65097
[38] Botchev MA Grimm V Hochbruck M Residual, restarting and Richardson iteration for the matrix exponential Technical Report Nr. 12-10 2012 www.math.kit.edu/iwrmm/page/preprints/en · Zbl 1278.65052
[39] Berland, EXPINT-a MATLAB package for exponential integrators, ACM Transactions on Mathematical Software 33 (1) (2007) · Zbl 05458466
[40] Krukier, Implicit difference schemes and an iterative method for solving them for a certain class of systems of quasi-linear equations, Soviet Mathematics 23 (7) pp 43– (1979) · Zbl 0476.65067
[41] Hochbruck, Exponential integrators for large systems of differential equations, SIAM Journal on Scientific Computing 19 (5) pp 1552– (1998) · Zbl 0912.65058
[42] Sidje, EXPOKIT. A software package for computing matrix exponentials, ACM Transactions on Mathematical Software 24 (1) pp 130– (1998) · Zbl 0917.65063
[43] Shurina, Mathematical modelling of non-stationary electromagnetic fields of defectoscope of casings, Computational technologies 7 (6) pp 114– (2002) · Zbl 1024.86003
[44] Davis, A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, ACM Transactions on Mathematical Software 30 (2) pp 167– (2004) · Zbl 1072.65036
[45] Davis, Algorithm 832: UMFPACK V4.3-an unsymmetric-pattern multifrontal method, ACM Transactions on Mathematical Software 30 (2) pp 196– (2004) · Zbl 1072.65037
[46] Rodrigue, A vector finite element time-domain method for solving Maxwell’s equations on unstructured hexahedral grids, SIAM Journal on Scientific Computing 23 (3) pp 683– (2001) · Zbl 1003.78008
[47] Botchev, Numerical integration of damped Maxwell equations, SIAM Journal on Scientific Computing 31 (2) pp 1322– (2009) · Zbl 1229.78026
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.