15.4 Algorithms for lattice field theories 481a Gaussian distributionρ(φn), according to the procedure just described. Then we
accept this new field value with a probability exp(−gφn^4 / 2 ).Ifgis not too large
(and this will be the case in most of the examples given below), then the acceptance
rate will still be reasonably close to 1 and not too many trial steps are rejected. If
gis large, then a different procedure for generating the trial field value should be
followed [9].
There is an intimate relation between the heat-bath method described here and
the Gauss–Seidel method for finding the solution of the Poisson equation (see
Appendix A7.2). In the Gauss–Seidel method, the sites are visited in lexicographic
order (the same can be done in the heat-bath method), andφnis set equal toφ ̄n
without adding a Gaussian random number to it. InAppendix A7.2the problem
of slow convergence of the numerical solution of the Poisson problem will be
addressed: it turns out that the relaxation time, measured in sweeps over the entire
lattice, scales as the square of the linear lattice size. The amount of computer time
involved in one lattice sweep also scales linearly with the lattice volume, so the
total time needed to obtain results within a certain level of accuracy scales with
the volume squared. Because of this power-law scaling behaviour of the standard
Poisson solvers, one might call this problem ‘critical’: the relaxation time scales
with the system size in a way similar to a system subject to critical fluctuations.
The relation between Poisson solvers and free field theory leads us to apply clever
methods for solving Poisson’s equation to the problem of generating configurations
with a probability density exp(−S[φ]). InAppendix A, successive over-relaxation
(SOR), the use of fast Fourier transforms (FFT), and the multigrid method are
mentioned, and we shall see that all of these methods have their counterpart in
Monte Carlo.
Successive over-relaxation is a method for increasing the efficiency of the Gauss–
Seidel method. The idea behind this method is that if we update the sites in
lexicographic order, half of the neighbours of the site being updated have already
been updated and the other half are still to be treated. In SOR, a compensation is
built in for the fact that half of the neighbouring sites have not yet been updated.
Sitenis being updated according to
φnnew=φoldn +ω(φ ̄n−φoldn ). (15.57)It can be shown that the optimal value forωis close to 2: in that case the relaxation
time, which scales asL^2 (measured in lattice sweeps) in the Gauss–Seidel method is
reduced toL(seeAppendix A7.2andRef.[10]). Adler has shown that the relaxation
time for a Monte Carlo algorithm where a Gaussian random number is added to
φnew[11]:
φnnew→φnnew+√
ω( 2 −ω)r/√
2 d+m^2 , (15.58)