Explicit stabilized multirate method for stiff differential equations

Abdulle, Assyr; Grote, Marcus; Rosilho de Souza, Giacomo

doi:10.1090/mcom/3753

Explicit stabilized multirate method for stiff differential equations
HTML articles powered by AMS MathViewer

by Assyr Abdulle, Marcus J. Grote and Giacomo Rosilho de Souza HTML | PDF

Math. Comp. 91 (2022), 2681-2714 Request permission

Abstract:

Stabilized Runge–Kutta methods are especially efficient for the numerical solution of large systems of stiff nonlinear differential equations because they are fully explicit. For semi-discrete parabolic problems, for instance, stabilized Runge–Kutta methods overcome the stringent stability condition of standard methods without sacrificing explicitness. However, when stiffness is only induced by a few components, as in the presence of spatially local mesh refinement, their efficiency deteriorates. To remove the crippling effect of a few severely stiff components on the entire system of differential equations, we derive a modified equation, whose stiffness solely depends on the remaining mildly stiff components. By applying stabilized Runge–Kutta methods to this modified equation, we then devise an explicit multirate Runge–Kutta–Chebyshev (mRKC) method whose stability conditions are independent of a few severely stiff components. Stability of the mRKC method is proved for a model problem, whereas its efficiency and usefulness are demonstrated through a series of numerical experiments.

References

Assyr Abdulle, Fourth order Chebyshev methods with recurrence relation, SIAM J. Sci. Comput. 23 (2002), no. 6, 2041–2054. MR 1923724, DOI 10.1137/S1064827500379549
Assyr Abdulle and Alexei A. Medovikov, Second order Chebyshev methods based on orthogonal polynomials, Numer. Math. 90 (2001), no. 1, 1–18. MR 1868760, DOI 10.1007/s002110100292
A. Abdulle and G. A. Pavliotis, Numerical methods for stochastic partial differential equations with multiple scales, J. Comput. Phys. 231 (2012), no. 6, 2482–2497. MR 2881027, DOI 10.1016/j.jcp.2011.11.039
Assyr Abdulle and Giacomo Rosilho de Souza, Explicit stabilized multirate method for stiff stochastic differential equations, SIAM J. Sci. Comput. 44 (2022), no. 4, A1859–A1883. MR 4448832, DOI 10.1137/21M1439018
A. Abdulle and G. Rosilho de Souza, Instabilities and order reduction phenomenon of an interpolation based multirate Runge–Kutta–Chebyshev method, Tech. Report, EPFL, arXiv:2003.03154 [math.NA], 2020.
Assyr Abdulle and Gilles Vilmart, PIROCK: a swiss-knife partitioned implicit-explicit orthogonal Runge-Kutta Chebyshev integrator for stiff diffusion-advection-reaction problems with or without noise, J. Comput. Phys. 242 (2013), 869–888. MR 3062064, DOI 10.1016/j.jcp.2013.02.009
J. F. Andrus, Numerical solution of systems of ordinary differential equations separated into subsystems, SIAM J. Numer. Anal. 16 (1979), no. 4, 605–611. MR 537274, DOI 10.1137/0716045
Marsha J. Berger and Joseph Oliger, Adaptive mesh refinement for hyperbolic partial differential equations, J. Comput. Phys. 53 (1984), no. 3, 484–512. MR 739112, DOI 10.1016/0021-9991(84)90073-1
Clint N. Dawson, Qiang Du, and Todd F. Dupont, A finite difference domain decomposition algorithm for numerical solution of the heat equation, Math. Comp. 57 (1991), no. 195, 63–71. MR 1079011, DOI 10.1090/S0025-5718-1991-1079011-4
Daniele Antonio Di Pietro and Alexandre Ern, Mathematical aspects of discontinuous Galerkin methods, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 69, Springer, Heidelberg, 2012. MR 2882148, DOI 10.1007/978-3-642-22980-0
Thierry Dumont, Max Duarte, Stéphane Descombes, Marie-Aimée Dronne, Marc Massot, and Violaine Louvet, Simulation of human ischemic stroke in realistic 3D geometry, Commun. Nonlinear Sci. Numer. Simul. 18 (2013), no. 6, 1539–1557. MR 3016905, DOI 10.1016/j.cnsns.2012.10.002
Weinan E, Analysis of the heterogeneous multiscale method for ordinary differential equations, Commun. Math. Sci. 1 (2003), no. 3, 423–436. MR 2069938, DOI 10.4310/CMS.2003.v1.n3.a3
Bjorn Engquist and Yen-Hsi Tsai, Heterogeneous multiscale methods for stiff ordinary differential equations, Math. Comp. 74 (2005), no. 252, 1707–1742. MR 2164093, DOI 10.1090/S0025-5718-05-01745-X
Ch. Engstler and Ch. Lubich, Multirate extrapolation methods for differential equations with different time scales, Computing 58 (1997), no. 2, 173–185 (English, with English and German summaries). MR 1443062, DOI 10.1007/BF02684438
W. H. Enright, T. E. Hull, and B. Lindberg, Comparing numerical methods for stiff systems of O.D.E:s, BIT 15 (1975), no. 1, 10–48.
Richard E. Ewing, Raytcho D. Lazarov, and Apostol T. Vassilev, Finite difference scheme for parabolic problems on composite grids with refinement in time and space, SIAM J. Numer. Anal. 31 (1994), no. 6, 1605–1622. MR 1302677, DOI 10.1137/0731083
R. E. Ewing, R. D. Lazarov, and P. S. Vassilevski, Finite difference schemes on grids with local refinement in time and space for parabolic problems. I. Derivation, stability, and error analysis, Computing 45 (1990), no. 3, 193–215 (English, with German summary). MR 1080791, DOI 10.1007/BF02250633
M. J. Gander and L. Halpern, Techniques for locally adaptive time stepping developed over the last two decades, Lect. Notes Comput. Sci. Eng. 91 (2013), no. 1, 377–385.
C. W. Gear and Ioannis G. Kevrekidis, Projective methods for stiff differential equations: problems with gaps in their eigenvalue spectrum, SIAM J. Sci. Comput. 24 (2003), no. 4, 1091–1106. MR 1976207, DOI 10.1137/S1064827501388157
C. W. Gear and D. R. Wells, Multirate linear multistep methods, BIT 24 (1984), no. 4, 484–502. MR 764821, DOI 10.1007/BF01934907
Marcus J. Grote, Michaela Mehlin, and Teodora Mitkova, Runge-Kutta-based explicit local time-stepping methods for wave propagation, SIAM J. Sci. Comput. 37 (2015), no. 2, A747–A775. MR 3324978, DOI 10.1137/140958293
G. Guennebaud and B. Jacob, Eigen v3, 2010, http://eigen.tuxfamily.org/.
A. Guillou and B. Lago, Domaine de stabilité associé aux formules d’intégration numérique d’équations différentielles, à pas séparés et à pas liés. Recherche de formules à grand rayon de stabilité, 1er Congr. Ass. Fran. Calc. AFCAL, Grenoble, 1960, pp. 43–56.
M. Günther, A. Kværnø, and P. Rentrop, Multirate partitioned Runge-Kutta methods, BIT 41 (2001), no. 3, 504–514. MR 1854271, DOI 10.1023/A:1021967112503
M. Günther and P. Rentrop, Multirate ROW methods and latency of electric circuits, Appl. Numer. Math. 13 (1993), no. 1-3, 83–102. Sixth Conference on the Numerical Treatment of Differential Equations (Halle, 1992). MR 1238766, DOI 10.1016/0168-9274(93)90133-C
Michael Günther and Adrian Sandu, Multirate generalized additive Runge Kutta methods, Numer. Math. 133 (2016), no. 3, 497–524. MR 3510018, DOI 10.1007/s00211-015-0756-z
Ernst Hairer, Christian Lubich, and Gerhard Wanner, Geometric numerical integration, Springer Series in Computational Mathematics, vol. 31, Springer, Heidelberg, 2010. Structure-preserving algorithms for ordinary differential equations; Reprint of the second (2006) edition. MR 2840298
E. Hairer, S. P. Nørsett, and G. Wanner, Solving ordinary differential equations. I, Springer Series in Computational Mathematics, vol. 8, Springer-Verlag, Berlin, 1987. Nonstiff problems. MR 868663, DOI 10.1007/978-3-662-12607-3
E. Hairer and G. Wanner, Solving ordinary differential equations. II, 2nd ed., Springer Series in Computational Mathematics, vol. 14, Springer-Verlag, Berlin, 1996. Stiff and differential-algebraic problems. MR 1439506, DOI 10.1007/978-3-642-05221-7
Marlis Hochbruck and Christian Lubich, A Gautschi-type method for oscillatory second-order differential equations, Numer. Math. 83 (1999), no. 3, 403–426. MR 1715573, DOI 10.1007/s002110050456
Marlis Hochbruck and Alexander Ostermann, Exponential integrators, Acta Numer. 19 (2010), 209–286. MR 2652783, DOI 10.1017/S0962492910000048
E. Hofer, A partially implicit method for large stiff systems of ODEs with only few equations introducing small time-constants, SIAM J. Numer. Anal. 13 (1976), no. 5, 645–663. MR 433887, DOI 10.1137/0713054
B. S. Kirk, J. W. Peterson, R. H. Stogner, and G. F. Carey, libMesh: a C++ library for parallel adaptive mesh refinement/coarsening simulations, Eng. Comput. 22 (2006), no. 3-4, 237–254.
Oswald Knoth and Ralf Wolke, Implicit-explicit Runge-Kutta methods for computing atmospheric reactive flows, Appl. Numer. Math. 28 (1998), no. 2-4, 327–341. Eighth Conference on the Numerical Treatment of Differential Equations (Alexisbad, 1997). MR 1655168, DOI 10.1016/S0168-9274(98)00051-8
A. Kværnø, Stability of multirate Runge–Kutta schemes, Proc. 10th Coll. Differ. Equations, vol. 1A, 1999, pp. 97–105.
V. I. Lebedev, How to solve stiff systems of differential equations by explicit methods, Numerical methods and applications, CRC, Boca Raton, FL, 1994, pp. 45–80. MR 1282307
V. I. Lebedev and A. A. Medovikov, Explicit Methods of Second Order for the Solution of Stiff Systems of ODEs, Russ. Acad. Sci., 1994.
B. Lindberg, IMPEX: a program package for solution of systems of stiff differential equations, Technical Report, Dept. of Information Processing, Royal Inst. of Tech., Stockholm, 1972.
Alexei A. Medovikov, High order explicit methods for parabolic equations, BIT 38 (1998), no. 2, 372–390. MR 1638136, DOI 10.1007/BF02512373
R. Minero, M. J. H. Anthonissen, and R. M. M. Mattheij, A local defect correction technique for time-dependent problems, Numer. Methods Partial Differential Equations 22 (2006), no. 1, 128–144. MR 2185528, DOI 10.1002/num.20078
T. Mirzakhanian, Multi-rate Runge–Kutta–Chebyshev time stepping for parabolic equations on adaptively refined meshes, Master Thesis, Boise State University, 2017, DOI 10.18122/B2V715.
John R. Rice, Split Runge-Kutta method for simultaneous equations, J. Res. Nat. Bur. Standards Sect. B 64B (1960), 151–170. MR 129136, DOI 10.6028/jres.064B.018
Steven Roberts, John Loffeld, Arash Sarshar, Carol S. Woodward, and Adrian Sandu, Implicit multirate GARK methods, J. Sci. Comput. 87 (2021), no. 1, Paper No. 4, 32. MR 4218017, DOI 10.1007/s10915-020-01400-z
Steven Roberts, Arash Sarshar, and Adrian Sandu, Coupled multirate infinitesimal GARK schemes for stiff systems with multiple time scales, SIAM J. Sci. Comput. 42 (2020), no. 3, A1609–A1638. MR 4101372, DOI 10.1137/19M1266952
G. Rosilho De Souza, Numerical methods for deterministic and stochastic differential equations with multiple scales and high contrasts, PhD Thesis, EPFL, Lausanne, 2020, DOI 10.5075/epfl-thesis-7445.
Adrian Sandu, A class of multirate infinitesimal GARK methods, SIAM J. Numer. Anal. 57 (2019), no. 5, 2300–2327. MR 4013926, DOI 10.1137/18M1205492
Adrian Sandu and Michael Günther, A generalized-structure approach to additive Runge-Kutta methods, SIAM J. Numer. Anal. 53 (2015), no. 1, 17–42. MR 3296613, DOI 10.1137/130943224
Arash Sarshar, Steven Roberts, and Adrian Sandu, Design of high-order decoupled multirate GARK schemes, SIAM J. Sci. Comput. 41 (2019), no. 2, A816–A847. MR 3928350, DOI 10.1137/18M1182875
V. Savcenco, W. Hundsdorfer, and J. G. Verwer, A multirate time stepping strategy for stiff ordinary differential equations, BIT 47 (2007), no. 1, 137–155. MR 2312501, DOI 10.1007/s10543-006-0095-7
V. Savcenco and R. M. M. Mattheij, Multirate numerical integration for stiff ODEs, Progress in industrial mathematics at ECMI 2008, Math. Ind., vol. 15, Springer, Heidelberg, 2010, pp. 327–332. MR 2767034, DOI 10.1007/978-3-642-12110-4_{5}0
J. M. Sexton and D. R. Reynolds, Relaxed multirate infinitesimal step methods for initial-value problems, Preprint, arXiv:1808.03718 [math.NA], 2019.
G. I. Shishkin and P. N. Vabishchevich, Interpolation finite difference schemes on grids locally refined in time, Comput. Methods Appl. Mech. Engrg. 190 (2000), no. 8-10, 889–901. MR 1797722, DOI 10.1016/S0045-7825(99)00451-X
Stig Skelboe and Per Ulfkjaer Andersen, Stability properties of backward Euler multirate formulas, SIAM J. Sci. Statist. Comput. 10 (1989), no. 5, 1000–1009. MR 1009552, DOI 10.1137/0910059
B. P. Sommeijer, L. F. Shampine, and J. G. Verwer, RKC: an explicit solver for parabolic PDEs, J. Comput. Appl. Math. 88 (1998), no. 2, 315–326. MR 1613246, DOI 10.1016/S0377-0427(97)00219-7
R. A. Trompert and J. G. Verwer, A static-regridding method for two-dimensional parabolic partial differential equations, Appl. Numer. Math. 8 (1991), no. 1, 65–90. MR 1128618, DOI 10.1016/0168-9274(91)90098-K
J. G. Verwer and R. A. Trompert, Analysis of local uniform grid refinement, Appl. Numer. Math. 13 (1993), no. 1-3, 251–270. Sixth Conference on the Numerical Treatment of Differential Equations (Halle, 1992). MR 1238780, DOI 10.1016/0168-9274(93)90147-J
R. A. Trompert and J. G. Verwer, Analysis of the implicit Euler local uniform grid refinement method, SIAM J. Sci. Comput. 14 (1993), no. 2, 259–278. MR 1204230, DOI 10.1137/0914017
R. A. Trompert and J. G. Verwer, Runge-Kutta methods and local uniform grid refinement, Math. Comp. 60 (1993), no. 202, 591–616. MR 1181332, DOI 10.1090/S0025-5718-1993-1181332-3
P. J. van der Houwen and B. P. Sommeijer, On the internal stability of explicit, $m$-stage Runge-Kutta methods for large $m$-values, Z. Angew. Math. Mech. 60 (1980), no. 10, 479–485 (English, with German and Russian summaries). MR 614285, DOI 10.1002/zamm.19800601005
Eric Vanden-Eijnden, Numerical techniques for multi-scale dynamical systems with stochastic effects, Commun. Math. Sci. 1 (2003), no. 2, 385–391. MR 1980483, DOI 10.4310/CMS.2003.v1.n2.a11
A. S. Vasudeva Murthy and J. G. Verwer, Solving parabolic integro-differential equations by an explicit integration method, J. Comput. Appl. Math. 39 (1992), no. 1, 121–132. MR 1158196, DOI 10.1016/0377-0427(92)90229-Q
J. G. Verwer, An implementation of a class of stabilized explicit methods for the time integration of parabolic equations, ACM Trans. Math. Software 6 (1980), no. 2, 188–205.
J. G. Verwer, Explicit Runge-Kutta methods for parabolic partial differential equations, Appl. Numer. Math. 22 (1996), no. 1-3, 359–379. Special issue celebrating the centenary of Runge-Kutta methods. MR 1424308, DOI 10.1016/S0168-9274(96)00022-0
J. G. Verwer, W. H. Hundsdorfer, and B. P. Sommeijer, Convergence properties of the Runge-Kutta-Chebyshev method, Numer. Math. 57 (1990), no. 2, 157–178. MR 1048310, DOI 10.1007/BF01386405
Jörg Wensch, Oswald Knoth, and Alexander Galant, Multirate infinitesimal step methods for atmospheric flow simulation, BIT 49 (2009), no. 2, 449–473. MR 2507611, DOI 10.1007/s10543-009-0222-3
Christophe J. Zbinden, Partitioned Runge-Kutta-Chebyshev methods for diffusion-advection-reaction problems, SIAM J. Sci. Comput. 33 (2011), no. 4, 1707–1725. MR 2821265, DOI 10.1137/100807892