diff options
| -rw-r--r-- | monte-carlo.bib | 85 | ||||
| -rw-r--r-- | monte-carlo.pdf | bin | 189179 -> 193213 bytes | |||
| -rw-r--r-- | monte-carlo.tex | 120 |
3 files changed, 149 insertions, 56 deletions
diff --git a/monte-carlo.bib b/monte-carlo.bib index a624861..4629ce5 100644 --- a/monte-carlo.bib +++ b/monte-carlo.bib @@ -327,6 +327,56 @@ file = {ScienceDirect Full Text PDF:/home/pants/.zotero/data/storage/QD7P2N8S/Dimitrović et al. - 1991 - Finite-size effects, goldstone bosons and critical.pdf:application/pdf;ScienceDirect Snapshot:/home/pants/.zotero/data/storage/H5G2N432/055032139190167V.html:text/html} } +@article{chayes_graphical_1998, + title = {Graphical {Representations} for {Ising} {Systems} in {External} {Fields}}, + volume = {93}, + issn = {0022-4715, 1572-9613}, + url = {https://link.springer.com/article/10.1023/B:JOSS.0000026726.43558.80}, + doi = {10.1023/B:JOSS.0000026726.43558.80}, + abstract = {A graphical representation based on duplication is developed that is suitable for the study of Ising systems in external fields. Two independent replicas of the Ising system in the same field are treated as a single four-state (Ashkin–Teller) model. Bonds in the graphical representation connect the Ashkin–Teller spins. For ferromagnetic systems it is proved that ordering is characterized by percolation in this representation. The representation leads immediately to cluster algorithms; some applications along these lines are discussed.}, + language = {en}, + number = {1-2}, + urldate = {2018-04-12}, + journal = {Journal of Statistical Physics}, + author = {Chayes, L. and Machta, J. and Redner, O.}, + month = oct, + year = {1998}, + pages = {17--32}, + file = {Full Text PDF:/home/pants/.zotero/data/storage/JG5PWZTG/Chayes et al. - 1998 - Graphical Representations for Ising Systems in Ext.pdf:application/pdf;Snapshot:/home/pants/.zotero/data/storage/P9ILGDUH/BJOSS.0000026726.43558.html:text/html} +} + +@article{machta_replica-exchange_2000, + title = {Replica-exchange algorithm and results for the three-dimensional random field {Ising} model}, + volume = {62}, + url = {https://link.aps.org/doi/10.1103/PhysRevE.62.8782}, + doi = {10.1103/PhysRevE.62.8782}, + abstract = {The random field Ising model with Gaussian disorder is studied using a different Monte Carlo algorithm. The algorithm combines the advantages of the replica-exchange method and the two-replica cluster method and is much more efficient than the Metropolis algorithm for some disorder realizations. Three-dimensional systems of size 243 are studied. Each realization of disorder is simulated at a value of temperature and uniform field that is adjusted to the phase-transition region for that disorder realization. Energy and magnetization distributions show large variations from one realization of disorder to another. For some realizations of disorder there are three well separated peaks in the magnetization distribution and two well separated peaks in the energy distribution suggesting a first-order transition.}, + number = {6}, + urldate = {2018-04-12}, + journal = {Physical Review E}, + author = {Machta, J. and Newman, M. E. J. and Chayes, L. B.}, + month = dec, + year = {2000}, + pages = {8782--8789}, + file = {APS Snapshot:/home/pants/.zotero/data/storage/UIKCMAUG/PhysRevE.62.html:text/html;Machta et al. - 2000 - Replica-exchange algorithm and results for the thr.pdf:/home/pants/.zotero/data/storage/6LTIQN3L/Machta et al. - 2000 - Replica-exchange algorithm and results for the thr.pdf:application/pdf} +} + +@article{redner_graphical_1998, + title = {Graphical representations and cluster algorithms for critical points with fields}, + volume = {58}, + url = {https://link.aps.org/doi/10.1103/PhysRevE.58.2749}, + doi = {10.1103/PhysRevE.58.2749}, + abstract = {A two-replica graphical representation and associated cluster algorithm are described that are applicable to ferromagnetic Ising systems with arbitrary fields. Critical points are associated with the percolation threshold of the graphical representation. Results from numerical simulations of the Ising model in a staggered field are presented. For this case, the dynamic exponent for the algorithm is measured to be less than 0.5.}, + number = {3}, + urldate = {2018-04-12}, + journal = {Physical Review E}, + author = {Redner, O. and Machta, J. and Chayes, L. F.}, + month = sep, + year = {1998}, + pages = {2749--2752}, + file = {APS Snapshot:/home/pants/.zotero/data/storage/Q5RL6Q8U/PhysRevE.58.html:text/html;Redner et al. - 1998 - Graphical representations and cluster algorithms f.pdf:/home/pants/.zotero/data/storage/WYEU9G6Y/Redner et al. - 1998 - Graphical representations and cluster algorithms f.pdf:application/pdf} +} + @article{stauffer_scaling_1979, title = {Scaling theory of percolation clusters}, volume = {54}, @@ -442,4 +492,39 @@ year = {1991}, pages = {72--75}, file = {ScienceDirect Full Text PDF:/home/pants/.zotero/data/storage/CADBLAPP/Caracciolo et al. - 1991 - Generalized Wolff-type embedding algorithms for no.pdf:application/pdf;ScienceDirect Snapshot:/home/pants/.zotero/data/storage/XW9KUK53/092056329190883G.html:text/html} +} + +@article{dotsenko_cluster_1991, + title = {Cluster {Monte} {Carlo} algorithms for random {Ising} models}, + volume = {170}, + issn = {0378-4371}, + url = {http://www.sciencedirect.com/science/article/pii/037843719190045E}, + doi = {10.1016/0378-4371(91)90045-E}, + abstract = {Variations of the Swendsen-Wang and Wolff cluster flip algorithms are proposed to perform Monte Carlo simulations of Ising models with random bonds and random fields, including systems with frustration. The new methods are tested by applying them to small lattices and comparing the results with exact data.}, + number = {2}, + urldate = {2018-05-09}, + journal = {Physica A: Statistical Mechanics and its Applications}, + author = {Dotsenko, Vl. S. and Selke, W. and Talapov, A. L.}, + month = jan, + year = {1991}, + pages = {278--281}, + file = {ScienceDirect Full Text PDF:/home/pants/.zotero/data/storage/39ZPGDAE/Dotsenko et al. - 1991 - Cluster Monte Carlo algorithms for random Ising mo.pdf:application/pdf;ScienceDirect Snapshot:/home/pants/.zotero/data/storage/8YGYCZZ8/037843719190045E.html:text/html} +} + +@incollection{rieger_monte_1995, + title = {Monte {Carlo} {Studies} of {Ising} {Spin} {Glasses} and {Random} {Field} {Systems}}, + url = {http://adsabs.harvard.edu/abs/1995arc2.book..295R}, + abstract = {We review recent numerical progress in the study of finite dimensional +strongly disordered magnetic systems like spin glasses and random field +systems. In particular we report in some detail results for the critical +properties and the non-equilibrium dynamics of Ising spin glasses. +Furthermore we present an overview of recent investigations on the +random field Ising model and finally of quantum spin glasses.}, + urldate = {2018-05-09}, + booktitle = {Annual {Reviews} of {Computational} {Physics} {II}. {Edited} by {STAUFFER} {DIETRICH}. {Published} by {World} {Scientific} {Publishing} {Co}. {Pte}. {Ltd}., 1995. {ISBN} \#9789812831149, pp. 295-341}, + author = {Rieger, Heiko}, + year = {1995}, + doi = {10.1142/9789812831149_0007}, + pages = {295--341}, + file = {arXiv\:cond-mat/9411017 PDF:/home/pants/.zotero/data/storage/NTUDS8GH/Rieger - 1995 - Monte Carlo Studies of Ising Spin Glasses and Rand.pdf:application/pdf} }
\ No newline at end of file diff --git a/monte-carlo.pdf b/monte-carlo.pdf Binary files differindex c80b3c2..41b32e6 100644 --- a/monte-carlo.pdf +++ b/monte-carlo.pdf 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}}}$ |