Replica Monte Carlo Simulation Jian-Sheng Wang National University of Singapore : Replica Monte Carlo Simulation Jian-Sheng Wang National University of Singapore
Outline : Outline Review of extended ensemble methods (multi-canonical, Wang-Landau, flat-histogram, simulated tempering)
Replica MC
Connection to parallel tempering and cluster algorithm of Houdayer
Early and new results
Slowing Down at First-Order Phase Transition : Slowing Down at First-Order Phase Transition At first-order phase transition, the longest time scale is controlled by the interface barrier
where β=1/(kBT), σ is interface free energy, d is dimension, L is linear size
Multi-Canonical Ensemble : Multi-Canonical Ensemble We define multi-canonical ensemble as such that the (exact) energy histogram is a constant
h(E) = n(E) f(E) = const
This implies that the probability of configuration is
P(X) f(E(X)) 1/n(E(X))
Multi-Canonical Simulation (Berg et al) : Multi-Canonical Simulation (Berg et al) Do simulation with probability weight fn(E), using Metropolis acceptance rate min[1, fn(E’)/fn(E) ]
Collection histogram H(E)
Re-compute weight by
fn+1(E) = fn(E)/H(E)
Iterate until H(E) is flat
Multi-Canonical Simulation and Reweighting : Multi-Canonical Simulation and Reweighting Multicanonical histogram and reweighted canonical distribution for 2D 10-state Potts model
From A B Berg and T Neuhaus, Phys Rev Lett 68 (1992) 9.
Wang-Landau Method : Wang-Landau Method Work directly with n(E), starting with some initial guess, n(E) ≈ const, f = f0 > 1 (say 2.7)
Flip a spin according to acceptance rate min[1, n(E)/n(E ’)]
And also update n(E) by
n(E) <- n(E) f
Reduce f by f <-f 1/2 after certain number of MC steps, when the histogram H(E) is “flat”.
Flat Histogram Algorithm : Flat Histogram Algorithm Pick a site at random
Flip the spin with probability
where E is current and E ’ is new energy
3. Accumulate statistics for E
The Ising Model : The Ising Model - + + + + + + + + + + + + + + + + - - - - - - - - - - - - - - - - - - - Total energy is
E(σ) = - J ∑ σi σj
sum over nearest neighbors, σi = ±1
N(s,DE) is the number of sites, such that flip spin costs energy DE. σ = {σ1, σ2, …, σi, … } DE=0 DE=-8J
Spin Glass Model : Spin Glass Model + + + + + + + + + + + + + + + + + + + + + + + + - - - - - - - - - - - - - - - - - - - - - - - - - A random interaction Ising model - two types of random, but fixed coupling constants (ferro Jij > 0) and (anti-ferro Jij < 0)
Slow Dynamics in Spin Glass : Slow Dynamics in Spin Glass Correlation time in single spin flip dynamics for 3D spin glass. t |T-Tc|6.
From Ogielski, Phys Rev B 32 (1985) 7384.
Tunneling Time for 3D Spin Glass : Tunneling Time for 3D Spin Glass Diamond: standard flat histogram algorithm; dot: with N-fold way; triangle: equal-hit algorithm.
From J S Wang & R H Swendsen, J Stat Phys, 106 (2002) 245.
First-Passage Time to Ground States : First-Passage Time to Ground States Number of sweeps needed to discover a ground state for the first time. Extremal Optimization (EO) is an optimization algorithm.
From J S Wang and Y Okabe, J Phys Soc Jpn, 72 (2003) 1380.
Simulated Tempering (Marinari & Parisi, 1992) : Simulated Tempering (Marinari & Parisi, 1992) Simulated tempering treats parameters as dynamical variables, e.g., β jumps among a set of values βi. We enlarge sample space as {X, βi}, and make move {X,βi} -> {X’,β’i} according to the usual Metropolis rate.
Replica Monte Carlo : Replica Monte Carlo A collection of M systems at different temperatures is simulated in parallel, allowing exchange of information among the systems. β1 β2 β3 βM . . .
Moves between Replicas : Moves between Replicas Consider two neighboring systems, σ1 and σ2, the joint distribution is
P(σ1,σ2) exp[-β1E(σ1) –β2E(σ2)]
= exp[-Hpair(σ1, σ2)]
Any valid Monte Carlo move should preserve this distribution
Pair Hamiltonian in Replica Monte Carlo : Pair Hamiltonian in Replica Monte Carlo We define i=σi1σi2, then Hpair can be rewritten as
The Hpair again is a spin glass. If β1≈β2, and two systems have consistent signs, the interaction is twice as strong; if they have opposite sign, the interaction is 0.
Cluster Flip in Replica Monte Carlo : Cluster Flip in Replica Monte Carlo = +1 = -1 Clusters are defined by the values of i of same sign, The effective Hamiltonian for clusters is
Hcl = - Σ kbc sbsc
Where kbc is the interaction strength between cluster b and c, kbc= sum over boundary of cluster b and c of Kij. b c Metropolis algorithm is used to flip the clusters, i.e., σi1 -> -σi1, σi2 -> -σi2 fixing for all i in a given cluster.
Apply Swendsen-Wang in Replica MC : Apply Swendsen-Wang in Replica MC The t-cluster can be further broken down. Within a t-cluster, a bond is set with probability P = 1 – exp(-2 (b1+b2)|Jij|) if interaction is satisfied Jijsisj > 0; no bond otherwise.
No interaction between clusters broken this way. = +1 = -1 b c
Implementation Issues : Implementation Issues Use Hoshen-Kompelman algorithm to identify clusters
Based on cluster size and total number of clusters, pre-allocate memory to store effective cluster coupling kab
Order O(N) algorithm for each sweep
Comparing Correlation Times : Comparing Correlation Times Correlation times as a function of inverse temperature K=βJ on 2D, ±J Ising spin glass of 32x32 lattice.
From R H Swendsen and J-S Wang, Phys Rev Lett 57 (1986) 2607. Replica MC Single spin flip
Cluster Algorithm of S Liang : Cluster Algorithm of S Liang 2D Gaussian spin glass on 16x16 lattice, using a generalization due to F Niedermayer.
From S Liang, PRL 69 (1992) 2145.
Replica Exchange (Hukushima & Nemoto, 1996) : Replica Exchange (Hukushima & Nemoto, 1996) A simple move of exchange configurations, σ1 <-> σ2, with Metropolis acceptance rate
min{ 1, exp[(β2-β1)(E(σ2)-E(σ1))] }
This is equivalent to flip all the ti =-1 clusters in replica Monte Carlo. Also known as parallel tempering
Replica Exchange : Replica Exchange Spin-spin exponential relaxation time for replica exchange on 123 lattice.
From K Hukushima and K Nemoto, J Phys Soc Jpn, 65 (1996) 1604.
Houdayer’s Cluster Algorithm : Houdayer’s Cluster Algorithm β1 β2 β3 βM . . . β1 β2 β3 βM . . . β1 β2 β3 βM . . . . . . Replica exchange between different temperatures Single t-cluster flip between same temperature set 1 set 2 set N Simulate simultaneously M by N systems.
Relaxation towards Equilibrium at LowT : Relaxation towards Equilibrium at LowT Relaxation of energy for 100x100 +/-J Ising spin glass at T = 0.1 [32 set of 26 replicas for cluster algorithm].
From J Houdayer, Eur Phys J B 22 (2001) 479.
Correlation Functions in Replica MC : Correlation Functions in Replica MC Time correlation function for order parameter q on 128x128 ±J Ising spin glass. 106 MCS used. Labels are K=1/T.
q=|∑ii|
From J-S Wang and R H Swendsen, cond-mat/0407273.
Comparison of Single-spin-flip, Parallel Tempering, Houdayer, and Replica MC : Comparison of Single-spin-flip, Parallel Tempering, Houdayer, and Replica MC 2D ±J Ising spin glass integrated correlation time on a 32x32 lattice.
From cond-mat/0407273, to appear (2005) Prog Theor Phys Suppl.
Integrated Correlation Times, 128x128 system : Integrated Correlation Times, 128x128 system
Comparison in 3D : Comparison in 3D Integrated correlation times for ±J Ising spin glass on 12x12x12 lattice.
2D Spin Glass Susceptibility : 2D Spin Glass Susceptibility 2D ±J spin glass susceptibility on 128x128 lattice, 1.8x104 MC steps.
From J S Wang and R H Swendsen, PRB 38 (1988) 4840.
K5.11 was concluded.
Heat Capacity at Low T : Heat Capacity at Low T c T -2exp(-2J/T)
This result is confirmed recently by Lukic et al, PRL 92 (2004) 117202. slope = -2
Monte Carlo Renormalization Group : Monte Carlo Renormalization Group YH defined by
with RG iterations for difference sizes in 2D.
From J S Wang and R H Swendsen, PRB 37 (1988) 7745.
MCRG in 3D : MCRG in 3D 3D result of YH.
MCS is 104 to 105, with 23 samples for L= 8, 8 samples for L= 12, and 5 samples for L= 16.
Correlation Length : Correlation Length Correlation length (defined by ratio of wavenumber dependent susceptibilities) on 128x128 lattice, averaged of 96 random coupling samples.
Unpublished.
Summary : Summary Replica MC is very efficient in 2D, and becomes equivalent to Parallel Tempering in 3D
Replica MC has been used for equilibrium simulations (heat capacity, MCRG, etc)