中国科学技术大学 Youjin Deng--Home--Notes.pdf

Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Worm Algorithms Youjin Deng Department of Modern Physics University of Science and Technology of China P.R.China November 6 Hefei Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Outline References/Collaborators 1. Youjin Deng, Timothy M. Garoni, and Alan D. Sokal, Dynamic Critical Behavior of the Worm Algorithm for the Ising Model, Phys. Rev. Lett. 99, 110601 (2007). 2. Wei Zhang, Timothy M. Garoni, and Youjin Deng, Simulating the fully-packed loop model on the honeycomb lattice with a worm algorithm, preprint. Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Outline How do we efficiently simulate models near criticality? ◮ Problem: critical slowing-down Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Outline How do we efficiently simulate models near criticality? ◮ Problem: critical slowing-down ◮ The current state-of-the-art: cluster algorithms ◮ ◮ Swendsen & Wang PRL 1987 Use global moves in clever way Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Outline How do we efficiently simulate models near criticality? ◮ Problem: critical slowing-down ◮ The current state-of-the-art: cluster algorithms ◮ ◮ Swendsen & Wang PRL 1987 Use global moves in clever way ◮ More recent idea: worm algorithms Prokof’ev & Svistunov PRL 2001 Enlarge an Eulerian configuration space to include defects ◮ Move the defects via random walk ◮ ◮ Outline Worm algorithms for Ising high-temperature graphs High-temperature expansions, state spaces, worm dynamics . . . Eulerian subgraphs ◮ Fix a finite graph G = (V , E) Worm algorithms for fully-packed loops Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary High-temperature expansions, state spaces, worm dynamics . . . Eulerian subgraphs ◮ Fix a finite graph G = (V , E) ◮ A ⊆ E is Eulerian if every vertex in (V , A) has even degree Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary High-temperature expansions, state spaces, worm dynamics . . . Eulerian subgraphs ◮ Fix a finite graph G = (V , E) ◮ A ⊆ E is Eulerian if every vertex in (V , A) has even degree ◮ The cycle space C(G) = {A ⊆ E : A is Eulerian} Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary High-temperature expansions, state spaces, worm dynamics . . . Eulerian subgraphs ◮ Fix a finite graph G = (V , E) ◮ A ⊆ E is Eulerian if every vertex in (V , A) has even degree ◮ The cycle space C(G) = {A ⊆ E : A is Eulerian} ◮ Consider the Ising model on G ZIsing = X Y σ∈{−1,+1}V ij∈E eβσi σj Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary High-temperature expansions, state spaces, worm dynamics . . . Eulerian subgraphs ◮ Fix a finite graph G = (V , E) ◮ A ⊆ E is Eulerian if every vertex in (V , A) has even degree ◮ The cycle space C(G) = {A ⊆ E : A is Eulerian} ◮ Consider the Ising model on G ZIsing = X Y eβσi σj σ∈{−1,+1}V ij∈E ◮ The high-temperature expansion is   X (tanh β)|A| ZIsing = 2|V | cosh|E| β A∈C(G) Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . State space for worm dynamics ◮ Let ∂A be the set of all vertices with odd degree in (V , A) y x ◮ For distinct x, y ∈ V define Sx,y = {A ⊆ E : ∂A = {x, y }} Sx,x = {A ⊆ E : ∂A = ∅} ◮ In this notation Sx,x = C(G) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . State space for worm dynamics ◮ Let ∂A be the set of all vertices with odd degree in (V , A) y x ◮ For distinct x, y ∈ V define Sx,y = {A ⊆ E : ∂A = {x, y }} Sx,x = {A ⊆ E : ∂A = ∅} ◮ In this notation Sx,x = C(G) ◮ State space of worm algorithm is S = {(A, x, y ) : x, y ∈ V and A ∈ Sx,y } Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . State space for worm dynamics ◮ Let ∂A be the set of all vertices with odd degree in (V , A) y x ◮ For distinct x, y ∈ V define Sx,y = {A ⊆ E : ∂A = {x, y }} Sx,x = {A ⊆ E : ∂A = ∅} ◮ In this notation Sx,x = C(G) ◮ State space of worm algorithm is S = {(A, x, y ) : x, y ∈ V and A ∈ Sx,y } ◮ Assign (A, x, y ) ∈ S probability π(A, x, y ) ∝ dx dy (tanh β)|A| Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Ising susceptibility P ◮ If Z := A∈C(G) w |A| and w := tanh β   ZIsing = 2|V | cosh|E| β Z X Z hσx σy iIsing = w |A| Partition function Two-point function A∈Sx,y Z hM2 iIsing = X A∈S w |A| Magnetization Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Ising susceptibility P ◮ If Z := A∈C(G) w |A| and w := tanh β   ZIsing = 2|V | cosh|E| β Z X Z hσx σy iIsing = w |A| Partition function Two-point function A∈Sx,y Z hM2 iIsing = X w |A| A∈S ◮ If G is translationally invariant then π(A, x, y ) = w |A| /Z V χ Magnetization Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Ising susceptibility P ◮ If Z := A∈C(G) w |A| and w := tanh β   ZIsing = 2|V | cosh|E| β Z X Z hσx σy iIsing = w |A| Partition function Two-point function A∈Sx,y Z hM2 iIsing = X w |A| Magnetization A∈S ◮ If G is translationally invariant then π(A, x, y ) = w |A| /Z V χ ◮ Therefore the observable D0 (A, x, y ) = δx,y satisfies hD0 iπ = 1/χ Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Worm dynamics y x ◮ Start in configuration (A, x, y ) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Worm dynamics y x ◮ Start in configuration (A, x, y ) ◮ Pick x or y Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Worm dynamics y x x′ ◮ Start in configuration (A, x, y ) ◮ Pick x or y ◮ Pick x ′ ∼ x Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Worm dynamics y x x′ ◮ Start in configuration (A, x, y ) ◮ Pick x or y ◮ Pick x ′ ∼ x ◮ Propose (A, x, y ) → (A△xx ′ , x ′ , y ) ◮ If transition removes an edge accept with probability 1 Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Worm dynamics y x x′ ◮ Start in configuration (A, x, y ) ◮ Pick x or y ◮ Pick x ′ ∼ x ◮ Propose (A, x, y ) → (A△xx ′ , x ′ , y ) ◮ If transition removes an edge accept with probability 1 ◮ If transition adds an edge accept with probability w Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Worm dynamics ◮ Start in configuration (A, x, y ) ◮ Pick x or y ◮ Pick x ′ ∼ x ◮ Propose (A, x, y ) → (A△xx ′ , x ′ , y ) ◮ If transition removes an edge accept with probability 1 ◮ If transition adds an edge accept with probability w Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Worm dynamics ◮ Start in configuration (A, x, y ) ◮ Pick x or y ◮ Pick x ′ ∼ x ◮ Propose (A, x, y ) → (A△xx ′ , x ′ , y ) ◮ If transition removes an edge accept with probability 1 ◮ If transition adds an edge accept with probability w Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Worm dynamics ◮ Start in configuration (A, x, y ) ◮ Pick x or y ◮ Pick x ′ ∼ x ◮ Propose (A, x, y ) → (A△xx ′ , x ′ , y ) ◮ If transition removes an edge accept with probability 1 ◮ If transition adds an edge accept with probability w Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Worm dynamics ◮ Start in configuration (A, x, y ) ◮ Pick x or y ◮ Pick x ′ ∼ x ◮ Propose (A, x, y ) → (A△xx ′ , x ′ , y ) ◮ If transition removes an edge accept with probability 1 ◮ If transition adds an edge accept with probability w Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Worm dynamics ◮ Start in configuration (A, x, y ) ◮ Pick x or y ◮ Pick x ′ ∼ x ◮ Propose (A, x, y ) → (A△xx ′ , x ′ , y ) ◮ If transition removes an edge accept with probability 1 ◮ If transition adds an edge accept with probability w Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Worm dynamics ◮ Start in configuration (A, x, y ) ◮ Pick x or y ◮ Pick x ′ ∼ x ◮ Propose (A, x, y ) → (A△xx ′ , x ′ , y ) ◮ If transition removes an edge accept with probability 1 ◮ If transition adds an edge accept with probability w Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Transition matrix ◮ Let G be translationally invariant with degree z ◮ Worm dynamics corresponds to transition matrix P on S 11 P[(A, x, y ) → (A△xx ′ , x ′ , y )] = 2z ◮ ◮ ( 1, xx ′ ∈ A, w, xx ′ ∈ 6 A, And similarly for y moves. . . All other non-diagonal elements of P are zero Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Transition matrix ◮ Let G be translationally invariant with degree z ◮ Worm dynamics corresponds to transition matrix P on S 11 P[(A, x, y ) → (A△xx ′ , x ′ , y )] = 2z ◮ ◮ ( 1, xx ′ ∈ A, w, xx ′ ∈ 6 A, And similarly for y moves. . . All other non-diagonal elements of P are zero Lemma P is in detailed balance with π(A, x, y ) = w |A| /Z V χ ◮ Can estimate χ by running the worm dynamics Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Efficiency ◮ Worm dynamics provide a valid way to compute χ Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Efficiency ◮ Worm dynamics provide a valid way to compute χ ◮ But how efficient is the worm algorithm? Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Efficiency ◮ Worm dynamics provide a valid way to compute χ ◮ But how efficient is the worm algorithm? ◮ How do we measure efficiency anyway? Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops High-temperature expansions, state spaces, worm dynamics . . . Efficiency ◮ Worm dynamics provide a valid way to compute χ ◮ But how efficient is the worm algorithm? ◮ How do we measure efficiency anyway? ◮ Empirically – measuring autocorrelations Summary Outline Worm algorithms for Ising high-temperature graphs Autocorrelations, critical slowing down . . . Markov-chain Monte Carlo ◮ Markov chain State space S, with |S| < ∞ Transition matrix P ◮ Stationary distribution π ◮ ◮ Worm algorithms for fully-packed loops Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Markov-chain Monte Carlo ◮ Markov chain State space S, with |S| < ∞ Transition matrix P ◮ Stationary distribution π ◮ ◮ ◮ Observables (random variables) X , Y , . . . Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Markov-chain Monte Carlo ◮ Markov chain State space S, with |S| < ∞ Transition matrix P ◮ Stationary distribution π ◮ ◮ ◮ Observables (random variables) X , Y , . . . P P P ◮ Simulate Markov chain s0 − → s1 − → s2 − → . . . with st ∈ S Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Markov-chain Monte Carlo ◮ Markov chain State space S, with |S| < ∞ Transition matrix P ◮ Stationary distribution π ◮ ◮ ◮ Observables (random variables) X , Y , . . . P P P ◮ Simulate Markov chain s0 − → s1 − → s2 − → . . . with st ∈ S ◮ Get time series X0 , X1 , X2 , . . . with Xt = X (st ) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Markov-chain Monte Carlo ◮ Markov chain State space S, with |S| < ∞ Transition matrix P ◮ Stationary distribution π ◮ ◮ ◮ Observables (random variables) X , Y , . . . P P P ◮ Simulate Markov chain s0 − → s1 − → s2 − → . . . with st ∈ S ◮ Get time series X0 , X1 , X2 , . . . with Xt = X (st ) ◮ Define the autocorrelation function ρX (t) := hXs Xs+t iπ − hX i2π varπ (X ) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Markov-chain Monte Carlo ◮ Markov chain State space S, with |S| < ∞ Transition matrix P ◮ Stationary distribution π ◮ ◮ ◮ Observables (random variables) X , Y , . . . P P P ◮ Simulate Markov chain s0 − → s1 − → s2 − → . . . with st ∈ S ◮ Get time series X0 , X1 , X2 , . . . with Xt = X (st ) ◮ Define the autocorrelation function ρX (t) := hXs Xs+t iπ − hX i2π varπ (X ) ◮ Stationary process – start “in equilibrium” Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Integrated autocorrelation times ◮ The integrated autocorrelation time ∞ 1 X ρX (t) τint,X := 2 t=−∞ Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Integrated autocorrelation times ◮ The integrated autocorrelation time ∞ 1 X ρX (t) τint,X := 2 t=−∞ b is the sample mean of {Xt }T then we have ◮ If X t=1 b ) ∼ 2 τint,X var(X var(X ) , T T →∞ Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Autocorrelations, critical slowing down . . . Integrated autocorrelation times ◮ The integrated autocorrelation time ∞ 1 X ρX (t) τint,X := 2 t=−∞ b is the sample mean of {Xt }T then we have ◮ If X t=1 b ) ∼ 2 τint,X var(X var(X ) , T T →∞ ◮ 1 “effectively independent” observation every 2 τint,X steps Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Exponential autocorrelation times ◮ ρX (t) typically decays exponentially as t → ∞ ◮ The exponential autocorrelation time τexp,X := lim sup t→∞ t − log |ρX (t)| and τexp := sup τexp,X X Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Exponential autocorrelation times ◮ ρX (t) typically decays exponentially as t → ∞ ◮ The exponential autocorrelation time τexp,X := lim sup t→∞ ◮ t − log |ρX (t)| and τexp := sup τexp,X X Typically τexp,X = τexp < ∞ and τint,X ≤ τexp for all X Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Exponential autocorrelation times ◮ ρX (t) typically decays exponentially as t → ∞ ◮ The exponential autocorrelation time τexp,X := lim sup t→∞ ◮ t − log |ρX (t)| and τexp := sup τexp,X X Typically τexp,X = τexp < ∞ and τint,X ≤ τexp for all X ◮ Start the chain with arbitrary distribution α ◮ Distribution at time t is αP t Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Exponential autocorrelation times ◮ ρX (t) typically decays exponentially as t → ∞ ◮ The exponential autocorrelation time τexp,X := lim sup t→∞ ◮ t − log |ρX (t)| and τexp := sup τexp,X X Typically τexp,X = τexp < ∞ and τint,X ≤ τexp for all X ◮ Start the chain with arbitrary distribution α ◮ Distribution at time t is αP t Lemma αP t tends to π with rate bounded by e−t/τexp Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Critical slowing-down ◮ Near a critical point the autocorrelation times typically diverge like τ ∼ ξz Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Critical slowing-down ◮ Near a critical point the autocorrelation times typically diverge like τ ∼ ξz ◮ More precisely, we have a family of exponents: zexp , and zint,X for each observable X . Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Autocorrelations, critical slowing down . . . Critical slowing-down ◮ Near a critical point the autocorrelation times typically diverge like τ ∼ ξz ◮ More precisely, we have a family of exponents: zexp , and zint,X for each observable X . ◮ Different algorithms for the same model can have very different z ◮ E.g. d = 2 Ising model ◮ ◮ Glauber (Metropolis) algorithm z ≈ 2 Swendsen-Wang algorithm z ≈ 0.2 Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Worm simulations ◮ Simulated the critical square-lattice Ising model Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Worm simulations ◮ Simulated the critical square-lattice Ising model ◮ Focus on two observables: ◮ ◮ N (A, x, y) = |A| D0 (A, x, y) = δx,y ◮ hN i is “energy-like” ◮ hD0 i = 1/χ Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Worm simulations ◮ Simulated the critical square-lattice Ising model ◮ Focus on two observables: ◮ ◮ N (A, x, y) = |A| D0 (A, x, y) = δx,y ◮ hN i is “energy-like” ◮ hD0 i = 1/χ ◮ Measured observables after every hit (worm update) ◮ Natural unit of time is one sweep (Ld hits) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Numerical results Dynamics of N ◮ ρN (t) is almost a perfect exponential ρN (t) 1 8 16 32 64 128 256 512 1024 2048 0.1 ◮ Scaled time by τint,N ◮ Good data collapse suggests zexp ≈ zint,N ◮ Fitting τint,N gives zint,N ≈ 0.379 0.01 0 1 2 3 t/τint,N 4 5 6 ◮ Li-Sokal bound zexp , zint,N ≥ α/ν applies to worm dynamics Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Dynamics of D0 ◮ ρD (t) decays significantly in O(1) hits! 0 0 ρD (t) 1 10 -1 10 -2 10 -3 10 -4 10 -5 10 -6 8 16 32 64 128 256 512 1024 2048 ◮ ρD (t) ∼ t −s with s ≈ 0.75 0 L increases 1 10 2 10 3 4 10 10 5 10 6 10 7 10 t ◮ D0 decorrelates on a totally different time scale to N Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Three dimensions ◮ Qualitatively similar behavior when d = 3: Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Three dimensions ◮ Qualitatively similar behavior when d = 3: ◮ ρD (t) ∼ t −s 0 ◮ s ≈ 0.66 Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Three dimensions ◮ Qualitatively similar behavior when d = 3: ◮ ρD (t) ∼ t −s 0 ◮ s ≈ 0.66 ◮ ρN (t) roughly exponential ◮ zexp ≈ zint,N ≈ α/ν ≈ 0.174 ◮ Li-Sokal bound may be sharp for d = 3 worm algorithm Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Three dimensions ◮ Qualitatively similar behavior when d = 3: ◮ ρD (t) ∼ t −s 0 ◮ s ≈ 0.66 ◮ ρN (t) roughly exponential ◮ zexp ≈ zint,N ≈ α/ν ≈ 0.174 ◮ Li-Sokal bound may be sharp for d = 3 worm algorithm ◮ Compare Swendsen-Wang zSW ≈ 0.46 Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Numerical results Practical efficiency for square/cubic lattice critical Ising ◮ Swendsen-Wang seems to outperform worm when d = 2 Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Numerical results Practical efficiency for square/cubic lattice critical Ising ◮ Swendsen-Wang seems to outperform worm when d = 2 ◮ Efficiency depends on observable, X Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Numerical results Practical efficiency for square/cubic lattice critical Ising ◮ Swendsen-Wang seems to outperform worm when d = 2 ◮ Efficiency depends on observable, X ◮ A simple way to compare worm and SW is to compute b for both algorithms κ = TCPU varX Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Numerical results Practical efficiency for square/cubic lattice critical Ising ◮ Swendsen-Wang seems to outperform worm when d = 2 ◮ Efficiency depends on observable, X ◮ A simple way to compare worm and SW is to compute b for both algorithms κ = TCPU varX ◮ When d = 3 and X = D0 we find κworm /κSW ≈ L−0.33 ◮ With the crossover κworm /κSW ≈ 1 at around L ≈ 20 Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Numerical results Practical efficiency for square/cubic lattice critical Ising ◮ Swendsen-Wang seems to outperform worm when d = 2 ◮ Efficiency depends on observable, X ◮ A simple way to compare worm and SW is to compute b for both algorithms κ = TCPU varX ◮ When d = 3 and X = D0 we find κworm /κSW ≈ L−0.33 ◮ With the crossover κworm /κSW ≈ 1 at around L ≈ 20 ◮ There is also a natural worm estimator for ξ Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Numerical results Practical efficiency for square/cubic lattice critical Ising ◮ Swendsen-Wang seems to outperform worm when d = 2 ◮ Efficiency depends on observable, X ◮ A simple way to compare worm and SW is to compute b for both algorithms κ = TCPU varX ◮ When d = 3 and X = D0 we find κworm /κSW ≈ L−0.33 ◮ With the crossover κworm /κSW ≈ 1 at around L ≈ 20 ◮ There is also a natural worm estimator for ξ ◮ Again SW outperforms worm when d = 2 Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Numerical results Practical efficiency for square/cubic lattice critical Ising ◮ Swendsen-Wang seems to outperform worm when d = 2 ◮ Efficiency depends on observable, X ◮ A simple way to compare worm and SW is to compute b for both algorithms κ = TCPU varX ◮ When d = 3 and X = D0 we find κworm /κSW ≈ L−0.33 ◮ With the crossover κworm /κSW ≈ 1 at around L ≈ 20 ◮ There is also a natural worm estimator for ξ ◮ Again SW outperforms worm when d = 2 ◮ For d = 3 we find κworm /κSW ≈ L−0.32 ◮ With the crossover κworm /κSW ≈ 1 at around L ≈ 45 Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics An alternative perspective on worm dynamics ◮ Our perspective so far: Worm algorithm ⇐⇒ simulate Ising high-temperature graphs Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics An alternative perspective on worm dynamics ◮ Our perspective so far: Worm algorithm ⇐⇒ simulate Ising high-temperature graphs ◮ Eulerian-subgraph model Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics An alternative perspective on worm dynamics ◮ Our perspective so far: Worm algorithm ⇐⇒ simulate Ising high-temperature graphs ◮ Eulerian-subgraph model ◮ State space C(G) Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics An alternative perspective on worm dynamics ◮ Our perspective so far: Worm algorithm ⇐⇒ simulate Ising high-temperature graphs ◮ Eulerian-subgraph model ◮ ◮ State space C(G) P(A) ∝ w |A| Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics An alternative perspective on worm dynamics ◮ Our perspective so far: Worm algorithm ⇐⇒ simulate Ising high-temperature graphs ◮ Eulerian-subgraph model ◮ ◮ State space C(G) P(A) ∝ w |A| ◮ Run a worm simulation Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics An alternative perspective on worm dynamics ◮ Our perspective so far: Worm algorithm ⇐⇒ simulate Ising high-temperature graphs ◮ Eulerian-subgraph model ◮ ◮ State space C(G) P(A) ∝ w |A| ◮ Run a worm simulation ◮ Only observe the chain when A ∈ C(G), i.e. when x = y Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics An alternative perspective on worm dynamics ◮ Our perspective so far: Worm algorithm ⇐⇒ simulate Ising high-temperature graphs ◮ Eulerian-subgraph model ◮ ◮ State space C(G) P(A) ∝ w |A| ◮ Run a worm simulation ◮ Only observe the chain when A ∈ C(G), i.e. when x = y ◮ Obtain a new Markov chain P ◮ Stationary distribution π(A, x, x) ∝ f (x) w |A| Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics An alternative perspective on worm dynamics ◮ Our perspective so far: Worm algorithm ⇐⇒ simulate Ising high-temperature graphs ◮ Eulerian-subgraph model ◮ ◮ State space C(G) P(A) ∝ w |A| ◮ Run a worm simulation ◮ Only observe the chain when A ∈ C(G), i.e. when x = y ◮ Obtain a new Markov chain P ◮ Stationary distribution π(A, x, x) ∝ f (x) w |A| ◮ New perspective: Worm algorithm ⇐⇒ simulate Eulerian-subgraph model Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Loop models ◮ Honeycomb lattice Eulerian subgraphs = disjoint cycles ◮ Nienhuis loop model Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Loop models ◮ Honeycomb lattice Eulerian subgraphs = disjoint cycles ◮ Nienhuis loop model 0 < w < wc Disordered phase wc < w < ∞ Critical densely-packed phase w = +∞ Critical fully-packed phase Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics Loop models ◮ Honeycomb lattice Eulerian subgraphs = disjoint cycles ◮ Nienhuis loop model 0 < w < wc Disordered phase wc < w < ∞ Critical densely-packed phase w = +∞ Critical fully-packed phase + + + − + − + − + − − + ◮ 1 loop config ↔ 2 dual spin configs + ◮ Ising spin domains + + + + + − + − + + + − + + Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics Loop models ◮ Honeycomb lattice Eulerian subgraphs = disjoint cycles ◮ Nienhuis loop model 0 < w < wc Disordered phase wc < w < ∞ Critical densely-packed phase w = +∞ Critical fully-packed phase + + + − + − + − + − − + ◮ 1 loop config ↔ 2 dual spin configs + ◮ Ising spin domains + + + + + − + − + + + − + + ◮ w = e−2β Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics Loop models ◮ Honeycomb lattice Eulerian subgraphs = disjoint cycles ◮ Nienhuis loop model 0 < w < wc Disordered phase wc < w < ∞ Critical densely-packed phase w = +∞ Critical fully-packed phase + + + − + − + − + − − + ◮ 1 loop config ↔ 2 dual spin configs + ◮ Ising spin domains + + + + + − + − + + + − + + ◮ w = e−2β ◮ w >1 =⇒ antiferromagnetic β Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics Loop models ◮ Honeycomb lattice Eulerian subgraphs = disjoint cycles ◮ Nienhuis loop model 0 < w < wc Disordered phase wc < w < ∞ Critical densely-packed phase w = +∞ Critical fully-packed phase + + + − + − + − + − − + ◮ Worm ◮ 1 loop config ↔ 2 dual spin configs + ◮ Ising spin domains + + + + + − + − + + + − + + ◮ w = e−2β ◮ w >1 =⇒ antiferromagnetic β ⇐⇒ simulate dual Ising domain boundaries Outline Worm algorithms for Ising high-temperature graphs An alternate perspective on worm dynamics Fully-packed loop model (FPL) Worm algorithms for fully-packed loops Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Fully-packed loop model (FPL) ◮ FPL ↔ triangular-lattice Ising antiferromagnet at T = 0 Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Fully-packed loop model (FPL) + − + Frustration ◮ FPL ↔ triangular-lattice Ising antiferromagnet at T = 0 ◮ Frustrated systems hard to simulate Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics Fully-packed loop model (FPL) + − + Frustration ◮ FPL ↔ triangular-lattice Ising antiferromagnet at T = 0 ◮ Frustrated systems hard to simulate ◮ Cluster algorithms for frustrated Ising models thought to be non-ergodic at T = 0 Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics Fully-packed loop model (FPL) + − + Frustration ◮ FPL ↔ triangular-lattice Ising antiferromagnet at T = 0 ◮ Frustrated systems hard to simulate ◮ Cluster algorithms for frustrated Ising models thought to be non-ergodic at T = 0 ◮ Can we use worm instead? Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics P∞ has absorbing states ◮ Standard worm transitions for w ≥ 1 on z-regular graph: 1 Pw [(A, x, y ) → (A△xx ′ , x ′ , y )] = 2z ( 1/w 1 xx ′ ∈ A xx ′ 6∈ A Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics P∞ has absorbing states ◮ Standard worm transitions for w ≥ 1 on z-regular graph: 1 Pw [(A, x, y ) → (A△xx ′ , x ′ , y )] = 2z ( 1/w 1 xx ′ ∈ A xx ′ 6∈ A ◮ Identity transitions are fixed by normalization: Pw [(A, x, y ) → (A, x, y )] = (1 − 1/w) dx (A) + dy (A) 2z Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics P∞ has absorbing states ◮ Standard worm transitions for w ≥ 1 on z-regular graph: 1 Pw [(A, x, y ) → (A△xx ′ , x ′ , y )] = 2z ( 1/w 1 xx ′ ∈ A xx ′ 6∈ A ◮ Identity transitions are fixed by normalization: Pw [(A, x, y ) → (A, x, y )] = (1 − 1/w) dx (A) + dy (A) 2z ◮ P∞ [(A, x, y ) → (A, x, y )] = 1 whenever dx (A) = dy (A) = z Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics P∞ has absorbing states ◮ Standard worm transitions for w ≥ 1 on z-regular graph: 1 Pw [(A, x, y ) → (A△xx ′ , x ′ , y )] = 2z ( 1/w 1 xx ′ ∈ A xx ′ 6∈ A ◮ Identity transitions are fixed by normalization: Pw [(A, x, y ) → (A, x, y )] = (1 − 1/w) dx (A) + dy (A) 2z ◮ P∞ [(A, x, y ) → (A, x, y )] = 1 whenever dx (A) = dy (A) = z ◮ Cannot use standard worm algorithm when w = +∞ Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics How do we solve the problem? ◮ P∞ [(A, x, y ) → (A, x, y )] = 1 whenever dx (A) = dy (A) = z Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics How do we solve the problem? ◮ P∞ [(A, x, y ) → (A, x, y )] = 1 whenever dx (A) = dy (A) = z ◮ But on the honeycomb lattice z = 3 Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics How do we solve the problem? ◮ P∞ [(A, x, y ) → (A, x, y )] = 1 whenever dx (A) = dy (A) = z ◮ But on the honeycomb lattice z = 3 ◮ So states with Eulerian A never get stuck Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics How do we solve the problem? ◮ P∞ [(A, x, y ) → (A, x, y )] = 1 whenever dx (A) = dy (A) = z ◮ But on the honeycomb lattice z = 3 ◮ So states with Eulerian A never get stuck ◮ To simulate loop models, we only observe the chain when A is Eulerian. . . Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics How do we solve the problem? ◮ P∞ [(A, x, y ) → (A, x, y )] = 1 whenever dx (A) = dy (A) = z ◮ But on the honeycomb lattice z = 3 ◮ So states with Eulerian A never get stuck ◮ To simulate loop models, we only observe the chain when A is Eulerian. . . ′ such that: ◮ Try defining new transition matrix P∞ Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics How do we solve the problem? ◮ P∞ [(A, x, y ) → (A, x, y )] = 1 whenever dx (A) = dy (A) = z ◮ But on the honeycomb lattice z = 3 ◮ So states with Eulerian A never get stuck ◮ To simulate loop models, we only observe the chain when A is Eulerian. . . ′ such that: ◮ Try defining new transition matrix P∞ ◮ ′ P∞ [(A, x, x) → · ] = limw→∞ Pw [(A, x, x) → · ] Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics How do we solve the problem? ◮ P∞ [(A, x, y ) → (A, x, y )] = 1 whenever dx (A) = dy (A) = z ◮ But on the honeycomb lattice z = 3 ◮ So states with Eulerian A never get stuck ◮ To simulate loop models, we only observe the chain when A is Eulerian. . . ′ such that: ◮ Try defining new transition matrix P∞ ◮ ◮ ′ P∞ [(A, x, x) → · ] = limw→∞ Pw [(A, x, x) → · ] ′ [(A, x, y) → (A, x, y)] = 0 when x 6= y P∞ Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics How do we solve the problem? ◮ P∞ [(A, x, y ) → (A, x, y )] = 1 whenever dx (A) = dy (A) = z ◮ But on the honeycomb lattice z = 3 ◮ So states with Eulerian A never get stuck ◮ To simulate loop models, we only observe the chain when A is Eulerian. . . ′ such that: ◮ Try defining new transition matrix P∞ ◮ ◮ ′ P∞ [(A, x, x) → · ] = limw→∞ Pw [(A, x, x) → · ] ′ [(A, x, y) → (A, x, y)] = 0 when x 6= y P∞ ◮ This will get rid of the absorbing states. . . Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics How do we solve the problem? ◮ P∞ [(A, x, y ) → (A, x, y )] = 1 whenever dx (A) = dy (A) = z ◮ But on the honeycomb lattice z = 3 ◮ So states with Eulerian A never get stuck ◮ To simulate loop models, we only observe the chain when A is Eulerian. . . ′ such that: ◮ Try defining new transition matrix P∞ ◮ ◮ ′ P∞ [(A, x, x) → · ] = limw→∞ Pw [(A, x, x) → · ] ′ [(A, x, y) → (A, x, y)] = 0 when x 6= y P∞ ◮ This will get rid of the absorbing states. . . ′ will simulate the FPL. . . ◮ If we are lucky P∞ Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y ◮ Pick x ′ ∼ x Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Pick x ′ ∼ x ◮ If xx ′ 6∈ A ◮ ◮ (A, x, x) → (A ∪ xx ′ , x ′ , x) or (A, x, x) → (A ∪ xx ′ , x, x ′ ) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Pick x ′ ∼ x ◮ If xx ′ 6∈ A ◮ ◮ ◮ (A, x, x) → (A ∪ xx ′ , x ′ , x) or (A, x, x) → (A ∪ xx ′ , x, x ′ ) Else (A, x, x) → (A, x, x) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Pick x ′ ∼ x ◮ If xx ′ 6∈ A ◮ ◮ ◮ (A, x, x) → (A ∪ xx ′ , x ′ , x) or (A, x, x) → (A ∪ xx ′ , x, x ′ ) Else (A, x, x) → (A, x, x) ◮ Else if x 6= y Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Pick x ′ ∼ x ◮ If xx ′ 6∈ A ◮ ◮ ◮ (A, x, x) → (A ∪ xx ′ , x ′ , x) or (A, x, x) → (A ∪ xx ′ , x, x ′ ) Else (A, x, x) → (A, x, x) ◮ Else if x 6= y ◮ Pick x or y (say x) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Pick x ′ ∼ x ◮ If xx ′ 6∈ A ◮ ◮ ◮ (A, x, x) → (A ∪ xx ′ , x ′ , x) or (A, x, x) → (A ∪ xx ′ , x, x ′ ) Else (A, x, x) → (A, x, x) ◮ Else if x 6= y ◮ ◮ Pick x or y (say x) If dx (A) = 3 Pick one of the three xx ′ ∈ A ◮ (A, x, y ) → (A \ xx ′ , x ′ , y ) ◮ Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Pick x ′ ∼ x ◮ If xx ′ 6∈ A ◮ ◮ ◮ (A, x, x) → (A ∪ xx ′ , x ′ , x) or (A, x, x) → (A ∪ xx ′ , x, x ′ ) Else (A, x, x) → (A, x, x) ◮ Else if x 6= y ◮ ◮ Pick x or y (say x) If dx (A) = 3 Pick one of the three xx ′ ∈ A ◮ (A, x, y ) → (A \ xx ′ , x ′ , y ) ◮ Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Pick x ′ ∼ x ◮ If xx ′ 6∈ A ◮ ◮ ◮ (A, x, x) → (A ∪ xx ′ , x ′ , x) or (A, x, x) → (A ∪ xx ′ , x, x ′ ) Else (A, x, x) → (A, x, x) ◮ Else if x 6= y ◮ ◮ Pick x or y (say x) If dx (A) = 3 Pick one of the three xx ′ ∈ A ◮ (A, x, y ) → (A \ xx ′ , x ′ , y ) ◮ ◮ Else if dx (A) = 1 ◮ ◮ Pick one of the two xx ′ 6∈ A (A, x, y ) → (A ∪ xx ′ , x ′ , y ) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Pick x ′ ∼ x ◮ If xx ′ 6∈ A ◮ ◮ ◮ (A, x, x) → (A ∪ xx ′ , x ′ , x) or (A, x, x) → (A ∪ xx ′ , x, x ′ ) Else (A, x, x) → (A, x, x) ◮ Else if x 6= y ◮ ◮ Pick x or y (say x) If dx (A) = 3 Pick one of the three xx ′ ∈ A ◮ (A, x, y ) → (A \ xx ′ , x ′ , y ) ◮ ◮ Else if dx (A) = 1 ◮ ◮ Pick one of the two xx ′ 6∈ A (A, x, y ) → (A ∪ xx ′ , x ′ , y ) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Pick x ′ ∼ x ◮ If xx ′ 6∈ A ◮ ◮ ◮ (A, x, x) → (A ∪ xx ′ , x ′ , x) or (A, x, x) → (A ∪ xx ′ , x, x ′ ) Else (A, x, x) → (A, x, x) ◮ Else if x 6= y ◮ ◮ Pick x or y (say x) If dx (A) = 3 Pick one of the three xx ′ ∈ A ◮ (A, x, y ) → (A \ xx ′ , x ′ , y ) ◮ ◮ Else if dx (A) = 1 ◮ ◮ Pick one of the two xx ′ 6∈ A (A, x, y ) → (A ∪ xx ′ , x ′ , y ) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Pick x ′ ∼ x ◮ If xx ′ 6∈ A ◮ ◮ ◮ (A, x, x) → (A ∪ xx ′ , x ′ , x) or (A, x, x) → (A ∪ xx ′ , x, x ′ ) Else (A, x, x) → (A, x, x) ◮ Else if x 6= y ◮ ◮ Pick x or y (say x) If dx (A) = 3 Pick one of the three xx ′ ∈ A ◮ (A, x, y ) → (A \ xx ′ , x ′ , y ) ◮ ◮ Else if dx (A) = 1 ◮ ◮ Pick one of the two xx ′ 6∈ A (A, x, y ) → (A ∪ xx ′ , x ′ , y ) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Worm algorithm for honeycomb-lattice FPL ◮ Start in configuration (A, x, y ) ◮ If x = y Pick x ′ ∼ x ◮ If xx ′ 6∈ A ◮ ◮ ◮ (A, x, x) → (A ∪ xx ′ , x ′ , x) or (A, x, x) → (A ∪ xx ′ , x, x ′ ) Else (A, x, x) → (A, x, x) ◮ Else if x 6= y ◮ ◮ Pick x or y (say x) If dx (A) = 3 Pick one of the three xx ′ ∈ A ◮ (A, x, y ) → (A \ xx ′ , x ′ , y ) ◮ ◮ Else if dx (A) = 1 ◮ ◮ Pick one of the two xx ′ 6∈ A (A, x, y ) → (A ∪ xx ′ , x ′ , y ) Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops An alternate perspective on worm dynamics Transition matrix ◮ x 6= y ( 1/6 dx (A) = 3 ′ P∞ [(A, x, y ) → (A△xx ′ , x ′ , y )] = 1/4 xx ′ 6∈ A ◮ x =y dx (A) ′ P∞ [(A, x, x) → (A, x, x)] = 3 1 ′ P∞ [(A, x, x) → (A ∪ xx ′ , x ′ , x)] = 6 Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics Transition matrix ◮ x 6= y ( 1/6 dx (A) = 3 ′ P∞ [(A, x, y ) → (A△xx ′ , x ′ , y )] = 1/4 xx ′ 6∈ A ◮ x =y dx (A) ′ P∞ [(A, x, x) → (A, x, x)] = 3 1 ′ P∞ [(A, x, x) → (A ∪ xx ′ , x ′ , x)] = 6 Theorem The set of states in S with no isolated vertices is recurrent and irreducible, its complement is transient, and the stationary ′ is uniform on the fully-packed configurations distribution of P∞ Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary An alternate perspective on worm dynamics Transition matrix ◮ x 6= y ( 1/6 dx (A) = 3 ′ P∞ [(A, x, y ) → (A△xx ′ , x ′ , y )] = 1/4 xx ′ 6∈ A ◮ x =y dx (A) ′ P∞ [(A, x, x) → (A, x, x)] = 3 1 ′ P∞ [(A, x, x) → (A ∪ xx ′ , x ′ , x)] = 6 Theorem The set of states in S with no isolated vertices is recurrent and irreducible, its complement is transient, and the stationary ′ is uniform on the fully-packed configurations distribution of P∞ ′ correctly simulates the FPL ◮ Therefore P∞ Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Worm simulations of honeycomb-lattice FPL ◮ Simulated the honeycomb-lattice FPL Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Worm simulations of honeycomb-lattice FPL ◮ Simulated the honeycomb-lattice FPL ◮ Again observed multiple time scales Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Worm simulations of honeycomb-lattice FPL ◮ Simulated the honeycomb-lattice FPL ◮ Again observed multiple time scales ◮ Nl (A, x, y ) = number of loops (cyclomatic number) ◮ hNl i is “energy-like” Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Worm simulations of honeycomb-lattice FPL ◮ Simulated the honeycomb-lattice FPL ◮ Again observed multiple time scales ◮ Nl (A, x, y ) = number of loops (cyclomatic number) ◮ hNl i is “energy-like” ◮ Nl is the slowest mode observed Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Numerical results Dynamics of Nl ◮ ρN (t) is almost a perfect exponential l 1 12 24 30 60 90 150 240 600 900 l ρN (t) 0.1 0.01 ◮ Scaled time by τint,N zexp ≈ zint,Nl ◮ Fitting τint,N 0 1 2 3 4 t/τint,N 5 l 6 7 l ◮ Good data collapse suggests 8 gives zint,Nl = 0.515(8) l Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary ◮ Standard worm algorithm for Ising high-temperature graphs outperforms SW in three dimensions Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary ◮ Standard worm algorithm for Ising high-temperature graphs outperforms SW in three dimensions ◮ Worm decorrelates on different time scales – depends on observable Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary ◮ Standard worm algorithm for Ising high-temperature graphs outperforms SW in three dimensions ◮ Worm decorrelates on different time scales – depends on observable ◮ Modified worm algorithm is demonstrated to be valid for honeycomb lattice FPL ◮ Dynamic exponent z ≈ 0.5 Summary Outline Worm algorithms for Ising high-temperature graphs Worm algorithms for fully-packed loops Summary Summary ◮ Standard worm algorithm for Ising high-temperature graphs outperforms SW in three dimensions ◮ Worm decorrelates on different time scales – depends on observable ◮ Modified worm algorithm is demonstrated to be valid for honeycomb lattice FPL ◮ Dynamic exponent z ≈ 0.5 ◮ By contrast, even the best cluster algorithms for frustrated Ising models are thought to be non-ergodic at T = 0