diff options
| -rw-r--r-- | figs/fig_generator-times.gplot | 2 | ||||
| -rw-r--r-- | ising_standalone.cpp | 93 | ||||
| -rw-r--r-- | monte-carlo.bib | 74 | ||||
| -rw-r--r-- | monte-carlo.tex | 149 |
4 files changed, 241 insertions, 77 deletions
diff --git a/figs/fig_generator-times.gplot b/figs/fig_generator-times.gplot index 57e7036..57d1a5a 100644 --- a/figs/fig_generator-times.gplot +++ b/figs/fig_generator-times.gplot @@ -14,7 +14,7 @@ set rmargin 0.05 set lmargin 5.5 set xlabel '$|H|$' -set ylabel "$\\avg{s_{\\text{\\sc 1c}}}\\tau$" offset 2, 0 +set ylabel "$\\avg{s_{\\text{\\sc 1c}}}L^{-D}\\tau$" offset 2, 0 set xrange [0.00000008:3000] set yrange [40:3000] diff --git a/ising_standalone.cpp b/ising_standalone.cpp new file mode 100644 index 0000000..14c39e7 --- /dev/null +++ b/ising_standalone.cpp @@ -0,0 +1,93 @@ +#include <iostream> +#include <chrono> + +#include <wolff.hpp> + +using namespace wolff; + +class ising_t { + public: + int s; + + ising_t() : s(1) {}; + ising_t(int i) : s(i) {}; + + ising_t act(const ising_t& x) const { + return ising_t(s * x.s); + } + + ising_t act_inverse(const ising_t& x) const { + return this->act(x); + } +}; + +class measure_clusters : public measurement<ising_t, ising_t> { + private: + v_t C; + + public: + double Ctotal; + + measure_clusters() { Ctotal = 0; } + + void pre_cluster(N_t, N_t, const system<ising_t, ising_t>&, v_t, const ising_t&) { C = 0; } + + void plain_bond_visited(const system<ising_t, ising_t>&, v_t, const ising_t&, v_t, double) {} + + void ghost_bond_visited(const system<ising_t, ising_t>&, v_t, const ising_t&, const ising_t&, double) {} + + void plain_site_transformed(const system<ising_t, ising_t>&, v_t, const ising_t&) { C++; } + + void ghost_site_transformed(const system<ising_t, ising_t>&, const ising_t&) {} + + void post_cluster(N_t, N_t, const system<ising_t, ising_t>&) { Ctotal += C; } +}; + +int main(int argc, char *argv[]) { + // set defaults + N_t N = (N_t)1e3; + D_t D = 2; + L_t L = 128; + double T = 2.26918531421; + double H = 0.01; + + // define the spin-spin coupling + std::function <double(const ising_t&, const ising_t&)> Z = + [](const ising_t& s1, const ising_t& s2) -> double { + return (double)(s1.s * s2.s); + }; + + // define the spin-field coupling + std::function <double(const ising_t&)> B = + [=](const ising_t& s) -> double { + return H * s.s; + }; + + // initialize the lattice + graph G(D, L); + + // initialize the system + system<ising_t, ising_t> S(G, T, Z, B); + + // define function that generates self-inverse rotations + std::function <ising_t(std::mt19937&, const system<ising_t, ising_t>&, v_t)> gen_R = + [] (std::mt19937&, const system<ising_t, ising_t>&, v_t) -> ising_t { + return ising_t(-1); + }; + + // initailze the measurement object + measure_clusters A; + + // initialize the random number generator + auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count(); + std::mt19937 rng{seed}; + + // run wolff N times + S.run_wolff(N, gen_R, A, rng); + + // print results + std::cout << "The average cluster size per site was " << (A.Ctotal / N) / S.nv << ".\n"; + + // exit + return 0; +} diff --git a/monte-carlo.bib b/monte-carlo.bib index 06a713a..0071b74 100644 --- a/monte-carlo.bib +++ b/monte-carlo.bib @@ -631,22 +631,24 @@ random field Ising model and finally of quantum spin glasses.}, file = {APS Snapshot:/home/pants/.zotero/data/storage/GD9PHBAV/RevModPhys.51.html:text/html;Mermin - 1979 - The topological theory of defects in ordered media.pdf:/home/pants/.zotero/data/storage/ZJE9JPN6/Mermin - 1979 - The topological theory of defects in ordered media.pdf:application/pdf} } -@article{ossola_dynamic_2004, - title = {Dynamic critical behavior of the {Swendsen}–{Wang} algorithm for the three-dimensional {Ising} model}, - volume = {691}, - issn = {0550-3213}, - url = {http://www.sciencedirect.com/science/article/pii/S0550321304003098}, - doi = {10.1016/j.nuclphysb.2004.04.026}, - abstract = {We have performed a high-precision Monte Carlo study of the dynamic critical behavior of the Swendsen–Wang algorithm for the three-dimensional Ising model at the critical point. For the dynamic critical exponents associated to the integrated autocorrelation times of the “energy-like” observables, we find zint,N=zint,E=zint,E′=0.459±0.005±0.025, where the first error bar represents statistical error (68\% confidence interval) and the second error bar represents possible systematic error due to corrections to scaling (68\% subjective confidence interval). For the “susceptibility-like” observables, we find zint,M2=zint,S2=0.443±0.005±0.030. For the dynamic critical exponent associated to the exponential autocorrelation time, we find zexp≈0.481. Our data are consistent with the Coddington–Baillie conjecture zSW=β/ν≈0.5183, especially if it is interpreted as referring to zexp.}, +@article{martin-mayor_tethered_2011, + title = {Tethered {Monte} {Carlo}: {Managing} {Rugged} {Free}-{Energy} {Landscapes} with a {Helmholtz}-{Potential} {Formalism}}, + volume = {144}, + issn = {1572-9613}, + shorttitle = {Tethered {Monte} {Carlo}}, + url = {https://doi.org/10.1007/s10955-011-0261-4}, + doi = {10.1007/s10955-011-0261-4}, + abstract = {Tethering methods allow us to perform Monte Carlo simulations in ensembles with conserved quantities. Specifically, one couples a reservoir to the physical magnitude of interest, and studies the statistical ensemble where the total magnitude (system+reservoir) is conserved. The reservoir is actually integrated out, which leaves us with a fluctuation-dissipation formalism that allows us to recover the appropriate Helmholtz effective potential with great accuracy. These methods are demonstrating a remarkable flexibility. In fact, we illustrate two very different applications: hard spheres crystallization and the phase transition of the diluted antiferromagnet in a field (the physical realization of the random field Ising model). The tethered approach holds the promise to transform cartoon drawings of corrugated free-energy landscapes into real computations. Besides, it reduces the algorithmic dynamic slowing-down, probably because the conservation law holds non-locally.}, + language = {en}, number = {3}, urldate = {2018-09-19}, - journal = {Nuclear Physics B}, - author = {Ossola, Giovanni and Sokal, Alan D.}, - month = jul, - year = {2004}, - keywords = {Ising model, Cluster algorithm, Autocorrelation time, Dynamic critical exponent, Monte Carlo, Potts model, Swendsen–Wang algorithm}, - pages = {259--291}, - file = {ScienceDirect Full Text PDF:/home/pants/.zotero/data/storage/MKA8WYZZ/Ossola and Sokal - 2004 - Dynamic critical behavior of the Swendsen–Wang alg.pdf:application/pdf;ScienceDirect Snapshot:/home/pants/.zotero/data/storage/YHGX7CDT/S0550321304003098.html:text/html} + journal = {Journal of Statistical Physics}, + author = {Martin-Mayor, V. and Seoane, B. and Yllanes, D.}, + month = aug, + year = {2011}, + keywords = {Effective potential, Monte Carlo methods, Barriers}, + pages = {554--596}, + file = {Martin-Mayor et al. - 2011 - Tethered Monte Carlo Managing Rugged Free-Energy .pdf:/home/pants/.zotero/data/storage/HEICZ4EE/Martin-Mayor et al. - 2011 - Tethered Monte Carlo Managing Rugged Free-Energy .pdf:application/pdf} } @article{martin-mayor_cluster_2009, @@ -665,24 +667,22 @@ random field Ising model and finally of quantum spin glasses.}, file = {APS Snapshot:/home/pants/.zotero/data/storage/2USVICMH/PhysRevE.80.html:text/html;Martin-Mayor and Yllanes - 2009 - Cluster Monte Carlo algorithm with a conserved ord.pdf:/home/pants/.zotero/data/storage/7G4SJC85/Martin-Mayor and Yllanes - 2009 - Cluster Monte Carlo algorithm with a conserved ord.pdf:application/pdf} } -@article{martin-mayor_tethered_2011, - title = {Tethered {Monte} {Carlo}: {Managing} {Rugged} {Free}-{Energy} {Landscapes} with a {Helmholtz}-{Potential} {Formalism}}, - volume = {144}, - issn = {1572-9613}, - shorttitle = {Tethered {Monte} {Carlo}}, - url = {https://doi.org/10.1007/s10955-011-0261-4}, - doi = {10.1007/s10955-011-0261-4}, - abstract = {Tethering methods allow us to perform Monte Carlo simulations in ensembles with conserved quantities. Specifically, one couples a reservoir to the physical magnitude of interest, and studies the statistical ensemble where the total magnitude (system+reservoir) is conserved. The reservoir is actually integrated out, which leaves us with a fluctuation-dissipation formalism that allows us to recover the appropriate Helmholtz effective potential with great accuracy. These methods are demonstrating a remarkable flexibility. In fact, we illustrate two very different applications: hard spheres crystallization and the phase transition of the diluted antiferromagnet in a field (the physical realization of the random field Ising model). The tethered approach holds the promise to transform cartoon drawings of corrugated free-energy landscapes into real computations. Besides, it reduces the algorithmic dynamic slowing-down, probably because the conservation law holds non-locally.}, - language = {en}, +@article{ossola_dynamic_2004, + title = {Dynamic critical behavior of the {Swendsen}–{Wang} algorithm for the three-dimensional {Ising} model}, + volume = {691}, + issn = {0550-3213}, + url = {http://www.sciencedirect.com/science/article/pii/S0550321304003098}, + doi = {10.1016/j.nuclphysb.2004.04.026}, + abstract = {We have performed a high-precision Monte Carlo study of the dynamic critical behavior of the Swendsen–Wang algorithm for the three-dimensional Ising model at the critical point. For the dynamic critical exponents associated to the integrated autocorrelation times of the “energy-like” observables, we find zint,N=zint,E=zint,E′=0.459±0.005±0.025, where the first error bar represents statistical error (68\% confidence interval) and the second error bar represents possible systematic error due to corrections to scaling (68\% subjective confidence interval). For the “susceptibility-like” observables, we find zint,M2=zint,S2=0.443±0.005±0.030. For the dynamic critical exponent associated to the exponential autocorrelation time, we find zexp≈0.481. Our data are consistent with the Coddington–Baillie conjecture zSW=β/ν≈0.5183, especially if it is interpreted as referring to zexp.}, number = {3}, urldate = {2018-09-19}, - journal = {Journal of Statistical Physics}, - author = {Martin-Mayor, V. and Seoane, B. and Yllanes, D.}, - month = aug, - year = {2011}, - keywords = {Effective potential, Monte Carlo methods, Barriers}, - pages = {554--596}, - file = {Martin-Mayor et al. - 2011 - Tethered Monte Carlo Managing Rugged Free-Energy .pdf:/home/pants/.zotero/data/storage/HEICZ4EE/Martin-Mayor et al. - 2011 - Tethered Monte Carlo Managing Rugged Free-Energy .pdf:application/pdf} + journal = {Nuclear Physics B}, + author = {Ossola, Giovanni and Sokal, Alan D.}, + month = jul, + year = {2004}, + keywords = {Ising model, Cluster algorithm, Autocorrelation time, Dynamic critical exponent, Monte Carlo, Potts model, Swendsen–Wang algorithm}, + pages = {259--291}, + file = {ScienceDirect Full Text PDF:/home/pants/.zotero/data/storage/MKA8WYZZ/Ossola and Sokal - 2004 - Dynamic critical behavior of the Swendsen–Wang alg.pdf:application/pdf;ScienceDirect Snapshot:/home/pants/.zotero/data/storage/YHGX7CDT/S0550321304003098.html:text/html} } @article{ala-nissila_numerical_1994, @@ -749,12 +749,13 @@ random field Ising model and finally of quantum spin glasses.}, file = {APS Snapshot:/home/pants/.zotero/data/storage/A8T7IR63/PhysRevLett.56.html:text/html;Dierker et al. - 1986 - Consequences of Bond-Orientational Order on the Ma.pdf:/home/pants/.zotero/data/storage/9XEH86XP/Dierker et al. - 1986 - Consequences of Bond-Orientational Order on the Ma.pdf:application/pdf} } -@misc{bierbaum_ising.js_nodate, +@misc{bierbaum_ising.js_2016, title = {Ising.js}, url = {https://mattbierbaum.github.io/ising.js/}, urldate = {2018-09-25}, author = {Bierbaum, Matthew K.}, - note = {Source: https://github.com/mattbierbaum/ising.js\vphantom{\{}\}} + year = {2016}, + note = {https://github.com/mattbierbaum/ising.js/} } @article{bortz_new_1975, @@ -788,4 +789,13 @@ random field Ising model and finally of quantum spin glasses.}, year = {1991}, pages = {938--946}, file = {APS Snapshot:/home/pants/.zotero/data/storage/NCJ8EBM9/PhysRevB.43.html:text/html;Zhang and Larese - 1991 - Melting of monolayer argon adsorbed on a graphite .pdf:/home/pants/.zotero/data/storage/MZTKK99U/Zhang and Larese - 1991 - Melting of monolayer argon adsorbed on a graphite .pdf:application/pdf} +} + +@misc{kent-dobias_wolff_2018, + title = {Wolff}, + url = {https://git.kent-dobias.com/wolff/}, + abstract = {Efficiently simulate spin models using a generalized Wolff algorithm.}, + author = {Kent-Dobias, Jaron}, + year = {2018}, + note = {https://git.kent-dobias.com/wolff/} }
\ No newline at end of file diff --git a/monte-carlo.tex b/monte-carlo.tex index 584dba9..3d6ed8e 100644 --- a/monte-carlo.tex +++ b/monte-carlo.tex @@ -4,7 +4,8 @@ \documentclass[aps,pre,reprint]{revtex4-1} -\usepackage{amsmath,amssymb,latexsym,mathtools} +\usepackage{amsmath,amssymb,latexsym,mathtools,algorithm,listings} + % uncomment to label only equations that are referenced in the text %\mathtoolsset{showonlyrefs=true} @@ -42,6 +43,9 @@ \frac{\partial\tmp#2}{\partial#3\tmp} } +% C++, but pretty +\def\CXX{C\texttt{++}} + \begin{document} \title{Cluster representations and the Wolff algorithm in arbitrary external fields} @@ -63,7 +67,8 @@ that this extension preserves the scaling of accelerated dynamics in the absence of a field for Ising, Potts, and $\mathrm O(n)$ models and demonstrate the method's use in modelling the presence of novel nonlinear - fields. + fields. We also provide a \CXX\ library for the method's convenient + implementation for arbitrary models. \end{abstract} \maketitle @@ -116,6 +121,12 @@ a `ghost' site coupled to all other sites that takes its values from the collection of spin symmetry transformations of the base model rather than resemble the base spins themselves. +We provide an open-source implementation of this method in the form of a \CXX\ +library, available at \url{https://git.kent-dobias.com/wolff/} +\cite{kent-dobias_wolff_2018}. Use of this library will be described briefly +within, but extensive documentation is also available at +\url{https://doc.kent-dobias.com/wolff/}. + \section{Clusters Without a Field} We will pose the problem in a general way, but several specific examples can @@ -174,10 +185,21 @@ redner_graphical_1998}. 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 the $\mathrm O(2)$ model \cite{jose_renormalization_1977}.} + to the $\mathrm O(2)$ model \cite{jose_renormalization_1977}. All models + listed here have example implementations in the provided \CXX\ library + \cite{kent-dobias_2018_wolff}. + } \label{table:models} \end{table*} +Implementation of a model in the provided library is as simple as defining a +class that represents an element of the state space $X$, with default +constructor (and destructor, if necessary), and a class that represents an +element of the group $R$, with default constructor and member functions that +define the action and inverse action of the class on both states and group +elements. Specific details may be found at +\url{https://doc.kent-dobias.com/wolff/models.html}. + 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 @@ -203,35 +225,48 @@ 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). +Measurements of observables during Monte Carlo in the provided library are +made by the use of hooks, which are member functions of a measurement class +that are run at designated points during the algorithm's execution and are +provided arbitrary information about the internal state of all relevant objects. +A detailed description of these hooks can be found at +\url{https://doc.kent-dobias.com/wolff/measurement.html}. + 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 $m_0$ and add it to the stack. - - \item Select a transformation $r\in R_2$ distributed by $f(r\mid m_0,\set s)$. - Often $f$ is taken as uniform on $R_2$, but it is sufficient for preserving - detailed balance that $f$ be any function of the seed site $m_0$ and - $Z(s,r\cdot s)$ for all $s\in\set s$. The flexibility offered by the - choice of distribution will be useful in situations where the set of spin - states is infinite. - \item While the stack isn't empty, - \begin{enumerate} - \item pop site $m$ from the stack. - \item If site $m$ isn't marked, - \begin{enumerate} - \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(\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$. +in the following way.\\ + +\begin{algorithm}[H] + \begin{enumerate} + \item Pick a random site $m_0$ and add it to the stack. + + \item Select a transformation $r\in R_2$ distributed by $f(r\mid m_0,\set s)$. + Often $f$ is taken as uniform on $R_2$, but it is sufficient for preserving + detailed balance that $f$ be any function of the seed site $m_0$ and + $Z(s,r\cdot s)$ for all $s\in\set s$. The flexibility offered by the + choice of distribution will be useful in situations where the set of spin + states is infinite. + \item While the stack isn't empty, + \begin{enumerate} + \item pop site $m$ from the stack. + \item If site $m$ isn't marked, + \begin{enumerate} + \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(\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} \end{enumerate} - \end{enumerate} -\end{enumerate} + \end{enumerate} + \caption{Wolff} + \label{alg:wolff} +\end{algorithm} + When the stack is exhausted, a cluster of connected spins will have been transformed by the action of $r$. In order for this algorithm to be useful, it must satisfy ergodicity and detailed balance. Ergodicity is satisfied since we @@ -266,6 +301,17 @@ of this dependence for a class of configuration spaces with continuous symmetry groups can be found in \cite{caracciolo_generalized_1991, caracciolo_wolff-type_1993}. +This algorithm can be run on a system using the provided library. To construct +a system, you must provide a graph representing the lattice, a temperature, +the spin coupling function $Z$, and the field coupling function $B$. Once +constructed, cluster flips as described in Alg.~\ref{alg:wolff} can be +performed by directly providing seed sites $m_0$ and transformations $r$, or +many in sequence by providing a function that generates random (appropriately +distributed to preserve detailed balance) transformations $r$. The +construction and use of Wolff systems is described at +\url{https://doc.kent-dobias.com/wolff/system.html}. + + \section{Adding the field} This algorithm relies on the fact that the coupling $\J$ depends only on @@ -379,12 +425,11 @@ are preserved, including correlators with the ghost site exists, we expect this representation to extend it to finite field, all other features of the algorithm held constant. For instance, the average cluster size in the Wolff algorithm is often said to be an estimator for the magnetic -susceptibility in the Ising and Potts models (average sum over $x$-components -in the cluster for the $\mathrm O(n)$), but really what it estimates is the -averaged squared magnetization, which corresponds to the susceptibility when -the average magnetization is zero. At finite field the latter thing is no -longer true, but the correspondence between cluster size (sum of -$x$-components) and the squared magnetization continues to hold (see +susceptibility in the Ising, Potts, and $\mathrm O(n)$ models, but really what +it estimates is the averaged squared magnetization, which corresponds to the +susceptibility when the average magnetization is zero. At finite field the +latter thing is no longer true, but the correspondence between cluster size +and the squared magnetization continues to hold (see \eqref{eq:cluster-size-scaling} and Fig.~\ref{fig:cluster_scaling} below). \section{Examples} @@ -407,8 +452,8 @@ 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}. +\url{https://mattbierbaum.github.io/ising.js} +\cite{bierbaum_ising.js_2016}. \subsection{The XY and other $\mathrm O(n)$ models} \label{sec:examples:on} @@ -436,7 +481,8 @@ 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 state of the +transformed, taking advantage of the freedom to choose the function $f$ in +Alg.~\ref{alg:wolff}. We implement this in the following way. Say that the state of 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 @@ -723,11 +769,12 @@ problem before now. We have taken several disparate extensions of cluster methods to spin models in an external field and generalized them to work for any model of a broad class. The resulting representation involves the introduction of not a ghost -spin, but a ghost transformation. We provided evidence that algorithmic -extensions deriving from this method are the natural way to extend cluster -methods in the presence of a field, in the sense that they appear to reproduce -the scaling of dynamic properties in a field that would be expected from -renormalization group predictions. +spin, but a ghost transformation. We provide a \CXX\ library with example +implementations of all models described here \cite{kent-dobias_wolff_2018}. We +provided evidence that algorithmic extensions deriving from this method are +the natural way to extend cluster methods in the presence of a field, in the +sense that they appear to reproduce the scaling of dynamic properties in a +field that would be expected from renormalization group predictions. In addition to uniting several extensions of cluster methods under a single description, our approach allows the application of fields not possible under @@ -738,13 +785,27 @@ 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} This work was supported by NSF grant NSF DMR-1719490. \end{acknowledgments} -\bibliography{monte-carlo} +\appendix +\section{Example Ising Implementation} + +Provided below is an example implementation of the Ising model using the +provided \CXX\ library. The example is also included with the library source, +along with several other more complicated ones \cite{kent-dobias_wolff_2018}. +The routine defines an Ising class that acts as both spin and symmetry group +and a measurement class that provides simple hooks for computing the average +cluster size. The canonical Ising couplings are defined, a square lattice is +initialized, the Wolff system is initialized, and the algorithm is run for a +designated number of cluster flips. + +\lstset{language=C++, basicstyle=\footnotesize, frame=single} +\lstinputlisting[breaklines]{ising_standalone.cpp} + +\bibliography{monte-carlo} \end{document} |