Using the k-d Tree Data Structure to Accelerate Monte Carlo Simulations

The k-d tree data structure is implemented in a Monte Carlo (MC) molecular simulation program to accelerate the range search for particles or interaction sites within the cutoff distance when Lennard-Jones and Coulomb interactions are computed. MC simulations are performed for different molecules in various ensembles to assess the efficiency enhancements due to the k-d tree data structure. It is found that the use of k-d trees accelerates significantly simulations for Lennard-Jones particles in the NVT and NVT-Gibbs ensembles and for n-butane and 2,4,6,8,10,12,14,16,18,20,22-undecamethylpentacosane represented by the TraPPE-UA force field in the NpT ensemble. Simulations for TraPPE-UA ethanol in the NpT ensemble and for the rigid TIP4P water model in the Gibbs ensemble gain slightly in efficiency with the k-d tree, whereas simulations for TIP4P water in the NpT ensemble do not benefit from the use of the k-d tree. The speed-up can be attributed to the reduction in the number of distance calculations in the range search from scaling as [Formula: see text] to [Formula: see text]. In addition, these tests suggest that the efficiency gain from the use of the k-d tree data structure depends on the flexibility of the molecular model (requiring configurational-bias MC moves to sample changes in conformation), on the ensemble (with open ensembles requiring special MC moves to aid particle transfers), and on the number of interaction sites per molecule (with compact multisite models not seeing an efficiency gain). Overall, the use of the k-d tree data structure can substantially enhance MC simulation efficiency for a variety of systems, and it will enable simulations for larger system sizes in the future.