C3P Technical Report
Non-local Cluster Update Algorithms for Spin Models
Paul D. Coddington and Clive F. Baillie
July 1990
Published in
Applications of Transputers 2,
Proc. of the 2nd Annual World Conference on Transputer Applications,
Southampton, U.K. (July 1990),
eds. D.J. Pritchard and C.J. Scott, (IOS Press, Amsterdam, 1990).
© Copyright IOS Press.
Abstract
Parallel computers are ideally suited to the Monte Carlo simulation of spin
models using the standard Metropolis algorithm, since it is regular and local.
However local algorithms have the major drawback that near a phase transition
the number of sweeps needed to generate a statistically independent spin
configuration increases as the square of the lattice size.
New algorithms have recently been developed which dramatically reduce this
`critical slowing down' by updating clusters of spins at a time. The
highly irregular and non-local nature of the clusters means that these
algorithms are much more difficult to parallelize efficiently.
Here we introduce some parallel algorithms for identifying and labeling
clusters, which have been implemented on the Meiko Computing Surface and
other MIMD machines using the Express parallel programming environment.
These algorithms are also applicable to the problem of labeling connected
components in image analysis.
PostScript version
(gzip compressed)
PDF version