A second-order fast marching eikonal solver

Next: Accuracy Up: Rickett & Fomel: Second-order Previous: Introduction

Fast marching and the eikonal equation

Under a high frequency approximation, propagating wavefronts may be described by the eikonal equation,
 (1)

where is the traveltime, is the slowness, and , and represent the spatial Cartesian coordinates.

The fast marching method solves equation (1) by directly mimicking the advancing wavefront. Every point on the computational grid is classified into three groups: points behind the wavefront, whose traveltimes are known and fixed; points on the wavefront, whose traveltimes have been calculated, but are not yet fixed; and points ahead of the wavefront. The algorithm then proceeds as follows:

1. Choose the point on the wavefront with the smallest traveltime.
2. Fix this traveltime.
3. Advance the wavefront, so that this point is behind it, and adjacent points are either on the wavefront or behind it.
4. Update traveltimes for adjacent points on the wavefront by solving equation (1) numerically.
5. Repeat until every point is behind the wavefront.

The update procedure (step 4.) requires the solution of the following quadratic equation for ,

 (2)

where is a backward difference operator at grid point, , is a forward operator, and finite-difference operators in and are defined similarly. The roots of the quadratic equation, , can be calculated explicitly as
 (3)

Solving equation (2) amounts to accumulating coefficients , and from its non-zero terms, and evaluating with equation (3).

If we choose a two-point finite-difference operator, such as

 (4) (5)

where , and . Coefficients , and can now be calculated from , , and , where the summation index, , refers to the six terms in equation (2) subject to the various min/max conditions.

This two-point stencil, however, is only accurate to first-order. If instead we choose a suitable three-point finite-difference stencil, we may expect the method to have second-order accuracy. For example, the second-order upwind stencil,

 (6) (7)

Coefficients, , and can be accumulated from , and as before, and if the traveltime, is not available, first-order values may be substituted.

 A second-order fast marching eikonal solver

Next: Accuracy Up: Rickett & Fomel: Second-order Previous: Introduction

2013-03-03