**THE FMM SCHEME**

**1. FMM in continuous media**

The Fast Marching Method (FMM) is a narrow band level set method for solving Eikonal-type equations. The unconditional stability of the scheme comes from finding entropy-satisfying weak solutions to the Eikonal Equation that permit the formation and propagation of gradient discontinuities in the evolving wavefront.

The FMM systematically constructs traveltimes
*T
*in
a downwind fashion from known values upwind by employing a
*narrow band*
approach as illustrated below.

The scheme works by locating the grid point with
minimum traveltime within the narrow band of **close** points.
This is achieved by using a heap sorting algorithm; hence the O(*M*log*M*)
efficiency of the scheme in the presence of *M* grid points. The minimum
traveltime node is then added to the set of **alive** points. All grid
points surrounding the new **alive**
point that are not **alive **have their
value updated (if they are **close**) or calculated for the first time
(if they are **far**). The grid point with minimum traveltime within
the narrow band is then chosen and the process is repeated until all grid
points within the medium are **alive**. The figure below demonstrates
three evolution steps of the FMM starting from a source point.

The process of calculating traveltimes to points adjacent to the minimum traveltime point of the narrow band is achieved by solving the Eikonal Equation using finite difference upwind gradient operators which take into account the direction of flow of information. We employ a mixed-order scheme which uses second order operators provided they respect causality; otherwise, first-order operators are used. For further discussion on the mechanics of the FMM, refer to http://math.berkeley.edu/~sethian.

**2. FMM in layered media
**

We apply the FMM in layered media to track phases comprised of any number of reflected or refracted branches. A regular grid is retained to describe the velocity media, but a locally irregular mesh of triangles suture the regular cells to the nodes of the irregular boundary. A first-order upwind scheme is used within the triangulated domain but elsewhere, a mixed order scheme is used. The figure below illustrates the way interface nodes are sutured to velocity nodes.

A two-stage process is used to track later arrival branches generated by the presence of velocity discontinuities. First, the wavefront is tracked through the medium to the interface until all interface nodes are tagged as alive. Then all velocity nodes are re-tagged as far points and the scheme is reinitiated using the set of interface nodes as the initial narrow band. A refraction branch is obtained by re-initializing the FMM in the adjacent layer; re-initializing the FMM in the same layer results in a reflected branch. The principle is illustrated below.

The method developed above can, in principle,
track phases composed of any number of reflection and refraction events. The
unconditional stability of the original scheme is retained.

For more information about this page or the FMM, please email