A variational formulation of the fast marching eikonal solver

Introduction

Traveltime computation is one of the most important tasks in seismic processing (Kirchhoff depth migration and related methods) and modeling. The traveltime field of a fixed source in a heterogeneous medium is governed by the eikonal equation, derived about 150 years ago by Sir William Rowan Hamilton. A direct numerical solution of the eikonal equation has become a popular method of computing traveltimes on regular grids, commonly used in seismic imaging (Podvin and Lecomte, 1991; Vidale, 1990; van Trier and Symes, 1991). A recent contribution to this field is the fast marching level set method, developed by Sethian (1996a) in the general context of level set methods for propagating interfaces (Sethian, 1996b; Osher and Sethian, 1988). Sethian and Popovici (1997) report a successful application of this method in three-dimensional seismic computations. The fast marching method belongs to the family of upwind finite-difference schemes aimed at providing the viscosity solution (Lions, 1982), which corresponds to the first-arrival branch of the traveltime field. The remarkable stability of the method results from a specifically chosen order of finite-difference evaluation. The order selection scheme resembles the expanding wavefronts method of Qin et al. (1992). The fast speed of the method is provided by the heap sorting algorithm, commonly used in Dijkstra's shortest path computation methods (Cormen et al., 1990). A similar idea has been used previously in a slightly different context, in the wavefront tracking algorithm of Cao and Greenhalgh (1994).

In this paper, I address the question of evaluating the fast marching method's applicability to more general situations. I describe a simple interpretation of the algorithm in terms of variational principles (namely, Fermat's principle in the case of eikonal solvers.) Such an interpretation immediately yields a useful extension of the method for unstructured grids: triangulations in two dimensions and tetrahedron tesselations in three dimensions. It also provides a constructive way of applying similar algorithms to solving other eikonal-like equations: anisotropic eikonal (Dellinger, 1991), ``focusing'' eikonal (Biondi et al., 1997), kinematic offset continuation (Fomel, 1995), and kinematic velocity continuation (Fomel, 1996). Additionally, the variational formulation can give us hints about higher-order enhancements to the original first-order scheme.

A variational formulation of the fast marching eikonal solver