A limiting strategy for the back and forth error compensation and correction method for solving advection equations

Hu, Lili; Li, Yao; Liu, Yingjie

doi:10.1090/mcom/3026

A limiting strategy for the back and forth error compensation and correction method for solving advection equations
HTML articles powered by AMS MathViewer

by Lili Hu, Yao Li and Yingjie Liu;

Math. Comp. 85 (2016), 1263-1280

DOI: https://doi.org/10.1090/mcom/3026

Published electronically: January 13, 2016

PDF | Request permission

Abstract:

We further study the properties of the back and forth error compensation and correction (BFECC) method for advection equations such as those related to the level set method and for solving Hamilton-Jacobi equations on unstructured meshes. In particular, we develop a new limiting strategy which requires another backward advection in time so that overshoots/ undershoots on the new time level get exposed when they are transformed back to compare with the solution on the old time level. This new technique is very simple to implement even for unstructured meshes and is able to eliminate artifacts induced by jump discontinuities in derivatives of the solution as well as by jump discontinuities in the solution itself (even if the solution has large gradients in the vicinities of a jump). Typically, a formal second order method for solving a time dependent Hamilton-Jacobi equation requires quadratic interpolation in space. A BFECC method on the other hand only requires linear interpolation in each step, thus is local and easy to implement even for unstructured meshes.

References

R. Abgrall, Numerical discretization of the first-order Hamilton-Jacobi equation on triangular meshes, Comm. Pure Appl. Math. 49 (1996), no. 12, 1339–1373. MR 1414589, DOI 10.1002/(SICI)1097-0312(199612)49:12<1339::AID-CPA5>3.0.CO;2-B
J. P. Boris and D. L. Book, Flux-Corrected Transport I. SHASTA, A Fluid Transport Algorithm That Works, J. Comput. Phys., 11 (1973), 38–69.
Steve Bryson, Alexander Kurganov, Doron Levy, and Guergana Petrova, Semi-discrete central-upwind schemes with reduced dissipation for Hamilton-Jacobi equations, IMA J. Numer. Anal. 25 (2005), no. 1, 113–138. MR 2110237, DOI 10.1093/imanum/drh015
Steve Bryson and Doron Levy, High-order semi-discrete central-upwind schemes for multi-dimensional Hamilton-Jacobi equations, J. Comput. Phys. 189 (2003), no. 1, 63–87. MR 1988140, DOI 10.1016/S0021-9991(03)00201-8
Y. Chen, Q. Kang, Q. Cai and D. Zhang, Lattice Boltzmann Method on Quadtree Grids, Physical Review E, 83 (2011).
Richard Courant, Eugene Isaacson, and Mina Rees, On the solution of nonlinear hyperbolic differential equations by finite differences, Comm. Pure Appl. Math. 5 (1952), 243–255. MR 53336, DOI 10.1002/cpa.3160050303
Douglas Enright, Frank Losasso, and Ronald Fedkiw, A fast and accurate semi-Lagrangian particle level set method, Comput. & Structures 83 (2005), no. 6-7, 479–490. MR 2143508, DOI 10.1016/j.compstruc.2004.04.024
Michael Lentine, Jón Tómas Grétarsson, and Ronald Fedkiw, An unconditionally stable fully conservative semi-Lagrangian method, J. Comput. Phys. 230 (2011), no. 8, 2857–2879. MR 2774321, DOI 10.1016/j.jcp.2010.12.036
Chi-Tien Lin and Eitan Tadmor, High-resolution nonoscillatory central schemes for Hamilton-Jacobi equations, SIAM J. Sci. Comput. 21 (2000), no. 6, 2163–2186. MR 1762036, DOI 10.1137/S1064827598344856
Todd F. Dupont and Yingjie Liu, Back and forth error compensation and correction methods for removing errors induced by uneven gradients of the level set function, J. Comput. Phys. 190 (2003), no. 1, 311–324. MR 2046766, DOI 10.1016/S0021-9991(03)00276-6
Todd F. Dupont and Yingjie Liu, Back and forth error compensation and correction methods for removing errors induced by uneven gradients of the level set function, J. Comput. Phys. 190 (2003), no. 1, 311–324. MR 2046766, DOI 10.1016/S0021-9991(03)00276-6
Todd F. Dupont and Yingjie Liu, Back and forth error compensation and correction methods for semi-Lagrangian schemes with application to level set interface computations, Math. Comp. 76 (2007), no. 258, 647–668. MR 2291832, DOI 10.1090/S0025-5718-06-01898-9
I.V. Gugushvili and N. M. Evstigneev, Semi-Lagrangian Method for Advection Equation on GPU in Unstructured $R^3$ Mesh for Fluid Dynamics Application, World Academy of Science, Engineering and Technology, 60 (2009).
Ami Harten, Björn Engquist, Stanley Osher, and Sukumar R. Chakravarthy, Uniformly high-order accurate essentially nonoscillatory schemes. III, J. Comput. Phys. 71 (1987), no. 2, 231–303. MR 897244, DOI 10.1016/0021-9991(87)90031-3
B.-M. Kim, Y.-J. Liu, I. Llamas and J. Rossignac, FlowFixer: Using BFECC for Fluid Simulation, Eurographics Workshop on Natural Phenomena, 2005.
B.-M. Kim, Y.-J. Liu, I. Llamas and J. Rossignac, Advections with significantly reduced dissipation and diffusion, IEEE Trans. Visual. and Comput. Graph. 13 (2007), 135–144.
B.-M. Kim, Y.-J. Liu, I. Llamas, X.-M. Jiao and J. Rossignac, Simulation of Bubbles in Foam by Volume Control, ACM SIGGRAPH, 2007.
T. Kim and M. Carlson, A simple boiling module, Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, 27–34.
Alexander Kurganov, Sebastian Noelle, and Guergana Petrova, Semidiscrete central-upwind schemes for hyperbolic conservation laws and Hamilton-Jacobi equations, SIAM J. Sci. Comput. 23 (2001), no. 3, 707–740. MR 1860961, DOI 10.1137/S1064827500373413
Alexander Kurganov and Guergana Petrova, Adaptive central-upwind schemes for Hamilton-Jacobi equations with nonconvex Hamiltonians, J. Sci. Comput. 27 (2006), no. 1-3, 323–333. MR 2285784, DOI 10.1007/s10915-005-9033-0
Alexander Kurganov and Eitan Tadmor, New high-resolution semi-discrete central schemes for Hamilton-Jacobi equations, J. Comput. Phys. 160 (2000), no. 2, 720–742. MR 1763829, DOI 10.1006/jcph.2000.6485
Peter D. Lax, On the stability of difference approximations to solutions of hyperbolic equations with variable coefficients, Comm. Pure Appl. Math. 14 (1961), 497–520. MR 145686, DOI 10.1002/cpa.3160140324
B. van Leer, Toward the ultimate conservative difference scheme: II. Monotonicity and conservation combined in a second order scheme, J. Comput. Phys. 14 (1974), 361–370.
Stanley Osher and James A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys. 79 (1988), no. 1, 12–49. MR 965860, DOI 10.1016/0021-9991(88)90002-2
Stanley Osher and Chi-Wang Shu, High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations, SIAM J. Numer. Anal. 28 (1991), no. 4, 907–922. MR 1111446, DOI 10.1137/0728049
Andrew Selle, Ronald Fedkiw, ByungMoon Kim, Yingjie Liu, and Jarek Rossignac, An unconditionally stable MacCormack method, J. Sci. Comput. 35 (2008), no. 2-3, 350–371. MR 2429944, DOI 10.1007/s10915-007-9166-4
Chi-Wang Shu and Stanley Osher, Efficient implementation of essentially nonoscillatory shock-capturing schemes, J. Comput. Phys. 77 (1988), no. 2, 439–471. MR 954915, DOI 10.1016/0021-9991(88)90177-5
John Strain, Semi-Lagrangian methods for level set equations, J. Comput. Phys. 151 (1999), no. 2, 498–533. MR 1686375, DOI 10.1006/jcph.1999.6194
Steven T. Zalesak, Fully multidimensional flux-corrected transport algorithms for fluids, J. Comput. Phys. 31 (1979), no. 3, 335–362. MR 534786, DOI 10.1016/0021-9991(79)90051-2
Yong-Tao Zhang and Chi-Wang Shu, High-order WENO schemes for Hamilton-Jacobi equations on triangular meshes, SIAM J. Sci. Comput. 24 (2002), no. 3, 1005–1030. MR 1950522, DOI 10.1137/S1064827501396798