REDUCING THE TIME-COMPLEXITY OF HYBRID MONTE-CARLO SIMULATION THROUGHRANDOMIZED SELECTION

Hybrid Monte Carlo provides an efficient means of sampling from the ca nonical ensemble, by using dynamical methods to propose transition sta tes, and accepting these states based on Metropolis acceptance rules. The dynamical methods reduce the random walk associated with pure Mont e Carlo, while the acceptance rules ensure the accuracy of the simulat ion. In this article, the dynamics of hybrid Monte Carlo are modified by the introduction of randomized selection, where only subsets of par ticles are updated each dynamics timestep. Randomized selection is a g eneral technique inspired from the area of randomized algorithms that could be ostensibly applied to any area of simulation model execution. Our simulation focus will be targeted toward Hamiltonian systems. It is shown that randomized selection can improve the efficiency of the s imulation, provided there is coupling between the Hamiltonian degrees of freedom. For a system of strongly coupled harmonic oscillators, the efficiency is seen to increase by up to 150%. Even in the case of a w eakly-coupled system of Lennard-Jones particles, there is an increase in efficiency of up to 25%. This indicates that randomized selection c an be used effectively not only on systems with short-range potentials , but also on those with long-range (for example, Coulombic) interacti ons.