Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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 $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 [Enhancements On Off] (What's this?)

Similar Articles

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

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