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.
A zero temperature (lowest energy) configuration of an antiferromagnetic Ising model with two spin states (represented by yellow and blue) on a triangular lattice.
SCCS-241
E. Marinari and G. Parisi,
Simulated Tempering: A New Monte Carlo Scheme,
Europhys. Lett. 19, 451 (1992).
SCCS-279
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-526
P.D. Coddington,
Analysis of Random Number Generators Using Monte Carlo Simulation,
Int. J. Mod. Phys. C, to appear.
SCCS-527
P.D. Coddington and L. Han,
On Generalized Cluster Algorithms for Frustrated Spin Models,
submitted to Phys. Rev. B.
S.-J. Bae, P.D. Coddington, S.-H. Ko, Parallel Wolff Cluster Algorithms, in preparation.
N.K. Copty and P.D. Coddington, Software Support for the Parallelization of Clustering Applications, in preparation.
P.D. Coddington, G.C. Fox, C.-H. Wu, E. Marinari, T. Rose, M. Shore, Optimal annealing schedules using simulated tempering, in preparation.