summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--monte-carlo.tex200
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