
\documentclass[fleqn,aspectratio=169]{beamer}

\setbeamerfont{frametitle}{family=\bf}
\setbeamerfont{normal text}{family=\rm}
\setbeamertemplate{navigation symbols}{}

\usepackage{textcomp,rotating}

\title{Rejection-free cluster Monte Carlo in arbitrary external fields}
\subtitle{Phys Rev E \textbf{98}, 063306 (2018)}
\author{Jaron Kent-Dobias \and James P Sethna}
\institute{Cornell University}
\date{}

\begin{document}

\def\tr{\mathop{\mathrm{Tr}}\nolimits}

\begin{frame}
  \maketitle
\end{frame}

\begin{frame}
  \frametitle{Monte Carlo is too slow}

  \begin{columns}
    \begin{column}{0.5\textwidth}
      Critical timescales diverge like $L^z$.

      \vspace{2em}

      For 2D Ising local algorithms have $z\simeq2$--4.

      \vspace{2em}

      Cluster methods have $z\simeq0.3$!

      \vspace{2em}



    \end{column}
    \begin{column}{0.5\textwidth}
      \begin{overprint}
        \onslide<1>\includegraphics[width=\columnwidth]{figs/ising_hl_0_0}
        \onslide<2,4>\includegraphics[width=\columnwidth]{figs/ising_hl_0_1}
        \onslide<5>\includegraphics[width=\columnwidth]{figs/ising_hl_0_2}
        \onslide<3,6>\includegraphics[width=\columnwidth]{figs/ising_hl_0_3}
      \end{overprint}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Monte Carlo is too slow}

  Monte Carlo useful for lattice models, but near critical points suffers from \emph{critical slowing down}, power-law divergence of timescales.

  \vspace{1em}

  Often alleviated with cluster algorithms, but many applications lack a clean solution.

  \vspace{1em}

  We introduce a generic, natural, efficient way to extend models with existing cluster algorithms to operate in arbitrary external fields.

  \vspace{1em}

  \begin{enumerate}
    \item Introduction: The Ising Model
      \begin{enumerate}
        \item The Fortuin--Kasteleyn representation \& related algorithm
        \item The ghost spin Hamiltonian \& extension to a field
      \end{enumerate}
    \item Our work: Other lattice models
      \begin{enumerate}
        \item Fortuin--Kasteleyn representations \& algorithms via Ising embeddings
        \item The ghost transformation Hamiltonian \& clusters in arbitrary fields
      \end{enumerate}
  \end{enumerate}

\end{frame}


\begin{frame}
  \frametitle{Introduction: The Ising Model}
  \framesubtitle{The Fortuin--Kasteleyn representation}

  The Ising model
  $
    \mathcal H=-\sum_{\langle ij\rangle}J_{ij}s_is_j
  $
  for $s_i=\pm1$ can be written
  \[
    Z=\tr_se^{-\beta\mathcal H}\propto\tr_f\tr_s\prod_{\langle ij\rangle}\big[\delta_{f_{ij},0}(1-p_{ij})+\delta_{f_{ij},1}\delta_{s_i,s_j}p_{ij}\big]
  \]
  for $f_{ij}\in\{0,1\}$ on the bonds and $p_{ij}=1-e^{-2\beta J_{ij}}$.

  \vspace{1em}

  This gives conditional probabilities 
  \begin{align*}
    P(f_{ij}=1\mid s_i,s_j)=\begin{cases}p_{ij} & s_i=s_j \\ 0 & s_i\neq s_j\end{cases}
    &&
    P(s_i=s_j\mid f)=\begin{cases}1 & \text{$i$, $j$ in same cluster} \\ \frac12 & \text{otherwise}\end{cases}
  \end{align*}
\end{frame}

\begin{frame}
  \frametitle{Introduction: The Ising Model}
  \framesubtitle{From representation to algorithm}

  \begin{columns}
    \begin{column}{0.55\textwidth}
      \begin{overprint}
        \onslide<1-2>\includegraphics[height=0.8\textheight]{figs/ising_fk_0_1}
        \onslide<3>\includegraphics[height=0.8\textheight]{figs/ising_fk_0_2}
        \onslide<4>\includegraphics[height=0.8\textheight]{figs/ising_fk_0_3}
        \onslide<5>\includegraphics[height=0.8\textheight]{figs/ising_fk_0_4}
      \end{overprint}
    \end{column}
    \begin{column}{0.45\textwidth}
      The joint probabilities imply algorithm based on switching back an forth:
      \begin{enumerate}
        \item\alert<2>{Take a spin configuration.}
        \item\alert<3>{Conditionally sample a configuration of bonds.}
        \item\alert<4>{Gather sites connected by bonds into clusters.}
        \item\alert<5>{Conditionally sample a configuration of spins.}
      \end{enumerate}

      \vspace{1em}

    \tiny\raggedleft {Swendsen \& Wang, Phys Rev Lett \textbf{58} (1987) 56.}
    \end{column}
  \end{columns}
\end{frame}
\begin{frame}
  \frametitle{Introduction: The Ising Model}
  \framesubtitle{The ghost spin representation}

  \begin{columns}
    \begin{column}{0.4\textwidth}
      A field means clusters flip with probability that depends on size.

      \vspace{1em}

      But, Fortuin--Kasteleyn doesn't care about lattice topology! Adding a ghost spin coupled to every site with $\tilde J_{0i}=H_i$ gives
      \[
        \begin{aligned}
          \tilde{\mathcal H}&=-\sum_{\langle ij\rangle}J_{ij}s_is_j-s_0\sum_iH_is_i \\
          &=-\sum_{\langle ij\rangle}\tilde J_{ij}s_is_j
        \end{aligned}
      \]
    \end{column}
    \begin{column}{0.6\textwidth}
      \includegraphics[width=\textwidth]{figs/ghost_site}

      \vspace{1em}
      \tiny\raggedleft {Coniglio, de Liberto, Monroy, \& Peruggi. J Phys A: Math Gen \textbf{22} (1989) L837.}
    \end{column}
  \end{columns}
\end{frame}
\begin{frame}
  \frametitle{Introduction: The Ising Model}
  \framesubtitle{The ghost spin algorithm}
  \begin{columns}
    \begin{column}{0.55\textwidth}
      \begin{overprint}
        \onslide<1>\includegraphics[height=0.8\textheight]{figs/ising_fk_h_1}
        \onslide<2>\includegraphics[height=0.8\textheight]{figs/ising_fk_h_2}
        \onslide<3>\includegraphics[height=0.8\textheight]{figs/ising_fk_h_3}
        \onslide<4>\includegraphics[height=0.8\textheight]{figs/ising_fk_h_4}
      \end{overprint}
    \end{column}
    \begin{column}{0.45\textwidth}
      Same algorithm can be run on new Hamiltonian without modification.

      \vspace{1em}

      If the cluster containing $s_0$ is flipped, flip it too!

      \vspace{1em}

      Properties of the original spins must be taken after ``unflipping'' the external field, or $s_0\times s$.

    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Other lattice models}
  \framesubtitle{Fortuin--Kasteleyn via embeddings}

  \begin{columns}
    \begin{column}{0.4\textwidth}
    Cluster methods also known for models whose spins live in more complicated spaces $X$ and have
    \[
      \mathcal H=-\sum_{\langle ij\rangle}Z(s_i,s_j)
    \]
    If $G$ is the symmetry group of the spins, then a self-inverse element $r\in G$ can embed an Ising model
    \[
      J_{ij}(r,s)=\frac12|Z(s_i, s_j)-Z(s_i, r\cdot s_j)|
    \]
    \end{column}
    \begin{column}{0.6\textwidth}
      \centering 
      \begin{tabular}{l|cc}
        & $X$ & $G$ \\
        \hline
        Ising & $\pm1$ & $\mathbb Z/2\mathbb Z$ \\
        $n$-vector & $(n-1)$ sphere & $\mathrm O(n)$ \\
        Potts & $\{1,\ldots,q\}$ & Symmetric \\
        Clock & $\{1,\ldots,q\}$ & Dihedral \\
        Roughening & $\mathbb Z$ & Infinite Dihedral
      \end{tabular}

      \vspace{1em}

      \includegraphics[width=0.9\textwidth]{figs/clocks}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Other lattice models}
  \framesubtitle{From embedding to algorithm\dots again}
  \begin{columns}
    \begin{column}{0.55\textwidth}
      \begin{overprint}
        \onslide<1-2>\includegraphics[height=0.8\textheight]{figs/ising_fks_0_1}
        \onslide<3>\includegraphics[height=0.8\textheight]{figs/ising_fks_0_2}
        \onslide<4>\includegraphics[height=0.8\textheight]{figs/ising_fks_0_3}
        \onslide<5>\includegraphics[height=0.8\textheight]{figs/ising_fks_0_4}
        \onslide<6>\includegraphics[height=0.8\textheight]{figs/ising_fks_0_5}
        \onslide<7>\includegraphics[height=0.8\textheight]{figs/ising_fks_0_6}
        \onslide<8>\includegraphics[height=0.8\textheight]{figs/ising_fks_0_7}
      \end{overprint}
    \end{column}
    \begin{column}{0.45\textwidth}
      \begin{enumerate}
        \item\alert<2>{Take a spin configuration.}
        \item\alert<3>{Draw a self-inverse $r\in G$.}
        \item\alert<4>{Infer Ising $J_{ij}$.}
        \item\alert<5>{Sample bonds as before.}
        \item\alert<6>{Gather sites into clusters.}
        \item\alert<7>{Sample spins by applying $r$ to clusters.}
      \end{enumerate}

      \vspace{1em}

      \tiny\raggedleft{Wolff, Phys Rev Lett \textbf{62} (1989) 361.}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Other lattice models}
  \framesubtitle{The ghost\dots something representation}

  Can we add an external field with a ghost spin as before? Yes, but only for fields whose interaction is like that of another spin.

  \vspace{1em}

  Rules out novel fields like harmonic lattice anisotropies, cubic potentials, around Potts first-order lines, etc.

  \vspace{1em}

  Need to track the full array of transformations that have included the ghost\dots

  \vspace{1em}

  \dots which is precisely what elements of the symmetry group do!
\end{frame}

\begin{frame}
  \frametitle{Other lattice models}
  \framesubtitle{The ghost transformation representation}

  For a lattice model with spins with symmetry group $G$ and
  \[
    \mathcal H=-\sum_{\langle ij\rangle}Z(s_i,s_j)-\sum_iB(s_i)
  \]
  for any function $B$, we introduce a ghost \emph{transformation} $s_0$ and modified Hamiltonian
  \[
    \tilde{\mathcal H}=-\sum_{\langle ij\rangle}Z(s_i,s_j)-\sum_iB(s_0^{-1}\cdot s_i)
    =-\sum_{\langle ij\rangle}\tilde Z(s_i,s_j)
  \]
  for $\tilde Z(s_0,s_i)=B(s_0^{-1}\cdot s_i)$. Both Hamiltonians yields the same statistics for $s_i$ if accumulated transformations are undone first with $s_0^{-1}\cdot s_i$.
\end{frame}

\begin{frame}
  \frametitle{Other lattice models}
  \framesubtitle{Ghost transformation in action}
  \begin{columns}
    \begin{column}{0.55\textwidth}
      \begin{overprint}
        \onslide<1-2>\includegraphics[height=0.8\textheight]{figs/potts_fk_h_1}
        \onslide<3>\includegraphics[height=0.8\textheight]{figs/potts_fk_h_2}
        \onslide<4>\includegraphics[height=0.8\textheight]{figs/potts_fk_h_3}
        \onslide<5>\includegraphics[height=0.8\textheight]{figs/potts_fk_h_4}
        \onslide<6>\includegraphics[height=0.8\textheight]{figs/potts_fk_h_5}
        \onslide<7>\includegraphics[height=0.8\textheight]{figs/potts_fk_h_6}
        \onslide<8>\includegraphics[height=0.8\textheight]{figs/potts_fk_h_7}
      \end{overprint}
    \end{column}
    \begin{column}{0.45\textwidth}
      Example: 5-spin clock model with a field favoring the two states to the bottom right.
      \begin{enumerate}
        \item\alert<2>{Take a spin configuration.}
        \item\alert<3>{Draw a self-inverse $r\in G$.}
        \item\alert<4>{Infer Ising $J_{ij}$.}
        \item\alert<5>{Sample bonds as before.}
        \item\alert<6>{Gather sites into clusters.}
        \item\alert<7>{Sample spins by applying $r$ to clusters.}
      \end{enumerate}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Other lattice models}
  \framesubtitle{The method is good}

  Results generalize to arbitrary bond and site dependence.

  \vspace{0.5em}

  Models already efficient at zero field are more efficient with a field.

  \vspace{0.5em}

  Extension appears natural in the scaling sense.

  \centering

  \includegraphics[width=0.85\textwidth]{figs/timescales}
  
\end{frame}

\begin{frame}
  \frametitle{Summary \& Extensions}

  Introduced a generic method for running cluster Monte Carlo on lattice systems with any external field.
s-
  \vspace{1em}

  Already used to efficiently show relevance/irrelevance of various harmonic perturbations to the XY model.

  \vspace{1em}

  Presently being used to model novel lattice models with coupled spins on sites and bonds which act as effective fields for each other.

  \vspace{1em}

  Currently working on using machine learning techniques to maximize efficiency related to the choice of the distribution of self-inverse group elements, i.e., Ising embeddings.

  \vspace{1em}

  Phys Rev E \textbf{98}, 063306 (2018) or contact Jaron Kent-Dobias (\texttt{jpk247@cornell.edu}).

\end{frame}

\end{document}

