A bounding box search algorithm for DEM simulation

In Discrete Element Method (DEM) simulations, the most costly operation performed by the program in terms of CPU time is often the process of identifying which pairs of particles are potentially in contact. Program performance can especially be degraded when the relative size difference between the smallest and largest discrete elements is greater than a factor of 2 to 5. Recently, particle-based searches with a hierarchy of cell spaces were proposed to eliminate the size-dependence problem (Peters et al. (2009) 1]), He et al. (2007) 2]. Both methods allowed the cell size to be based on the diameter of the smallest particles, and the methods were found to be effective. In this paper, the authors evaluate the performance of a related but simpler algorithm dubbed the ‘bounding box search method’. The bounding box method entails identifying all cells which any part of a target particle may occupy, listing the target particle as present in those cells, and searching for potential contacts over the same set of cells (the ‘bounding box’). Where the hierarchy methods improve performance by creating multiple cell spaces based on particle sizes, the bounding box method uses only a single cell space, but allows the cell size to be based on the smallest particles, rather than the largest. To evaluate the performance of the bounding box algorithm, timed simulations were performed on systems with varying numbers of particles and particle size distributions, and runtimes were compared to identical systems simulated using a so-called ‘basic’ search algorithm, which places a target particle in a single cell and searches over all neighboring cells. Results presented herein show the bounding box approach to yield improved performance relative to the simple search method for most systems, especially those with the largest numbers of particles and least uniform size distributions. The effect of selected cell size is also examined, and it is shown that cell sizes between one and two times the smallest particle diameter yielded the best performance.