Dual geometric worm algorithm for two-dimensional discrete classical lattice models

We present a dual geometrical worm algorithm for two-dimensional Ising models. The existence of such dual algorithms was first pointed out by Prokof’ev and Svistunov [N. Prokof’ev and B. Svistunov, Phys. Rev. Lett. 87, 160601 (2001)]. The algorithm is defined on the dual lattice and is formulated in terms of bond variables and can therefore be generalized to other two-dimensional models that can be formulated in terms of bond variables. We also discuss two related algorithms formulated on the direct lattice, applicable in any dimension. These latter algorithms turn out to be less efficient but of considerable intrinsic interest. We show how such algorithms quite generally can be “directed” by minimizing the probability for the worms to erase themselves. Explicit proofs of detailed balance are given for all the algorithms. In terms of computational efficiency the dual geometrical worm algorithm is comparable to well known cluster algorithms such as the Swendsen-Wang and Wolff algorithms, however, it is quite different in structure and allows for a very simple and efficient implementation. The dual algorithm also allows for a very elegant way of calculating the domain wall free energy.

Figure 1

An example of the configuration of the neighbors for algorithm A,B. The current site, $s_i$, is indicated by $•$, the neighbors by $\circ$. The activation (weight) at the current site will depend on the spins at the nearest neighbor sites (shaded circles).

Figure 2

Autocorrelation functions for the energy $C_E\left(t\right)$ as a function of Monte Carlo time, calculated at $T_c$. Shown are results for $L=10$ for the Metropolis, Swendsen-Wang and for the linear worm (A) and directed linear worm (B) algorithms (with uniform worm length). Note that in order to compare the four algorithms the time axis has been scaled so that in all cases one time step corresponds to an attempted update of all the variables. The autocorrelation functions shown were calculated averaging over 20 million worms (MCS for the metropolis algorithm).

Figure 3

A worm moving through the dual lattice. The direct lattice is indicated by solid lines and the spins on the direct lattice by solid circles. The dual lattice is indicated by dashed lines and the sites on the dual lattice by open circles. As the worm moves through the lattice the bond variables are flipped as indicated by the thick bonds in the figure.

Figure 4

An illegal worm move. The worm winds around the lattice in the vertical direction and correspondingly all rows have an odd number of flipped bond variables $b$. The direct lattice is indicated by solid lines and the spins on the direct lattice by solid circles. The dual lattice is indicated by dashed lines and the sites on the dual lattice by open circles. As the worm moves through the lattice the bond variables are flipped as indicated by the thick bonds in the figure.

Figure 5

The notation used for the proof of the dual worm algorithm. The configuration shown corresponds to a worm (solid line) partly erased by its corresponding antiworm (dashed line).

Figure 6

Autocorrelation functions for the energy $C_E\left(t\right)$ as a function of Monte Carlo time, calculated at $T_c$. Shown are results for $L=10,20$ for the Metropolis, dual worm and dual directed worm algorithms. Note that, in order to compare the three algorithms the time axis has been scaled so that in all cases one time step corresponds to an attempted update of all the variables. The inset shows the scaling of the autocorrelation time ${\tau }^{\prime }$ as a function of the system size for the dual worm and dual directed worm algorithm. The autocorrelation time is here rescaled: ${\tau }^{\prime }=\tau ⟨\mathrm{W}⟩∕\left(2L^2\right)$. In both cases we find roughly a power-law form ${\tau }^{\prime }\simeq L^{0.46}$ shown as the solid lines in the inset. The autocorrelation functions shown were calculated averaging over $10–20$ million worms (MCS for the metropolis algorithm).