Fast sweeping method: Difference between revisions

Revision as of 21:00, 15 December 2018

Latest revision as of 05:40, 19 May 2024

(6 intermediate revisions by 6 users not shown)

Line 1:

In [[applied mathematics]], the '''fast sweeping method''' is a [[numerical method]] for solving [[boundary value problem]]s of the [[Eikonal equation]].

: <math>|\nabla u(\mathbf{x})| = \frac 1 {f(\mathbf{x})} \text{ for } \mathbf{x} \in \Omega

Line 7:

</math>

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 <math>L^2</math>[[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|url=http://www.ams.org/mcom/2005-74-250/S0025-5718-04-01678-3/|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>