1er Symposium canadien en analyse numérique et calcul scientifique
The Monotone Acceptance Ordered Upwind Method: A Causal Algorithm for Minimum Time / Cost Optimal Control
Mitchell, Ian M and Ken Alton
Department of Computer Science, University of British Columbia in Vancouver, Canada

The static or time-independent Hamilton-Jacobi equation -- an example of which is the Eikonal equation -- is a fully degenerate nonlinear elliptic PDE.  The viscosity solution of this PDE is useful in applications such as minimum time or cost optimal path planning or control to a target set.  Fast label setting algorithms are available for approximating the viscosity solution of some classes of these equations; most notably the Fast Marching Method (which is a continuous version of Dijkstra's algorithm for shortest path through a discrete graph) applies to some forms of the Eikonal equation.  The Ordered Upwind Method introduced by Sethian & Vladimirsky [SINUM 2003] expanded the class of equations to which these fast algorithms can be applied.  The Monotone Acceptance Ordered Upwind Method (MAOUM) solves the same class of problems as does Sethian's & Vladimirsky's algorithm, but it does so with a precomputed stencil that can adapt to local grid spacing.  Consequently, MAOUM is able to guarantee that nodes are accepted in order of their value and performs considerably better than the older algorithm when significant grid refinement is used to improve approximation quality for problems with nonsmooth solutions. 

[Alton & Mitchell, J. Scientific Computing, 2012]

Lundi, 17 juin, 10h30
Salle Des Plaines C