From 3902c90c737febdd0a501a8762e2ab4e4d1a6513 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Wed, 9 May 2018 17:12:45 -0400 Subject: minor changes --- monte-carlo.tex | 120 ++++++++++++++++++++++++++++++-------------------------- 1 file changed, 64 insertions(+), 56 deletions(-) (limited to 'monte-carlo.tex') diff --git a/monte-carlo.tex b/monte-carlo.tex index bff5ffb..8eef5b0 100644 --- a/monte-carlo.tex +++ b/monte-carlo.tex @@ -88,7 +88,7 @@ \begin{document} -\title{A natural extension of cluster algorithms in arbitrary symmetry-breaking fields} +\title{Accelerating Monte Carlo: Wolff in arbitrary external fields} \author{Jaron Kent-Dobias} \author{James P.~Sethna} \affiliation{Laboratory of Atomic and Solid State Physics, Cornell University, Ithaca, NY, USA} @@ -96,50 +96,54 @@ \date\today \begin{abstract} - We generalize the `ghost spin' representation of spin systems to restore - full symmetry group invariance in an arbitrary external field via the - introduction of a `ghost transformation.' This offers a natural way to - extend celebrated spin-cluster Monte Carlo algorithms to systems in - arbitrary fields by running the ordinary cluster-building process on the new + We introduce a natural way to extend celebrated spin-cluster Monte Carlo + algorithms for fast thermal lattice simulations at criticality, like Wolff, to + systems in arbitrary fields. The method relies on the generalization of the + `ghost spin' representation to one with a `ghost transformation' that + restores invariance to spin symmetries at the cost of an extra degree of + freedom. The ordinary cluster-building process can then be run on the new representation. For several canonical systems, we show that this extension - preserves the scaling of dynamics celebrated in the absence of a field. + preserves the scaling of accelerated dynamics in the absence of a field. \end{abstract} \maketitle -Spin systems are important in the study of statistical physics and phase +Lattice models are important in the study of statistical physics and phase transitions. Rarely exactly solvable, they are typically studied by -approximation and numeric methods. Monte Carlo techniques are a common way of +approximate and numerical methods. Monte Carlo techniques are a common way of doing this, approximating thermodynamic quantities by sampling the 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 for many spin -systems in the absence of symmetry-breaking fields by using nonlocal updates -\cite{janke_nonlocal_1998} whose eponymous clusters undergo a percolation -transition at the critical point of the system \cite{coniglio_clusters_1980} -and result in relatively small dynamic exponents \cite{wolff_comparison_1989, +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 -global rotations of spins. Some success has been made in extending these -algorithms to systems in certain external fields by applying the `ghost site' -representation \cite{coniglio_exact_1989} of certain spin systems that returns +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, but these results only allow the application of a narrow category -of fields \cite{alexandrowicz_swendsen-wang_1989, destri_swendsen-wang_1992, -lauwers_critical_1989, wang_clusters_1989}. We show that the scaling of +of freedom, allowing the method to be used in a subcategory of interesting +fields \cite{alexandrowicz_swendsen-wang_1989, destri_swendsen-wang_1992, +lauwers_critical_1989, wang_clusters_1989}. 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 this 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.' +using cluster methods. Rather than the introduction of a `ghost spin,\!' our +representation relies on introducing a `ghost transformation.\!' -Let $G=(V,E)$ be a graph, where the set of vertices $V=\{1,\ldots,N\}$ +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\}$ enumerates the sites of a lattice and the set of edges $E$ contains pairs of neighboring sites. Let $R$ be a group acting on a set $X$, with the action of group elements $r\in R$ on elements $s\in X$ denoted $r\cdot s$. $X$ is the @@ -168,8 +172,9 @@ and $s,t\in X$, $Z(r\cdot s,r\cdot t)=Z(s,t)$. One may also allow $Z$ 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 -paper hold equally well for these cases, but we will drop the additional index -notation for clarity. +paper (that the algorithm obeys detailed balance and ergodicity) hold equally +well for these cases, but we will drop the additional index notation for +clarity. Statements about efficiency may not. \begin{table*}[htpb] \begin{tabular}{l||ccccc} @@ -191,7 +196,7 @@ notation for clarity. their external fields are also given. Other fields are possible, of course: for instance, some are interested in modulated fields $H\cos(2\pi k\theta(s))$ for integer $k$ and $\theta(s)$ giving the angle of $s$ to some axis applied - to $\mathrm O(n)$ models \cite{jose_renormalization_1977}.} + to the $\mathrm O(2)$ model \cite{jose_renormalization_1977}.} \label{table:models} \end{table*} @@ -254,18 +259,20 @@ to $\vec 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} +%\begin{widetext} \[ - \frac{P(\vec s\to\vec s')}{P(\vec s'\to\vec s)} + \begin{aligned} + &\frac{P(\vec s\to\vec s')}{P(\vec s'\to\vec s)} =\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)} - =\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')}}, +\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 @@ -374,12 +381,10 @@ 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. +Several specific examples from Table~\ref{table:models} are described in the +following. -\section{Examples} - -\subsection{The Ising Model} - -In the Ising model spins are drawn from the set $\{1,-1\}$. Its symmetry group +\emph{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. @@ -389,21 +394,21 @@ just using the `ghost spin' representation. This algorithm has been applied by several researchers \cite{wang_clusters_1989, ray_metastability_1990, destri_swendsen-wang_1992, lauwers_critical_1989}. -\subsection{The $\mathrm O(n)$ Model} - -In the $\mathrm O(n)$ model spins are described by vectors on the +\emph{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 $\pi$ rotations about any axis through the origin. Since the former generate the entire group, reflections alone suffice to provide ergodicity. The `ghost spin' version of the algorithm has been used to apply a simple vector field to -the $\mathrm O(3)$ model \cite{dimitrovic_finite-size_1991}. The method is -quickly generalized to spins whose symmetry groups other compact Lie groups. - -\subsection{The Potts \& Clock Models} - -In both the $q$-state Potts and clock models spins are described by elements +the $\mathrm O(3)$ model \cite{dimitrovic_finite-size_1991}. Other fields of +interest include $(n+1)$-dimensional spherical harmonics +\cite{jose_renormalization_1977} and cubic fields +\cite{bruce_coupled_1975,blankschtein_fluctuation-induced_1982}, which can be +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 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 @@ -414,11 +419,9 @@ on the vertices of a regular polygon that have been numbered $0$ through $q-1$. The elements of $D_q$ of order 2 are all reflections and $r_{q/2}$ if $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. +transitive and therefore the algorithm is ergodic. -\subsection{Roughening Models} - -Though not often thought of as a spin model, roughening of surfaces can be +\emph{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 @@ -431,12 +434,17 @@ of the system. A variant of the algorithm has been applied without a field \cite{evertz_stochastic_1991}. -\section{Dynamic scaling} - 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 considered successful if it likewise extends the efficiency of the Wolff -algorithm into that domain. +algorithm into that domain. Some systems are not efficient under Wolff, and we +don't expect this extension to help them. For instance, Ising models with +random fields or bonds technically can be treated with Wolff +\cite{dotsenko_cluster_1991}, but it is not efficient because the clusters +formed do scale naturally with the correlation length +\cite{rieger_monte_1995,redner_graphical_1998}. Other approaches, like replica methods, should +be relied on instead +\cite{redner_graphical_1998,chayes_graphical_1998,machta_replica-exchange_2000}. At a critical point, correlation time $\tau$ scales with system size $L=N^{-D}$ as $\tau\sim L^z$. Cluster algorithms are celebrated for their @@ -499,10 +507,10 @@ to the scaling functions of the magnetization and susceptibility per site by \begin{aligned} \avg{s_{\text{\sc 1c}}} &=L^{D}\avg{M^2}=\beta\avg\chi+L^{D}\avg{M}^2\\ - &=L^{\gamma/\nu}\big[(hL^{\beta\delta/\nu})^{-\gamma/\beta\delta}\beta \mathcal - Y(hL^{\beta\delta/\nu})\\ - &\hspace{7em}+(hL^{\beta\delta/\nu})^{2/\delta}\mathcal - M(hL^{\beta\delta/\nu})\big]. + &=L^{\gamma/\nu}\big[(hL^{\beta\delta/\nu},ht^{-\beta\delta})^{-\gamma/\beta\delta}\beta \mathcal + Y(hL^{\beta\delta/\nu,ht^{-\beta\delta}})\\ + &\hspace{1em}+(hL^{\beta\delta/\nu},ht^{-\beta\delta})^{2/\delta}\mathcal + M(hL^{\beta\delta/\nu},ht^{-\beta\delta})\big]. \end{aligned} \] We therefore expect that, for the Ising model, $\avg{s_{\text{\sc 1c}}}$ -- cgit v1.2.3-54-g00ecf