An \({O(}\)\(\mathrm{log}\) \({N})\) Monte Carlo Method for Periodic Coulomb Systems

Abstract.

Efficient Monte Carlo (MC) sampling of many-body systems with long-range electrostatics is often limited by the cost of per-move energy-difference evaluation under periodic boundary conditions. We present DMK-MC, an accelerated MC method that adapts the dual-space multilevel kernel-splitting (DMK) framework to single-particle Metropolis updates. DMK-MC computes the energy change and, on acceptance, updates the stored incoming plane-wave fields with [Formula: see text] work per tree level, yielding an overall [Formula: see text] expected work per trial move for fixed accuracy. The method decomposes the Coulomb kernel into three components: a global, periodized smooth part; a multilevel sequence of smooth difference kernels whose interactions are restricted to same-level colleague boxes; and a singular residual kernel whose short-range interactions are evaluated directly. Benchmarks on uniform, highly nonuniform, and implicit-solvent electrolyte and colloidal configurations show that DMK-MC consistently outperforms a recent fast multipole method–based [Formula: see text] MC method, delivering several-fold speedups at comparable tolerances.

Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/xuanzhaogao/DMK-MC-Benchmark and in the supplementary materials ( DMK-MC-Benchmark-main.zip [6.86MB]). [Formula: see text]