Ordered upwind methods for static Hamilton–Jacobi equations
-
Edited by Alexandre J. Chorin, University of California, Berkeley, CA, and approved June 1, 2001 (received for review May 4, 2001)
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.
Footnotes
-
↵ * To whom reprint requests should be addressed. E-mail: sethian{at}math.berkeley.edu.
-
This paper was submitted directly (Track II) to the PNAS office.
-
See commentary on page 10992.
-
↵ † For the sake of notational clarity, we restrict our discussion to R 2; all results can be restated for R n and for meshes on manifolds.
-
↵ ‡ In ref. 8, the property is proven for the discretization on a uniform Cartesian grid only; the corresponding lemma for triangulated acute meshes is proven in ref. 22. An iterative approach to the corresponding system of discretized equations was earlier used in refs. 3, 11, and 23.
-
↵ § In ref. 10, the property is proven for the first-order discretization on a uniform Cartesian grid; the property for triangulated acute meshes in R 2 and R n is proven in refs. 12 and 13. An iterative approach to the corresponding system of discretized equations on a uniform Cartesian grid was earlier used in ref. 4.
-
↵ ¶ We show that all of the PDEs of the form (Eq. 9) can be produced as Hamilton–Jacobi–Bellman PDEs (Eq. 11) for min-time optimal trajectory problems. We show that the speed functions F and f are related by the homogeneous Legendre transform and that the function f generated from F will satisfy the same inequality 0 < F 1 ≤ f(a, x) ≤ F2 < ∞ for all a and x. The geometric relationship between these two classes of problems is the basis for the alternative (anisotropic) Huyghens' construction using Wulff's shapes. This construction allows one to treat anisotropic front expansion/contraction problems by using the methods for the Hamilton–Jacobi–Bellman PDEs, provided the Hamiltonian H is convex. We note that aspects of these issues have been previously discussed in several specific contexts, including geometric optics (18), geophysics (19) and crystal growth (20).
-
↵ ‖ The algorithm presented in ref. 12 on the manifold-approximating mesh is more efficient for this problem; here, it serves as a convenient test problem for the general anisotropic case: the numerical solution obtained by the Fast Marching Method on the manifold can then be compared to the solution obtained by the “general” method in the x-y plane. We note, of course, that only specific anisotropic problems can be converted into Eikonal equations on manifolds; see ref. 13 for details.
- Abbreviation:
- PDE,
- partial differential equation
- Copyright © 2001, The National Academy of Sciences
