An efficient algorithm for Hamilton–Jacobi equations in high dimension

In this paper we develop a new version of the semi-Lagrangian algorithm for first order Hamilton–Jacobi equations. This implementation is well suited to deal with problems in high dimension, i.e. in Rm with m ≥ 3, which typically arise in the study of control problems and differential games. Our model problem is the evolutive Hamilton–Jacobi equation related to the optimal control finite horizon problem. We will give a step-by-step description of the algorithm focusing our attention on two critical routines: the interpolation in high dimension and the search for the global minimum. We present some numerical results on test problems which range from m = 3 to m = 5 and deal with applications to front propagation, aerospace engineering, ecomomy and biology.