Cell-veto Monte Carlo algorithm for long-range systems

We present a rigorous efficient event-chain Monte Carlo algorithm for long-range interacting particle systems. Using a cell-veto scheme within the factorized Metropolis algorithm, we compute each single-particle move with a fixed number of operations. For slowly decaying potentials such as Coulomb interactions, screening line charges allow us to take into account periodic boundary conditions. We discuss the performance of the cell-veto Monte Carlo algorithm for general inverse-power-law potentials, and illustrate how it provides a new outlook on one of the prominent bottlenecks in large-scale atomistic Monte Carlo simulations.

Figure 1

Pairwise factorized Monte Carlo algorithm. Left: The move of the active particle is vetoed by one target particle, so that the necessary consensus (all “Y”) is not reached [see Eq. (2)]. Right: In the cell-veto algorithm, vetos are provisionally solicited on the cell level (between the active cell ${\mathcal{C}}_a$ and the target cell ${\mathcal{C}}_t$) before being confirmed for the active particle, at ${\mathbf{r}}_a\in {\mathcal{C}}_a$ and the target particle, at ${\mathbf{r}}_t\in {\mathcal{C}}_t$. Nearby and surplus particles are treated differently.

Figure 2

Event-chain algorithm for a long-ranged dipolar potential in two dimensions, $\beta U=10{(d/r)}^3$. (a) The active particle takes infinitesimal moves in the $+x$ direction. At time $\mathrm{\Delta }s$, a move is vetoed by particle $t$, at event-time distance ${\mathbf{r}}_{at}$. The vetoing particle $t$ becomes the new active particle and starts to move in the $+x$ direction. (b) Heatmap representation of the particle-event rate $q\left({\mathbf{r}}_{at}\right)$. The active particle is in the center; black corresponds to $q=0$. (c) Probability distributions of the step size $\mathrm{\Delta }s$ taken by the active particle and of particle-event distances $r_{at}$.

Figure 3

(a) Total cell-veto rate $Q_{\text{tot}}$, Eq. (5), for inverse-power-law potentials in $D=2$. The event rate for bare particles diverges as $n\to D-1$ (vertical line) because of the presence of periodic images, while screened event rates stay finite. Solid bullets are the Coulomb system [$n=D-2$; for 2D, $U\left(r\right)\sim -lnr$]. (b) Scaling of $Q_{\text{tot}}$ with system size $N$, for the screened-lattice algorithm (green solid), and for the bare-particle algorithm (purple dashed). The inclined line is $\sim N^{1/2}$.

Figure 4

Periodic particle system with screening line charges. Left: Active and target particles and screening line charge segments in a periodic two-dimensional square box. Right: Folded-out periodic system with image target particles, each of which forms a neutral composite particle together with its screening charge.