×

High order fast sweeping methods for static Hamilton-Jacobi equations. (English) Zbl 1149.70302

Summary: We construct high order fast sweeping numerical methods for computing viscosity solutions of static Hamilton-Jacobi equations on rectangular grids. These methods combine high order weighted essentially non-oscillatory (WENO) approximations to derivatives, monotone numerical Hamiltonians and Gauss-Seidel iterations with alternating-direction sweepings. Based on well-developed first order sweeping methods, we design a novel approach to incorporate high order approximations to derivatives into numerical Hamiltonians such that the resulting numerical schemes are formally high order accurate and inherit the fast convergence from the alternating sweeping strategy. Extensive numerical examples verify efficiency, convergence and high order accuracy of the new methods.

MSC:

70-08 Computational methods for problems pertaining to mechanics of particles and systems
70H20 Hamilton-Jacobi equations in mechanics
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Abgrall R. (1996). Numerical discretization of the first-order Hamilton–Jacobi equation on triangular meshes. Commun. Pure Appl. Math. 49, 1339–1373 · Zbl 0870.65116
[2] Augoula S., Abgrall R. (2000). High order numerical discretization for Hamilton–Jacobi equations on triangular meshes. J. Sci. Comput. 15, 197–229 · Zbl 1077.65506
[3] Boué M., Dupuis P. (1999). Markov chain approximations for deterministic control problems with affine dynamics and quadratic cost in the control. SIAM J. Numer. Anal. 36, 667–695 · Zbl 0933.65073
[4] Bryson S.,Levy D. (2003). High-order central WENO schemes for multidimensional Hamilton–Jacobi equations. SIAM J Numer. Anal. 41, 1339–1369 · Zbl 1050.65076
[5] Barth T., Sethian J. (1998). Numerical schemes for the Hamilton–Jacobi and level set equations on triangulated domains J. Comput. Phys. 145, 1–40 · Zbl 0911.65091
[6] Cecil T., Qian J., Osher S. (2004). Numerical methods for high dimensional Hamilton–Jacobi equations using radial basis functions. J. Comput. Phys. 196, 327–347 · Zbl 1053.65086
[7] Crandall M.G., Lions P.L. (1983). Viscosity solutions of Hamilton–Jacobi equations. Trans. Amer. Math. Soc. 277, 1–42 · Zbl 0599.35024
[8] Dellinger, J., and Symes, W. W. (1997). Anisotropic finite-difference traveltimes using a Hamilton–Jacobi solver, 67th Ann. Internat. Mtg., Soc. Expl. Geophys., Expanded Abstracts, 1786–1789
[9] Falcone M., Ferretti R. (1994). Discrete time high-order schemes for viscosity solutions of Hamilton–Jacobi–Bellman equations Numer. Math. 67, 315–344 · Zbl 0791.65046
[10] Falcone M., Ferretti R. (2002). Semi-Lagrangian schemes for Hamilton–Jacobi equations, discrete representation formulae and Godunov methods. J. Comput. Phys. 175, 559–575 · Zbl 1007.65060
[11] Gray S., May W. (1994). Kirchhoff migration using eikonal equation travel-times. Geophysics 59, 810-817
[12] Helmsen J., Puckett E., Colella P., Dorr M. (1996) Two new methods for simulating photolithography development in 3d, Proc SPIE, 2726: 253–261
[13] Hu C., Shu C.-W. (1999). A discontinuous Galerkin finite element method for Hamilton–Jacobi equations. SIAM J. Sci Comput. 20, 666–690 · Zbl 0946.65090
[14] Jiang G.-S., Peng D. (2000). Weighted ENO Schemes for Hamilton–Jacobi equations. SIAM J. Sci. Comput. 21, 2126–2143 · Zbl 0957.35014
[15] Jiang G.-S., Shu C.-W. (1996). Efficient implementation of weighted ENO schemes. J. Comput. Phy. 126, 202–228 · Zbl 0877.65065
[16] Jin S., Xin Z. (1998). Numerical passage from systems of conservation laws to Hamilton–Jacobi equations and relaxation schemes. SIAM J. Numer. Anal. 35, 2385–2404 · Zbl 0921.65063
[17] Kim S., Cook R. (1999). 3D traveltime computation using second-order ENO scheme. Geophys. 64, 1867–1876
[18] Kao C.Y., Osher S., Qian J. (2004). Lax-Friedrichs sweeping scheme for static Hamilton–Jacobi equations. J Comput. Phys. 196, 367–391 · Zbl 1053.65088
[19] Kao C.Y., Osher S., Tsai Y.H. (2005). Fast sweeping methods for Hamilton–Jacobi equations. SIAM J. Numer. Anal. 42, 2612–2632 · Zbl 1090.35016
[20] Lin C.-T., Tadmor E. (2000). High-resolution non-oscillatory central schemes for approximate Hamilton–Jacobi equations. SIAM J. Sci. Comput. 21, 2163–2186 · Zbl 0964.65097
[21] Lin C.-T., Tadmor E. (2001). L 1-stability and error estimates for approximate Hamilton–Jacobi solutions. Numer Math. 87, 701–735 · Zbl 0977.65059
[22] Osher S. (1993). A level set formulation for the solution of the Dirichlet problem for Hamilton–Jacobi equations. SIAM J. Math Anal. 24, 1145–1152 · Zbl 0804.35021
[23] Osher S., Sethian J. (1988). Fronts propagating with curvature dependent speed: algorithms based on Hamilton–Jacobi formulations. J. Comput. Phys. 79, 12–49 · Zbl 0659.65132
[24] Osher S., Shu C.-W. (1991). High-order essentially nonoscillatory schemes for Hamilton–Jacobi equations. SIAM J. Numer Anal. 28, 907–922 · Zbl 0736.65066
[25] Peng D., Osher S., Merriman B., Zhao H.-K., Rang M. (1999). A PDE-based fast local level set method. J. Comput Phys. 155, 410–438 · Zbl 0964.76069
[26] Qian J., Cheng L.T., Osher S. (2003). A level set based Eulerian approach for anisotropic wave propagations. Wave Motion 37, 365–379 · Zbl 1163.74426
[27] Qian J., Symes W.W. (2001). Paraxial eikonal solvers for anisotropic quasi-P travel times. J. Comput Phys. 174, 256–278 · Zbl 1056.35042
[28] Qian J., Symes W.W. (2002). Finite-difference quasi-P traveltimes for anisotropic media. Geophysics 67, 147–155
[29] Qian J., Symes W.W. (2002). An adaptive finite-difference method for traveltime and amplitude. Geophysics 67, 166–176
[30] Qin F., Schuster G. T. (1993). First-arrival traveltime calculation for anisotropic media. Geophysics 58, 1349–1358
[31] Rouy E., Tourin A. (1992). A viscosity solutions approach to shape-from-shading. SIAM J. Numer. Anal. 29, 867–884 · Zbl 0754.65069
[32] Sethian J.A. (1996). A fast marching level set method for monotonically advancing fronts. Proc. Nat. Acad. Sci. 93, 1591–1595 · Zbl 0852.65055
[33] Sethian J.A., Vladimirsky A. (2001). Ordered upwind methods for static Hamilton–Jacobi equations. Proc. Natl. Acad. Sci. 98, 11069–11074 · Zbl 1002.65112
[34] Sethian J.A., Vladimirsky A. (2003) Ordered upwind methods for static Hamilton–Jacobi equations: theory and algorithms SIAM J. Numer. Anal. 41, 325–363 · Zbl 1040.65088
[35] Chi-Wang Shu (2004) High Order Numerical Methods for Time Dependent Hamilton–Jacobi Equations, WSPC/Lecture Notes Series
[36] Shu C.-W., Osher S. (1988) Efficient Implementation of essentially non-oscillatory shock-capturing schemes J. Comput. Phys. 77, 439–471 · Zbl 0653.65072
[37] Tsai Y.-H. R., Cheng L.-T., Osher S., Zhao H.-K. (2003) Fast sweeping algorithms for a class of Hamilton–Jacobi equations SIAM J. Numer. Anal. 41, 673–694 · Zbl 1049.35020
[38] Tsitsiklis J.N. (1995). Efficient algorithms for globally optimal trajectories. IEEE Trans. Auto. Control 40, 1528–1538 · Zbl 0831.93028
[39] Zhang Y.-T., Shu C.-W. (2003). High order WENO schemes for Hamilton–Jacobi equations on triangular meshes. SIAM J Sci. Comput. 24, 1005–1030 · Zbl 1034.65051
[40] Zhao H. (2004). A fast sweeping method for Eikonal equations. Math Comp. 74, 603–627 · Zbl 1070.65113
[41] Zhao H., Osher S., Merriman B., Kang M. (2000). Implicit and non-parametric shape reconstruction from unorganized points using variational level set method. Comput. Vision Image Understand. 80, 295–319 · Zbl 1011.68538
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.