Monte Carlo Simulations of Spin Models

SUMMARY
We have developed parallel Monte Carlo algorithms for numerical modeling of magnetic materials, and are studying the issues of software and runtime support for these irregular algorithms. We are also working on improving Monte Carlo methods, such as simulated annealing, for solving hard optimization problems.

PARTICIPATING INSTITUTIONS
NPAC, Syracuse University
Physics Department, Syracuse University

KEY CONTACTS
Paul Coddington | paulc@npac.syr.edu | 315-443-4883
Enzo Marinari | marinari@npac.syr.edu | 315-443-5976

IMPACT
These spin model programs are part of the HPF/F90D benchmark suite. The programs also provide sensitive tests of the quality of random number generators, which are important in a wide variety of applications in computational science. We are also developing and improving Monte Carlo techniques such as simulated annealing for general combinatorial optimization problems, including real-world problems such as scheduling.

PROJECT DESCRIPTION
Standard Monte Carlo algorithms for simulating spin models of magnetism, such as the Metropolis algorithm, make regular and local changes to the system, and thus are easy to parallelize efficiently. However the more recent cluster update algorithms perform much better since they make non-local updates to large clusters of spins, rather than local updates of single spins. However the non-local and irregular nature of these updates means they are difficult to parallelize efficiently.

The main computational task in cluster algorithms is connected component labeling, to identify the clusters of spins to be updated. We have developed a number of parallel component labeling algorithms, for both the single cluster (Wolff) and multiple cluster (Swendsen-Wang) algorithms, for SIMD and MIMD architectures. We are also working with the Fortran 90D group at Syracuse on language and runtime support requirements for clustering applications, such as connected component labeling for spin models and percolation, image segmentation and region growing for image analysis, and data clustering.

Simulated tempering is a recent computational technique developed for the study of spin models of magnetism. It is closely related to simulated annealing, which has been applied with great success to general optimization problems. We are investigating the use of simulated tempering for optimization, since it appears to have a number of advantages to simulated annealing, and is closely related to the construction of optimal adaptive cooling schedules. We are working on applying these stochastic optimization techniques to complex real-world combinatorial optimization problems, such as academic scheduling.

Click on the image to see a larger version.

A zero temperature (lowest energy) configuration of an antiferromagnetic Ising model with two spin states (represented by yellow and blue) on a triangular lattice.

REFERENCES
  1. E. Marinari and G. Parisi, Simulated Tempering: A New Monte Carlo Scheme, Europhys. Lett. 19, 451 (1992). SCCS-241.
  2. John Apostolakis, Paul Coddington and Enzo Marinari, New SIMD Algorithms for Cluster Labeling on Parallel Computers, Int. J. Mod. Phys. C 4, 749 (1993). SCCS-279
  3. P.D. Coddington, Analysis of Random Number Generators Using Monte Carlo Simulation, Int. J. Mod. Phys. C, to appear. SCCS-526
  4. P.D. Coddington and L. Han, On Generalized Cluster Algorithms for Frustrated Spin Models, submitted to Phys. Rev. B. SCCS-527
  5. S.-J. Bae, P.D. Coddington, S.-H. Ko, Parallel Wolff Cluster Algorithms, in preparation.
  6. N.K. Copty and P.D. Coddington, Software Support for the Parallelization of Clustering Applications, in preparation.
  7. P.D. Coddington, G.C. Fox, C.-H. Wu, E. Marinari, T. Rose, M. Shore, Optimal annealing schedules using simulated tempering, in preparation.