Top

Journal of Scientific Computing

Published in:

01-07-2014

High-Order Multiderivative Time Integrators for Hyperbolic Conservation Laws

Authors: David C. Seal, Yaman Güçlü, Andrew J. Christlieb

Published in: Journal of Scientific Computing | Issue 1/2014

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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.

previous article Domain Decomposition Methods for Nonlocal Total Variation Image Restoration

next article Richardson Extrapolation on Some Recent Numerical Quadrature Formulas for Singular and Hypersingular Integrals and Its Study of Stability

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

When applied to partial differential equations, Taylor methods are commonly referred to as Lax–Wendroff methods.

A finite difference method is conservative if the method satisfies \(\frac{d}{dt}\left( \sum _i q_i(t) \right) = 0\) on a periodic (or infinite) domain.

Bettis, D.G., Horn, M.K.: An optimal \((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)

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)CrossRefMATHMathSciNet

Buckley, S.E., Leverett, M.C.: Mechanism of fluid displacement in sands. Trans. AIME 146(1), 107–116 (1942)

Butcher, J.C.: General linear methods: a survey. Appl. Numer. Math. 1(4), 273–284 (1985)CrossRefMATHMathSciNet

Butcher, J.C.: General linear methods. Comput. Math. Appl. 31(4–5), 105–112 (1996). Selected topics in numerical methods (Miskolc, 1994)

Butcher, J.C.: General linear methods. Acta Numer. 15, 157–256 (2006)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

Chan, R.P.K., Tsai, A.Y.J.: On explicit two-derivative Runge-Kutta methods. Numer. Algorithms 53(2–3), 171–194 (2010)CrossRefMATHMathSciNet

Cockburn, B., Shu, C.W.: Runge-Kutta discontinuous Galerkin methods for convection-dominated problems. J. Sci. Comput. 16(3), 173–261 (2002)CrossRefMathSciNet

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)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

12.

Dumbser, M., Munz, C.D.: Building blocks for arbitrary high order discontinuous Galerkin schemes. J. Sci. Comput. 27(1–3), 215–230 (2006)CrossRefMATHMathSciNet

13.

Fehlberg, E.: Neue genauere Runge-Kutta-Formeln für Differentialgleichungen \(n\)-ter Ordnung. Z. Angew. Math. Mech. 40, 449–455 (1960)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

15.

Friedman, A.: A new proof and generalizations of the Cauchy-Kowalewski theorem. Trans. Am. Math. Soc. 98, 1–20 (1961)CrossRefMATH

16.

Fusaro, B.A.: The Cauchy-Kowalewski theorem and a singular initial value problem. SIAM Rev. 10, 417–421 (1968)CrossRefMATHMathSciNet

17.

Gekeler, E., Widmann, R.: On the order conditions of Runge-Kutta methods with higher derivatives. Numer. Math. 50(2), 183–203 (1986)CrossRefMATHMathSciNet

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)

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)

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)MATHMathSciNet

21.

Gottlieb, S., Shu, C.W.: Total variation diminishing Runge-Kutta schemes. Math. Comput. Am. 67(221), 73–85 (1998)CrossRefMATHMathSciNet

22.

Gottlieb, S., Shu, C.W., Tadmor, E.: Strong stability-preserving high-order time discretization methods. SIAM Rev. 43(1), 89–112 (electronic) (2001)

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)CrossRef

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)

25.

Hairer, E., Wanner, G.: Multistep-multistage-multiderivative methods of ordinary differential equations. Computing (Arch. Elektron. Rechnen) 11(3), 287–303 (1973)MATHMathSciNet

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)MATHMathSciNet

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)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

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)CrossRefMATH

30.

Jiang, G.S., Shu, C.W.: Efficient implementation of weighted ENO schemes. J. Comput. Phys. 126(1), 202–228 (1996)CrossRefMATHMathSciNet

31.

Kastlunger, K., Wanner, G.: On Turán type implicit Runge-Kutta methods. Computing (Arch. Elektron. Rechnen) 9, 317–325 (1972)

32.

Kastlunger, K.H., Wanner, G.: Runge Kutta processes with multiple nodes. Computing (Arch. Elektron. Rechnen) 9, 9–24 (1972)MATHMathSciNet

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)CrossRefMathSciNet

34.

Ketcheson, D.I.: Runge-Kutta methods with minimum storage implementations. J. Comput. Phys. 229(5), 1763–1773 (2010)CrossRefMATHMathSciNet

35.

Krivodonova, L.: Limiters for high-order discontinuous Galerkin methods. J. Comput. Phys. 226(1), 879–896 (2007)CrossRefMATHMathSciNet

36.

Lax, P., Wendroff, B.: Systems of conservation laws. Comm. Pure Appl. Math. 13, 217–237 (1960)CrossRefMATHMathSciNet

37.

LeVeque, R.: Finite Volume Methods for Hyperbolic Problems. Cambridge University Press, Cambridge (2002)CrossRefMATH

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)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

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)CrossRefMathSciNet

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)CrossRefMATHMathSciNet

44.

Obreschkoff, N.: Neue Quadraturformeln. Abh. Preuss. Akad. Wiss. Math.-Nat. Kl. 1940(4), 20 (1940)

45.

Ono, H., Yoshida, T.: Two-stage explicit Runge-Kutta type methods using derivatives. Jpn. J. Ind. Appl. Math. 21(3), 361–374 (2004)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

47.

Qiu, J.: WENO schemes with Lax-Wendroff type time discretizations for Hamilton-Jacobi equations. J. Comput. Appl. Math. 200(2), 591–605 (2007)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

50.

Reed, W., Hill, T.: Triangular mesh methods for the neutron transport equation. Technical report LA-UR-73-479, Los Alamos Scientific Laboratory (1973)

51.

Roe, P.L.: Approximate Riemann solvers, parameter vectors, and difference schemes. J. Comput. Phys. 43(2), 357–372 (1981)CrossRefMATHMathSciNet

52.

Rossmanith, J.: DoGPack software (2013). Available from http://www.dogpack-code.org

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)CrossRefMATHMathSciNet

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)MathSciNet

55.

Seal, D.C.: Discontinuous Galerkin methods for Vlasov models of plasma. Ph.D. thesis, Madison, WI, University of Wisconsin, Madison, WI (2012)

56.

Shintani, H.: On one-step methods utilizing the second derivative. Hiroshima Math. J. 1, 349–372 (1971)MATHMathSciNet

57.

Shintani, H.: On explicit one-step methods utilizing the second derivative. Hiroshima Math. J. 2, 353–368 (1972)MATHMathSciNet

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)

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)CrossRefMATHMathSciNet

60.

Shu, C.W.: High order weighted essentially nonoscillatory schemes for convection dominated problems. SIAM Rev. 51(1), 82–126 (2009)CrossRefMATHMathSciNet

61.

Shu, C.W., Osher, S.: Efficient implementation of essentially nonoscillatory shock-capturing schemes. J. Comput. Phys. 77(2), 439–471 (1988)CrossRefMATHMathSciNet

62.

Shu, C.W., Osher, S.: Efficient implementation of essentially nonoscillatory shock-capturing schemes, II. J. Comput. Phys. 83(1), 32–78 (1989)CrossRefMATHMathSciNet

63.

Stancu, D.D., Stroud, A.H.: Quadrature formulas with simple Gaussian nodes and multiple fixed nodes. Math. Comput. 17, 384–394 (1963)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

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)

66.

Titarev, V.A., Toro, E.F.: ADER schemes for three-dimensional non-linear hyperbolic systems. J. Comput. Phys. 204(2), 715–736 (2005)

67.

Toro, E.F.: Riemann Solvers and Numerical Methods for Fluid Dynamics: A Practical Introduction, 2nd edn. Springer, Berlin (1999)

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)

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)

70.

Toro, E.F., Titarev, V.A.: TVD fluxes for the high-order ADER schemes. J. Sci. Comput. 24(3), 285–309 (2005)

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)

72.

Williamson, J.H.: Low-storage Runge-Kutta schemes. J. Comput. Phys. 35(1), 48–56 (1980)CrossRefMATHMathSciNet

73.

Yoshida, T., Ono, H.: Two stage explicit Runge-Kutta type method using second and third derivatives. IPSJ J. 44(1), 82–87 (2003)MathSciNet

74.

Zurmühl, R.: Runge-Kutta-Verfahren unter Verwendung höherer Ableitungen. Z. Angew. Math. Mech. 32, 153–154 (1952)CrossRefMATHMathSciNet

Title: High-Order Multiderivative Time Integrators for Hyperbolic Conservation Laws
Authors: David C. Seal
Yaman Güçlü
Andrew J. Christlieb
Publication date: 01-07-2014
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 1/2014
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-013-9787-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2014

Star-Based a Posteriori Error Estimates for Elliptic Problems

Domain Decomposition Methods for Nonlocal Total Variation Image Restoration

The Local Discontinuous Galerkin Method for the Fourth-Order Euler–Bernoulli Partial Differential Equation in One Space Dimension. Part II: A Posteriori Error Estimation

Kullback–Leibler Divergence Based Composite Prior Modeling for Bayesian Super-Resolution

A Partition of Unity Method with Penalty for Fourth Order Problems

Adaptive Finite Element Approximation for an Elliptic Optimal Control Problem with Both Pointwise and Integral Control Constraints

Premium Partner