An Efficient Algorithm for Operating on Large Numbers of Aggregate Particles with Applications to Simulating the Dynamics of Irregularly Shaped Grains
Authors: DeMartini Joseph , Richardson Derek 
Published: October 2020

It is believed that many near-Earth asteroids are rubble piles: aggregates of smaller regolith particles bound together by self gravity and cohesive forces, formed from the reaccumulation of much larger, monolithic progenitors after catastrophic collisions [1]. The recent OSIRIS-REx and Hayabusa2 sample-return missions to Bennu and Ryugu, respectively [2, 3], have shown complex and diverse regolith surfaces on rubble piles, with grains spanning from millimeters to tens of meters in radius, evidence of granular flow (slumping), and artifacts such as large surface boulders without surrounding craters (potentially indicating vertical regolith migration).A successful approach to simulating rubble piles is the discrete element method (DEM), which uses individual (typically spherical) particles to represent the constituent blocks of the rubble pile, with particle properties (including friction parameters) chosen to mimic bulk properties of real materials, such as angle of repose. Particles that make up real granular materials, however, are most often not spherical. The shapes of real grains make it more difficult for them to slide past one another, can create quasi-stable equilibria when grains are vertically stacked, and cause the material to &#8220;bulk&#8221; (creating more void space and less efficient packing). These phenomena of real granular materials are not well exhibited by spherical particles, thus the most accurate way to capture a realistic picture of granular dynamics is to use irregularly shaped particles instead of spheres in simulations. The aim of this work is to present a new algorithm for handling simulations using large numbers of irregularly shaped particles with pkdgrav, a DEM code that has been used effectively in the past to model granular dynamics on rubble piles [4, 5, 6, 7], and show that simulating with irregularly shaped grains can lead to results more akin to real granular systems.We construct irregular particles by &#8220;gluing&#8221; spheres together to make bonded (rigid) aggregates. Originally, aggregate routines for pkdgrav were written to handle a few large aggregates made up of many individual particles. In this scheme, aggregate properties are tracked in serial, where a brute force search finds particles belonging to an aggregate then operates on them, searching through every particle on every processor for every aggregate in the simulation. An inefficiency arises when the number of aggregates is similar to the total number of particles (N), as in a simulation of a granular bed made up of small aggregates, each only containing a few particles. Here, the brute force search becomes an &#8764;O(N2) operation. This is prohibitively expensive for processes requiring large N, like granular dynamics simulations.We solved the issue of efficiently locating particles that belong to an aggregate by forcing a reordering of the particles before the search ever occurs, to put them in order of their aggregate index numbers on each processor. We then exploit this particle ordering by replacing the original brute-force search with a binary-search algorithm [8] that scales as O(NlogN) and added a &#8220;cache-line&#8221; method. The binary search is used whenever the particle information is not immediately known, i.e., not in the cache (like the first time a search needs to occur in a simulation). The cache line stores the index of the previously found particle in order to easily step forward and find the next particle that needs to be acted on when the code returns to the function&#8212;this is a linear operation in N (O(N) scaling), so it scales well. Preliminary tests show a 25&#8211;50% decrease in total (wallclock) runtime for moderate resolution simulations using this algorithm overthe original scheme, and expect better performance at higher resolutions.To show the importance of being able to simulate irregularly shaped granular material, we apply our method to an investigation of a scientific application for granular dynamics in low gravity: the Brazil-nut effect. The Brazil-nut effect (BNE) [5, 6, 9] is a mechanism for the vertical migration of boulders in a granular medium that has been suggested as an explanation for exposed boulders on asteroid surfaces. In granular dynamics, the BNE is a method in which frictional interactions between particles in a granular medium cause larger blocks to rise to the surface when the medium is subjected to repeated seismic shaking (like Brazil nuts rising to the top of a shaken jar of mixed nuts).In previous studies with spherical particles, it was shown that increased interparticle friction accounted for a more efficient rise of the large subsurface intruder, but in our preliminary simulations, when simulating with irregular grains, we show that interparticle friction makes the void-filling mechanism less efficient and thus the Brazil nut rises slower. We will explore a broad parameter space in particle size ratio, grain shape, interparticle friction, and interparticle cohesion, to establish how more realistic, irregularly shaped particles exhibit the BNE in low-gravity environments.

Acknowledgments
This work was supported in part by the GEODES grant, number 80NSSC19M0216, awarded by the NASA SSERVI Program. Simulations were carried out at the University of Maryland on the yorp cluster administered by the Department of Astronomy.
&#160;
References
[1] P. Michel, W. Benz, P. Tanga, D. C. Richardson, Science 294 (2001) 1696&#8211;1700.
[2] D. S. Lauretta, D. N. DellaGiustina, C. A. Bennett, et al., Nature 568 (2019) 55&#8211;60.
[3] S. Watanabe, M. Hirabayashi, N. Hirata, et al., Science 364 (2019) 268&#8211;272.2
[4] Y. Yu, D. C. Richardson, P. Michel, S. R. Schwartz, R.-L. Ballouz (2014).arXiv:1408.0168.
[5] S. Matsumura, D. C. Richardson, P. Michel, S. R. Schwartz, R. L. Ballouz, MNRAS 443 (2014) 3368&#8211;3380.arXiv:1407.2748.
[6] C. Maurel, R.-L. Ballouz, D. C. Richardson, P. Michel, S. R. Schwartz, MNRAS 464 (2017) 2866&#8211;2881.
[7] Y. Zhang, D. C. Richardson, et al. (2017).arXiv:1703.01595.
[8] J. L. Bentley, Communications of the ACM 18 (1975) 509&#8211;517.
[9] A. Rosato, K. J. Strandburg, F. Prinz, R. H. Swendsen, Physical Review Letters 58 (1987) 1038&#8211;1040.