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(MlogM) 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.