Fast, Hierarchical, and Adaptive Algorithm for Metropolis Monte Carlo Simulations of Long-Range Interacting Systems

Abstract

We present a fast, hierarchical, and adaptive algorithm for Metropolis Monte Carlo simulations of systems with long-range interactions that reproduces the dynamics of a standard implementation exactly, i.e., the generated configurations and consequently all measured observables are identical, allowing in particular for nonequilibrium studies. The method is demonstrated for the power-law interacting long-range Ising and XY spin models with nonconserved order parameter and a Lennard-Jones particle system, all in two dimensions. The measured run times support an average complexity O(NlogN), where N is the number of spins or particles. Importantly, prefactors of this scaling behavior are small, which in practice manifests in speedup factors larger than 10^{4}. The method is general and will allow the treatment of large systems that were out of reach before, likely enabling a more detailed understanding of physical phenomena rooted in long-range interactions.