A second order discontinuous Galerkin fast sweeping method for eikonal equations. (English) Zbl 1151.65092
Summary: We construct a second order fast sweeping method with a discontinuous Galerkin (DG) local solver for computing viscosity solutions of a class of static Hamilton-Jacobi equations, namely the eikonal equations. Our piecewise linear DG local solver is built on a DG method developed recently by Y. Cheng and C.-W. Shu [ibid. 223, No. 1, 398–415 (2007; Zbl 1124.65090)] for the time-dependent Hamilton-Jacobi equations. The causality property of eikonal equations is incorporated into the design of this solver. The resulting local nonlinear system in the Gauss-Seidel iterations is a simple quadratic system and can be solved explicitly. The compactness of the DG method and the fast sweeping strategy lead to fast convergence of the new scheme for eikonal equations. Extensive numerical examples verify efficiency, convergence and second order accuracy of the proposed method.
MSC:
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
| 35F15 | Boundary value problems for linear first-order PDEs |
| 49L25 | Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games |
| 65N12 | Stability and convergence of numerical methods for boundary value problems involving PDEs |
| 65N15 | Error bounds for boundary value problems involving PDEs |
Keywords:
fast sweeping methods; discontinuous Galerkin finite element methods; second order accuracy; static Hamilton-Jacobi equations; eikonal equationsCitations:
Zbl 1124.65090References:
| [1] | Abgrall, R., Numerical discretization of the first-order Hamilton-Jacobi equation on triangular meshes, Communications on Pure and Applied Mathematics, 49, 1339-1373 (1996) · Zbl 0870.65116 |
| [2] | Arnold, D. N.; Brezzi, F.; Cockburn, B.; Marini, L. D., Unified analysis of discontinuous Galerkin methods for elliptic problems, SIAM Journal on Numerical Analysis, 39, 1749-1779 (2001/02) · Zbl 1008.65080 |
| [3] | Augoula, S.; Abgrall, R., High order numerical discretization for Hamilton-Jacobi equations on triangular meshes, Journal of Scientific Computing, 15, 197-229 (2000) · Zbl 1077.65506 |
| [4] | Barth, T.; Sethian, J., Numerical schemes for the Hamilton-Jacobi and level set equations on triangulated domains, Journal of Computational Physics, 145, 1-40 (1998) · Zbl 0911.65091 |
| [5] | Boué, M.; Dupuis, P., Markov chain approximations for deterministic control problems with affine dynamics and quadratic cost in the control, SIAM Journal on Numerical Analysis, 36, 667-695 (1999) · Zbl 0933.65073 |
| [6] | Bryson, S.; Levy, D., High-order central WENO schemes for multidimensional Hamilton-Jacobi equations, SIAM Journal on Numerical Analysis, 41, 1339-1369 (2003) · Zbl 1050.65076 |
| [7] | Cecil, T.; Qian, J.; Osher, S., Numerical methods for high dimensional Hamilton-Jacobi equations using radial basis functions, Journal of Computational Physics, 196, 327-347 (2004) · Zbl 1053.65086 |
| [8] | L.-T. Cheng, Y.-H. Tsai, Redistancing by flow of time dependent Eikonal equation, UCLA CAM Report 07-16.; L.-T. Cheng, Y.-H. Tsai, Redistancing by flow of time dependent Eikonal equation, UCLA CAM Report 07-16. |
| [9] | Cheng, Y.; Shu, C.-W., A discontinuous Galerkin finite element method for directly solving the Hamilton-Jacobi equations, Journal of Computational Physics, 223, 398-415 (2007) · Zbl 1124.65090 |
| [10] | Cockburn, B.; Hou, S.; Shu, C.-W., The Runge-Kutta local projection discontinuous Galerkin finite element method for conservation laws IV: the multidimensional case, Mathematics of Computation, 54, 545-581 (1990) · Zbl 0695.65066 |
| [11] | Cockburn, B.; Lin, S.-Y.; Shu, C.-W., TVB Runge-Kutta local projection discontinuous Galerkin finite element method for conservation laws III: one dimensional systems, Journal of Computational Physics, 84, 90-113 (1989) · Zbl 0677.65093 |
| [12] | Cockburn, B.; Shu, C.-W., TVB Runge-Kutta local projection discontinuous Galerkin finite element method for conservation laws II: general framework, Mathematics of Computation, 52, 411-435 (1989) · Zbl 0662.65083 |
| [13] | Cockburn, B.; Shu, C.-W., The Runge-Kutta discontinuous Galerkin method for conservation laws V: multidimensional systems, Journal of Computational Physics, 141, 199-224 (1998) · Zbl 0920.65059 |
| [14] | Cockburn, B.; Shu, C.-W., The local discontinuous Galerkin method for time-dependent convection-diffusion systems, SIAM Journal on Numerical Analysis, 35, 2440-2463 (1998) · Zbl 0927.65118 |
| [15] | Cockburn, B.; Shu, C.-W., Runge-Kutta discontinuous Galerkin methods for convection-dominated problems, Journal of Scientific Computing, 16, 173-261 (2001) · Zbl 1065.76135 |
| [16] | Crandall, M. G.; Lions, P. L., Viscosity solutions of Hamilton-Jacobi equations, Transactions of American Mathematical Society, 277, 1-42 (1983) · Zbl 0599.35024 |
| [17] | J. Dellinger, W.W. Symes, Anisotropic finite-difference traveltimes using a Hamilton-Jacobi solver, in: 67th Ann. Internat. Mtg., Soc. Expl. Geophys., Expanded Abstracts, 1997, pp. 1786-1789.; J. Dellinger, W.W. Symes, Anisotropic finite-difference traveltimes using a Hamilton-Jacobi solver, in: 67th Ann. Internat. Mtg., Soc. Expl. Geophys., Expanded Abstracts, 1997, pp. 1786-1789. |
| [18] | Dijkstra, E. W., A note on two problems in connection with graphs, Numerische Mathematik, 1, 269-271 (1959) · Zbl 0092.16002 |
| [19] | Falcone, M.; Ferretti, R., Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations, Numerische Mathematik, 67, 315-344 (1994) · Zbl 0791.65046 |
| [20] | Falcone, M.; Ferretti, R., Semi-Lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and Godunov methods, Journal of Computational Physics, 175, 559-575 (2002) · Zbl 1007.65060 |
| [21] | Gray, S.; May, W., Kirchhoff migration using Eikonal equation travel-times, Geophysics, 59, 810-817 (1994) |
| [22] | Helmsen, J.; Puckett, E.; Colella, P.; Dorr, M., Two new methods for simulating photolithography development in 3D, Proceedings of the SPIE, 2726, 253-261 (1996) |
| [23] | C. Hu, O. Lepsky, C.-W. Shu, The effect of the least square procedure for discontinuous Galerkin methods for Hamilton-Jacobi equations. Discontinuous Galerkin methods (Newport, RI, 1999), Lecture Notes in Computational Science and Engineering, Springer, Berlin, 2000, pp. 343-348.; C. Hu, O. Lepsky, C.-W. Shu, The effect of the least square procedure for discontinuous Galerkin methods for Hamilton-Jacobi equations. Discontinuous Galerkin methods (Newport, RI, 1999), Lecture Notes in Computational Science and Engineering, Springer, Berlin, 2000, pp. 343-348. · Zbl 0946.65086 |
| [24] | Hu, C.; Shu, C.-W., A discontinuous Galerkin finite element method for Hamilton-Jacobi equations, SIAM Journal on Scientific Computing, 20, 666-690 (1999) · Zbl 0946.65090 |
| [25] | Jiang, G.-S.; Peng, D., Weighted ENO schemes for Hamilton-Jacobi equations, SIAM Journal on Scientific Computing, 21, 2126-2143 (2000) · Zbl 0957.35014 |
| [26] | Jin, S.; Xin, Z., Numerical passage from systems of conservation laws to Hamilton-Jacobi equations and relaxation schemes, SIAM Journal on Numerical Analysis, 35, 2385-2404 (1998) · Zbl 0921.65063 |
| [27] | Kao, C. Y.; Osher, S.; Qian, J., Lax-Friedrichs sweeping schemes for static Hamilton-Jacobi equations, Journal of Computational Physics, 196, 367-391 (2004) · Zbl 1053.65088 |
| [28] | Kao, C. Y.; Osher, S.; Tsai, Y. H., Fast sweeping method for static Hamilton-Jacobi equations, SIAM Journal on Numerical Analysis, 42, 2612-2632 (2005) · Zbl 1090.35016 |
| [29] | Kim, S.; Cook, R., 3D traveltime computation using second-order ENO scheme, Geophysics, 64, 1867-1876 (1999) |
| [30] | Li, F.; Shu, C.-W., Reinterpretation and simplified implementation of a discontinuous Galerkin method for Hamilton-Jacobi equations, Applied Mathematics Letters, 18, 1204-1209 (2005) · Zbl 1118.65105 |
| [31] | Lin, C.-T.; Tadmor, E., High-resolution non-oscillatory central schemes for approximate Hamilton-Jacobi equations, SIAM Journal on Scientific Computing, 21, 2163-2186 (2000) · Zbl 0964.65097 |
| [32] | Osher, S., A level set formulation for the solution of the Dirichlet problem for Hamilton-Jacobi equations, SIAM Journal on Mathematical Analysis, 24, 1145-1152 (1993) · Zbl 0804.35021 |
| [33] | Osher, S.; Sethian, J., Fronts propagating with curvature dependent speed: algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, 79, 12-49 (1988) · Zbl 0659.65132 |
| [34] | Osher, S.; Shu, C.-W., High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations, SIAM Journal on Numerical Analysis, 28, 907-922 (1991) · Zbl 0736.65066 |
| [35] | Peng, D.; Osher, S.; Merriman, B.; Zhao, H.-K.; Rang, M., A PDE-based fast local level set method, Journal of Computational Physics, 155, 410-438 (1999) · Zbl 0964.76069 |
| [36] | Qian, J.; Symes, W. W., Paraxial Eikonal solvers for anisotropic quasi-P travel times, Journal of Computational Physics, 174, 256-278 (2001) · Zbl 1056.35042 |
| [37] | Qian, J.; Symes, W. W., Finite-difference quasi-P traveltimes for anisotropic media, Geophysics, 67, 147-155 (2002) |
| [38] | Qian, J.; Zhang, Y.-T.; Zhao, H.-K., Fast sweeping methods for Eikonal equations on triangular meshes, SIAM Journal on Numerical Analysis, 45, 83-107 (2007) · Zbl 1149.65087 |
| [39] | Qian, J.; Zhang, Y.-T.; Zhao, H.-K., A fast sweeping method for static convex Hamilton-Jacobi equations, Journal of Scientific Computing, 31, 237-271 (2007) · Zbl 1115.70005 |
| [40] | C. Rasch, T. Satzger, Remarks on the \(ON\) http://www.citebase.org/abstract?id=oai:arXiv.org:cs/0703082; C. Rasch, T. Satzger, Remarks on the \(ON\) http://www.citebase.org/abstract?id=oai:arXiv.org:cs/0703082 · Zbl 1241.65087 |
| [41] | Rouy, E.; Tourin, A., A viscosity solutions approach to shape-from-shading, SIAM Journal on Numerical Analysis, 29, 867-884 (1992) · Zbl 0754.65069 |
| [42] | W.H. Reed, T.R. Hill, Triangular mesh method for the neutron transport equation, Technical report LA-UR-73-479, Los Alamos Scientific Laboratory, Los Alamos, NM, 1973.; W.H. Reed, T.R. Hill, Triangular mesh method for the neutron transport equation, Technical report LA-UR-73-479, Los Alamos Scientific Laboratory, Los Alamos, NM, 1973. |
| [43] | Sethian, J. A., A fast marching level set method for monotonically advancing fronts, Proceedings of the National Academy of Sciences of the United States of America, 93, 1591-1595 (1996) · Zbl 0852.65055 |
| [44] | Sethian, J. A.; Vladimirsky, A., Ordered upwind methods for static Hamilton-Jacobi equations, Proceedings of the National Academy of Sciences of the United States of America, 98, 11069-11074 (2001) · Zbl 1002.65112 |
| [45] | Sethian, J. A.; Vladimirsky, A., Ordered upwind methods for static Hamilton-Jacobi equations: theory and algorithms, SIAM Journal on Numerical Analysis, 41, 325-363 (2003) · Zbl 1040.65088 |
| [46] | Shu, C.-W., High order numerical methods for time dependent Hamilton-Jacobi equations, IMS Lecture Notes Series. IMS Lecture Notes Series, Mathematics and Computation in Imaging Science and Information Processing, vol. 11 (2007), World Scientific Publishing: World Scientific Publishing Singapore · Zbl 1131.68115 |
| [47] | Tsai, Y.-H. R.; Cheng, L.-T.; Osher, S.; Zhao, H.-K., Fast sweeping algorithms for a class of Hamilton-Jacobi equations, SIAM Journal on Numerical Analysis, 41, 673-694 (2003) · Zbl 1049.35020 |
| [48] | Tsitsiklis, J. N., Efficient algorithms for globally optimal trajectories, IEEE Transactions on Automatic Control, 40, 1528-1538 (1995) · Zbl 0831.93028 |
| [49] | Yan, J.; Shu, C.-W., A local discontinuous Galerkin method for KdV type equations, SIAM Journal on Numerical Analysis, 40, 769-791 (2002) · Zbl 1021.65050 |
| [50] | Yatziv, L.; Bartesaghi, A.; Sapiro, G., \(O(N)\) implementation of the fast marching algorithm, Journal of Computational Physics, 212, 393-399 (2006) · Zbl 1083.65083 |
| [51] | Zhang, Y.-T.; Shu, C.-W., High order WENO schemes for Hamilton-Jacobi equations on triangular meshes, SIAM Journal on Scientific Computing, 24, 1005-1030 (2003) · Zbl 1034.65051 |
| [52] | Zhang, Y.-T.; Zhao, H.-K.; Chen, S., Fixed-point iterative sweeping methods for static Hamilton-Jacobi equations, Methods and Applications of Analysis, 13, 299-320 (2006) · Zbl 1134.65076 |
| [53] | Zhang, Y.-T.; Zhao, H.-K.; Qian, J., High order fast sweeping methods for static Hamilton-Jacobi equations, Journal of Scientific Computing, 29, 25-56 (2006) · Zbl 1149.70302 |
| [54] | Zhao, H.-K., A fast sweeping method for Eikonal equations, Mathematics of Computation, 74, 603-627 (2005) · Zbl 1070.65113 |
| [55] | Zhao, H.; Osher, S.; Merriman, B.; Kang, M., Implicit and non-parametric shape reconstruction from unorganized points using variational level set method, Computer Vision and Image Understanding, 80, 295-319 (2000) · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
