Fast sweeping method explained

In applied mathematics, the fast sweeping method is a numerical method for solving boundary value problems of the Eikonal equation.

|\nabla u( x )| = (1)/(f( x )) for x \in \Omega u( x ) = 0 for x \in \partial \Omega

where

\Omega is an open set in R ^{n} , f( x ) is a function with positive values, \partial \Omega is a well-behaved boundary of the open set and | ⋅ | is the Euclidean norm.

The fast sweeping method is an iterative method which uses upwind difference for discretization and uses Gauss–Seidel iterations with alternating sweeping ordering to solve the discretized Eikonal equation on a rectangular grid. The origins of this approach lie in the paper by Boue and Dupuis.^[1] Although fast sweeping methods have existed in control theory, it was first proposed for Eikonal equations^[2] by Hongkai Zhao, an applied mathematician at the University of California, Irvine.

Sweeping algorithms are highly efficient for solving Eikonal equations when the corresponding characteristic curves do not change direction very often.^[3]

References

1. M. Boue and P. Dupuis. Markov chain approximations for deterministic control problems with affine dynamics and quadratic cost in the control, SIAM J. on Numerical Analysis 36, 667-695, 1999.
2. Zhao. Hongkai. 2005-01-01. A fast sweeping method for Eikonal equations. Mathematics of Computation. 74. 250. 603–627. 10.1090/S0025-5718-04-01678-3. 0025-5718. free.
3. A. Chacon and A. Vladimirsky. Fast two-scale methods for Eikonal equations. SIAM J. on Scientific Computing 34/2: A547-A578, 2012. https://arxiv.org/abs/1110.6220

See also

• Fast marching method