Ordered upwind methods for static Hamilton-Jacobi equations: Theory and algorithms

We develop a family of fast methods for approximating the solutions to a wide class of static Hamilton-Jacobi PDEs; these fast methods include both semi-Lagrangian and fully Eulerian versions. Numerical solutions to these problems are typically obtained by solving large systems of coupled nonlinear discretized equations. Our techniques, which we refer to as "Ordered Upwind Methods" (OUMs), use partial information about the characteristic directions to decouple these nonlinear systems, greatly reducing the computational labor. Our techniques are considered in the context of control-theoretic and front-propagation problems. We begin by discussing existing OUMs, focusing on those designed for isotropic problems. We then introduce a new class of OUMs which decouple systems for general ( anisotropic) problems. We prove convergence of one such scheme to the viscosity solution of the corresponding Hamilton-Jacobi PDE. Next, we introduce a set of finite-differences methods based on an analysis of the role played by anisotropy in the context of front propagation and optimal trajectory problems. The performance of the methods is analyzed, and computational experiments are performed using test problems from computational geometry and seismology.