diff options
| -rw-r--r-- | monte-carlo.tex | 200 |
1 files changed, 119 insertions, 81 deletions
diff --git a/monte-carlo.tex b/monte-carlo.tex index 9456b7a..265e376 100644 --- a/monte-carlo.tex +++ b/monte-carlo.tex @@ -214,6 +214,7 @@ in the following way. stack with probability \[ p_r(s_m,s_j)=\min\{0,1-e^{\beta(\J(r\cdot s_m,s_j)-\J(s_m,s_j))}\}. + \label{eq:bond_probability} \] \item Take $s_m\mapsto r\cdot s_m$. \end{enumerate} @@ -361,18 +362,22 @@ transformation' representation. Several specific examples from Table~\ref{table:models} are described in the following. -\subsection{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. -Since the symmetry group and the spins are described by the same elements, -performing the algorithm on the Ising model in a field is fully described by -just using the `ghost spin' representation. This algorithm or algorithms -based on the same decomposition of the Hamiltonian have been applied -by several researchers \cite{alexandrowicz_swendsen-wang_1989, -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}. +same as the spins themselves. The only nontrivial element is of order two, and +is selected every time in the algorithm. Since the symmetry group and the +spins are described by the same elements, performing the algorithm on the +Ising model in a field is fully described by just using the `ghost spin' +representation. This algorithm or algorithms based on the same decomposition +of the Hamiltonian have been applied by several researchers +\cite{alexandrowicz_swendsen-wang_1989, 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}. \subsection{The $\mathrm O(n)$ model} \label{sec:examples:on} @@ -382,65 +387,99 @@ $(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}. Other fields of +the entire group, reflections alone suffice to provide ergodicity. Sampling +those reflections uniformly works well at criticality. 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}. 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. - -At low temperature or high field, selecting reflections uniformly becomes -inefficient because the excitations of the model are spin waves, in which the -magnetization only differs by a small amount between neighboring spins. Under -these conditions, most choices of reflection plane will cause a change in -energy so great that the whole system is always flipped, resulting in many -highly correlated and inefficiently generated samples. To ameliorate this, one -can draw reflections from a distribution that depends on how the first spin -flip is transformed. We implement this in the following way. Say that the seed -of the cluster is $s$. Generate a vector $t$ taken uniformly from the space of -unit vectors orthogonal to $s$. Let the plane of reflection that whose normal -is $n=s+\zeta t$, where $\zeta$ is drawn from a normal distribution of mean -zero and variance $\sigma$. It follows that the tangent of the angle between -$s$ and the plane of reflection is also distributed normally with zero mean -and variance $\sigma$. Since the distribution of reflection planes only -depends on the angle between $s$ and the plane and that angle is invariant -under the reflection, this choice preserves detailed balance. The choice of -$\sigma$ can be inspired by mean field theory. At high field or low -temperature, spins are likely to both align with the field and each other and -the model is asymptotically equal to a simple Gaussian one, with in the limit -of large $L$ the expected square angle between neighbors being +\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 are +other compact Lie groups \cite{caracciolo_generalized_1991, +caracciolo_wolff-type_1993}. + +At low temperature or high external vector field field selecting reflections +uniformly becomes inefficient because the excitations of the model are spin +waves, in which the magnetization only differs by a small amount between +neighboring spins. Under these conditions, most choices of reflection plane +will cause a change in energy so great that the whole system is always +flipped, resulting in many correlated samples. To ameliorate this, one can +draw reflections from a distribution that depends on how the seed spin is +transformed. We implement this in the following way. Say that the seed of the +cluster is $s$. Generate a vector $t$ taken uniformly from the space of unit +vectors orthogonal to $s$. Let the plane of reflection be that whose normal is +$n=s+\zeta t$, where $\zeta$ is drawn from a normal distribution of mean zero +and variance $\sigma$. It follows that the tangent of the angle between $s$ +and the plane of reflection is also distributed normally with zero mean and +variance $\sigma$. Since the distribution of reflection planes only depends on +the angle between $s$ and the plane, and since that angle is invariant under +the reflection, this choice preserves detailed balance. + +The choice of $\sigma$ can be inspired by mean field theory. At high field or +low temperature, spins are likely to both align with the field and each other +and the model is asymptotically equal to a simple Gaussian one, with in the +limit of large $L$ the expected square angle between neighbors being \[ - \avg{\theta^2}\simeq\frac{(n-1)T}{D+H/2} + \avg{\theta^2}\simeq\frac{(n-1)T}{D+H/2}. \] -We shall in in the numeric experiments of Section \ref{sec:performance} that -this choice ameliorates the problem but probably is not the best. A more -subtle technique---for instance by matching statistics of the effective -Gaussian model that results in these circumstances to the cluster -statistics---may result in better performance. - -\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 -$2\pi n/q$, and the element $s_n$ represents a reflection composed with the -rotation $r_n$. The group acts on spins by permutation: $r_n\cdot m={n+m}\pmod -q$ and $s_n\cdot m={-(n+m)}\pmod q$. This is the natural action of the group -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 and therefore the algorithm is ergodic. - -\subsection{Roughening models} Though not often thought of as a spin model, roughening of surfaces can be +Fig.~\ref{fig:generator_times} shows the effect of making such a choice on +autocorrelation times for a critical \threedee $\mathrm O(2)$ model. At small +fields both methods perform the same as zero field Wolff. Intermediate field +values see efficiency gains for both methods. At large field the uniform +sampling method sees correlation times grow rapidly, while for the sampling +method described here the correlation time crosses over to a constant. A +similar behavior holds for the critical $\mathrm O(3)$ model, though in that +case the constant value the correlation time approaches at large field is +larger than that at zero field (see Fig.~\ref{fig:correlation_time-collapse}). +More detailed discussion on correlation times and these numeric experiments +can be found in section \ref{sec:performance}. + +\begin{figure} + \include{fig_generator-times} + \caption{ + The scaled autocorrelation time of the energy $\H$ for the Wolff algorithm + on a $32\times32\times32$ O(2) model at its critical temperature as a + function of applied vector field magnitude $|H|$. Red points correspond to + reflections sampled uniformly, while the green points represent + reflections sampled as described in section \ref{sec:examples:on}. + } + \label{fig:generator_times} +\end{figure} + +While this approach ameliorates the inefficiency at large field, it is likely +not the best solution. Here we have set the scale of transformation based on +the average difference between nearest neighbors, but cluster methods succeed +because they tend to produce changes on the order of the system's correlation +length. A more nuanced analysis that samples reflections with producing this +behavior in mind may perform much better. + +\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 the $q$-state clock model 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 $2\pi n/q$, and +the element $s_n$ represents a reflection composed with the rotation $r_n$. +The group acts on spins by permutation: $r_n\cdot m={n+m}\pmod q$ and +$s_n\cdot m={-(n+m)}\pmod q$. This is the natural action of the group 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 +and therefore the algorithm is ergodic. + +\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 @@ -448,10 +487,20 @@ $s_i\cdot j=-i-j$. The elements of order two are reflections $s_i$, whose action on $\Z$ is transitive. The coupling can be any function of the absolute difference $|i-j|$. Because random choice of reflection will almost always result in energy changes so large that the whole system is flipped, it is -better to select random reflections about integers or half-integers close to the average state -of the system. A variant of the algorithm has been applied without a field -whose success relies both on this and on using nonzero $q$ -\cite{evertz_stochastic_1991}. +better to select random reflections about integers or half-integers close to +the average state of the system. A variant of the algorithm has been applied +without a field whose success relies both on this and another technique +\cite{evertz_stochastic_1991}. They note that detailed balance is still +satisfied if the bond probabilities \eqref{eq:bond_probability} is modified by +adding a constant $0<x\leq1$ with +\[ + p_r(s_m,s_j\mid x)=\min\{0,1-xe^{\beta(\J(r\cdot s_m,s_j)-\J(s_m,s_j))}\}. +\] +When $x<1$ transformations that do not change the energy of a bond can still +activate it in the cluster, which allows nontrival clusters to be seeded when +the height of the starting site is also the plane of reflection. This +modification is likely useful in general for systems with large yet discrete +configuration spaces $X$. \section{Performance} \label{sec:performance} @@ -556,17 +605,6 @@ conjecture. \label{fig:cluster_scaling} \end{figure*} -\begin{figure} - \include{fig_generator-times} - \caption{ - The scaled correlation time of the Wolff algorithm for a $32\times32$ O(2) - model as a function of applied vector field magnitude $|H|$. The red line - represents reflections sampled from a uniform distribution on $S^1$, - while the green line represents reflections sampled as described in - section \ref{sec:examples:on}. - } -\end{figure} - \section{Applying Nonlinear Fields to the xy Model} This far our numeric work has quantified the performance of existing |