Page 274 -

5.3 Generalized Ising models 261

procedure markov-spin-glass
input {σ 1 ,... ,σ N },E
k ← nran(1,N)

∆ E ← σ k J kl σ Nbr(l,k) (matrix {J kl } from Fig. 5.26)
l
Υ ← e −β∆ E
if (ran(0, 1) < Υ)then

σ k ←−σ k
E ← E +∆ E
output {σ 1 ,...,σ N },E
——
Algorithm 5.10 markov-spin-glass. Local Metropolis algorithm for
the Ising spin glass.

recover the data in Table 5.9,butitdoes not lead to the spectacular
performance gains that we witnessed in the ferromagnetic Ising model.

procedure cluster-spin-glass
input {J kl }
.
.
.
while (P
= ∅)do
⎧
⎪ k ← any element of P
⎨
for (∀ l
∈C with l neighbor of k, σ l J lk σ k > 0) do
⎪ .
⎩ .
.
——
Algorithm 5.11 cluster-spin-glass. Lines that must be changed in
order in Alg. 5.9 (cluster-ising) to allow it to be used for spin glasses.
The reasonforthis lack ofefficiency is the following.The cluster algo-
rithm forthe Ising modelwas constructed with the aim ofmaking large
strides in magnetizationat eachstep.This enables quick moves between
the two ground states ofthe Ising model,butdoes notfacilitate moves
between the large number of valleysin the spin glass.
Finally, Alg.5.6 (combinatorial-ising) can also be generalized to
the two-dimensional spin glass, and we again must modifyonly afew
lines (see Alg.5.12 (combinatorial-spin-glass)). This algorithm (Saul
and Kardar 1993) can reproduce the data in Table 5.9 exactly. It works
for large two-dimensional spin glasses, where Gray-code enumerationis
notan option.It represents the best computational methodforstudy-
ing the thermodynamics oftwo-dimensional spin glasses, allowing one to
reach verylarge system sizes and to average over many samples.How-
ever, the methodcannot be generalized to three dimensions.
Inconclusion, in this subsection wehavebriefly discussed the Ising
spin glass in two dimensions, with the aim oftesting ouralgorithms.Lo-
calMonte Carlo methods slow downso much that they are practically
useless, and cluster algorithms do notimprovethe convergence.How-
ever, the purely theoretical combinatorial approach of Kac and Ward,