MC 5158
Speaker
Ian
M.
Mitchell
Department
of
Computer
Science
University
of
British
Columbia
Title
The Monotone Acceptance Ordered Upwind Method (A Causal Algorithm for Minimum Time / Cost Optimal Control) and some Lessons in (Ir)Reproducible Research in Computational Math
Abstract
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.]
This research was undertaken with the best of intentions and a typically rigorous numerical analysis approach. Unfortunately, although the code is available in a zip-file, I doubt I could recreate any of the computational results today without significant effort. In the second half of the talk I will discuss the dangers of the status quo in computational science, and some tools and techniques that can significantly reduce your risk, improve your reproducibility, and in most cases increase your productivity if consistently adopted.
Ian M. Mitchell received a PhD in Scientific Computing and Computational Mathematics from Stanford University in 2002. After spending a year as a postdoc jointly between Berkeley EECS and Stanford CS, Dr. Mitchell joined the faculty in the Department of Computer Science at the University of British Columbia where he is now an associate professor. He is the author of the Toolbox of Level Set Methods, the first publicly available high accuracy implementation of solvers for dynamic implicit surfaces and the time dependent Hamilton-Jacobi equation that works in arbitrary dimension. His research interests include development of algorithms and software for nonlinear differential equations, formal verification, control and planning in cyber-physical and robotic systems, assistive technology and reproducible research.
*This is a joint event Applied Math/Computational Math