A fast sweeping method for Eikonal equations

Author:
Hongkai Zhao

Journal:
Math. Comp. **74** (2005), 603-627

MSC (2000):
Primary 65N06, 65N12, 65N15, 35L60

Published electronically:
May 21, 2004

MathSciNet review:
2114640

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 for 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 Gauss-Seidel iterations is enough for the distance function in dimensions. An estimation of the number of iterations for general Eikonal equations is also studied. Numerical examples are used to verify the analysis.

**1.**M. Bardi and S. Osher,*The nonconvex multi-dimensional Riemann problem for Hamilton-Jacobi equations*, SIAM Anal.**22(2)**(1991), 344-351. MR**91k:35056****2.**M. Boué and P. 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**2000a:49054****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 (D. Estep and S. Tavener, Eds.), SIAM, 2002.**4.**M.G. Crandall and P.L. Lions,*Viscosity solutions of Hamilton-Jacobi equations*, Trans. Amer. Math. Soc.**277**(1983) no. 1, 1-42. MR**85g:35029****5.**-,*Two approximations of solutions of Hamilton-Jacobi equations*, Math. Comp.**43**(1984), no. 167, 1-19. MR**86j:65121****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).**8.**Lawrence C. Evans,*Partial differential equations*, Graduate Studies in Mathematics, vol. 19, AMS, 1998. MR**99e:35001****9.**M. Falcone and R. Ferretti,*Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations*, Numer. Math.**7**(1994), no. 3, 315-344. MR**95d:49045****10.**-,*Semi-Lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and Godunov methods*, J. Comput. Phys.**175**(2002), no. 2, 559-575. MR**2003f:65151****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).**13.**S. Kim,*An level set method for Eikonal equations*, SIAM J. Sci. Comput. (2001).**14.**E. Rouy and A. Tourin,*A viscosity solution approach to shape-from-shading*, SIAM J. Num. Anal.**29**(1992), no. 3, 867-884. MR**93d:65019****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.**93**(1996), no. 4, 1591-1595. MR**97c:65171****17.**Y.R. Tsai,*Rapid and accurate computation of the distance function using grids*, J. Comp. Phys.**178**(2002), no. 1, 175-195. MR**2003e:65029****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.**19.**J.N. Tsitsiklis,*Efficient algorithms for globally optimal trajectories*, IEEE Transactions on Automatic Control**40**(1995), no. (9), 1528-1538.MR**96d:49039****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.

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65N06,
65N12,
65N15,
35L60

Retrieve articles in all journals with MSC (2000): 65N06, 65N12, 65N15, 35L60

Additional Information

**Hongkai Zhao**

Affiliation:
Department of Mathematics, University of California, Irvine, California 92697-3875

Email:
zhao@math.uci.edu

DOI:
http://dx.doi.org/10.1090/S0025-5718-04-01678-3

Keywords:
Eikonal equation,
characteristics,
Godunov scheme,
upwind difference,
Gauss-Seidel iteration,
Courant-Friedrichs-Lewy (CFL) condition

Received by editor(s):
September 20, 2003

Published electronically:
May 21, 2004

Additional Notes:
This work was partially supported by the Sloan Fundation, ONR grant N00014-02-1-0090 and DARPA grant N00014-02-1-0603

Article copyright:
© Copyright 2004
American Mathematical Society