Identifying clusters is important for modeling various phenomena, including nucleation and growth, micelle formation, and agglomeration. Once clusters are identified, their properties--such as size, location, velocity, shape, and angular momentum--may be compared statistically with experiment. Additionally, cluster identification is important because some models imbue clusters with special properties.
While many clustering algorithms exist, most are unsuitable for massively parallel molecular dynamics simulations, in which clusters must be repeatedly identified to capture cluster dynamics. We therefore propose an efficient parallel algorithm for clustering in large molecular dynamics simulations. Our method relies on cell subdivision of space to reduce the computational time for clustering N molecules from O(N^2) to O(N), and it scales well with processor number. Our method's efficiency will enable studies of nucleation and other phase transformation phenomena in large systems with complex intermolecular potentials to be completely more quickly.