In this paper a new multiscale modeling technique is proposed. It relies on a recently introduced measure-theoretic approach, which allows one to manage the microscopic and the macroscopic scale under a unique framework. In the resulting coupled model the two scales coexist and share information. This way it is possible to perform numerical simulations in which the trajectories and the density of the particles affect each other. Crowd dynamics is the motivating application throughout the paper.

In this paper we present a new algorithm for the solution of Hamilton--Jacobi--Bellman equations related to optimal control problems. The key idea is to divide the domain of computation into subdomains which are shaped by the optimal dynamics of the underlying control problem. This can result in a rather complex geometrical subdivision, but it has the advantage that every subdomain is invariant with respect to the optimal dynamics, and then the solution can be computed independently in each subdomain. The features of this dynamics-dependent domain decomposition can be exploited to speed up the computation and for an efficient parallelization, since the classical transmission conditions at the boundaries of the subdomains can be avoided. For their properties, the subdomains are patches in the sense introduced by Ancona and Bressan [ESAIM Control Optim. Calc. Var., 4 (1999), pp. 445--471]. Several examples in two and three dimensions illustrate the properties of the new method.

We introduce and analyze a fast version of the semi-Lagrangian algorithm for front propagation originally proposed in [M. Falcone, “The minimum time problem and its applications to front propagation,” in Motion by Mean Curvature and Related Topics, A. Visintin and G. Buttazzo, eds., de Gruyter, Berlin, 1994, pp. 70–88]. The new algorithm is obtained using the local definition of the approximate solution typical of semi-Lagrangian schemes and redefining the set of “neighboring nodes” necessary for fast marching schemes. A new proof of convergence is needed since that definition produces a new narrow band centered at the interphase which is larger than the one used in fast marching methods based on finite differences. We show that the new algorithm converges to the viscosity solution of the problem and that its complexity is $O(N \log N_{nb})$, as it is for the fast marching method based on finite difference (N and $N_{nb}$ being, respectively, the total number of nodes and the number of nodes in the narrow band). A new sufficient condition for the convergence of the standard finite difference fast marching method is also given. We present several tests comparing the two algorithms and other fast methods (e.g., fast sweeping) on a series of benchmarks which include the minimum time problem and the shape-from-shading problem.