# Fast sweeping method

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Fast_sweeping_method
> Markdown URL: https://mediated.wiki/source/Fast_sweeping_method.md
> Source: https://en.wikipedia.org/wiki/Fast_sweeping_method
> Source revision: 1224577321
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [applied mathematics](/source/applied_mathematics), the '''fast sweeping method''' is a [numerical method](/source/numerical_method) for solving [boundary value problem](/source/boundary_value_problem)s of the [Eikonal equation](/source/Eikonal_equation).

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

: <math>u(\mathbf{x}) = 0 \text{ for } \mathbf{x} \in \partial \Omega  
</math>

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

The fast sweeping method is an iterative method which uses upwind difference for discretization and uses [Gauss–Seidel iterations](/source/Gauss%E2%80%93Seidel_method) 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 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](/source/Hongkai_Zhao), an applied mathematician at the [University of California, Irvine](/source/University_of_California%2C_Irvine).

Sweeping algorithms are highly efficient for solving Eikonal equations when the corresponding [characteristic curves](/source/Method_of_characteristics) 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> 

== References ==
<references />

== See also ==
* [Fast marching method](/source/Fast_marching_method)

Category:Numerical differential equations
Category:Partial differential equations
Category:Hyperbolic partial differential equations

{{applied-math-stub}}

---
Adapted from the Wikipedia article [Fast sweeping method](https://en.wikipedia.org/wiki/Fast_sweeping_method) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Fast_sweeping_method?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.