zbMATH — the first resource for mathematics

A fast sweeping method for eikonal equations. (English) Zbl 1070.65113
The eikonal equation \[ | \nabla u(x)| =f(x),\;\;x\in{\mathbb R}^n \] has various applications. This nice paper gives an elegant numerical method for numerical approximation of the positive solution of the eikonal equation with Dirichlet boundary condition stated on the boundary \(\Gamma\) of a given domain. The method is based on the so called upwind finite difference scheme, a variant of the Godunov method. The method is presented with all details in the two dimensional case. Let \(u_{j,k}\) be the numerical solution at an interior grid point \(x_{j,k}\) on a square grid with the step \(h\). The Godunov scheme for \(u_{j,k}\) reads as follows: \[ [(u_{j,k}-u_{x,min})^+]^2+[(u_{j,k}-u_{y,min})^+]^2=h^2f(x_{j,k})^2, \] here \((\cdot)^+\) gives the value of the expression in brackets if it is positive, and zero otherwise; \(u_{x,min}=\min\{u_{j-1,k},u_{j+1,k}\}\), and similarly for the variable \(y\). The above system of quadratic equations is solved by iteration of the Gauss-Seidel type. In the two dimensional case the whole domain is sweeped with four alternating ordering: in both opposite direction with respect to \(j\), and then similarly, with respect to \(k\). Various properties of the proposed method are proven: the most important is its monotonicity, and in consequence its convergence as well as its optimal complexity. Several numerical examples are joint.

65N06 Finite difference methods for boundary value problems involving PDEs
65N12 Stability and convergence of numerical methods for boundary value problems involving PDEs
65N15 Error bounds for boundary value problems involving PDEs
35L50 Initial-boundary value problems for first-order hyperbolic systems
35L60 First-order nonlinear hyperbolic equations
PDF BibTeX Cite
Full Text: DOI
[1] Martino Bardi and Stanley Osher, The nonconvex multidimensional Riemann problem for Hamilton-Jacobi equations, SIAM J. Math. Anal. 22 (1991), no. 2, 344 – 351. · Zbl 0733.35073
[2] Michelle Boué and Paul Dupuis, Markov chain approximations for deterministic control problems with affine dynamics and quadratic cost in the control, SIAM J. Numer. Anal. 36 (1999), no. 3, 667 – 695. · Zbl 0933.65073
[3] B. Cockburn and J. Qian, A short introduction to continuous dependence results for Hamilton-Jacobi equations, Collected Lectures on the Preservation of Stability Under Discretization , SIAM, 2002.
[4] Michael G. Crandall and Pierre-Louis Lions, Viscosity solutions of Hamilton-Jacobi equations, Trans. Amer. Math. Soc. 277 (1983), no. 1, 1 – 42. · Zbl 0599.35024
[5] M. G. Crandall and P.-L. Lions, Two approximations of solutions of Hamilton-Jacobi equations, Math. Comp. 43 (1984), no. 167, 1 – 19. · Zbl 0556.65076
[6] P. Danielsson, Euclidean distance mapping, Computer Graphics and Image Processing 14 (1980), 227-248.
[7] K. Deckelnick and C.M. Elliott, Uniqueness and error analysis for Hamilton-Jacobi equations with discontinuities, preprint (2003). · Zbl 1081.35115
[8] Lawrence C. Evans, Partial differential equations, Graduate Studies in Mathematics, vol. 19, American Mathematical Society, Providence, RI, 1998. · Zbl 0902.35002
[9] Marizio Falcone and Roberto Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations, Numer. Math. 67 (1994), no. 3, 315 – 344. · Zbl 0791.65046
[10] M. Falcone and R. Ferretti, Semi-Lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and Godunov methods, J. Comput. Phys. 175 (2002), no. 2, 559 – 575. · Zbl 1007.65060
[11] J. Helmsen, E. Puckett, P. Colella, and M. Dorr, Two new methods for simulating photolithography development in 3d, Proc. SPIE 2726 (1996), 253-261.
[12] C.Y. Kao, S. Osher, and J. Qian, Lax-Friedrichs sweeping scheme for static Hamilton-Jacobi equations, UCLA CAM report (2003). · Zbl 1053.65088
[13] S. Kim, An \(o(n)\) level set method for Eikonal equations, SIAM J. Sci. Comput. (2001). · Zbl 0994.76080
[14] Elisabeth Rouy and Agnès Tourin, A viscosity solutions approach to shape-from-shading, SIAM J. Numer. Anal. 29 (1992), no. 3, 867 – 884. · Zbl 0754.65069
[15] W. A. J. Schneider, K. A. Ranzinger, A. H. Balch, and C. Kruse, A dynamic programming approach to first arrival traveltime computation in media with arbitrarily distributed velocities, Geophysics (1992).
[16] J. A. Sethian, A fast marching level set method for monotonically advancing fronts, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), no. 4, 1591 – 1595. · Zbl 0852.65055
[17] Yen-hsi Richard Tsai, Rapid and accurate computation of the distance function using grids, J. Comput. Phys. 178 (2002), no. 1, 175 – 195. · Zbl 0997.65090
[18] Y.R. Tsai, L.-T Cheng, S. Osher, and H.K. Zhao, Fast sweeping algorithms for a class of Hamilton-Jacobi equations, SIAM J. Numer. Anal. 41 (2003), no. 2, 673-694. · Zbl 1049.35020
[19] John N. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. Automat. Control 40 (1995), no. 9, 1528 – 1538. · Zbl 0831.93028
[20] H.K. Zhao, Analysis and visualization of large set of unorganized data points using the distance function, preprint (2002).
[21] H.K. Zhao, S. Osher, B. Merriman, and M. Kang, Implicit and non-parametric shape reconstruction from unorganized points using variational level set method, Computer Vision and Image Understanding 80 (2000), no. 3, 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.