Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

The Eikonal equation is a special type of Hamilton-Jacobi equation that appears very often in optimal control, geometric optics and many other applications. The equation is nonlinear and only admits a unique viscosity solution in general. In this talk I will discuss a very efficient iterative scheme for solving Eikonal equations: the fast sweeping method. An upwind scheme is used to discretize the partial differential equation which results in a large non-linear system. The key idea is to use Gauss-Seidel iterations with alternating sweeping directions to solve this non-linear system so that the causality along all characteristics are followed in a parallel way. The algorithm is optimal in the sense that the complexity is linear. I will show convergence and order of accuracy of the algorithm. In particular a "condition number", which determines the maximum number of iterations needed, will be computed explicitly from the equation. I will then talk about applications of this fast algorithm to the analysis and visualization of large data sets of unorganized points using the distance function and distance contours. At the end I will show some recent results on computing multiple arrival times from the Eikonal equations in geometric optics.