An optimal scheme for simulations of colliding, particle-laden flows on unstructured grids

The cost of tracking Lagrangian particles in a domain discretized on an unstructured grid can become prohibitively expensive as the number of particles or elements grows. A major part of the cost in these calculations is spent on locating the element that hosts a particle and detecting binary collisions, with the latter traditionally requiring $$ operations, $$ being the number of particles. This paper introduces an optimal search box strategy to significantly reduce the cost of these two operations, ensuring a nearly $$ scaling of the cost of collision detection for large-scale simulations. The particle localization strategy is constructed by obtaining an a priori estimate for the optimal number of search boxes as a function of the number of elements, particles, and time steps. The introduced method is generic, as it must be tuned only once for a given implementation and element type. The optimal number of search boxes for collision detection, although complex in form, can be reasonably approximated as the number of particles. The optimality of our method is shown using three drastically varying geometries.