0000000000134893
AUTHOR
Martin Weigel
GPU accelerated Monte Carlo simulations of lattice spin models
We consider Monte Carlo simulations of classical spin models of statistical mechanics using the massively parallel architecture provided by graphics processing units (GPUs). We discuss simulations of models with discrete and continuous variables, and using an array of algorithms ranging from single-spin flip Metropolis updates over cluster algorithms to multicanonical and Wang-Landau techniques to judge the scope and limitations of GPU accelerated computation in this field. For most simulations discussed, we find significant speed-ups by two to three orders of magnitude as compared to single-threaded CPU implementations.
Cross Correlations in Scaling Analyses of Phase Transitions
Thermal or finite-size scaling analyses of importance sampling Monte Carlo time series in the vicinity of phase transition points often combine different estimates for the same quantity, such as a critical exponent, with the intent to reduce statistical fluctuations. We point out that the origin of such estimates in the same time series results in often pronounced cross-correlations which are usually ignored even in high-precision studies, generically leading to significant underestimation of statistical fluctuations. We suggest to use a simple extension of the conventional analysis taking correlation effects into account, which leads to improved estimators with often substantially reduced …
Performance potential for simulating spin models on GPU
Graphics processing units (GPUs) are recently being used to an increasing degree for general computational purposes. This development is motivated by their theoretical peak performance, which significantly exceeds that of broadly available CPUs. For practical purposes, however, it is far from clear how much of this theoretical performance can be realized in actual scientific applications. As is discussed here for the case of studying classical spin models of statistical mechanics by Monte Carlo simulations, only an explicit tailoring of the involved algorithms to the specific architecture under consideration allows to harvest the computational power of GPU systems. A number of examples, ran…
Connected-component identification and cluster update on graphics processing units.
Cluster identification tasks occur in a multitude of contexts in physics and engineering such as, for instance, cluster algorithms for simulating spin models, percolation simulations, segmentation problems in image processing, or network analysis. While it has been shown that graphics processing units (GPUs) can result in speedups of two to three orders of magnitude as compared to serial codes on CPUs for the case of local and thus naturally parallelized problems such as single-spin flip update simulations of spin models, the situation is considerably more complicated for the nonlocal problem of cluster or connected component identification. I discuss the suitability of different approaches…
Regular packings on periodic lattices.
We investigate the problem of packing identical hard objects on regular lattices in d dimensions. Restricting configuration space to parallel alignment of the objects, we study the densest packing at a given aspect ratio X. For rectangles and ellipses on the square lattice as well as for biaxial ellipsoids on a simple cubic lattice, we calculate the maximum packing fraction \phi_d(X). It is proved to be continuous with an infinite number of singular points X^{\rm min}_\nu, X^{\rm max}_\nu, \nu=0, \pm 1, \pm 2,... In two dimensions, all maxima have the same height, whereas there is a unique global maximum for the case of ellipsoids. The form of \phi_d(X) is discussed in the context of geomet…
Efficient simulation of the random-cluster model
The simulation of spin models close to critical points of continuous phase transitions is heavily impeded by the occurrence of critical slowing down. A number of cluster algorithms, usually based on the Fortuin-Kasteleyn representation of the Potts model, and suitable generalizations for continuous-spin models have been used to increase simulation efficiency. The first algorithm making use of this representation, suggested by Sweeny in 1983, has not found widespread adoption due to problems in its implementation. However, it has been recently shown that it is indeed more efficient in reducing critical slowing down than the more well-known algorithm due to Swendsen and Wang. Here, we present…
Fragmentation of fractal random structures.
We analyze the fragmentation behavior of random clusters on the lattice under a process where bonds between neighboring sites are successively broken. Modeling such structures by configurations of a generalized Potts or random-cluster model allows us to discuss a wide range of systems with fractal properties including trees as well as dense clusters. We present exact results for the densities of fragmenting edges and the distribution of fragment sizes for critical clusters in two dimensions. Dynamical fragmentation with a size cutoff leads to broad distributions of fragment sizes. The resulting power laws are shown to encode characteristic fingerprints of the fragmented objects.
Simulating spin models on GPU
Over the last couple of years it has been realized that the vast computational power of graphics processing units (GPUs) could be harvested for purposes other than the video game industry. This power, which at least nominally exceeds that of current CPUs by large factors, results from the relative simplicity of the GPU architectures as compared to CPUs, combined with a large number of parallel processing units on a single chip. To benefit from this setup for general computing purposes, the problems at hand need to be prepared in a way to profit from the inherent parallelism and hierarchical structure of memory accesses. In this contribution I discuss the performance potential for simulating…
Percolation and Schramm–Loewner evolution in the 2D random-field Ising model
Abstract The presence of random fields is well known to destroy ferromagnetic order in Ising systems in two dimensions. When the system is placed in a sufficiently strong external field, however, the size of clusters of like spins diverges. There is evidence that this percolation transition is in the universality class of standard site percolation. It has been claimed that, for small disorder, a similar percolation phenomenon also occurs in zero external field. Using exact algorithms, we study ground states of large samples and find little evidence for a transition at zero external field. Nevertheless, for sufficiently small random-field strengths, there is an extended region of the phase d…
Corner contribution to cluster numbers in the Potts model
For the two-dimensional Q-state Potts model at criticality, we consider Fortuin-Kasteleyn and spin clusters and study the average number N_Gamma of clusters that intersect a given contour Gamma. To leading order, N_Gamma is proportional to the length of the curve. Additionally, however, there occur logarithmic contributions related to the corners of Gamma. These are found to be universal and their size can be calculated employing techniques from conformal field theory. For the Fortuin-Kasteleyn clusters relevant to the thermal phase transition we find agreement with these predictions from large-scale numerical simulations. For the spin clusters, on the other hand, the cluster numbers are no…
Spin stiffness of vector spin glasses
Abstract We study domain-wall excitations for O ( m ) vector spin glasses in the limit m → ∞ , where the energy landscape is simplified considerably compared to XY or Heisenberg models due to the complete disappearance of metastability. Using numerical ground-state calculations and appropriate pairs of complementary boundary conditions, domain-wall defects are inserted into the systems and their excitation energies are measured. This allows us to determine the stiffness exponents for lattices of a range of spatial dimensions d = 2 , … , 7 . Compiling these results, we can finally determine the lower critical dimension of the model. The outcome is compared to estimates resulting from field-t…
Non-reversible Monte Carlo simulations of spin models
Abstract Monte Carlo simulations are used to study simple systems where the underlying Markov chain satisfies the necessary condition of global balance but does not obey the more restrictive condition of detailed balance. Here, we show that non-reversible Markov chains can be set up that generate correct stationary distributions, but reduce or eliminate the diffusive motion in phase space typical of the usual Monte Carlo dynamics. Our approach is based on splitting the dynamics into a set of replicas with each replica representing a biased movement in reaction-coordinate space. This introduction of an additional bias in a given replica is compensated for by choosing an appropriate dynamics …
Error estimation and reduction with cross correlations
Besides the well-known effect of autocorrelations in time series of Monte Carlo simulation data resulting from the underlying Markov process, using the same data pool for computing various estimates entails additional cross correlations. This effect, if not properly taken into account, leads to systematically wrong error estimates for combined quantities. Using a straightforward recipe of data analysis employing the jackknife or similar resampling techniques, such problems can be avoided. In addition, a covariance analysis allows for the formulation of optimal estimators with often significantly reduced variance as compared to more conventional averages.
SIMULATING SPIN MODELS ON GPU: A TOUR
The use of graphics processing units (GPUs) in scientific computing has gathered considerable momentum in the past five years. While GPUs in general promise high performance and excellent performance per Watt ratios, not every class of problems is equally well suitable for exploiting the massively parallel architecture they provide. Lattice spin models appear to be prototypic examples of problems suitable for this architecture, at least as long as local update algorithms are employed. In this review, I summarize our recent experience with the simulation of a wide range of spin models on GPU employing an equally wide range of update algorithms, ranging from Metropolis and heat bath updates,…
High-precision studies of domain-wall properties in the 2D Gaussian Ising spin glass
In two dimensions, short-range spin glasses order only at zero temperature, where efficient combinatorial optimization techniques can be used to study these systems with high precision. The use of large system sizes and high statistics in disorder averages allows for reliable finite-size extrapolations to the thermodynamic limit. Here, we use a recently introduced mapping of the Ising spin-glass ground-state problem to a minimum-weight perfect matching problem on a sparse auxiliary graph to study square-lattice samples of up to 10 000 × 10 000 spins. We propose a windowing technique that allows to extend this method, that is formally restricted to planar graphs, to the case of systems with …
Generalized-ensemble simulations and cluster algorithms
The importance-sampling Monte Carlo algorithm appears to be the universally optimal solution to the problem of sampling the state space of statistical mechanical systems according to the relative importance of configurations for the partition function or thermal averages of interest. While this is true in terms of its simplicity and universal applicability, the resulting approach suffers from the presence of temporal correlations of successive samples naturally implied by the Markov chain underlying the importance-sampling simulation. In many situations, these autocorrelations are moderate and can be easily accounted for by an appropriately adapted analysis of simulation data. They turn out…
Numerical tests of conjectures of conformal field theory for three-dimensional systems
The concept of conformal field theory provides a general classification of statistical systems on two-dimensional geometries at the point of a continuous phase transition. Considering the finite-size scaling of certain special observables, one thus obtains not only the critical exponents but even the corresponding amplitudes of the divergences analytically. A first numerical analysis brought up the question whether analogous results can be obtained for those systems on three-dimensional manifolds. Using Monte Carlo simulations based on the Wolff single-cluster update algorithm we investigate the scaling properties of O(n) symmetric classical spin models on a three-dimensional, hyper-cylindr…
Domain-wall excitations in the two-dimensional Ising spin glass
The Ising spin glass in two dimensions exhibits rich behavior with subtle differences in the scaling for different coupling distributions. We use recently developed mappings to graph-theoretic problems together with highly efficient implementations of combinatorial optimization algorithms to determine exact ground states for systems on square lattices with up to $10\,000\times 10\,000$ spins. While these mappings only work for planar graphs, for example for systems with periodic boundary conditions in at most one direction, we suggest here an iterative windowing technique that allows one to determine ground states for fully periodic samples up to sizes similar to those for the open-periodic…