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.
Copyright. All Rights Reserved.