Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



A level set approach for computing discontinuous solutions of Hamilton-Jacobi equations

Authors: Yen-Hsi Richard Tsai, Yoshikazu Giga and Stanley Osher
Journal: Math. Comp. 72 (2003), 159-181
MSC (2000): Primary 65Mxx, 35Lxx; Secondary 70H20
Published electronically: August 13, 2002
MathSciNet review: 1933817
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce two types of finite difference methods to compute the L-solution and the proper viscosity solution recently proposed by the second author for semi-discontinuous solutions to a class of Hamilton-Jacobi equations. By regarding the graph of the solution as the zero level curve of a continuous function in one dimension higher, we can treat the corresponding level set equation using the viscosity theory introduced by Crandall and Lions. However, we need to pay special attention both analytically and numerically to prevent the zero level curve from overturning so that it can be interpreted as the graph of a function. We demonstrate our Lax-Friedrichs type numerical methods for computing the L-solution using its original level set formulation. In addition, we couple our numerical methods with a singular diffusive term which is essential to computing solutions to a more general class of HJ equations that includes conservation laws. With this singular viscosity, our numerical methods do not require the divergence structure of equations and do apply to more general equations developing shocks other than conservation laws. These numerical methods are generalized to higher order accuracy using weighted ENO local Lax-Friedrichs methods as developed recently by Jiang and Peng. We verify that our numerical solutions approximate the proper viscosity solutions obtained by the second author in a recent Hokkaido University preprint. Finally, since the solution of scalar conservation law equations can be constructed using existing numerical techniques, we use it to verify that our numerical solution approximates the entropy solution.

References [Enhancements On Off] (What's this?)

  • 1. Martino Bardi and Italo Capuzzo-Dolcetta, Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations, Birkhäuser Boston Inc., Boston, MA, 1997, With appendices by Maurizio Falcone and Pierpaolo Soravia. MR 99e:14001
  • 2. Guy Barles, Discontinuous viscosity solutions of first-order Hamilton-Jacobi equations: a guided visit, Nonlinear Anal. 20 (1993), no. 9, 1123-1134. MR 94d:49047
  • 3. Guy Barles, Solution de viscosité des équations de Hamilton-Jacobi, Springer-Verlag, 1994. MR 2000b:49054
  • 4. E. N. Barron and R. Jensen, Semicontinuous viscosity solutions for Hamilton-Jacobi equations with convex Hamiltonians, Comm. Partial Differential Equations 15 (1990), no. 12, 1713-1742. MR 91b:35069
  • 5. C Caratheodory, Calculus of varieties of partial differential equations of the first order, Chelsea, 1982. MR 33:597; MR 38:590 (earlier ed.)
  • 6. M.G. Crandall and P.L. Lions, Two approximations of solutions of Hamilton-Jacobi equations, Mathematics of Computation 43 (1984), 1-19. MR 86j:65121
  • 7. Michael G. Crandall and Pierre-Louis Lions, Viscosity solutions of Hamilton-Jacobi equations, Trans. Amer. Math. Soc. 277 (1983), no. 1, 1-42. MR 85g:35029
  • 8. Lawrence C. Evans, A geometric interpretation of the heat equation with multivalued initial data, SIAM J. Math. Anal. 27 (1996), no. 4, 932-958. MR 98g:35092
  • 9. Mi-Ho Giga and Yoshikazu Giga, Crystalline and level set flow--convergence of a crystalline algorithm for a general anisotropic curvature flow in the plane, Free boundary problems: theory and applications, I (Chiba, 1999), Gakkotosho, Tokyo, 2000, pp. 64-79. MR 2002f:53117
  • 10. Mi-Ho Giga, Yoshikazu Giga, and Ryo Kobayashi, Very singular diffusion equations, Advanced Studies in Pure Mathematics 31, 2001, pp. 93-125.
  • 11. Y. Giga, S. Goto, H. Ishii, and M.-H. Sato, Comparison principle and convexity preserving properties for singular degenerate parabolic equations on unbounded domains, Indiana Univ. Math. J. 40 (1991), no. 2, 443-470. MR 92h:35010
  • 12. Yoshikazu Giga, Shocks and very strong vertical diffusion, To appear, Proc. of international conference on partial differential equations in celebration of the seventy fifth birthday of Professor Louis Nirenberg, Taiwan, 2001.
  • 13. -, Viscosity solutions with shocks, Hokkaido Univ. Preprint Series in Math. (2001), no. 519.
  • 14. Yoshikazu Giga and Moto-Hiko Sato, A level set approach to semicontinuous viscosity solutions for Cauchy problems, Comm. Partial Differential Equations 26 (2001), no. 5-6, 813-839.
  • 15. Ami Harten, High resolution schemes for hyperbolic conservation laws, J. Comput. Phys. 49 (1983), no. 3, 357-393. MR 84g:65115
  • 16. 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 90a:65199
  • 17. J. Helmsen, E. Puckett, P. Colella, and M. Dorr, Two new methods for simulating photolithography development in 3d, SPIE 2726, 1996, pp. 253-261.
  • 18. Hitoshi Ishii, Hamilton-Jacobi equations with discontinuous Hamiltonians on arbitrary open sets, Bull. Fac. Sci. Engrg. Chuo Univ. 28 (1985), 33-77. MR 87k:35055
  • 19. -, Existence and uniqueness of solutions of Hamilton-Jacobi equations, Funkcial. Ekvac. 29 (1986), no. 2, 167-188. MR 88c:35037
  • 20. -, Perron's method for Hamilton-Jacobi equations, Duke Math. J. 55 (1987), no. 2, 369-384. MR 89a:35053
  • 21. Guang-Shan Jiang and Danping Peng, Weighted ENO schemes for Hamilton-Jacobi equations, SIAM J. Sci. Comput. 21 (2000), no. 6, 2126-2143 (electronic). MR 2001e:65124
  • 22. R. Kobayashi and Y. Giga, Equations with singular diffusivity, J. Statist. Phys. 95 (1999), no. 5-6, 1187-1220. MR 2001f:82077
  • 23. Peter D. Lax, Hyperbolic systems of conservation laws and the mathematical theory of shock waves, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1973, Conference Board of the Mathematical Sciences Regional Conference Series in Applied Mathematics, No. 11. MR 50:2709
  • 24. 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 2001e:65125
  • 25. Stanley Osher, A level set formulation for the solution of the Dirichlet problem for Hamilton-Jacobi equations, SIAM J Math Anal 24 (1993), no. 5, 1145-1152. MR 94h:35039
  • 26. 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 89h:80012
  • 27. 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 92e:65118
  • 28. Danping Peng, Barry Merriman, Stanley Osher, Hongkai Zhao, and Myungjoo Kang, A PDE-based fast local level set method, J. Comput. Phys. 155 (1999), no. 2, 410-438. MR 2000j:65104
  • 29. J.A. Sethian, Fast marching level set methods for three dimensional photolithography development, SPIE 2726, 1996, pp. 261-272.
  • 30. 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 90i:65167
  • 31. Panagiotis E. Souganidis, Approximation schemes for viscosity solutions of Hamilton-Jacobi equations, J. Differential Equations 59 (1985), no. 1, 1-43. MR 86k:35028
  • 32. Yen-Hsi Richard Tsai, Rapid and accurate computation of the distance function using grids, UCLA CAM Report 00 (2000), no. 36.
  • 33. John Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Transactions on Automatic Control 40 (1995), no. 9, 1528-1538. MR 96d:49039
  • 34. Bram van Leer, Towards the ultimate conservative difference schemes V, J. Comput. Phys. 32 (1979), 102-136. MR 90h:70003

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65Mxx, 35Lxx, 70H20

Retrieve articles in all journals with MSC (2000): 65Mxx, 35Lxx, 70H20

Additional Information

Yen-Hsi Richard Tsai
Affiliation: Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095

Yoshikazu Giga
Affiliation: Department of Mathematics, Hokkaido University, Sapporo 060-0810, Japan

Stanley Osher
Affiliation: Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095

Keywords: Hamilton-Jacobi equations, singular diffusion, level sets
Received by editor(s): March 7, 2001
Published electronically: August 13, 2002
Additional Notes: The first and the third authors are supported by ONR N00014-97-1-0027, DARPA/NSF VIP grant NSF DMS 9615854 and ARO DAAG 55-98-1-0323.
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society