ABSTRACT
We introduce a family of fast ordered upwind methods for approximating solutions to a wide class of static Hamilton-Jacobi equations with Dirichlet boundary conditions. Standard techniques often rely on iteration to converge to the solution of a discretized version of the partial differential equation. Our fast methods avoid iteration through a careful use of information about the characteristic directions of the underlying partial differential equation. These techniques are of complexity O(M log M), where M is the total number of points in the domain. We consider anisotropic test problems in optimal control, seismology, and paths on surfaces.
Subject(s)
Algorithms , Mathematics , Models, Theoretical , Surface Properties , ViscosityABSTRACT
The Fast Marching Method is a numerical algorithm for solving the Eikonal equation on a rectangular orthogonal mesh in O(M log M) steps, where M is the total number of grid points. The scheme relies on an upwind finite difference approximation to the gradient and a resulting causality relationship that lends itself to a Dijkstra-like programming approach. In this paper, we discuss several extensions to this technique, including higher order versions on unstructured meshes in Rn and on manifolds and connections to more general static Hamilton-Jacobi equations.
