diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | fig_clusters_ising2d.eps | 4 | ||||
| -rw-r--r-- | monte-carlo.pdf | bin | 196687 -> 0 bytes | |||
| -rw-r--r-- | monte-carlo.tex | 301 |
4 files changed, 134 insertions, 172 deletions
@@ -1,3 +1,4 @@ +*.pdf *.aux *.log *.bbl diff --git a/fig_clusters_ising2d.eps b/fig_clusters_ising2d.eps index cd2d8a3..6015a4c 100644 --- a/fig_clusters_ising2d.eps +++ b/fig_clusters_ising2d.eps @@ -1,7 +1,7 @@ %!PS-Adobe-2.0 EPSF-2.0 %%Title: fig_clusters_ising2d.tex %%Creator: gnuplot 5.2 patchlevel 2 -%%CreationDate: Thu May 10 20:47:25 2018 +%%CreationDate: Tue May 15 20:44:22 2018 %%DocumentFonts: %%BoundingBox: 50 50 542 252 %%EndComments @@ -441,7 +441,7 @@ SDict begin [ /Creator (gnuplot 5.2 patchlevel 2) % /Producer (gnuplot) % /Keywords () - /CreationDate (Thu May 10 20:47:25 2018) + /CreationDate (Tue May 15 20:44:22 2018) /DOCINFO pdfmark end } ifelse diff --git a/monte-carlo.pdf b/monte-carlo.pdf Binary files differdeleted file mode 100644 index 00f87c8..0000000 --- a/monte-carlo.pdf +++ /dev/null diff --git a/monte-carlo.tex b/monte-carlo.tex index 222d6ed..944e506 100644 --- a/monte-carlo.tex +++ b/monte-carlo.tex @@ -1,62 +1,38 @@ -% % Created by Jaron Kent-Dobias on Thu Apr 20 12:50:56 EDT 2017. % Copyright (c) 2017 Jaron Kent-Dobias. All rights reserved. -% -\documentclass[aps,prl,reprint]{revtex4-1} -\usepackage[utf8]{inputenc} -\usepackage{amsmath,amssymb,latexsym,mathtools,xifthen,upgreek} -\usepackage{algcompatible} -\usepackage{algorithm} +\documentclass[aps,pre,reprint]{revtex4-1} + +\usepackage{amsmath,amssymb,latexsym,mathtools} % uncomment to label only equations that are referenced in the text %\mathtoolsset{showonlyrefs=true} -% I want labels but don't want to type out ``equation'' +% I want equation labels but don't want to type out `equation' \def\[{\begin{equation}} \def\]{\end{equation}} -% math not built-in -\def\arcsinh{\mathop{\mathrm{arcsinh}}\nolimits} -\def\arccosh{\mathop{\mathrm{arccosh}}\nolimits} -\def\ei{\mathop{\mathrm{Ei}}\nolimits} % exponential integral Ei -\def\re{\mathop{\mathrm{Re}}\nolimits} -\def\im{\mathop{\mathrm{Im}}\nolimits} -\def\tr{\mathop{\mathrm{Tr}}\nolimits} -\def\sgn{\mathop{\mathrm{sgn}}\nolimits} -\def\dd{d} % differential -\def\O{O} % big O -\def\o{o} % little O -\def\Z{\mathbb Z} -\def\R{\mathbb R} -\def\G{S} -\def\X{\mathbb X} -\def\inf{\mathrm{inf}} - -% subscript for ``critical'' values, e.g., T_\c -\def\c{\mathrm c} - -% scaling functions -\def\fM{\mathcal M} % magnetization -\def\fX{\mathcal Y} % susceptibility -\def\fF{\mathcal F} % free energy -\def\fiF{\mathcal H} % imaginary free energy -\def\fS{\mathcal S} % surface tension -\def\fG{\mathcal G} % exponential factor - -\def\H{\mathcal H} - -% lattice types -\def\sq{\mathrm{sq}} -\def\tri{\mathrm{tri}} -\def\hex{\mathrm{hex}} +% additional math +\def\tr{\mathop{\mathrm{Tr}}\nolimits} % trace +\def\sgn{\mathop{\mathrm{sgn}}\nolimits} % sign function +\def\dd{d} % differential +\def\Z{\mathbb Z} % integers +\def\R{\mathbb R} % reals + +% physics conventions +\def\c{\mathrm c} % critical label as in T_c +\def\H{\mathcal H} % Hamiltonian +\def\J{Z} % site-site coupling +\def\B{B} % external field +\newcommand\set[1]{\mathbf #1} % collection of N spins +\newcommand\avg[1]{\langle#1\rangle} % ensemble average % dimensions \def\dim{d} -\def\twodee{\textsc{2d} } -\def\threedee{\textsc{3d} } -\def\fourdee{\textsc{4d} } +\def\twodee{\textsc{2\dim} } +\def\threedee{\textsc{3\dim} } +\def\fourdee{\textsc{4\dim} } % fancy partial derivative \newcommand\pd[3][]{ @@ -66,26 +42,6 @@ \frac{\partial\tmp#2}{\partial#3\tmp} } -\newcommand\nn[2]{\langle#1#2\rangle} -\newcommand\avg[1]{\langle#1\rangle} -\newcommand\eavg[1]{\langle#1\rangle_{\mathrm e}} -\newcommand\mavg[1]{\langle#1\rangle_{\mathrm m}} -\def\e{\mathrm e} -\def\m{\mathrm m} -\newcommand\new[1]{\tilde{#1}} - -\renewcommand\vec[1]{\mathbf{#1}} -\newcommand\unit[1]{\hat{\mathbf{#1}}} - -\def\mcmc{\textsc{McMC}} -\def\vsigma{\pmb{\upsigma}} - -% used to reformat display math to fit in two-column ``reprint'' mode -\makeatletter -\newif\ifreprint -\@ifclasswith{revtex4-1}{reprint}{\reprinttrue}{\reprintfalse} -\makeatother - \begin{document} \title{Accelerating Monte Carlo: Wolff in arbitrary external fields} @@ -116,34 +72,36 @@ distribution of systems states. These Monte Carlo algorithms are better the faster they arrive at a statistically independent sample. This typically becomes a problem near critical points, where critical slowing down \cite{wolff_critical_1990} results in power-law divergences of dynamic -timescales. Celebrated cluster algorithms largely addressed this in the absence of symmetry-breaking fields by using nonlocal updates -\cite{janke_nonlocal_1998} whose clusters undergo a percolation -transition at the critical point of the system \cite{coniglio_clusters_1980}. -These result in relatively small dynamic exponents for many spin -systems \cite{wolff_comparison_1989, -du_dynamic_2006, liu_dynamic_2014, wang_cluster_1990}, including the Ising, -$\mathrm O(n)$ \cite{wolff_collective_1989}, and Potts -\cite{swendsen_nonuniversal_1987, baillie_comparison_1991} models. These -algorithms rely on the natural symmetry of the systems in question under -symmetry operations on the spins. Some success has been made in extending these -algorithms to systems in certain external fields by adding a `ghost site' -\cite{coniglio_exact_1989} that returns -global rotation invariance to spin Hamiltonians at the cost of an extra degree -of freedom, allowing the method to be used in a subcategory of interesting -fields \cite{alexandrowicz_swendsen-wang_1989, wang_clusters_1989, ray_metastability_1990}. Static -fields have also been applied by including a separate metropolis or heat bath -update step after cluster formation \cite{destri_swendsen-wang_1992, -lauwers_critical_1989}, and other categories of fields have -been applied using replica methods -\cite{redner_graphical_1998,chayes_graphical_1998,machta_replica-exchange_2000}. We show that the scaling of -correlation time near the critical point of several models suggests that the -`ghost' -approach is a natural one, e.g., that it extends the celebrated scaling of -dynamics in these algorithms at zero field to various non-symmetric -perturbations. We also show, by a redefinition of the spin--spin coupling in a -generic class of spin systems, \emph{arbitrary} external fields can be treated -using cluster methods. Rather than the introduction of a `ghost spin,\!' our -representation relies on introducing a `ghost transformation.\!' +timescales. Celebrated cluster algorithms largely addressed this in the +absence of symmetry-breaking fields by using nonlocal updates +\cite{janke_nonlocal_1998} whose clusters undergo a percolation transition at +the critical point of the system \cite{coniglio_clusters_1980}. These result +in relatively small dynamic exponents for many spin systems +\cite{wolff_comparison_1989, du_dynamic_2006, liu_dynamic_2014, +wang_cluster_1990}, including the Ising, $\mathrm O(n)$ +\cite{wolff_collective_1989}, and Potts \cite{swendsen_nonuniversal_1987, +baillie_comparison_1991} models. These algorithms rely on the natural symmetry +of the systems in question under symmetry operations on the spins. Some +success has been made in extending these algorithms to systems in certain +external fields by adding a `ghost site' \cite{coniglio_exact_1989} that +returns global rotation invariance to spin Hamiltonians at the cost of an +extra degree of freedom, allowing the method to be used in a subcategory of +interesting fields \cite{alexandrowicz_swendsen-wang_1989, wang_clusters_1989, +ray_metastability_1990}. Static fields have also been applied by including a +separate metropolis or heat bath update step after cluster formation +\cite{destri_swendsen-wang_1992, lauwers_critical_1989}, and other categories +of fields have been applied using replica methods +\cite{redner_graphical_1998,chayes_graphical_1998,machta_replica-exchange_2000}. +We show that the scaling of correlation time near the critical point of +several models suggests that the `ghost' approach is a natural one, e.g., that +it extends the celebrated scaling of dynamics in these algorithms at zero +field to various non-symmetric perturbations. We also show, by a redefinition +of the spin--spin coupling in a generic class of spin systems, +\emph{arbitrary} external fields can be treated using cluster methods. Rather +than the introduction of a `ghost spin,\!' our representation relies on +introducing a `ghost transformation.\!' + +\section{Introduction} We will pose the problem in a general way, but several specific examples can be found in Table~\ref{table:models} for concreteness. Let $G=(V,E)$ be a graph, where the set of vertices $V=\{1,\ldots,N\}$ @@ -162,16 +120,16 @@ $X$. This property, while apparently obscure, is shared by any symmetric space group. In fact, all the examples listed here have spins spaces with natural metrics whose symmetry group is their set of isometries. We put one spin at each site of the lattice described by $G$, so that the state of the entire -spin system is described by elements $\vec s\in X\times\cdots\times X=X^N$. +spin system is described by elements $\set s\in X\times\cdots\times X=X^N$. The Hamiltonian of this system is a function $\H:X^N\to\R$ defined by \[ - \H(\vec s)=-\!\!\!\!\sum_{\{i,j\}\in E}\!\!\!\!Z(s_i,s_j)-\sum_{i\in V}B(s_i), + \H(\set s)=-\!\!\!\!\sum_{\{i,j\}\in E}\!\!\!\!\J(s_i,s_j)-\sum_{i\in V}\B(s_i), \] -where $Z:X\times X\to\R$ couples adjacent spins and $B:X\to\R$ is an external -field. $Z$ must be symmetric in its arguments and invariant under the action +where $\J:X\times X\to\R$ couples adjacent spins and $B:X\to\R$ is an external +field. $\J$ must be symmetric in its arguments and invariant under the action of any element of $R$ applied to the entire lattice, that is, for any $r\in R$ -and $s,t\in X$, $Z(r\cdot s,r\cdot t)=Z(s,t)$. One may also allow $Z$ to also +and $s,t\in X$, $\J(r\cdot s,r\cdot t)=\J(s,t)$. One may also allow $\J$ to also be a function of edge---for modelling random-bond, long-range, or anisotropic interactions---or allow $B$ to be a function of site---for applying arbitrary boundary conditions or modelling random fields. The formal results of this @@ -182,16 +140,15 @@ clarity. Statements about efficiency may not. \begin{table*}[htpb] \begin{tabular}{l||ccccc} & Spins ($X$) & Symmetry ($R$) & Action ($g\cdot s$) & - Coupling ($Z(s,t)$) & Common Field ($B(s)$) \\ + Coupling ($\J(s,t)$) & Common Field ($B(s)$) \\ \hline\hline Ising & $\{-1,1\}$ & $\Z/2\Z$ & $0\cdot s\mapsto s$, $1\cdot s\mapsto -s$ & $st$ & $Hs$ \\ $\mathrm O(n)$ & $S^{n-1}$ & $\mathrm O(n)$ & $M\cdot s\mapsto Ms$ & $s^{\mathrm T}t$ & $H^{\mathrm T}s$\\ - Potts & $\mathbb Z/q\mathbb Z$ & $D_n$ & $r_m\cdot s=m+s$, $s_m\cdot - s=-m-s$ & $\delta(s,t)$ & $\sum_mH_m\delta(m,s)$\\ - Clock & $\mathbb Z/q\mathbb Z$ & $D_n$ & $r_m\cdot s=m+s$, $s_m\cdot + Potts & $\{1,\ldots,q\}$ & $\mathrm S_n$ & $(i_1,\ldots,i_q)\cdot s=i_s$ & $\delta(s,t)$ & $\sum_mH_m\delta(m,s)$\\ + Clock & $\Z/q\Z$ & $D_n$ & $r_m\cdot s=m+s$, $s_m\cdot s=-m-s$ & $\cos(2\pi\frac{s-t}q)$ & $\sum_mH_m\cos(2\pi\frac{s-m}q)$\\ - Discrete Gaussian & $\mathbb Z$ & $D_\inf$ & $r_m\cdot s=m+s$, $s_m\cdot s=-m-s$ + \textsc{Dgm} & $\Z$ & $D_{\mathrm{inf}}$ & $r_m\cdot s=m+s$, $s_m\cdot s=-m-s$ & $(s-t)^2$ & $Hs^2$\\ \end{tabular} \caption{Several examples of spin systems and the symmetry groups that act @@ -206,35 +163,38 @@ clarity. Statements about efficiency may not. The goal of statistical mechanics is to compute expectation values of observables $A:X^N\to\R$. Assuming the ergodic hypothesis holds (for systems with broken-symmetry states, it does not), the expected value $\avg A$ of an -observable $A$ is its average over every state $\vec s$ in the configuration +observable $A$ is its average over every state $\set s$ in the configuration space $X^N$ weighted by the Boltzmann probability of that state appearing, or \[ \avg A - =\frac{\int_{X^N}A(\vec s)e^{-\beta\H(\vec s)}\,\dd\mu(\vec s)} - {\int_{X^N}e^{-\beta\H(\vec s)}\,\dd\mu(\vec s)}, + =\frac{\int_{X^N}A(\set s)e^{-\beta\H(\set s)}\,\dd\mu(\set s)} + {\int_{X^N}e^{-\beta\H(\set s)}\,\dd\mu(\set s)}, \] -where for $Y_1\times\cdots\times Y_N=Y\subseteq X^N$ the measure +where for $Y_1\times\cdots\times Y_N=Y\subseteq X^N$ the product measure $\mu(Y)=\mu(Y_1)\cdots\mu(Y_N)$ is the simple extension of the measure on $X$ to a measure on $X^N$. These values are estimated using Monte Carlo techniques -by constructing a finite sequence of states $\{\vec s_1,\ldots,\vec s_M\}$ +by constructing a finite sequence of states $\{\set{s_1},\ldots,\set{s_M}\}$ such that \[ - \avg A\simeq\frac1M\sum_{i=1}^MA(\vec s_i). + \avg A\simeq\frac1M\sum_{i=1}^MA(\set{s_i}). \] Sufficient conditions for this average to converge to $\avg A$ as $M\to\infty$ -are that the process that selects $\vec s_{i+1}$ given the previous states be -Markovian (only depends on $\vec s_i$), ergodic (any state can be accessed), -and obey detailed balance (the ratio of probabilities that $\vec s'$ follows -$\vec s$ and vice versa is equal to the ratio of weights for $\vec s$ and -$\vec s'$ in the ensemble). +are that the process that selects $\set{s_{i+1}}$ given the previous states be +Markovian (only depends on $\set{s_i}$), ergodic (any state can be accessed), +and obey detailed balance (the ratio of probabilities that $\set{s'}$ follows +$\set s$ and vice versa is equal to the ratio of weights for $\set s$ and +$\set{s'}$ in the ensemble). While any of several related cluster algorithms can be described for this system, we will focus on the Wolff algorithm \cite{wolff_collective_1989}. In the absence of an external field, e.g., B(s)=0, the Wolff algorithm proceeds in the following way. \begin{enumerate} - \item Pick a random site and a random rotation $r\in R$ of order two, and add the site to - a stack. + \item Pick a random site $m_0$ and add it to the stack. + + \item Pick a random rotation $r\in R$ of order two from the set of such + rotations with a probability distribution of the form + $P_{m_0}(r)=f(\J(m_0,r\cdot m_0))$. \item While the stack isn't empty, \begin{enumerate} \item pop site $m$ from the stack. @@ -243,9 +203,9 @@ in the following way. \item mark the site. \item For every $j$ such that $\{m,j\}\in E$, add site $j$ to the stack with probability - \[ - p_r(s_m,s_j)=\min\{0,1-e^{\beta(Z(r\cdot s_m,s_j)-Z(s_m,s_j))}\}. - \] + \[ + p_r(s_m,s_j)=\min\{0,1-e^{\beta(\J(r\cdot s_m,s_j)-\J(s_m,s_j))}\}. + \] \item Take $s_m\mapsto r\cdot s_m$. \end{enumerate} \end{enumerate} @@ -257,28 +217,29 @@ have ensured that the subset of elements in $R$ that are order two acts transitively on $K$, e.g., for any $s,t\in X$ there exists $r\in R$ such that $r\cdot s=t$. Since there is a nonzero probability that only one spin is rotated and that spin can be rotated into any state, ergodicity follows. The -probability $P(\vec s\to\vec s')$ that the configuration $\vec s$ is brought -to $\vec s'$ by the flipping of a cluster formed by accepting rotations of +probability $P(\set s\to\set{s'})$ that the configuration $\set s$ is brought +to $\set s'$ by the flipping of a cluster formed by accepting rotations of spins via bonds $C\subseteq E$ and rejecting rotations via bonds $\partial -C\subset E$ is related to the probability of the reverse process $P(\vec -s'\to\vec s)$ by -%\begin{widetext} +C\subset E$ is related to the probability of the reverse process $P(\set{s'}\to\set s)$ by +\begin{widetext} \[ \begin{aligned} - &\frac{P(\vec s\to\vec s')}{P(\vec s'\to\vec s)} - =\prod_{\{i,j\}\in + \frac{P(\set s\to\set{s'})}{P(\set{s'}\to\set s)} + &=\frac{P_{m_0}(r)}{P_{m_0}(r^{-1})}\prod_{\{i,j\}\in C}\frac{p_r(s_i,s_j)}{p_{r^{-1}}(s_i',s_j')}\prod_{\{i,j\}\in\partial C}\frac{1-p_r(s_i,s_j)}{1-p_{r^{-1}}(s'_i,s'_j)}\\ - &\quad=\prod_{\{i,j\}\in\partial - C}e^{\beta(Z(r\cdot s_i,s_j)-Z(s_i,s_j))} - =\frac{p_r(s_i,s_j)}{p_{r}(s_i,s_j)}\frac{e^{-\beta\H(\vec - s)}}{e^{-\beta\H(\vec s')}}, + &=\prod_{\{i,j\}\in\partial + C}e^{\beta(\J(r\cdot s_i,s_j)-\J(s_i,s_j))} + =\frac{p_r(s_i,s_j)}{p_{r}(s_i,s_j)}\frac{e^{-\beta\H(\set + s)}}{e^{-\beta\H(\set{s'})}}, \end{aligned} \] -%\end{widetext} +\end{widetext} whence detailed balance is also satisfied. -This algorithm relies on the fact that the coupling $Z$ depends only on +\section{Adding the field} + +This algorithm relies on the fact that the coupling $\J$ depends only on relative orientation of the spins---global reorientations do not affect the Hamiltonian. The external field $B$ breaks this symmetry. However, it can be restored. Define a new graph $\tilde G=(\tilde V,\tilde E)$, where $\tilde @@ -292,18 +253,18 @@ the configuration space of the new model is $R\times X^N$. We introduce the Hamiltonian $\tilde\H:R\times X^N\to\R$ defined by \[ \begin{aligned} - \tilde\H(s_0,\vec s) - &=-\!\!\!\!\sum_{\{i,j\}\in E}\!\!\!\!Z(s_i,s_j) + \tilde\H(s_0,\set s) + &=-\!\!\!\!\sum_{\{i,j\}\in E}\!\!\!\!\J(s_i,s_j) -\sum_{i\in V}B(s_0^{-1}\cdot s_i)\\ - &=-\!\!\!\!\sum_{\{i,j\}\in\tilde E}\!\!\!\!\tilde Z(s_i,s_j), + &=-\!\!\!\!\sum_{\{i,j\}\in\tilde E}\!\!\!\!\tilde\J(s_i,s_j), \end{aligned} \] -where the new coupling $\tilde Z:(R\cup X)\times(R\cup X)\to\R$ is defined for +where the new coupling $\tilde\J:(R\cup X)\times(R\cup X)\to\R$ is defined for $s,t\in R\cup X$ by \[ - \tilde Z(s,t) = + \tilde\J(s,t) = \begin{cases} - Z(s,t) & \text{if $s,t\in X$} \\ + \J(s,t) & \text{if $s,t\in X$} \\ B(s^{-1}\cdot t) & \text{if $s\in R$} \\ B(t^{-1}\cdot s) & \text{if $t\in R$}. \end{cases} @@ -313,14 +274,14 @@ The modified coupling is invariant under the action of group elements: for any $r,s_0\in R$ and $s\in X$, \[ \begin{aligned} - \tilde Z(rs_0,r\cdot s) + \tilde\J(rs_0,r\cdot s) &=B((rs_0)^{-1}\cdot (r\cdot s))\\ &=B(s_0^{-1}\cdot s) - =\tilde Z(s_0,s) + =\tilde\J(s_0,s) \end{aligned} \] -The invariance of $\tilde Z$ to rotations given other arguments follows from -the invariance properties of $Z$. +The invariance of $\tilde\J$ to rotations given other arguments follows from +the invariance properties of $\J$. We have produced a system incorporating the field function $B$ whose Hamiltonian is invariant under global rotations, but how does it relate to our @@ -328,44 +289,38 @@ old system, whose properties we actually want to measure? If $A:X^N\to\R$ is an observable of the original system, we construct an observable $\tilde A:R\times X^N\to\R$ of the new system defined by \[ - \tilde A(s_0,\vec s)=A(s_0^{-1}\cdot\vec s) + \tilde A(s_0,\set s)=A(s_0^{-1}\cdot\set s) \] whose expectation value in the new system equals that of the original -observable in the old system. First, note that $\tilde\H(1,\vec s)=\H(\vec +observable in the old system. First, note that $\tilde\H(1,\set s)=\H(\set s)$. Since the Hamiltonian is invariant under global rotations, it follows -that for any $g\in R$, $\tilde\H(g,g\cdot\vec s)=\H(\vec s)$. Using the +that for any $g\in R$, $\tilde\H(g,g\cdot\set s)=\H(\set s)$. Using the invariance properties of the measure on $X$ and introducing a measure $\rho$ on $R$, it follows that \[ \begin{aligned} \avg{\tilde A} &=\frac{ - \int_R\int_{X^N}\tilde A(s_0,\vec - s)e^{-\beta\tilde\H(s_0,\vec s)}\,\dd\mu(\vec s)\,\dd\rho(s_0) + \int_R\int_{X^N}\tilde A(s_0,\set + s)e^{-\beta\tilde\H(s_0,\set s)}\,\dd\mu(\set s)\,\dd\rho(s_0) } { - \int_R\int_{X^N}e^{-\beta\tilde\H(s_0,\vec s)}\,\dd\mu(\vec s)\,\dd\rho(s_0) + \int_R\int_{X^N}e^{-\beta\tilde\H(s_0,\set s)}\,\dd\mu(\set s)\,\dd\rho(s_0) }\\ &=\frac{ - \int_R\int_{X^N}A(s_0^{-1}\cdot\vec - s)e^{-\beta\tilde\H(s_0,\vec s)}\,\dd\mu(\vec s)\,\dd\rho(s_0) + \int_R\int_{X^N}A(s_0^{-1}\cdot\set + s)e^{-\beta\tilde\H(s_0,\set s)}\,\dd\mu(\set s)\,\dd\rho(s_0) } { - \int_R\int_{X^N}e^{-\beta\tilde\H(s_0,\vec s)}\,\dd\mu(\vec s)\,\dd\rho(s_0) + \int_R\int_{X^N}e^{-\beta\tilde\H(s_0,\set s)}\,\dd\mu(\set s)\,\dd\rho(s_0) }\\ &=\frac{ - \int_R\int_{X^N}A(\vec - s')e^{-\beta\tilde\H(s_0,s_0\cdot\vec - s')}\dd\mu(s_0\cdot\vec s')\,\dd\rho(s_0) + \int_R\int_{X^N}A(\set{s'})e^{-\beta\tilde\H(s_0,s_0\cdot\set{s'})}\dd\mu(s_0\cdot\set{s'})\,\dd\rho(s_0) } { - \int_R\int_{X^N}e^{-\beta\tilde\H(s_0,s_0\cdot\vec s')}\dd\mu(s_0\cdot\vec - s')\,\dd\rho(s_0) + \int_R\int_{X^N}e^{-\beta\tilde\H(s_0,s_0\cdot\set{s'})}\dd\mu(s_0\cdot\set{s'})\,\dd\rho(s_0) }\\ &=\frac{ \int_R\dd\rho(s_0)}{ - \int_R\dd\rho(s_0)}\frac{\int_{X^N}A(\vec - s')e^{-\beta\H(\vec - s')}\dd\mu(\vec s') -}{\int_{X^N}e^{-\beta\H(\vec s')}\dd\mu(\vec - s') + \int_R\dd\rho(s_0)}\frac{\int_{X^N}A(\set{s'})e^{-\beta\H(\set{s'})}\dd\mu(\set{s'}) + }{\int_{X^N}e^{-\beta\H(\set{s'})}\dd\mu(\set{s'}) } =\avg A. \end{aligned} @@ -377,17 +332,19 @@ following way. \item Initialize a `spin' at that site whose value is a representation of a member of the symmetry group of your ordinary spins. \item Carry out the ordinary Wolff cluster-flip procedure on this new - lattice, substituting $\tilde Z$ as defined in \eqref{eq:new.z} for $Z$. + lattice, substituting $\tilde\J$ as defined in \eqref{eq:new.z} for $\J$. \end{enumerate} Ensemble averages of observables $A$ can then be estimated by sampling the value of $\tilde A$ on the new system. In contrast with the simpler ghost spin representation, this form of the Hamiltonian might be considered the `ghost transformation' representation. +\section{Examples} + Several specific examples from Table~\ref{table:models} are described in the following. -\emph{The Ising model.} In the Ising model spins are drawn from the set $\{1,-1\}$. Its symmetry group +\subsection{The Ising model} In the Ising model spins are drawn from the set $\{1,-1\}$. Its symmetry group is $C_2$, the cyclic group on two elements, which can be conveniently represented by a multiplicative group with elements $\{1,-1\}$, exactly the same as the spins themselves. The only nontrivial element is of order two. @@ -400,7 +357,7 @@ wang_clusters_1989, ray_metastability_1990}. The algorithm has been implemented by one of the authors in an existing interactive Ising simulator at \texttt{https://mattbierbaum.github.io/ising.js} \cite{bierbaum_ising.js_nodate}. -\emph{The $\mathrm O(n)$ model.} In the $\mathrm O(n)$ model spins are described by vectors on the +\subsection{The $\mathrm O(n)$ model} In the $\mathrm O(n)$ model spins are described by vectors on the $(n-1)$-sphere $S^{n-1}$. Its symmetry group is $O(n)$, $n\times n$ orthogonal matrices, which act on the spins by matrix multiplication. The elements of $O(n)$ of order two are reflections about hyperplanes through the origin and @@ -414,7 +371,14 @@ interest include $(n+1)$-dimensional spherical harmonics applied with the new method. The method is quickly generalized to spins whose symmetry groups other compact Lie groups -\emph{The Potts \& clock models.} In both the $q$-state Potts and clock models spins are described by elements +\subsection{The Potts model} In the $q$-state Potts model spins are described +by elements of $\{1,\ldots,q\}$. Its symmetry group is the symmetric group +$\mathrm S_n$ of permutations of its elements. The element $(i_1,\ldots,i_q)$ +takes the spin $s$ to $i_s$. There are potentially many elements of order two, +but the two-element swaps alone are sufficient to both generate the group and +act transitively on $\{1,\ldots,q\}$, providing ergodicity. + +\subsection{Clock models} In both the $q$-state Potts and clock models spins are described by elements of $\Z/q\Z$, the set of integers modulo $q$. Its symmetry group is the dihedral group $D_q=\{r_0,\ldots,r_{q-1},s_0,\ldots,s_{q-1}\}$, the group of symmetries of a regular $q$-gon. The element $r_n$ represents a rotation by @@ -427,7 +391,7 @@ $q$ is even, though the former can generate the latter. While reflections do not necessarily generate the entire group, their action on $\Z/q\Z$ is transitive and therefore the algorithm is ergodic. -\emph{Roughening models.} Though not often thought of as a spin model, roughening of surfaces can be +\subsection{Roughening models} Though not often thought of as a spin model, roughening of surfaces can be described in this framework. Spins are described by integers $\Z$ and their symmetry group is the infinite dihedral group $D_\infty=\{r_i,s_i\mid i\in\Z\}$, whose action on the spin $j\in\Z$ is given by $r_i\cdot j=i+j$ and @@ -439,6 +403,7 @@ better to select random reflections about integers close to the average state of the system. A variant of the algorithm has been applied without a field \cite{evertz_stochastic_1991}. +\section{Performance} No algorithm is worthwhile if it doesn't run efficiently. This algorithm, being an extension of the Wolff algorithm into a new domain, should be @@ -563,11 +528,7 @@ perturbations on spin models can be tested numerically \cite{jose_renormalization_1977, blankschtein_fluctuation-induced_1982, bruce_coupled_1975, manuel_carmona_$n$-component_2000}. -\begin{acknowledgments} -\end{acknowledgments} - \bibliography{monte-carlo} - \end{document} |