A fast sweeping method for Eikonal equations

Zhao, Hongkai

doi:10.1090/S0025-5718-04-01678-3

A fast sweeping method for Eikonal equations
HTML articles powered by AMS MathViewer

by Hongkai Zhao HTML | PDF

Math. Comp. 74 (2005), 603-627 Request permission

Abstract:

In this paper a fast sweeping method for computing the numerical solution of Eikonal equations on a rectangular grid is presented. The method is an iterative method which uses upwind difference for discretization and uses Gauss-Seidel iterations with alternating sweeping ordering to solve the discretized system. The crucial idea is that each sweeping ordering follows a family of characteristics of the corresponding Eikonal equation in a certain direction simultaneously. The method has an optimal complexity of $O(N)$ for $N$ grid points and is extremely simple to implement in any number of dimensions. Monotonicity and stability properties of the fast sweeping algorithm are proven. Convergence and error estimates of the algorithm for computing the distance function is studied in detail. It is shown that $2^{n}$ Gauss-Seidel iterations is enough for the distance function in $n$ dimensions. An estimation of the number of iterations for general Eikonal equations is also studied. Numerical examples are used to verify the analysis.

References

Martino Bardi and Stanley Osher, The nonconvex multidimensional Riemann problem for Hamilton-Jacobi equations, SIAM J. Math. Anal. 22 (1991), no. 2, 344–351. MR 1084960, DOI 10.1137/0522022
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. MR 1681057, DOI 10.1137/S0036142997323521
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 (D. Estep and S. Tavener, Eds.), SIAM, 2002.
Michael G. Crandall and Pierre-Louis Lions, Viscosity solutions of Hamilton-Jacobi equations, Trans. Amer. Math. Soc. 277 (1983), no. 1, 1–42. MR 690039, DOI 10.1090/S0002-9947-1983-0690039-8
M. G. Crandall and P.-L. Lions, Two approximations of solutions of Hamilton-Jacobi equations, Math. Comp. 43 (1984), no. 167, 1–19. MR 744921, DOI 10.1090/S0025-5718-1984-0744921-8
P. Danielsson, Euclidean distance mapping, Computer Graphics and Image Processing 14 (1980), 227–248.
K. Deckelnick and C.M. Elliott, Uniqueness and error analysis for Hamilton-Jacobi equations with discontinuities, preprint (2003).
Lawrence C. Evans, Partial differential equations, Graduate Studies in Mathematics, vol. 19, American Mathematical Society, Providence, RI, 1998. MR 1625845
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. MR 1269500, DOI 10.1007/s002110050031
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. MR 1880118, DOI 10.1006/jcph.2001.6954
J. Helmsen, E. Puckett, P. Colella, and M. Dorr, Two new methods for simulating photolithography development in 3d, Proc. SPIE 2726 (1996), 253–261.
C.Y. Kao, S. Osher, and J. Qian, Lax-Friedrichs sweeping scheme for static Hamilton-Jacobi equations, UCLA CAM report (2003).
S. Kim, An $o(n)$ level set method for Eikonal equations, SIAM J. Sci. Comput. (2001).
Elisabeth Rouy and Agnès Tourin, A viscosity solutions approach to shape-from-shading, SIAM J. Numer. Anal. 29 (1992), no. 3, 867–884. MR 1163361, DOI 10.1137/0729053
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).
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. MR 1374010, DOI 10.1073/pnas.93.4.1591
Yen-hsi Richard Tsai, Rapid and accurate computation of the distance function using grids, J. Comput. Phys. 178 (2002), no. 1, 175–195. MR 1899139, DOI 10.1006/jcph.2002.7028
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.
John N. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. Automat. Control 40 (1995), no. 9, 1528–1538. MR 1347833, DOI 10.1109/9.412624
H.K. Zhao, Analysis and visualization of large set of unorganized data points using the distance function, preprint (2002).
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.