Ordered upwind methods for static Hamilton-Jacobi equations

We introduce a family of fast ordered upwind methods for approximating solu tions to a wide class of static Hamilton-Jacobi equations with Dirichlet bo undary conditions. Standard techniques often rely on iteration to converge to the solution of a discretized version of the partial differential equati on. Our fast methods avoid iteration through a careful use of information a bout the characteristic directions of the underlying partial differential e quation. These techniques are of complexity O(M log M), where M is the tota l number of points in the domain. We consider anisotropic test problems in optimal control, seismology, and paths on surfaces.