Fast sweeping method

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

${\displaystyle |\nabla u(\mathbf {x} )|={\frac {1}{f(\mathbf {x} )}}{\text{ for }}\mathbf {x} \in \Omega }$

${\displaystyle u(\mathbf {x} )=0{\text{ for }}\mathbf {x} \in \partial \Omega }$

where ${\displaystyle \Omega }$ is an open set in ${\displaystyle \mathbb {R} ^{n}}$, ${\displaystyle f(\mathbf {x} )}$ is a function with positive values, ${\displaystyle \partial \Omega }$ is a well-behaved boundary of the open set and ${\displaystyle |\cdot |}$ 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 control theory. Although fast sweeping methods have existed in control theory, it was first proposed for Eikonal equations[1] 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.[2]

References

1. Zhao, Hongkai (2005-01-01). "A fast sweeping method for Eikonal equations". Mathematics of Computation. 74 (250): 603–627. doi:10.1090/S0025-5718-04-01678-3. ISSN 0025-5718.
2. A. Chacon and A. Vladimirsky. Fast two-scale methods for Eikonal equations. SIAM J. on Scientific Computing 34/2: A547-A578, 2012.

See also

• Fast marching method