Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Authors: Lili Hu, Yao Li and Yingjie Liu
Journal: Math. Comp. 85 (2016), 1263-1280
MSC (2010): Primary 65M06, 65M12
DOI: https://doi.org/10.1090/mcom/3026
Published electronically: January 13, 2016
MathSciNet review: 3454364
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (98d:65121), https://doi.org/10.1002/(SICI)1097-0312(199612)49:12$ \langle $1339::AID-CPA5$ \rangle $3.0.CO;2-B
  • [2] 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.
  • [3] 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 (2005k:65166), https://doi.org/10.1093/imanum/drh015
  • [4] 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 (2004d:65087), https://doi.org/10.1016/S0021-9991(03)00201-8
  • [5] Y. Chen, Q. Kang, Q. Cai and D. Zhang,
    Lattice Boltzmann Method on Quadtree Grids,
    Physical Review E, 83 (2011).
  • [6] 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 0053336 (14,756e)
  • [7] 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 (2005k:76104), https://doi.org/10.1016/j.compstruc.2004.04.024
  • [8] 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 (2012b:76115), https://doi.org/10.1016/j.jcp.2010.12.036
  • [9] 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 (electronic). MR 1762036 (2001e:65125), https://doi.org/10.1137/S1064827598344856
  • [10] 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 (2004m:65162), https://doi.org/10.1016/S0021-9991(03)00276-6
  • [11] 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 (2004m:65162), https://doi.org/10.1016/S0021-9991(03)00276-6
  • [12] 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 (2008c:65202), https://doi.org/10.1090/S0025-5718-06-01898-9
  • [13] 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).
  • [14] 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 (90a:65199), https://doi.org/10.1016/0021-9991(87)90031-3
  • [15] B.-M. Kim, Y.-J. Liu, I. Llamas and J. Rossignac,
    FlowFixer: Using BFECC for Fluid Simulation,
    Eurographics Workshop on Natural Phenomena, 2005.
  • [16] 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.
  • [17] 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.
  • [18] T. Kim and M. Carlson,
    A simple boiling module,
    Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, 27-34.
  • [19] 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 (electronic). MR 1860961 (2003a:65065), https://doi.org/10.1137/S1064827500373413
  • [20] 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 (2008e:65251), https://doi.org/10.1007/s10915-005-9033-0
  • [21] 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 (2001c:65102), https://doi.org/10.1006/jcph.2000.6485
  • [22] 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 0145686 (26 #3215)
  • [23] 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.
  • [24] 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 (89h:80012), https://doi.org/10.1016/0021-9991(88)90002-2
  • [25] 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 (92e:65118), https://doi.org/10.1137/0728049
  • [26] 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 (2009j:65210), https://doi.org/10.1007/s10915-007-9166-4
  • [27] 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 (89g:65113), https://doi.org/10.1016/0021-9991(88)90177-5
  • [28] John Strain, Semi-Lagrangian methods for level set equations, J. Comput. Phys. 151 (1999), no. 2, 498-533. MR 1686375 (2000a:76133), https://doi.org/10.1006/jcph.1999.6194
  • [29] Steven T. Zalesak, Fully multidimensional flux-corrected transport algorithms for fluids, J. Comput. Phys. 31 (1979), no. 3, 335-362. MR 534786 (80f:76048), https://doi.org/10.1016/0021-9991(79)90051-2
  • [30] 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 (electronic). MR 1950522 (2004b:65128), https://doi.org/10.1137/S1064827501396798

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65M06, 65M12

Retrieve articles in all journals with MSC (2010): 65M06, 65M12


Additional Information

Lili Hu
Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332
Email: lhu33@math.gatech.edu

Yao Li
Affiliation: Courant Institute of Mathematics, New York University, New York
Email: yaoli@cims.nyu.edu

Yingjie Liu
Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332
Email: yingjie@math.gatech.edu

DOI: https://doi.org/10.1090/mcom/3026
Received by editor(s): April 11, 2013
Received by editor(s) in revised form: April 22, 2014
Published electronically: January 13, 2016
Additional Notes: The first author’s research was supported in part by NSF grant DMS-1115671
The third author’s research was supported in part by NSF grant DMS-1115671
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society