Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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

Authors: Todd F. Dupont and Yingjie Liu
Journal: Math. Comp. 76 (2007), 647-668
MSC (2000): Primary 65M06, 65M12
Published electronically: October 30, 2006
MathSciNet review: 2291832
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

  • 1. S. CHEN, B. MERRIMAN, S. OSHER, AND P. SMEREKA, A simple level set method for solving Stefan problems, J. Comput. Phys., 135 (1997), pp. 8-29. MR 1461705 (98c:80002)
  • 2. R. COURANT, E. ISAACSON, AND M. REES, On the solution of nonlinear hyperbolic differential equations by finite differences, Comm. Pure Appl. Math., 5 (1952), pp. 243-255. MR 0053336 (14:756e)
  • 3. T. F. DUPONT AND Y.-J. 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), pp. 311-324. MR 2046766 (2004m:65162)
  • 4. D. ENRIGHT, R. FEDKIW, J. FERZIGER, AND I. MITCHELL, A hybrid particle level set method for improved interface capturing, J. Comput. Phys., 183 (2002), pp. 83-116. MR 1944529 (2003j:76084)
  • 5. D. ENRIGHT, F. LOSASSO, AND R. FEDKIW, A fast and accurate semi-Lagrangian particle level set method, Computers and Structures, 83 (2005), pp. 479-490. MR 2143508 (2005k:76104)
  • 6. M. FALCONE AND R. FERRETTI, Convergence analysis for a class of high-order semi-Lagrangian advection schemes, SIAM J. Numer. Anal., 35 (1998), pp. 909-940.MR 1619910 (99c:65164)
  • 7. J. GLIMM, J. W. GROVE, X.-L. LI, K.-M. SHYUE, Q. ZHANG, AND Y. ZENG, Three dimensional front tracking, SIAM J. Sci. Comput., 19 (1998), pp. 703-727.MR 1616658 (99c:35153)
  • 8. J. GLIMM, D. MARCHESIN, AND O. MCBRYAN, Subgrid resolution of fluid discontinuities, II, J. Comput. Phys., 37 (1980), pp. 336-354. MR 0588257 (81k:76041)
  • 9. A. HARTEN AND J. M. HYMAN, Self-adjusting grid methods for one-dimensional hyperbolic conservation laws, J. Comput. Phys., 50 (1983), pp. 235-269.MR 0707200 (85g:65111)
  • 10. A. HARTEN, S. OSHER, B. ENGQUIST, AND S. CHAKRAVARTHY, Uniformly high order accurate essentially non-oscillatory schemes, III, J. Comput. Phys., 71 (1987), pp. 231-303.MR 0897244 (90a:65199)
  • 11. G.-S. JIANG AND C.-W. SHU, Efficient implementation of weighted ENO schemes, J. Comput. Phys., 126 (1996), pp. 202-228. MR 1391627 (97e:65081)
  • 12. B.-M. KIM, Y.-J. LIU, I. LLAMAS, AND J. ROSSIGNAC, FlowFixer: Using BFECC for fluid simulation, Eurographics Workshop on Natural Phenomena (2005).
  • 13. -, Advections with significantly reduced dissipation and diffusion, IEEE Transactions on Visualization and Computer Graphics (in press).
  • 14. P. D. LAX, On the stability of difference approximations to solutions of hyperbolic equations with variable coefficients, Comm. Pure Appl. Math., 14 (1961), pp. 497-520. MR 0145686 (26:3215)
  • 15. R. LEVEQUE, High-resolution conservative algorithms for advection in incompressible flow, SIAM J. Numer. Anal., 33 (1996), pp. 627-665. MR 1388492 (98b:76049)
  • 16. X. D. LIU, S. OSHER, AND T. CHAN, Weighted essentially non-oscillatory schemes, J. Comput. Phys., 115 (1994), pp. 200-212. MR 1300340
  • 17. R. W. MACCORMACK, AIAA Paper 69-354 (1969).
  • 18. S. OSHER, Riemann solvers, the entropy condition, and difference approximations, SIAM J. Numer. Anal., 21 (1984), pp. 217-235. MR 0736327 (86d:65119)
  • 19. S. OSHER AND J. SETHIAN, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi equations, J. Comput. Phys, 79 (1988), pp. 12-49.MR 0965860 (89h:80012)
  • 20. 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.
  • 21. P. L. ROE, Approximate Riemann solvers, parameter vectors, and difference schemes, J. Comput. Phys, 43 (1981), pp. 357-372. MR 0640362 (82k:65055)
  • 22. G. RUSSO AND P. SMEREKA, A remark on computing distance functions, J. Comput. Phys, 163 (2000), pp. 51-67. MR 1777721 (2001d:65139)
  • 23. C.-W. SHU AND S. OSHER, Efficient implementation of essentially non-oscillatory shock-capturing schemes, J. Comput. Phys, 77 (1988), pp. 439-471.MR 0954915 (89g:65113)
  • 24. -, Efficient implementation of essentially non-oscillatory shock-capturing schemes, II, J. Comput. Phys, 83 (1989), pp. 32-78. MR 1010162 (90i:65167)
  • 25. J. STRAIN, Semi-Lagrangian methods for level set equations, J. Comput. Phys, 151 (1999), pp. 498-533. MR 1686375 (2000a:76133)
  • 26. -, A fast modular semi-Lagrangian method for moving interfaces, J. Comput. Phys, 161 (2000), pp. 512-536. MR 1764248
  • 27. -, A fast semi-Lagrangian contouring method for moving interfaces, J. Comput. Phys, 170 (2001), pp. 373-394. MR 1843614 (2002c:65035)
  • 28. M. SUSSMAN AND E. FATEMI, An efficient, interface preserving level set re-distancing algorithm and its application to interfacial incompressible fluid flow, SIAM J. Sci. Comput., 20 (1999), pp. 1165-1191. MR 1675468 (2000f:65084)
  • 29. M. SUSSMAN AND E. G. PUCKETT, A coupled level set and volume-of-fluid method for computing 3D and axisymmetric incompressible two-phase flows., J. Comput. Phys, 162 (2000), pp. 301-337. MR 1774261 (2001c:76099)
  • 30. 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.
  • 31. E. TADMOR, Numerical viscosity and the entropy condition for conservative difference schemes, Math. Comp., 43 (1984), pp. 369-381. MR 0758189 (86g:65163)
  • 32. 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.
  • 33. S. T. ZALESAK, Fully multidimensional flux-corrected transport, J. Comput. Phys., 31 (1979), pp. 335-362. MR 0534786 (80f:76048)
  • 34. H.-K. ZHAO, T. CHAN, B. MERRIMAN, AND S. OSHER, A variational level set approach to multiphase motion, J. Comput. Phys., 127 (1996), pp. 179-195.MR 1408069 (97g:80013)

Similar Articles

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

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

Additional Information

Todd F. Dupont
Affiliation: Department of Computer Science, University of Chicago, Chicago, Illinois 60637

Yingjie Liu
Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332

Keywords: CIR scheme, front tracking, level set method, MacCormack scheme, semi-Lagrangian scheme.
Received by editor(s): February 1, 2005
Received by editor(s) in revised form: December 19, 2005
Published electronically: October 30, 2006
Additional Notes: The work of the first author was supported by the ASC Flash Center at the University of Chicago under DOE contract B532820, and by the MRSEC Program of the National Science Foundation under award DMR-0213745.
The work of the second author was supported by NSF grant DMS-0511815.
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society