An efficient data structure to solve front propagation problems

In this paper we develop a general efficient sparse storage technique suitable to coding front evolutions in d ≥ 2 space dimensions. This technique is mainly applied here to deal with deterministic target problems with constraints, and solve the associated minimal time problems. To this end we consider an Hamilton-Jacobi-Bellman equation and use an adapted anti-diffusive Ultra-Bee scheme. We obtain a general method which is faster than a full storage technique. We show that we can compute problems that are out of reach by full storage techniques (because of memory). Numerical experiments are provided in dimension d = 2, 3, 4. Moreover, the application of the sparse storage technique to the implementation of the Fast Marching Method for the eikonal equation, in dimensions 2 and 3, is discussed. AMS Classification: 65M06, 49L99