Back and forth error compensation and correction methods for semi-lagrangian schemes with application to level set interface computations

Dupont, Todd; Liu, Yingjie

doi:10.1090/S0025-5718-06-01898-9

Back and forth error compensation and correction methods for semi-lagrangian schemes with application to level set interface computations
HTML articles powered by AMS MathViewer

by Todd F. Dupont and Yingjie Liu PDF

Math. Comp. 76 (2007), 647-668 Request permission

Abstract:

Semi-Lagrangian schemes have been explored by several authors recently for transport problems, in particular for moving interfaces using the level set method. We incorporate the backward error compensation method developed in our paper from 2003 into semi-Lagrangian schemes with almost the same simplicity and three times the complexity of a first order semi-Lagrangian scheme but with improved order of accuracy. Stability and accuracy results are proved for a constant coefficient linear hyperbolic equation. We apply this technique to the level set method for interface computation.

References

S. Chen, B. Merriman, S. Osher, and P. Smereka, A simple level set method for solving Stefan problems, J. Comput. Phys. 135 (1997), no. 1, 8–29. MR 1461705, DOI 10.1006/jcph.1997.5721
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
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
Douglas Enright, Ronald Fedkiw, Joel Ferziger, and Ian Mitchell, A hybrid particle level set method for improved interface capturing, J. Comput. Phys. 183 (2002), no. 1, 83–116. MR 1944529, DOI 10.1006/jcph.2002.7166
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
Maurizio Falcone and Roberto Ferretti, Convergence analysis for a class of high-order semi-Lagrangian advection schemes, SIAM J. Numer. Anal. 35 (1998), no. 3, 909–940. MR 1619910, DOI 10.1137/S0036142994273513
James Glimm, John W. Grove, Xiao Lin Li, Keh-Ming Shyue, Yanni Zeng, and Qiang Zhang, Three-dimensional front tracking, SIAM J. Sci. Comput. 19 (1998), no. 3, 703–727. MR 1616658, DOI 10.1137/S1064827595293600
J. Glimm, D. Marchesin, and O. McBryan, Subgrid resolution of fluid discontinuities. II, J. Comput. Phys. 37 (1980), no. 3, 336–354. MR 588257, DOI 10.1016/0021-9991(80)90041-8
Ami Harten and James M. Hyman, Self-adjusting grid methods for one-dimensional hyperbolic conservation laws, J. Comput. Phys. 50 (1983), no. 2, 235–269. MR 707200, DOI 10.1016/0021-9991(83)90066-9
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
Guang-Shan Jiang and Chi-Wang Shu, Efficient implementation of weighted ENO schemes, J. Comput. Phys. 126 (1996), no. 1, 202–228. MR 1391627, DOI 10.1006/jcph.1996.0130
B.-M. Kim, Y.-J. Liu, I. Llamas, and J. Rossignac, FlowFixer: Using BFECC for fluid simulation, Eurographics Workshop on Natural Phenomena (2005).
—, Advections with significantly reduced dissipation and diffusion, IEEE Transactions on Visualization and Computer Graphics (in press).
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
Randall J. Leveque, High-resolution conservative algorithms for advection in incompressible flow, SIAM J. Numer. Anal. 33 (1996), no. 2, 627–665. MR 1388492, DOI 10.1137/0733033
Xu-Dong Liu, Stanley Osher, and Tony Chan, Weighted essentially non-oscillatory schemes, J. Comput. Phys. 115 (1994), no. 1, 200–212. MR 1300340, DOI 10.1006/jcph.1994.1187
R. W. MacCormack, AIAA Paper 69-354 (1969).
Stanley Osher, Riemann solvers, the entropy condition, and difference approximations, SIAM J. Numer. Anal. 21 (1984), no. 2, 217–235. MR 736327, DOI 10.1137/0721016
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
W. Rider and D. Kothe, A marker particle method for interface tracking, Proceedings of the Sixth International Symposium on Computational Fluid Dynamics, 163 (1995), p. 976.
P. L. Roe, Approximate Riemann solvers, parameter vectors, and difference schemes, J. Comput. Phys. 43 (1981), no. 2, 357–372. MR 640362, DOI 10.1016/0021-9991(81)90128-5
Giovanni Russo and Peter Smereka, A remark on computing distance functions, J. Comput. Phys. 163 (2000), no. 1, 51–67. MR 1777721, DOI 10.1006/jcph.2000.6553
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
Chi-Wang Shu and Stanley Osher, Efficient implementation of essentially nonoscillatory shock-capturing schemes. II, J. Comput. Phys. 83 (1989), no. 1, 32–78. MR 1010162, DOI 10.1016/0021-9991(89)90222-2
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
John Strain, A fast modular semi-Lagrangian method for moving interfaces, J. Comput. Phys. 161 (2000), no. 2, 512–536. MR 1764248, DOI 10.1006/jcph.2000.6508
John Strain, A fast semi-Lagrangian contouring method for moving interfaces, J. Comput. Phys. 170 (2001), no. 1, 373–394. MR 1843614, DOI 10.1006/jcph.2001.6740
Mark Sussman and Emad Fatemi, An efficient, interface-preserving level set redistancing algorithm and its application to interfacial incompressible fluid flow, SIAM J. Sci. Comput. 20 (1999), no. 4, 1165–1191. MR 1675468, DOI 10.1137/S1064827596298245
Mark Sussman and Elbridge Gerry Puckett, A coupled level set and volume-of-fluid method for computing 3D and axisymmetric incompressible two-phase flows, J. Comput. Phys. 162 (2000), no. 2, 301–337. MR 1774261, DOI 10.1006/jcph.2000.6537
M. Sussman, P. Smereka, and S. Osher, A level set method for computing solutions to imcompressible two-phase flow, J. Comput. Phys, 119 (1994), pp. 146–159.
Eitan Tadmor, Numerical viscosity and the entropy condition for conservative difference schemes, Math. Comp. 43 (1984), no. 168, 369–381. MR 758189, DOI 10.1090/S0025-5718-1984-0758189-X
G. Tryggvason, B. Bunner, A. Esmaeeli, D. Juric, N. Al-Rawahi, W. Tauber, J. Han, S. Nas, and Y.-J. Jan, A front-tracking method for the computations of multiphase flow, J. Comput. Phys, 169 (2001), pp. 708–759.
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
Hong-Kai Zhao, T. Chan, B. Merriman, and S. Osher, A variational level set approach to multiphase motion, J. Comput. Phys. 127 (1996), no. 1, 179–195. MR 1408069, DOI 10.1006/jcph.1996.0167