Numerical Hopf–Lax formulae for Hamilton–Jacobi equations on unstructured geometries

We consider a scheme of Semi-Lagrangian (SL) type for the numerical solution of Hamilton–Jacobi (HJ) equations on unstructured triangular grids. As it is well known, SL schemes are not well suited for unstructured grids, due to the cost of the point location phase; this drawback is augmented by the need for repeated minimization. In this work, we consider an existing, monotone version of the scheme, that works only on the basis of node values, and adapt the algorithm to the case of an unstructured grid, using the connectivity information. Then, applying a quadratic refinement to the numerical solution, we improve accuracy at the price of some extra computational cost. The scheme can be applied to both time-dependent and stationary HJ equations; in the latter case, we also study the construction of a fast policy iteration solver and of a parallel version. We perform a theoretical analysis of the two versions, and validate them with an extensive set of examples, both in the time-dependent and in the stationary case.