×

High-order multiderivative time integrators for hyperbolic conservation laws. (English) Zbl 1304.65223

Summary: Multiderivative time integrators have a long history of development for ordinary differential equations, and yet to date, only a small subset of these methods have been explored as a tool for solving partial differential equations (PDEs). This large class of time integrators include all popular (multistage) Runge-Kutta as well as single-step (multiderivative) Taylor methods. (The latter are commonly referred to as Lax-Wendroff methods when applied to PDEs). In this work, we offer explicit multistage multiderivative time integrators for hyperbolic conservation laws. Like Lax-Wendroff methods, multiderivative integrators permit the evaluation of higher derivatives of the unknown in order to decrease the memory footprint and communication overhead. Like traditional Runge-Kutta methods, multiderivative integrators admit the addition of extra stages, which introduce extra degrees of freedom that can be used to increase the order of accuracy or modify the region of absolute stability. We describe a general framework for how these methods can be applied to two separate spatial discretizations: the discontinuous Galerkin (DG) method and the finite difference essentially non-oscillatory (FD-WENO) method. The two proposed implementations are substantially different: for DG we leverage techniques that are closely related to generalized Riemann solvers; for FD-WENO we construct higher spatial derivatives with central differences. Among multiderivative time integrators, we argue that multistage two-derivative methods have the greatest potential for multidimensional applications, because they only require the flux function and its Jacobian, which is readily available. Numerical results indicate that multiderivative methods are indeed competitive with popular strong stability preserving time integrators.

MSC:

65M60 Finite element, Rayleigh-Ritz and Galerkin methods for initial value and initial-boundary value problems involving PDEs
35L65 Hyperbolic conservation laws
65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
65M20 Method of lines for initial value and initial-boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bettis, D.G., Horn, M.K.: An optimal \[(m+3)[m+4]\](m+3)[m+4] Runge Kutta algorithm. In: Proceedings of the Fifth Conference on Mathematical Methods in Celestial Mechanics (Oberwolfach, 1975), Part I, vol. 14, pp. 133-140 (1976) · Zbl 0346.65029
[2] Borges, R., Carmona, M., Costa, B., Don, W.S.: An improved weighted essentially non-oscillatory scheme for hyperbolic conservation laws. J. Comput. Phys. 227(6), 3191-3211 (2008) · Zbl 1136.65076 · doi:10.1016/j.jcp.2007.11.038
[3] Buckley, S.E., Leverett, M.C.: Mechanism of fluid displacement in sands. Trans. AIME 146(1), 107-116 (1942) · Zbl 0674.65061
[4] Butcher, J.C.: General linear methods: a survey. Appl. Numer. Math. 1(4), 273-284 (1985) · Zbl 0619.65057 · doi:10.1016/0168-9274(85)90007-8
[5] Butcher, J.C.: General linear methods. Comput. Math. Appl. 31(4-5), 105-112 (1996). Selected topics in numerical methods (Miskolc, 1994) · Zbl 0874.65057
[6] Butcher, J.C.: General linear methods. Acta Numer. 15, 157-256 (2006) · Zbl 1113.65072 · doi:10.1017/S0962492906220014
[7] Castro, M., Costa, B., Don, W.S.: High order weighted essentially non-oscillatory WENO-Z schemes for hyperbolic conservation laws. J. Comput. Phys. 230(5), 1766-1792 (2011) · Zbl 1211.65108 · doi:10.1016/j.jcp.2010.11.028
[8] Chan, R.P.K., Tsai, A.Y.J.: On explicit two-derivative Runge-Kutta methods. Numer. Algorithms 53(2-3), 171-194 (2010) · Zbl 1185.65122 · doi:10.1007/s11075-009-9349-1
[9] Cockburn, B., Shu, C.W.: Runge-Kutta discontinuous Galerkin methods for convection-dominated problems. J. Sci. Comput. 16(3), 173-261 (2002) · Zbl 1065.76135 · doi:10.1023/A:1012873910884
[10] Daru, V., Tenaud, C.: High order one-step monotonicity-preserving schemes for unsteady compressible flow calculations. J. Comput. Phys. 193(2), 563-594 (2004) · Zbl 1109.76338 · doi:10.1016/j.jcp.2003.08.023
[11] Dumbser, M., Balsara, D.S., Toro, E.F., Munz, C.D.: A unified framework for the construction of one-step finite volume and discontinuous Galerkin schemes on unstructured meshes. J. Comput. Phys. 227(18), 8209-8253 (2008) · Zbl 1147.65075 · doi:10.1016/j.jcp.2008.05.025
[12] Dumbser, M., Munz, C.D.: Building blocks for arbitrary high order discontinuous Galerkin schemes. J. Sci. Comput. 27(1-3), 215-230 (2006) · Zbl 1115.65100 · doi:10.1007/s10915-005-9025-0
[13] Fehlberg, E.: Neue genauere Runge-Kutta-Formeln für Differentialgleichungen \[n\] n-ter Ordnung. Z. Angew. Math. Mech. 40, 449-455 (1960) · Zbl 0099.33202 · doi:10.1002/zamm.19600401003
[14] Fehlberg, E.: New high-order Runge-Kutta formulas with step size control for systems of first- and second-order differential equations. Z. Angew. Math. Mech. 44, T17-T29 (1964) · Zbl 0137.33105 · doi:10.1002/zamm.19640440303
[15] Friedman, A.: A new proof and generalizations of the Cauchy-Kowalewski theorem. Trans. Am. Math. Soc. 98, 1-20 (1961) · Zbl 0117.31002 · doi:10.1090/S0002-9947-1961-0166462-2
[16] Fusaro, B.A.: The Cauchy-Kowalewski theorem and a singular initial value problem. SIAM Rev. 10, 417-421 (1968) · Zbl 0169.12801 · doi:10.1137/1010092
[17] Gekeler, E., Widmann, R.: On the order conditions of Runge-Kutta methods with higher derivatives. Numer. Math. 50(2), 183-203 (1986) · Zbl 0589.65057 · doi:10.1007/BF01390429
[18] Goeken, D., Johnson, O.: Fifth-order Runge-Kutta with higher order derivative approximations. In: Proceedings of the 15th Annual Conference of Applied Mathematics (Edmond, OK, 1999), Electron. J. Differ. Equ. Conf., vol. 2, pp. 1-9 (electronic). Southwest Texas State University, San Marcos, TX (1999) · Zbl 0941.65069
[19] Goeken, D., Johnson, O.: Runge-Kutta with higher order derivative approximations. Appl. Numer. Math. 34(2-3), 207-218 (2000). Auckland numerical ordinary differential equations (Auckland, 1998) · Zbl 0951.65068
[20] Gottlieb, S.: On high order strong stability preserving Runge-Kutta and multi step time discretizations. J. Sci. Comput. 25(1-2), 105-128 (2005) · Zbl 1203.65166
[21] Gottlieb, S., Shu, C.W.: Total variation diminishing Runge-Kutta schemes. Math. Comput. Am. 67(221), 73-85 (1998) · Zbl 0897.65058 · doi:10.1090/S0025-5718-98-00913-2
[22] Gottlieb, S., Shu, C.W., Tadmor, E.: Strong stability-preserving high-order time discretization methods. SIAM Rev. 43(1), 89-112 (electronic) (2001) · Zbl 0967.65098
[23] Hairer, E., Nørsett, S.P., Wanner, G.: Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, 2nd revised edn. Springer, Berlin (1991) · doi:10.1007/978-3-662-09947-6
[24] Hairer, E., Nørsett, S.P., Wanner, G.: Solving Ordinary Differential Equations I: Nonstiff Problems, Springer Series in Computational Mathematics, vol. 1, 3rd edn. Springer, Berlin (2009) · Zbl 1185.65115
[25] Hairer, E., Wanner, G.: Multistep-multistage-multiderivative methods of ordinary differential equations. Computing (Arch. Elektron. Rechnen) 11(3), 287-303 (1973) · Zbl 0271.65048
[26] Harten, A.: The artificial compression method for computation of shocks and contact discontinuities. III. Self-adjusting hybrid schemes. Math. Comput. 32(142), 363-389 (1978) · Zbl 0409.76057
[27] Harten, A., Engquist, B., Osher, S., Chakravarthy, S.R.: Uniformly high-order accurate essentially nonoscillatory schemes. III. J. Comput. Phys. 71(2), 231-303 (1987) · Zbl 0652.65067 · doi:10.1016/0021-9991(87)90031-3
[28] Harten, A., Lax, P.D., van Leer, B.: On upstream differencing and Godunov-type schemes for hyperbolic conservation laws. SIAM Rev. 25(1), 35-61 (1983) · Zbl 0565.65051 · doi:10.1137/1025002
[29] Henrick, A.K., Aslam, T.D., Powers, J.M.: Mapped weighted essentially non-oscillatory schemes: Achieving optimal order near critical points. J. Comput. Phys. 207(2), 542-567 (2005) · Zbl 1072.65114 · doi:10.1016/j.jcp.2005.01.023
[30] Jiang, G.S., Shu, C.W.: Efficient implementation of weighted ENO schemes. J. Comput. Phys. 126(1), 202-228 (1996) · Zbl 0877.65065 · doi:10.1006/jcph.1996.0130
[31] Kastlunger, K., Wanner, G.: On Turán type implicit Runge-Kutta methods. Computing (Arch. Elektron. Rechnen) 9, 317-325 (1972) · Zbl 0258.65078
[32] Kastlunger, K.H., Wanner, G.: Runge Kutta processes with multiple nodes. Computing (Arch. Elektron. Rechnen) 9, 9-24 (1972) · Zbl 0234.65067
[33] Ketcheson, D.I.: Highly efficient strong stability-preserving Runge-Kutta methods with low-storage implementations. SIAM J. Sci. Comput. 30(4), 2113-2136 (2008) · Zbl 1168.65382 · doi:10.1137/07070485X
[34] Ketcheson, D.I.: Runge-Kutta methods with minimum storage implementations. J. Comput. Phys. 229(5), 1763-1773 (2010) · Zbl 1183.65093 · doi:10.1016/j.jcp.2009.11.006
[35] Krivodonova, L.: Limiters for high-order discontinuous Galerkin methods. J. Comput. Phys. 226(1), 879-896 (2007) · Zbl 1125.65091 · doi:10.1016/j.jcp.2007.05.011
[36] Lax, P., Wendroff, B.: Systems of conservation laws. Comm. Pure Appl. Math. 13, 217-237 (1960) · Zbl 0152.44802 · doi:10.1002/cpa.3160130205
[37] LeVeque, R.: Finite Volume Methods for Hyperbolic Problems. Cambridge University Press, Cambridge (2002) · Zbl 1010.65040 · doi:10.1017/CBO9780511791253
[38] Liu, W., Cheng, J., Shu, C.W.: High order conservative Lagrangian schemes with Lax-Wendroff type time discretization for the compressible Euler equations. J. Comput. Phys. 228(23), 8872-8891 (2009) · Zbl 1287.76181 · doi:10.1016/j.jcp.2009.09.001
[39] Lu, C., Qiu, J.: Simulations of shallow water equations with finite difference Lax-Wendroff weighted essentially non-oscillatory schemes. J. Sci. Comput. 47(3), 281-302 (2011) · Zbl 1358.76017 · doi:10.1007/s10915-010-9437-3
[40] Mitsui, T.: Runge-Kutta type integration formulas including the evaluation of the second derivative. I. Publ. Res. Inst. Math. Sci. 18(1), 325-364 (1982) · Zbl 0529.65042 · doi:10.2977/prims/1195184026
[41] Montecinos, G., Castro, C.E., Dumbser, M., Toro, E.F.: Comparison of solvers for the generalized Riemann problem for hyperbolic systems with source terms. J. Comput. Phys. 231(19), 6472-6494 (2012) · Zbl 1284.35268 · doi:10.1016/j.jcp.2012.06.011
[42] Nguyen-Ba, T., Božić, V., Kengne, E., Vaillancourt, R.: Nine-stage multi-derivative Runge-Kutta method of order 12. Publ. Inst. Math. (Beograd) (N.S.) 86(100), 75-96 (2009) · Zbl 1265.65134 · doi:10.2298/PIM0900075N
[43] Niegemann, J., Diehl, R., Busch, K.: Efficient low-storage Runge-Kutta schemes with optimized stability regions. J. Comput. Phys. 231(2), 364-372 (2012) · Zbl 1243.65113 · doi:10.1016/j.jcp.2011.09.003
[44] Obreschkoff, N.: Neue Quadraturformeln. Abh. Preuss. Akad. Wiss. Math.-Nat. Kl. 1940(4), 20 (1940) · Zbl 0169.12801
[45] Ono, H., Yoshida, T.: Two-stage explicit Runge-Kutta type methods using derivatives. Jpn. J. Ind. Appl. Math. 21(3), 361-374 (2004) · Zbl 1061.65066 · doi:10.1007/BF03167588
[46] Qiu, J.: A numerical comparison of the Lax-Wendroff discontinuous Galerkin method based on different numerical fluxes. J. Sci. Comput. 30(3), 345-367 (2007) · Zbl 1176.76080 · doi:10.1007/s10915-006-9109-5
[47] Qiu, J.: WENO schemes with Lax-Wendroff type time discretizations for Hamilton-Jacobi equations. J. Comput. Appl. Math. 200(2), 591-605 (2007) · Zbl 1115.65094 · doi:10.1016/j.cam.2006.01.022
[48] Qiu, J., Dumbser, M., Shu, C.W.: The discontinuous Galerkin method with Lax-Wendroff type time discretizations. Comput. Methods Appl. Mech. Eng. 194(42-44), 4528-4543 (2005) · Zbl 1093.76038 · doi:10.1016/j.cma.2004.11.007
[49] Qiu, J., Shu, C.W.: Finite difference WENO schemes with Lax-Wendroff-type time discretizations. SIAM J. Sci. Comput. 24(6), 2185-2198 (2003) · Zbl 1034.65073 · doi:10.1137/S1064827502412504
[50] Reed, W., Hill, T.: Triangular mesh methods for the neutron transport equation. Technical report LA-UR-73-479, Los Alamos Scientific Laboratory (1973) · Zbl 0099.33202
[51] Roe, P.L.: Approximate Riemann solvers, parameter vectors, and difference schemes. J. Comput. Phys. 43(2), 357-372 (1981) · Zbl 0474.65066 · doi:10.1016/0021-9991(81)90128-5
[52] Rossmanith, J.: DoGPack software (2013). Available from http://www.dogpack-code.org · Zbl 1147.65075
[53] Rossmanith, J.A., Seal, D.C.: A positivity-preserving high-order semi-Lagrangian discontinuous Galerkin scheme for the Vlasov-Poisson equations. J. Comput. Phys. 230(16), 6203-6232 (2011) · Zbl 1419.76506 · doi:10.1016/j.jcp.2011.04.018
[54] Rusanov, V.V.: The calculation of the interaction of non-stationary shock waves with barriers. Ž. Vyčisl. Mat. i Mat. Fiz. 1, 267-279 (1961)
[55] Seal, D.C.: Discontinuous Galerkin methods for Vlasov models of plasma. Ph.D. thesis, Madison, WI, University of Wisconsin, Madison, WI (2012) · Zbl 0589.65057
[56] Shintani, H.: On one-step methods utilizing the second derivative. Hiroshima Math. J. 1, 349-372 (1971) · Zbl 0284.65055
[57] Shintani, H.: On explicit one-step methods utilizing the second derivative. Hiroshima Math. J. 2, 353-368 (1972) · Zbl 0284.65056
[58] Shu, C.W.: Essentially non-oscillatory and weighted essentially non-oscillatory schemes for hyperbolic conservation laws. In: Advanced numerical approximation of nonlinear hyperbolic equations (Cetraro, 1997), Lecture Notes in Mathematics, vol. 1697, pp. 325-432. Springer, Berlin (1998) · Zbl 0927.65111
[59] Shu, C.W.: High-order finite difference and finite volume WENO schemes and discontinuous Galerkin methods for CFD. Int. J. Comput. Fluid Dyn. 17(2), 107-118 (2003) · Zbl 1034.76044 · doi:10.1080/1061856031000104851
[60] Shu, C.W.: High order weighted essentially nonoscillatory schemes for convection dominated problems. SIAM Rev. 51(1), 82-126 (2009) · Zbl 1160.65330 · doi:10.1137/070679065
[61] Shu, C.W., Osher, S.: Efficient implementation of essentially nonoscillatory shock-capturing schemes. J. Comput. Phys. 77(2), 439-471 (1988) · Zbl 0653.65072 · doi:10.1016/0021-9991(88)90177-5
[62] Shu, C.W., Osher, S.: Efficient implementation of essentially nonoscillatory shock-capturing schemes, II. J. Comput. Phys. 83(1), 32-78 (1989) · Zbl 0674.65061 · doi:10.1016/0021-9991(89)90222-2
[63] Stancu, D.D., Stroud, A.H.: Quadrature formulas with simple Gaussian nodes and multiple fixed nodes. Math. Comput. 17, 384-394 (1963) · Zbl 0233.65013 · doi:10.1090/S0025-5718-1963-0157485-3
[64] Taube, A., Dumbser, M., Balsara, D.S., Munz, C.D.: Arbitrary high-order discontinuous Galerkin schemes for the magnetohydrodynamic equations. J. Sci. Comput. 30(3), 441-464 (2007) · Zbl 1176.76075 · doi:10.1007/s10915-006-9101-0
[65] Titarev, V.A., Toro, E.F.: ADER: Arbitrary high order Godunov approach. In: Proceedings of the Fifth International Conference on Spectral and High Order Methods (ICOSAHOM-01) (Uppsala), vol. 17, pp. 609-618 (2002) · Zbl 1024.76028
[66] Titarev, V.A., Toro, E.F.: ADER schemes for three-dimensional non-linear hyperbolic systems. J. Comput. Phys. 204(2), 715-736 (2005) · Zbl 1060.65641
[67] Toro, E.F.: Riemann Solvers and Numerical Methods for Fluid Dynamics: A Practical Introduction, 2nd edn. Springer, Berlin (1999) · Zbl 0923.76004
[68] Toro, E.F., Titarev, V.A.: Solution of the generalized Riemann problem for advection-reaction equations. R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 458(2018), 271-281 (2002) · Zbl 1019.35061
[69] Toro, E.F., Titarev, V.A.: ADER schemes for scalar non-linear hyperbolic conservation laws with source terms in three-space dimensions. J. Comput. Phys. 202(1), 196-215 (2005) · Zbl 1061.65103
[70] Toro, E.F., Titarev, V.A.: TVD fluxes for the high-order ADER schemes. J. Sci. Comput. 24(3), 285-309 (2005) · Zbl 1096.76029
[71] Turán, P.: On the theory of the mechanical quadrature. Acta Sci. Math. Szeged 12(Leopoldo Fejer et Frederico Riesz LXX annos natis dedicatus, Pars A), 30-37 (1950) · Zbl 0045.33606
[72] Williamson, J.H.: Low-storage Runge-Kutta schemes. J. Comput. Phys. 35(1), 48-56 (1980) · Zbl 0425.65038 · doi:10.1016/0021-9991(80)90033-9
[73] Yoshida, T., Ono, H.: Two stage explicit Runge-Kutta type method using second and third derivatives. IPSJ J. 44(1), 82-87 (2003)
[74] Zurmühl, R.: Runge-Kutta-Verfahren unter Verwendung höherer Ableitungen. Z. Angew. Math. Mech. 32, 153-154 (1952) · Zbl 0047.36501 · doi:10.1002/zamm.19520320407
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.