A single-step third-order temporal discretization with Jacobian-free and Hessian-free formulations for finite difference methods. (English) Zbl 07510249

Summary: In this paper, we present an algorithmic extension of the method called the Picard Integration Formulation (PIF) that belongs to temporal updates based on the Lax-Wendroff procedure. The new extension is called the system-free (SF) approach, which furnishes ease of calculating the Jacobian and the Hessian terms necessary for third-order temporal accuracy in the original PIF method. In contrast to the analytical calculations of the Jacobian and the Hessian tensor terms in the original PIF method, our new SF approach utilizes finite difference approximations that replace the analytical calculations of the Jacobian and Hessian terms with Jacobian-free and Hessian-free approximations in a way commonly adopted in the context of iterative methods. The resulting SF approach enables our new PIF method to be a computationally efficient single-step, third-order accurate temporal scheme, whose computational performance is twice faster than the three-stage SSP-RK3 method with the same accuracy.


76-XX Fluid mechanics
78-XX Optics, electromagnetic theory


Full Text: DOI arXiv


[1] Attig, Norbert; Gibbon, Paul; Lippert, Th., Trends in supercomputing: the European path to exascale, Comput. Phys. Commun., 182, 9, 2041-2046 (2011)
[2] ASCAC Subcommittee, Top ten exascale research challenges (2014), US Department of Energy Report
[3] Colella, Phillip; Woodward, Paul R., The piecewise parabolic method (PPM) for gas-dynamical simulations, J. Comput. Phys., 54, 1, 174-201 (1984)
[4] Jiang, Guang-Shan; Shu, Chi-Wang, Efficient implementation of weighted ENO schemes, J. Comput. Phys., 126, 1, 202-228 (1996)
[5] Gottlieb, Sigal; Shu, Chi-Wang, Total variation diminishing Runge-Kutta schemes, Math. Comput. Am. Math. Soc., 67, 221, 73-85 (1998)
[6] Gottlieb, Sigal; Shu, Chi-Wang; Tadmor, Eitan, Strong stability-preserving high-order time discretization methods, SIAM Rev., 43, 1, 89-112 (2001)
[7] Gottlieb, Sigal; Ketcheson, David I.; Shu, Chi-Wang, Strong Stability Preserving Runge-Kutta and Multistep Time Discretizations (2011), World Scientific
[8] Balsara, Dinshaw S.; Shu, Chi-Wang, Monotonicity preserving weighted essentially non-oscillatory schemes with increasingly high order of accuracy, J. Comput. Phys., 160, 2, 405-452 (2000)
[9] Mignone, Andrea; Tzeferacos, Petros; Bodo, Gianluigi, High-order conservative finite difference GLM-MHD schemes for cell-centered MHD, J. Comput. Phys., 229, 17, 5896-5920 (2010)
[10] Spiteri, Raymond J.; Ruuth, Steven J., A new class of optimal high-order strong-stability-preserving time discretization methods, SIAM J. Numer. Anal., 40, 2, 469-491 (2002)
[11] Spiteri, Raymond J.; Ruuth, Steven J., Non-linear evolution using optimal fourth-order strong-stability-preserving Runge-Kutta methods, Math. Comput. Simul., 62, 1-2, 125-135 (2003)
[12] Ruuth, Steven J.; Spiteri, Raymond J., Two barriers on strong-stability-preserving time discretization methods, J. Sci. Comput., 17, 1-4, 211-220 (2002)
[13] Giuliani, Andrew; Krivodonova, Lilia, On the optimal CFL number of SSP methods for hyperbolic problems, Appl. Numer. Math., 135, 165-172 (2019)
[14] Toro, E. F.; Millington, R. C.; Nejad, L. A.M., Towards very high order Godunov schemes, (Godunov Methods (2001), Springer), 907-940
[15] Van Leer, Bram, Towards the ultimate conservative difference scheme. V. A second-order sequel to Godunov’s method, J. Comput. Phys., 32, 1, 101-136 (1979)
[16] Ben-Artzi, Matania; Falcovitz, Joseph, A second-order Godunov-type scheme for compressible fluid dynamics, J. Comput. Phys., 55, 1, 1-32 (1984)
[17] Ben-Artzi, Matania; Li, Jiequan, Hyperbolic balance laws: Riemann invariants and the generalized Riemann problem, Numer. Math., 106, 3, 369-425 (2007)
[18] Titarev, Vladimir A.; Toro, Eleuterio F., ADER: arbitrary high order Godunov approach, J. Sci. Comput., 17, 1-4, 609-618 (2002)
[19] Titarev, Vladimir A.; Toro, Eleuterio F., ADER schemes for three-dimensional non-linear hyperbolic systems, J. Comput. Phys., 204, 2, 715-736 (2005)
[20] Dumbser, Michael; Balsara, Dinshaw S.; Toro, Eleuterio F.; Munz, Claus-Dieter, 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)
[21] Balsara, Dinshaw S.; Rumpf, Tobias; Dumbser, Michael; Munz, Claus-Dieter, Efficient, high accuracy ADER-WENO schemes for hydrodynamics and divergence-free magnetohydrodynamics, J. Comput. Phys., 228, 7, 2480-2516 (2009)
[22] Balsara, Dinshaw S., Higher-order accurate space-time schemes for computational astrophysics—part I: finite volume methods, Living Rev. Comput. Astrophys., 3, 1, 2 (2017)
[23] Balsara, Dinshaw S.; Meyer, Chad; Dumbser, Michael; Du, Huijing; Xu, Zhiliang, Efficient implementation of ADER schemes for Euler and magnetohydrodynamical flows on structured meshes—speed comparisons with Runge-Kutta methods, J. Comput. Phys., 235, 934-969 (2013)
[24] Dumbser, Michael; Zanotti, Olindo; Hidalgo, Arturo; Balsara, Dinshaw S., ADER-WENO finite volume schemes with space-time adaptive mesh refinement, J. Comput. Phys., 248, 257-286 (2013)
[25] Fambri, Francesco; Dumbser, Michael; Zanotti, Olindo, Space-time adaptive ADER-DG schemes for dissipative flows: compressible Navier-Stokes and resistive MHD equations, Comput. Phys. Commun., 220, 297-318 (2017)
[26] Clain, Stéphane; Diot, Steven; Loubère, Raphaël, A high-order finite volume method for systems of conservation laws—multi-dimensional optimal order detection (MOOD), J. Comput. Phys., 230, 10, 4028-4050 (2011)
[27] Diot, Steven; Clain, Stéphane; Loubère, Raphaël, Improved detection criteria for the multi-dimensional optimal order detection (MOOD) on unstructured meshes with very high-order polynomials, Comput. Fluids, 64, 43-63 (2012)
[28] Diot, Steven; Loubère, Raphaël; Clain, Stephane, The multidimensional optimal order detection method in the three-dimensional case: very high-order finite volume method for hyperbolic systems, Int. J. Numer. Methods Fluids, 73, 4, 362-392 (2013)
[29] Boscheri, Walter; Loubère, Raphaël; Dumbser, Michael, Direct arbitrary-Lagrangian-Eulerian ADER-MOOD finite volume schemes for multidimensional hyperbolic conservation laws, J. Comput. Phys., 292, 56-87 (2015)
[30] Loubère, Raphaël; Dumbser, Michael; Diot, Steven, A new family of high order unstructured MOOD and ADER finite volume schemes for multidimensional systems of hyperbolic conservation laws, Commun. Comput. Phys., 16, 3, 718-763 (2014)
[31] Zanotti, Olindo; Dumbser, Michael, Efficient conservative ADER schemes based on WENO reconstruction and space-time predictor in primitive variables, Comput. Astrophys. Cosmol., 3, 1, 1 (2016)
[32] Norman, Matthew R.; Finkel, Hal, Multi-moment ADER-Taylor methods for systems of conservation laws with source terms in one dimension, J. Comput. Phys., 231, 20, 6622-6642 (2012)
[33] Norman, Matthew R., Algorithmic improvements for schemes using the ADER time discretization, J. Comput. Phys., 243, 176-178 (2013)
[34] Norman, Matthew R., A WENO-limited, ADER-DT, finite-volume scheme for efficient, robust, and communication-avoiding multi-dimensional transport, J. Comput. Phys., 274, 1-18 (2014)
[35] Del Zanna, L.; Zanotti, O.; Bucciantini, N.; Londrillo, P., ECHO: a Eulerian conservative high-order scheme for general relativistic magnetohydrodynamics and magnetodynamics, Astron. Astrophys., 473, 1, 11-30 (2007)
[36] Chen, Yuxi; Tóth, Gábor; Gombosi, Tamas I., A fifth-order finite difference scheme for hyperbolic equations on block-adaptive curvilinear grids, J. Comput. Phys., 305, 604-621 (2016)
[37] Reyes, Adam; Lee, Dongwook; Graziani, Carlo; Tzeferacos, Petros, A variable high-order shock-capturing finite difference method with GP-WENO, J. Comput. Phys., 381, 189-217 (2019)
[38] Hairer, Ernst; Wanner, Gerhard, Multistep-multistage-multiderivative methods for ordinary differential equations, Computing, 11, 3, 287-303 (1973)
[39] Seal, David C.; Güçlü, Yaman; Christlieb, Andrew J., High-order multiderivative time integrators for hyperbolic conservation laws, J. Sci. Comput., 60, 1, 101-140 (2014)
[40] Christlieb, Andrew J.; Guclu, Yaman; Seal, David C., The Picard integral formulation of weighted essentially nonoscillatory schemes, SIAM J. Numer. Anal., 53, 4, 1833-1856 (2015)
[41] Seal, David C.; Tang, Qi; Xu, Zhengfu; Christlieb, Andrew J., An explicit high-order single-stage single-step positivity-preserving finite difference WENO method for the compressible Euler equations, J. Sci. Comput., 68, 1, 171-190 (2016)
[42] Qiu, Jianxian; Shu, Chi-Wang, Finite difference WENO schemes with Lax-Wendroff-type time discretizations, SIAM J. Sci. Comput., 24, 6, 2185-2198 (2003)
[43] Jiang, Yan; Shu, Chi-Wang; Zhang, Mengping, An alternative formulation of finite difference weighted ENO schemes with Lax-Wendroff time discretization for conservation laws, SIAM J. Sci. Comput., 35, 2, A1137-A1160 (2013)
[44] Godunov, Sergei Konstantinovich, A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics, Mat. Sb., 89, 3, 271-306 (1959)
[45] Lee, Dongwook; Faller, Hugues; Reyes, Adam, The piecewise cubic method (PCM) for computational fluid dynamics, J. Comput. Phys., 341, 230-257 (2017)
[46] Brown, Peter N.; Saad, Youcef, Hybrid Krylov methods for nonlinear systems of equations, SIAM J. Sci. Stat. Comput., 11, 3, 450-481 (1990)
[47] Knoll, Dana A.; Keyes, David E., Jacobian-free Newton-Krylov methods: a survey of approaches and applications, J. Comput. Phys., 193, 2, 357-397 (2004)
[48] Knoll, Dana A.; Park, H.; Smith, Kord, Application of the Jacobian-free Newton-Krylov method to nonlinear acceleration of transport source iteration in slab geometry, Nucl. Sci. Eng., 167, 2, 122-132 (2011)
[49] Gear, Charles William; Saad, Youcef, Iterative solution of linear equations in ODE codes, SIAM J. Sci. Stat. Comput., 4, 4, 583-601 (1983)
[50] An, Heng-Bin; Wen, Ju; Feng, Tao, On finite difference approximation of a matrix-vector product in the Jacobian-free Newton-Krylov method, J. Comput. Appl. Math., 236, 6, 1399-1409 (2011)
[51] Kent, James; Whitehead, Jared P.; Jablonowski, Christiane; Rood, Richard B., Determining the effective resolution of advection schemes. Part I: dispersion analysis, J. Comput. Phys., 278, 485-496 (2014)
[52] Kent, James; Jablonowski, Christiane; Whitehead, Jared P.; Rood, Richard B., Determining the effective resolution of advection schemes. Part II: numerical testing, J. Comput. Phys., 278, 497-508 (2014)
[53] Sod, Gary A., A survey of several finite difference methods for systems of nonlinear hyperbolic conservation laws, J. Comput. Phys., 27, 1, 1-31 (1978)
[54] Woodward, Paul; Colella, Phillip, The numerical simulation of two-dimensional fluid flow with strong shocks, J. Comput. Phys., 54, 1, 115-173 (1984)
[55] Shu, Chi-Wang; Osher, Stanley, Efficient implementation of essentially non-oscillatory shock-capturing schemes, II, (Upwind and High-Resolution Schemes (1989), Springer), 328-374
[56] Shu, Chi-Wang, Essentially non-oscillatory and weighted essentially non-oscillatory schemes for hyperbolic conservation laws, (Advanced Numerical Approximation of Nonlinear Hyperbolic Equations (1998), Springer), 325-432
[57] Spiegel, Seth C.; Huynh, H. T.; DeBonis, James R., A survey of the isentropic Euler vortex problem using high-order methods, (22nd AIAA Computational Fluid Dynamics Conference (2015)), 2444
[58] Zhang, Tong; Zheng, Yu Xi, Conjecture on the structure of solutions of the Riemann problem for two-dimensional gas dynamics systems, SIAM J. Math. Anal., 21, 3, 593-630 (1990)
[59] Schulz-Rinne, Carsten W., Classification of the Riemann problem for two-dimensional gas dynamics, SIAM J. Math. Anal., 24, 1, 76-88 (1993)
[60] Schulz-Rinne, Carsten W.; Collins, James P.; Glaz, Harland M., Numerical solution of the Riemann problem for two-dimensional gas dynamics, SIAM J. Sci. Comput., 14, 6, 1394-1414 (1993)
[61] Balsara, Dinshaw S., Multidimensional HLLE Riemann solver: application to Euler and magnetohydrodynamic flows, J. Comput. Phys., 229, 6, 1970-1993 (2010)
[62] Buchmüller, Pawel; Helzel, Christiane, Improved accuracy of high-order WENO finite volume methods on Cartesian grids, J. Sci. Comput., 61, 2, 343-368 (2014)
[63] Don, Wai-Sun; Gao, Zhen; Li, Peng; Wen, Xiao, Hybrid compact-WENO finite difference scheme with conjugate Fourier shock detection algorithm for hyperbolic conservation laws, SIAM J. Sci. Comput., 38, 2, A691-A711 (2016)
[64] Hui, W. H.; Li, P. Y.; Li, Z. W., A unified coordinate system for solving the two-dimensional Euler equations, J. Comput. Phys., 153, 2, 596-637 (1999)
[65] Liska, Richard; Wendroff, Burton, Comparison of several difference schemes on 1D and 2D test problems for the Euler equations, SIAM J. Sci. Comput., 25, 3, 995-1017 (2003)
[66] Stone, James M.; Gardiner, Thomas A.; Teuben, Peter; Hawley, John F.; Simon, Jacob B., Athena: a new code for astrophysical MHD, Astrophys. J. Suppl. Ser., 178, 1, 137 (2008)
[67] Kemm, Friedemann, On the proper setup of the double Mach reflection as a test case for the resolution of gas dynamics codes, Comput. Fluids, 132, 72-75 (2016)
[68] Alcrudo, Francisco; Garcia-Navarro, Pilar, A high-resolution Godunov-type scheme in finite volumes for the 2D shallow-water equations, Int. J. Numer. Methods Fluids, 16, 6, 489-505 (1993)
[69] Toro, Eleuterio F., Shock-Capturing Methods for Free-Surface Shallow Flows (2001), John Wiley
[70] Delis, Anargiros I.; Katsaounis, Th., Numerical solution of the two-dimensional shallow water equations by the application of relaxation methods, Appl. Math. Model., 29, 8, 754-783 (2005)
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.