Abstract
This paper constructs multirate time discretizations for hyperbolic conservation laws that allow different timesteps to be used in different parts of the spatial domain. The proposed family of discretizations is second order accurate in time and has conservation and linear and nonlinear stability properties under local CFL conditions. Multirate timestepping avoids the necessity to take small global timesteps (restricted by the largest value of the Courant number on the grid) and therefore results in more efficient algorithms. Numerical results obtained for the advection and Burgers’ equations confirm the theoretical findings.
Similar content being viewed by others
References
Andrus, J.: Numerical solution for ordinary differential equations separated into subsystems. SIAM J. Numer. Anal. 16, 605–611 (1979)
Andrus, J.: Stability of a multi-rate method for numerical integration of ODEs. Comput. Math. Appl. 25, 3–14 (1993)
Bartel, A., Günther, M.: A multirate W-method for electrical networks in state-space formulation. J. Comput. Appl. Math. 147, 411–425 (2002)
Berkvens, P., Botchev, M., Lioen, W., Verwer, J.: A zooming technique for wind transport of air pollution. Tech. report, Centrum voor Wiskundeen Informatica, 1999
Boris, J., Book, D.: Flux-corrected transport I. SHASTA, a fluid transport algorithm that works. J. Comput. Phys. 135, 172–186 (1997)
Chakravarthy, S., Osher, S.: Numerical experiments with the Osher upwind scheme for the Euler equations. AIAA J. 21, 241–1248 (1983)
Chakravarthy, S., Osher, S.: Computing with high-resolution upwind schemes for hyperbolic equations. Lect. Appl. Math. 22, 57–86 (1985)
Dawson, C., Kirby, R.: High resolution schemes for conservation laws with locally varying time steps. SIAM J. Sci. Comput. 22, 2256–2281 (2001)
Dormand, J., Prince, P.J.: A family of embedded Runge–Kutta formulae. J. Comput. Appl. Math. 6, 19–26 (1980)
Engquist, B., Tsai, R.: Heterogeneous multiscale methods for stiff ordinary differential equations. Math. Comput. 74, 1707–1742 (2005)
Engstler, C., Lubich, C.: Multirate extrapolation methods for differential equations with different time scales. Computing 58, 173–185 (1997)
Ferm, L., Lötstedt, P.: Space–time adaptive solution of first order PDES. J. Sci. Comput. 26, 83–110 (2006)
Ferracina, L., Spijker, M.: Stepsize restrictions for total-variation-boundedness in general Runge–Kutta procedures. Appl. Numer. Math. 53, 265–279 (2005)
Gear, C., Wells, D.: Multirate linear multistep methods. BIT 24, 484–502 (1984)
Godunov, S.: A finite difference method for the numerical computation of discontinuous solutions of the equations of fluid dynamics. Mat. Sb. 47, 271–290 (1959)
Goodman, J., LeVeque, R., Randall, J.: On the accuracy of stable schemes for 2D scalar conservation laws. Math. Comput. 45, 15–21 (1985)
Gottlieb, S., Shu, C.-W.: Total variation diminishing Runge–Kutta schemes. Math. Comput. 67, 73–85 (1998)
Gottlieb, S., Shu, C.-W., Tadmor, E.: Strong stability-preserving high-order time discretization methods. SIAM Rev. 43, 89–112 (2001)
Günther, M., Hoschek, M.: ROW methods adapted to electric circuit simulation packages. In: ICCAM ’96: Proceedings of the 7th International Congress on Computational and Applied Mathematics, pp. 159–170. Elsevier, Amsterdam (1997)
Günther, M., Kværnø, A., Rentrop, P.: Multirate partitioned Runge–Kutta methods. BIT 41, 504–514 (2001)
Günther, M., Rentrop, P.: Multirate ROW-methods and latency of electric circuits, Appl. Numer. Math. (1993)
Hairer, E.: Order conditions for numerical methods for partitioned ordinary differential equations. Numer. Math. 36, 431–445 (1981)
Hairer, E., Norsett, S., Wanner, G.: Solving Ordinary Differential Equations I. Nonstiff Problems. Springer, Berlin (1993), Chapter II. 1
Hairer, E., Norsett, S., Wanner, G.: Solving Ordinary Differential Equations I: Nonstiff Problems. Springer, Berlin (1993) Chapter. II. 15
Harten, A.: High resolution schemes for hyperbolic conservation laws. J. Comput. Phys. 49, 357–393 (1983)
Higueras, I.: On strong stability preserving time discretization methods. J. Sci. Comput. 21, 193–223 (2004)
Hundsdorfer, W., Koren, B., van Loon, M.: A positive finite-difference advection scheme. J. Comput. Phys. 117, 35–46 (1995)
Hundsdorfer, W., Ruuth, S., Spiteri, R.: Monotonicity-preserving linear multistep methods. SIAM J. Numer. Anal. 41, 605–623 (2003)
Kato, T., Kataoka, T.: Circuit analysis by a new multirate method. Electr. Eng. Jpn. 126, 55–62 (1999)
Kirby, R.: On the convergence of high resolution methods with multiple time scales for hyperbolic conservation laws. Math. Comput. 72, 1239–1250 (2002)
Kværnø, A.: Stability of multirate Runge–Kutta schemes. Int. J. Differ. Equ. Appl. 1, 97–105 (2000)
Kvæ rnø, A., Rentrop, P.: Low order multirate Runge–Kutta methods in electric circuit simulation (1999)
Laney, C.: Computational Gasdynamics. Cambridge University Press, Cambridge (1998)
LeVeque, R.: Finite Volume Methods for Hyperbolic Problems. Cambridge University Press, Cambridge (2002)
Logg, A.: Multi-adaptive Galerkin methods for ODEs I. SIAM J. Sci. Comput. 24, 1879–1902 (2003)
Logg, A.: Multi-adaptive Galerkin methods for ODEs II: Implementation and applications. SIAM J. Sci. Comput. 25, 1119–1141 (2003)
Logg, A.: Multi-adaptive Galerkin methods for ODEs III: A priory estimates. SIAM J. Numer. Anal. 43, 2624–2646 (2006)
Osher, A., Chakravarthy, S.: High resolution schemes and the entropy condition. SIAM J. Numer. Anal. 21, 955–984 (1984)
Osher, A., Chakravarthy, S.: Very high order accurate TVD schemes. In: Oscillation Theory, Computation, and Methods of Compensated Compactness. IMA Vol. Math. Appl., vol. 2, pp. 229–274. Springer, Berlin (1986)
Rice, J.: Split Runge–Kutta methods for simultaneous equations, J. Res. National Inst. Standards Technol. 60 (1960)
Roe, P.: Approximate Riemann solvers, parameter vectors and difference schemes. J. Comput. Phys. 43, 357–372 (1981)
Sand, J., Burrage, K.: A Jacobi waveform relaxation method for ODEs. SIAM J. Sci. Comput. 20, 534–552 (1998)
Savcenco, V., Hundsdorfer, W., Verwer, J.: A multirate time stepping strategy for parabolic PDE. Tech. Report MAS-E0516, Centrum voor Wiskundeen Informatica, 2005
Savcenco, V., Hundsdorfer, W., Verwer, J.: A multirate time stepping strategy for stiff ODEs. BIT (2006, to appear)
Shampine, L.: Conservation laws and the numerical solution of ODEs. Comput. Math. Appl. B 12, 1287–1296 (1986)
Shu, C.-W.: Total-variation-diminishing time discretizations. SIAM J. Sci. Stat. Comput. 9, 1073–1084 (1988)
Shu, C.-W., Osher, S.: TVB uniformly high-order schemes for conservation laws. Math. Comput. 49, 105–121 (1987)
Shu, C.-W., Osher, S.: Efficient implementation of essentially non-oscillatory shock-capturing schemes. J. Comput. Phys. 77, 439–471 (1988)
Shu, C.-W., Osher, S.: Efficient implementation of essentially non-oscillatory shock-capturing schemes II. J. Comput. Phys. 83, 32��78 (1989)
Spiteri, R., Ruuth, S.: A new class of optimal high-order strong-stability-preserving time discretization methods. SIAM J. Numer. Anal. 40, 469–491 (2002)
Sweby, P.: High resolution schemes using flux limiters for hyperbolic conservation laws. SIAM J. Numer. Anal. 21, 995–1011 (1984)
Tang, H.-Z., Warnecke, G.: A class of high resolution schemes for hyperbolic conservation laws and convection-diffusion equations with varying time and space grids. J. Comput. Math. 24, 121–140 (2006)
Vreugdenhil, C., Koren, B. (eds.): Numerical Methods for Advection–Diffusion Problems, vol. 45. Vieweg, Wiesbaden (1993)
Zalesak, S.: Fully multidimensional flux corrected transport algorithms for fluids. J. Comput. Phys. 31, 335–362 (1979)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by the National Science Foundation through award NSF CCF-0515170.
Rights and permissions
About this article
Cite this article
Constantinescu, E.M., Sandu, A. Multirate Timestepping Methods for Hyperbolic Conservation Laws. J Sci Comput 33, 239–278 (2007). https://doi.org/10.1007/s10915-007-9151-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-007-9151-y