Fast sweeping method: Difference between revisions

Revision as of 15:34, 21 March 2021

Revision as of 23:53, 11 May 2024

Line 9:

where <math>\Omega</math> is an [[open set]] in <math>\mathbb{R}^n</math>, <math>f(\mathbf{x})</math> is a [[function (mathematics)|function]] with positive values, <math>\partial \Omega</math> is a well-behaved [[boundary (topology)|boundary]] of the open set and <math>|\cdot|</math> is the [[Euclidean norm]].

The fast sweeping method is an iterative method which uses upwind difference for discretization and uses [[Gauss–Seidel method|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 <ref>M. Boue and P. Dupuis. Markov chain approximations for deterministic control theory]]problems with affine dynamics and quadratic cost in the control, SIAM J. on Numerical Analysis 36, 667-695, 1999.</ref>. Although fast sweeping methods have existed in control theory, it was first proposed for Eikonal equations<ref>{{Cite journal|last=Zhao|first=Hongkai|date=2005-01-01|title=A fast sweeping method for Eikonal equations|journal=Mathematics of Computation|volume=74|issue=250|pages=603–627|doi=10.1090/S0025-5718-04-01678-3|issn=0025-5718|doi-access=free}}</ref> by [[Hongkai Zhao]], an applied mathematician at the [[University of California, Irvine]].

Sweeping algorithms are highly efficient for solving Eikonal equations when the corresponding [[Method of characteristics|characteristic curves]] do not change direction very often.<ref name="chacon_twoscale">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]</ref>