A level set approach for computing discontinuous solutions of HamiltonJacobi equations
Authors:
YenHsi Richard Tsai, Yoshikazu Giga and Stanley Osher
Journal:
Math. Comp. 72 (2003), 159181
MSC (2000):
Primary 65Mxx, 35Lxx; Secondary 70H20
Published electronically:
August 13, 2002
MathSciNet review:
1933817
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We introduce two types of finite difference methods to compute the Lsolution and the proper viscosity solution recently proposed by the second author for semidiscontinuous solutions to a class of HamiltonJacobi 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 LaxFriedrichs type numerical methods for computing the Lsolution 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 LaxFriedrichs 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.
 1.
Martino Bardi and Italo CapuzzoDolcetta, Optimal control and viscosity solutions of HamiltonJacobiBellman 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 firstorder HamiltonJacobi equations: a guided visit, Nonlinear Anal. 20 (1993), no. 9, 11231134. MR 94d:49047
 3.
Guy Barles, Solution de viscosité des équations de HamiltonJacobi, SpringerVerlag, 1994. MR 2000b:49054
 4.
E. N. Barron and R. Jensen, Semicontinuous viscosity solutions for HamiltonJacobi equations with convex Hamiltonians, Comm. Partial Differential Equations 15 (1990), no. 12, 17131742. 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 HamiltonJacobi equations, Mathematics of Computation 43 (1984), 119. MR 86j:65121
 7.
Michael G. Crandall and PierreLouis Lions, Viscosity solutions of HamiltonJacobi equations, Trans. Amer. Math. Soc. 277 (1983), no. 1, 142. 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, 932958. MR 98g:35092
 9.
MiHo Giga and Yoshikazu Giga, Crystalline and level set flowconvergence 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. 6479. MR 2002f:53117
 10.
MiHo Giga, Yoshikazu Giga, and Ryo Kobayashi, Very singular diffusion equations, Advanced Studies in Pure Mathematics 31, 2001, pp. 93125.
 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, 443470. 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 MotoHiko Sato, A level set approach to semicontinuous viscosity solutions for Cauchy problems, Comm. Partial Differential Equations 26 (2001), no. 56, 813839.
 15.
Ami Harten, High resolution schemes for hyperbolic conservation laws, J. Comput. Phys. 49 (1983), no. 3, 357393. MR 84g:65115
 16.
Ami Harten, Björn Engquist, Stanley Osher, and Sukumar R. Chakravarthy, Uniformly highorder accurate essentially nonoscillatory schemes. III, J. Comput. Phys. 71 (1987), no. 2, 231303. 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. 253261.
 18.
Hitoshi Ishii, HamiltonJacobi equations with discontinuous Hamiltonians on arbitrary open sets, Bull. Fac. Sci. Engrg. Chuo Univ. 28 (1985), 3377. MR 87k:35055
 19.
, Existence and uniqueness of solutions of HamiltonJacobi equations, Funkcial. Ekvac. 29 (1986), no. 2, 167188. MR 88c:35037
 20.
, Perron's method for HamiltonJacobi equations, Duke Math. J. 55 (1987), no. 2, 369384. MR 89a:35053
 21.
GuangShan Jiang and Danping Peng, Weighted ENO schemes for HamiltonJacobi equations, SIAM J. Sci. Comput. 21 (2000), no. 6, 21262143 (electronic). MR 2001e:65124
 22.
R. Kobayashi and Y. Giga, Equations with singular diffusivity, J. Statist. Phys. 95 (1999), no. 56, 11871220. 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.
ChiTien Lin and Eitan Tadmor, Highresolution nonoscillatory central schemes for HamiltonJacobi equations, SIAM J. Sci. Comput. 21 (2000), no. 6, 21632186 (electronic). MR 2001e:65125
 25.
Stanley Osher, A level set formulation for the solution of the Dirichlet problem for HamiltonJacobi equations, SIAM J Math Anal 24 (1993), no. 5, 11451152. MR 94h:35039
 26.
Stanley Osher and James A. Sethian, Fronts propagating with curvaturedependent speed: algorithms based on HamiltonJacobi formulations, J. Comput. Phys. 79 (1988), no. 1, 1249. MR 89h:80012
 27.
Stanley Osher and ChiWang Shu, Highorder essentially nonoscillatory schemes for HamiltonJacobi equations, SIAM J. Numer. Anal. 28 (1991), no. 4, 907922. MR 92e:65118
 28.
Danping Peng, Barry Merriman, Stanley Osher, Hongkai Zhao, and Myungjoo Kang, A PDEbased fast local level set method, J. Comput. Phys. 155 (1999), no. 2, 410438. MR 2000j:65104
 29.
J.A. Sethian, Fast marching level set methods for three dimensional photolithography development, SPIE 2726, 1996, pp. 261272.
 30.
ChiWang Shu and Stanley Osher, Efficient implementation of essentially nonoscillatory shockcapturing schemes. II, J. Comput. Phys. 83 (1989), no. 1, 3278. MR 90i:65167
 31.
Panagiotis E. Souganidis, Approximation schemes for viscosity solutions of HamiltonJacobi equations, J. Differential Equations 59 (1985), no. 1, 143. MR 86k:35028
 32.
YenHsi 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, 15281538. MR 96d:49039
 34.
Bram van Leer, Towards the ultimate conservative difference schemes V, J. Comput. Phys. 32 (1979), 102136. MR 90h:70003
 1.
 Martino Bardi and Italo CapuzzoDolcetta, Optimal control and viscosity solutions of HamiltonJacobiBellman 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 firstorder HamiltonJacobi equations: a guided visit, Nonlinear Anal. 20 (1993), no. 9, 11231134. MR 94d:49047
 3.
 Guy Barles, Solution de viscosité des équations de HamiltonJacobi, SpringerVerlag, 1994. MR 2000b:49054
 4.
 E. N. Barron and R. Jensen, Semicontinuous viscosity solutions for HamiltonJacobi equations with convex Hamiltonians, Comm. Partial Differential Equations 15 (1990), no. 12, 17131742. 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 HamiltonJacobi equations, Mathematics of Computation 43 (1984), 119. MR 86j:65121
 7.
 Michael G. Crandall and PierreLouis Lions, Viscosity solutions of HamiltonJacobi equations, Trans. Amer. Math. Soc. 277 (1983), no. 1, 142. 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, 932958. MR 98g:35092
 9.
 MiHo Giga and Yoshikazu Giga, Crystalline and level set flowconvergence 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. 6479. MR 2002f:53117
 10.
 MiHo Giga, Yoshikazu Giga, and Ryo Kobayashi, Very singular diffusion equations, Advanced Studies in Pure Mathematics 31, 2001, pp. 93125.
 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, 443470. 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 MotoHiko Sato, A level set approach to semicontinuous viscosity solutions for Cauchy problems, Comm. Partial Differential Equations 26 (2001), no. 56, 813839.
 15.
 Ami Harten, High resolution schemes for hyperbolic conservation laws, J. Comput. Phys. 49 (1983), no. 3, 357393. MR 84g:65115
 16.
 Ami Harten, Björn Engquist, Stanley Osher, and Sukumar R. Chakravarthy, Uniformly highorder accurate essentially nonoscillatory schemes. III, J. Comput. Phys. 71 (1987), no. 2, 231303. 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. 253261.
 18.
 Hitoshi Ishii, HamiltonJacobi equations with discontinuous Hamiltonians on arbitrary open sets, Bull. Fac. Sci. Engrg. Chuo Univ. 28 (1985), 3377. MR 87k:35055
 19.
 , Existence and uniqueness of solutions of HamiltonJacobi equations, Funkcial. Ekvac. 29 (1986), no. 2, 167188. MR 88c:35037
 20.
 , Perron's method for HamiltonJacobi equations, Duke Math. J. 55 (1987), no. 2, 369384. MR 89a:35053
 21.
 GuangShan Jiang and Danping Peng, Weighted ENO schemes for HamiltonJacobi equations, SIAM J. Sci. Comput. 21 (2000), no. 6, 21262143 (electronic). MR 2001e:65124
 22.
 R. Kobayashi and Y. Giga, Equations with singular diffusivity, J. Statist. Phys. 95 (1999), no. 56, 11871220. 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.
 ChiTien Lin and Eitan Tadmor, Highresolution nonoscillatory central schemes for HamiltonJacobi equations, SIAM J. Sci. Comput. 21 (2000), no. 6, 21632186 (electronic). MR 2001e:65125
 25.
 Stanley Osher, A level set formulation for the solution of the Dirichlet problem for HamiltonJacobi equations, SIAM J Math Anal 24 (1993), no. 5, 11451152. MR 94h:35039
 26.
 Stanley Osher and James A. Sethian, Fronts propagating with curvaturedependent speed: algorithms based on HamiltonJacobi formulations, J. Comput. Phys. 79 (1988), no. 1, 1249. MR 89h:80012
 27.
 Stanley Osher and ChiWang Shu, Highorder essentially nonoscillatory schemes for HamiltonJacobi equations, SIAM J. Numer. Anal. 28 (1991), no. 4, 907922. MR 92e:65118
 28.
 Danping Peng, Barry Merriman, Stanley Osher, Hongkai Zhao, and Myungjoo Kang, A PDEbased fast local level set method, J. Comput. Phys. 155 (1999), no. 2, 410438. MR 2000j:65104
 29.
 J.A. Sethian, Fast marching level set methods for three dimensional photolithography development, SPIE 2726, 1996, pp. 261272.
 30.
 ChiWang Shu and Stanley Osher, Efficient implementation of essentially nonoscillatory shockcapturing schemes. II, J. Comput. Phys. 83 (1989), no. 1, 3278. MR 90i:65167
 31.
 Panagiotis E. Souganidis, Approximation schemes for viscosity solutions of HamiltonJacobi equations, J. Differential Equations 59 (1985), no. 1, 143. MR 86k:35028
 32.
 YenHsi 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, 15281538. MR 96d:49039
 34.
 Bram van Leer, Towards the ultimate conservative difference schemes V, J. Comput. Phys. 32 (1979), 102136. 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
YenHsi Richard Tsai
Affiliation:
Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095
Email:
ytsai@math.ucla.edu
Yoshikazu Giga
Affiliation:
Department of Mathematics, Hokkaido University, Sapporo 0600810, Japan
Email:
giga@math.sci.hokudai.ac.jp
Stanley Osher
Affiliation:
Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095
Email:
sjo@math.ucla.edu
DOI:
http://dx.doi.org/10.1090/S0025571802014382
PII:
S 00255718(02)014382
Keywords:
HamiltonJacobi 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 N000149710027, DARPA/NSF VIP grant NSF DMS 9615854 and ARO DAAG 559810323.
Article copyright:
© Copyright 2002
American Mathematical Society
