×

zbMATH — the first resource for mathematics

High order strong stability preserving time discretizations. (English) Zbl 1203.65135
Summary: Strong stability preserving (SSP) high order time discretizations were developed to ensure nonlinear stability properties necessary in the numerical solution of hyperbolic partial differential equations with discontinuous solutions. SSP methods preserve the strong stability properties-in any norm, seminorm or convex functional-of the spatial discretization coupled with first order Euler time stepping. This paper describes the development of SSP methods and the connections between the timestep restrictions for strong stability preservation and contractivity. Numerical examples demonstrate that common linearly stable but not strong stability preserving time discretizations may lead to violation of important boundedness properties, whereas SSP methods guarantee the desired properties provided only that these properties are satisfied with forward Euler timestepping. We review optimal explicit and implicit SSP Runge-Kutta and multistep methods, for linear and nonlinear problems. We also discuss the SSP properties of spectral deferred correction methods.

MSC:
65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
65M12 Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs
Software:
BARON; RODAS; WENO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baiotti, L., Hawke, I., Montero, P.J., Loffler, F., Rezzolla, L., Stergioulas, N., Font, J.A., Seidel, E.: Three-dimensional relativistic simulations of rotating neutron-star collapse to a Kerr black hole. Phys. Rev. D 71 (2005)
[2] Balbás, J., Tadmor, E.: A central differencing simulation of the Orszag-Tang vortex system. IEEE Trans. Plasma Sci. 33(2), 470–471 (2005) · doi:10.1109/TPS.2005.845282
[3] Bassano, E.: Numerical simulation of thermo-solutal-capillary migration of a dissolving drop in a cavity. Int. J. Numer. Methods Fluids 41, 765–788 (2003) · Zbl 1107.76359 · doi:10.1002/fld.470
[4] Butcher, J.C.: On the implementation of implicit Runge-Kutta methods. BIT 6, 237–240 (1976) · Zbl 0336.65037 · doi:10.1007/BF01932265
[5] Butcher, J.C.: Numerical Methods for Ordinary Differential Equations. Wiley, New York (2003) · Zbl 1040.65057
[6] Caiden, R., Fedkiw, R.P., Anderson, C.: A numerical method for two-phase flow consisting of separate compressible and incompressible regions. J. Comput. Phys. 166, 1–27 (2001) · Zbl 0990.76065 · doi:10.1006/jcph.2000.6624
[7] Carrillo, J., Gamba, I.M., Majorana, A., Shu, C.-W.: A WENO-solver for the transients of Boltzmann-Poisson system for semiconductor devices: performance and comparisons with Monte Carlo methods. J. Comput. Phys. 184, 498–525 (2003) · Zbl 1034.82063 · doi:10.1016/S0021-9991(02)00032-3
[8] Chen, M.-H., Cockburn, B., Reitich, F.: High-order RKDG methods for computational electromagnetics. J. Sci. Comput. 22–23, 205–226 (2005) · Zbl 1091.78015 · doi:10.1007/s10915-004-4152-6
[9] Cheng, L.-T., Liu, H., Osher, S.: Computational high-frequency wave propagation using the level set method, with applications to the semi-classical limit of Schrodinger equations. Commun. Math. Sci. 1(3), 593–621 (2003) · Zbl 1084.35066
[10] Cheruvu, V., Nair, R.D., Tufo, H.M.: A spectral finite volume transport scheme on the cubed-sphere. Appl. Numer. Math. 57, 1021–1032 (2007) · Zbl 1207.76095 · doi:10.1016/j.apnum.2006.09.008
[11] Cockburn, B., Li, F., Shu, C.-W.: Locally divergence-free discontinuous Galerkin methods for the Maxwell equations. J. Comput. Phys. 194, 588–610 (2004) · Zbl 1049.78019 · doi:10.1016/j.jcp.2003.09.007
[12] Cockburn, B., Qian, J., Reitich, F., Wang, J.: An accurate spectral/discontinuous finite-element formulation of a phase-space-based level set approach to geometrical optics. J. Comput. Phys. 208, 175–195 (2005) · Zbl 1066.78015 · doi:10.1016/j.jcp.2005.02.009
[13] Cockburn, B., Shu, C.-W.: TVB Runge–Kutta local projection discontinuous Galerkin finite element method for conservation laws II: general framework. Math. Comput. 52, 411–435 (1989) · Zbl 0662.65083
[14] Dahlquist, G., Jeltsch, R.: Generalized disks of contractivity for explicit and implicit Runge–Kutta methods. Technical Report, Department of Numerical Analysis and Computational Science, Royal Institute of Technology, Stockholm (1979) · Zbl 1106.65062
[15] Dekker, K., Verwer, J.G.: Stability of Runge–Kutta Methods for Stiff Nonlinear Differential Equations. CWI Monographs, vol. 2. North-Holland, Amsterdam (1984) · Zbl 0571.65057
[16] Del Zanna, L., Bucciantini, N.: An efficient shock-capturing central-type scheme for multidimensional relativistic flows: I. hydrodynamics. Astron. Astrophys. 390, 1177–1186 (2002) · Zbl 1209.76022 · doi:10.1051/0004-6361:20020776
[17] Dutt, A., Greengard, L., Rokhlin, V.: Spectral deferred correction methods for ordinary differential equations. BIT 40, 241–266 (2000) · Zbl 0959.65084 · doi:10.1023/A:1022338906936
[18] Enright, D., Fedkiw, R., Ferziger, J., Mitchell, I.: A hybrid particle level set method for improved interface capturing. J. Comput. Phys. 183, 83–116 (2002) · Zbl 1021.76044 · doi:10.1006/jcph.2002.7166
[19] Feng, L.-L., Shu, C.-W., Zhang, M.: A hybrid cosmological hydrodynamic/n-body code based on a weighted essentially nonoscillatory scheme. Astrophys. J. 612, 1–13 (2004) · doi:10.1086/422513
[20] Ferracina, L., Spijker, M.N.: Stepsize restrictions for the total-variation-diminishing property in general Runge-Kutta methods. SIAM J. Numer. Anal. 42, 1073–1093 (2004) · Zbl 1080.65087 · doi:10.1137/S0036142902415584
[21] Ferracina, L., Spijker, M.N.: Computing optimal monotonicity-preserving Runge-Kutta methods. Technical Report MI2005-07, Mathematical Institute, Leiden University (2005) · Zbl 1058.65098
[22] Ferracina, L., Spijker, M.N.: An extension and analysis of the Shu-Osher representation of Runge-Kutta methods. Math. Comput. 249, 201–219 (2005) · Zbl 1058.65098
[23] Ferracina, L., Spijker, M.N.: Strong stability of singly-diagonally-implicit Runge-Kutta methods. Appl. Numer. Math. (2008). doi: 10.1016/j.apnum.2007.10.004 · Zbl 1153.65080
[24] Gottlieb, D., Tadmor, E.: The CFL condition for spectral approximations to hyperbolic initial-boundary value problems. Math. Comput. 56, 565–588 (1991) · Zbl 0723.65079 · doi:10.1090/S0025-5718-1991-1066833-9
[25] Gottlieb, S.: On high order strong stability preserving Runge-Kutta and multi step time discretizations. J. Sci. Comput. 25, 105–127 (2005) · Zbl 1203.65166
[26] Gottlieb, S., Gottlieb, L.J.: Strong stability preserving properties of Runge-Kutta time discretization methods for linear constant coefficient operators. J. Sci. Comput. 18, 83–109 (2003) · Zbl 1030.65099 · doi:10.1023/A:1020338228736
[27] Gottlieb, S., Ruuth, S.J.: Optimal strong-stability-preserving time-stepping schemes with fast downwind spatial discretizations. J. Sci. Comput. 27, 289–303 (2006) · Zbl 1115.65092 · doi:10.1007/s10915-005-9054-8
[28] Gottlieb, S., Shu, C.-W.: Total variation diminishing Runge-Kutta schemes. Math. Comput. 67, 73–85 (1998) · Zbl 0897.65058 · doi:10.1090/S0025-5718-98-00913-2
[29] Gottlieb, S., Shu, C.-W., Tadmor, E.: Strong stability preserving high-order time discretization methods. SIAM Rev. 43, 89–112 (2001) · Zbl 0967.65098 · doi:10.1137/S003614450036757X
[30] Hairer, E., Wanner, G.: Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems. Springer Series in Computational Mathematics, vol. 14. Springer, Berlin (1991) · Zbl 0729.65051
[31] Harten, A.: High resolution schemes for hyperbolic conservation laws. J. Comput. Phys. 49, 357–393 (1983) · Zbl 0565.65050 · doi:10.1016/0021-9991(83)90136-5
[32] Higueras, I.: On strong stability preserving time discretization methods. J. Sci. Comput. 21, 193–223 (2004) · Zbl 1074.65095 · doi:10.1023/B:JOMP.0000030075.59237.61
[33] Higueras, I.: Representations of Runge-Kutta methods and strong stability preserving methods. SIAM J. Numer. Anal. 43, 924–948 (2005) · Zbl 1097.65078 · doi:10.1137/S0036142903427068
[34] Higueras, I.: Strong stability for additive Runge-Kutta methods. SIAM J. Numer. Anal. 44, 1735–1758 (2006) · Zbl 1126.65067 · doi:10.1137/040612968
[35] Horvath, Z.: On the positivity of matrix-vector products. Linear Algebra Appl. 393, 253–258 (2004) · Zbl 1070.15018 · doi:10.1016/j.laa.2004.03.012
[36] Horvath, Z.: On the positivity step size threshold of Runge-Kutta methods. Appl. Numer. Math. 53, 341–356 (2005) · Zbl 1073.65077 · doi:10.1016/j.apnum.2004.08.026
[37] Huang, C.: Strong stability preserving hybrid methods. Appl. Numer. Math. (2008). doi: 10.1016/j.apnum.2008.03.030
[38] Hundsdorfer, W., Ruuth, S.J.: On monotonicity and boundedness properties of linear multistep methods. Math. Comput. 75(254), 655–672 (2005) · Zbl 1092.65059 · doi:10.1090/S0025-5718-05-01794-1
[39] Hundsdorfer, W., Ruuth, S.J.: IMEX extensions of linear multistep methods with general monotonicity and boundedness properties. J. Comput. Phys. 225, 201–2042 (2007) · Zbl 1123.65068 · doi:10.1016/j.jcp.2007.03.003
[40] Hundsdorfer, W., Ruuth, S.J., Spiteri, R.J.: Monotonicity-preserving linear multistep methods. SIAM J. Numer. Anal. 41, 605–623 (2003) · Zbl 1050.65070 · doi:10.1137/S0036142902406326
[41] Jeltsch, R., Nevanlinna, O.: Stability of explicit time discretizations for solving initial value problems. Numer. Math. 37, 61–91 (1981) · Zbl 0457.65054 · doi:10.1007/BF01396187
[42] Jiang, G.-S., Shu, C.-W.: Efficient implementation of weighted ENO schemes. J. Comput. Phys. 126, 202–228 (1996) · Zbl 0877.65065 · doi:10.1006/jcph.1996.0130
[43] Jin, S., Liu, H., Osher, S., Tsai, Y.-H.R.: Computing multivalued physical observables for the semiclassical limit of the Schrodinger equation. J. Comput. Phys. 205, 222–241 (2005) · Zbl 1072.65132 · doi:10.1016/j.jcp.2004.11.008
[44] Kennedy, C.A., Carpenter, M.H., Lewis, R.M.: Low-storage, explicit Runge-Kutta schemes for the compressible Navier-Stokes equations. Appl. Numer. Math. 35, 177–219 (2000) · Zbl 0986.76060 · doi:10.1016/S0168-9274(99)00141-5
[45] Ketcheson, D.I.: Highly efficient strong stability preserving Runge-Kutta methods with low-storage implementations. SIAM J. Sci. Comput. (2008, to appear) · Zbl 1168.65382
[46] Ketcheson, D.I.: Computation of optimal contractive general linear methods and strong stability preserving linear multistep methods. Math. Comput. (to appear) · Zbl 1198.65117
[47] Ketcheson, D.I., Macdonald, C.B., Gottlieb, S.: Optimal implicit strong stability preserving Runge-Kutta methods. Appl. Numer. Math. (2008). doi: 10.1016/j.apnum.2008.03.034 · Zbl 1157.65046
[48] Ketcheson, D.I., Macdonald, C.B., Gottlieb, S.: Numerically optimal SSP Runge–Kutta methods (website). http://www.cfm.brown.edu/people/sg/ssp.html (2007)
[49] Ketcheson, D.I., Robinson, A.C.: On the practical importance of the SSP property for Runge-Kutta time integrators for some common Godunov-type schemes. Int. J. Numer. Methods Fluids 48, 271–303 (2005) · Zbl 1071.65121 · doi:10.1002/fld.837
[50] Kraaijevanger, J.F.B.M.: Absolute monotonicity of polynomials occurring in the numerical solution of initial value problems. Numer. Math. 48, 303–322 (1986) · Zbl 0561.65055 · doi:10.1007/BF01389477
[51] Kraaijevanger, J.F.B.M.: Contractivity of Runge-Kutta methods. BIT 31, 482–528 (1991) · Zbl 0763.65059 · doi:10.1007/BF01933264
[52] Kubatko, E.J., Westerink, J.J., Dawson, C.: Semi discrete discontinuous Galerkin methods and stage-exceeding-order, strong-stability-preserving Runge-Kutta time discretizations. J. Comput. Phys. 222, 832–848 (2007) · Zbl 1113.65093 · doi:10.1016/j.jcp.2006.08.005
[53] Kurganov, A., Tadmor, E.: New high-resolution schemes for nonlinear conservation laws and convection-diffusion equations. J. Comput. Phys. 160, 241–282 (2000) · Zbl 0987.65085 · doi:10.1006/jcph.2000.6459
[54] Labrunie, S., Carrillo, J., Bertrand, P.: Numerical study on hydrodynamic and quasi-neutral approximations for collisionless two-species plasmas. J. Comput. Phys. 200, 267–298 (2004) · Zbl 1288.76098 · doi:10.1016/j.jcp.2004.04.020
[55] Lax, P.D.: Gibbs Phenomena. J. Sci. Comput. 28, 445–449 (2006) · Zbl 1103.65095 · doi:10.1007/s10915-006-9075-y
[56] Lenferink, H.W.J.: Contractivity-preserving explicit linear multistep methods. Numer. Math. 55, 213–223 (1989) · Zbl 0649.65043 · doi:10.1007/BF01406515
[57] Lenferink, H.W.J.: Contractivity-preserving implicit linear multistep methods. Math. Comput. 56, 177–199 (1991) · Zbl 0722.65035 · doi:10.1090/S0025-5718-1991-1052098-0
[58] Levy, D., Tadmor, E.: From semi-discrete to fully discrete: stability of Runge-Kutta schemes by the energy method. SIAM Rev. 40, 40–73 (1998) · Zbl 0915.65093 · doi:10.1137/S0036144597316255
[59] Liu, X.-D., Osher, S., Chan, T.: Weighted essentially non-oscillatory schemes. J. Comput. Phys. 115(1), 200–212 (1994) · Zbl 0811.65076 · doi:10.1006/jcph.1994.1187
[60] Liu, Y., Shu, C.-W., Zhang, M.: Strong stability preserving property of the deferred correction time discretization. J. Comput. Math. 26, 633–656 (2008) · Zbl 1174.65036
[61] Macdonald, C.B.: Constructing high-order Runge-Kutta methods with embedded strong-stability-preserving pairs. Master’s Thesis, Simon Fraser University (2003)
[62] Macdonald, C.B., Gottlieb, S., Ruuth, S.: A numerical study of diagonally split Runge-Kutta methods for PDEs with discontinuities (2008, submitted) · Zbl 1203.65167
[63] Majda, A., Osher, S.: A systematic approach for correcting nonlinear instabilities. the Lax-Wendroff scheme for scalar conservation laws. Numer. Math. 30, 429–452 (1978) · Zbl 0368.65048 · doi:10.1007/BF01398510
[64] Mignone, A.: The dynamics of radiative shock waves: linear and nonlinear evolution. Astrophys. J. 626, 373–388 (2005) · doi:10.1086/429905
[65] Minion, M.L.: Semi-implicit spectral deferred correction methods for ordinary differential equations. SIAM J. Numer. Anal. 41, 605–623 (2003) · Zbl 1050.65070 · doi:10.1137/S0036142902406326
[66] Nessyahu, H., Tadmor, E.: Non-oscillatory central differencing for hyperbolic conservation laws. J. Comput. Phys. 87, 408–463 (1990) · Zbl 0697.65068 · doi:10.1016/0021-9991(90)90260-8
[67] Osher, S., Chakravarthy, S.: High resolution schemes and the entropy condition. SIAM J. Numer. Anal. 21, 955–984 (1984) · Zbl 0556.65074 · doi:10.1137/0721060
[68] Osher, S., Tadmor, E.: On the convergence of difference approximations to scalar conservation laws. Math. Comput. 50, 19–51 (1988) · Zbl 0637.65091 · doi:10.1090/S0025-5718-1988-0917817-X
[69] Pantano, C., Deiterding, R., Hill, D.J., Pullin, D.I.: A low numerical dissipation patch-based adaptive mesh refinement method for large-eddy simulation of compressible flows. J. Comput. Phys. 221, 63–87 (2007) · Zbl 1125.76034 · doi:10.1016/j.jcp.2006.06.011
[70] Patel, S., Drikakis, D.: Effects of preconditioning on the accuracy and efficiency of incompressible flows. Int. J. Numer. Methods Fluids 47, 963–970 (2005) · Zbl 1134.76433 · doi:10.1002/fld.876
[71] Peng, D., Merriman, B., Osher, S., Zhao, H., Kang, M.: A PDE-based fast local level set method. J. Comput. Phys. 155, 410–438 (1999) · Zbl 0964.76069 · doi:10.1006/jcph.1999.6345
[72] Ruuth, S.J.: Global optimization of explicit strong-stability-preserving Runge-Kutta methods. Math. Comput. 75, 183–207 (2006) · Zbl 1080.65088
[73] Ruuth, S.J., Hundsdorfer, W.: High-order linear multistep methods with general monotonicity and boundedness properties. J. Comput. Phys. 209, 226–248 (2005) · Zbl 1074.65085 · doi:10.1016/j.jcp.2005.02.029
[74] Ruuth, S.J., Spiteri, R.J.: Two barriers on strong-stability-preserving time discretization methods. J. Sci. Comput. 17, 211–220 (2002) · Zbl 1003.65107 · doi:10.1023/A:1015156832269
[75] Ruuth, S.J., Spiteri, R.J.: High-order strong-stability-preserving Runge-Kutta methods with downwind-biased spatial discretizations. SIAM J. Numer. Anal. 42, 974–996 (2004) · Zbl 1089.65069 · doi:10.1137/S0036142902419284
[76] Sahinidis, N.V., Tawarmalani, M.: BARON 7.2: Global optimization of mixed-integer nonlinear programs, user’s manual. Available at http://www.gams.com/dd/docs/solvers/baron.pdf (2004) · Zbl 1062.90041
[77] Shu, C.-W.: Total-variation diminishing time discretizations. SIAM J. Sci. Statist. Comput. 9, 1073–1084 (1988) · Zbl 0662.65081 · doi:10.1137/0909073
[78] Shu, C.-W.: A survey of strong stability-preserving high-order time discretization methods. In: Collected Lectures on the Preservation of Stability under Discretization. SIAM, Philadelphia (2002)
[79] Shu, C.-W., Osher, S.: Efficient implementation of essentially non-oscillatory shock-capturing schemes. J. Comput. Phys. 77, 439–471 (1988) · Zbl 0653.65072 · doi:10.1016/0021-9991(88)90177-5
[80] Spijker, M.N.: Contractivity in the numerical solution of initial value problems. Numer. Math. 42, 271–290 (1983) · Zbl 0504.65030 · doi:10.1007/BF01389573
[81] Spijker, M.N.: Stepsize conditions for general monotonicity in numerical initial value problems. SIAM J. Numer. Anal. 45, 1226–1245 (2007) · Zbl 1144.65055 · doi:10.1137/060661739
[82] Spiteri, R.J., Ruuth, S.J.: A new class of optimal high-order strong-stability-preserving time discretization methods. SIAM J. Numer. Anal. 40, 469–491 (2002) · Zbl 1020.65064 · doi:10.1137/S0036142901389025
[83] Spiteri, R.J., Ruuth, S.J.: Nonlinear evolution using optimal fourth-order strong-stability-preserving Runge-Kutta methods. Math. Comput. Simul. 62, 125–135 (2003) · Zbl 1015.65031 · doi:10.1016/S0378-4754(02)00179-9
[84] Strang, G.: Accurate partial difference methods II: nonlinear problems. Numer. Math. 6, 37–46 (1964) · Zbl 0143.38204 · doi:10.1007/BF01386051
[85] Strikwerda, J.C.: Finite Difference Schemes and Partial Differential Equations. Cole Mathematics Series. Wadsworth and Brooks, California (1989) · Zbl 0681.65064
[86] Sun, Y., Wang, Z.J., Liu, Y.: Spectral (finite) volume method for conservation laws on unstructured grids VI: Extension to viscous flow. J. Comput. Phys. 215, 41–58 (2006) · Zbl 1140.76381 · doi:10.1016/j.jcp.2005.10.019
[87] Sweby, P.K.: High resolution schemes using flux limiters for hyperbolic conservation laws. SIAM J. Numer. Anal. 21, 995–1011 (1984) · Zbl 0565.65048 · doi:10.1137/0721062
[88] Tadmor, E.: Approximate solutions of nonlinear conservation laws. In: Advanced Numerical Approximation of Nonlinear Hyperbolic Equations, Lectures Notes from CIME Course Cetraro, Italy, 1997. Lecture Notes in Mathematics, vol. 1697, pp. 1–150. Springer, Berlin (1998)
[89] Tanguay, M., Colonius, T.: Progress in modeling and simulation of shock wave lithotripsy (swl). In: Fifth International Symposium on Cavitation (CAV2003), number OS-2-1-010 (2003)
[90] van de Griend, J.A., Kraaijevanger, J.F.B.M.: Absolute monotonicity of rational functions occurring in the numerical solution of initial value problems. Numer. Math. 49, 413–424 (1986) · Zbl 0595.65085 · doi:10.1007/BF01389539
[91] Wang, R., Spiteri, R.J.: Linear instability of the fifth-order WENO method. SIAM J. Numer. Anal. 45(5), 1871–1901 (2007) · Zbl 1158.65065 · doi:10.1137/050637868
[92] Wang, Z.J., Liu, Y.: The spectral difference method for the 2D Euler equations on unstructured grids. In: 17th AIAA Computational Fluid Dynamics Conference. AIAA, Washington (2005)
[93] Wang, Z.J., Liu, Y., May, G., Jameson, A.: Spectral difference method for unstructured grids II: Extension to the Euler equations. J. Sci. Comput. 32(1), 45–71 (2007) · Zbl 1151.76543 · doi:10.1007/s10915-006-9113-9
[94] Williamson, J.H.: Low-storage Runge-Kutta schemes. J. Comput. Phys. 35, 48–56 (1980) · Zbl 0425.65038 · doi:10.1016/0021-9991(80)90033-9
[95] Xia, Y., Xu, Y., Shu, C.-W.: Efficient time discretization for local discontinuous Galerkin methods. Discrete Continuous Dyn. Syst. Ser B 8, 677–693 (2007) · Zbl 1141.65076 · doi:10.3934/dcdsb.2007.8.677
[96] Zhang, W., MacFayden, A.I.: RAM: A relativistic adaptive mesh refinement hydrodynamics code. Astrophys. J. Suppl. Ser. 164, 255–279 (2006) · doi:10.1086/500792
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.