Synchronous parallel kinetic Monte Carlo for continuum diffusion-reaction systems

A novel parallel kinetic Monte Carlo (kMC) algorithm formulated on the basis of perfect time synchronicity is presented. The algorithm is intended as a generalization of the standard n-fold kMC method, and is trivially implemented in parallel architectures. In its present form, the algorithm is not rigorous in the sense that boundary conflicts are ignored. We demonstrate, however, that, in their absence, or if they were correctly accounted for, our algorithm solves the same master equation as the serial method. We test the validity and parallel performance of the method by solving several pure diffusion problems (i.e. with no particle interactions) with known analytical solution. We also study diffusion-reaction systems with known asymptotic behavior and find that, for large systems with interaction radii smaller than the typical diffusion length, boundary conflicts are negligible and do not affect the global kinetic evolution, which is seen to agree with the expected analytical behavior. Our method is a controlled approximation in the sense that the error incurred by ignoring boundary conflicts can be quantified intrinsically, during the course of a simulation, and decreased arbitrarily (controlled) by modifying a few problem-dependent simulation parameters.     

Efficient kinetic Monte Carlo simulation

This paper concerns kinetic Monte Carlo (KMC) algorithms that have a single-event execution time independent of the system size. Two methods are presented—one that combines the use of inverted-list data structures with rejection Monte Carlo and a second that combines inverted lists with the Marsaglia–Norman–Cannon algorithm. The resulting algorithms apply to models with rates that are determined by the local environment but are otherwise arbitrary, time-dependent and spatially heterogeneous. While especially useful for crystal growth simulation, the algorithms are presented from the point of view that KMC is the numerical task of simulating a single realization of a Markov process, allowing application to a broad range of areas where heterogeneous random walks are the dominate simulation cost.     

Billion-atom synchronous parallel kinetic Monte Carlo simulations of critical 3D Ising systems

An extension of the synchronous parallel kinetic Monte Carlo (spkMC) algorithm developed by Martinez et al. [J. Comp. Phys. 227 (2008) 3804] to discrete lattices is presented. The method solves the master equation synchronously by recourse to null events that keep all processors’ time clocks current in a global sense. Boundary conflicts are resolved by adopting a chessboard decomposition into non-interacting sublattices. We find that the bias introduced by the spatial correlations attendant to the sublattice decomposition is within the standard deviation of serial calculations, which confirms the statistical validity of our algorithm. We have analyzed the parallel efficiency of spkMC and find that it scales consistently with problem size and sublattice partition. We apply the method to the calculation of scale-dependent critical exponents in billion-atom 3D Ising systems, with very good agreement with state-of-the-art multispin simulations.     

Statistical-temperature Monte Carlo and molecular dynamics algorithms

A simulation method is presented that achieves a flat energy distribution by updating the statistical temperature instead of the density of states in Wang-Landau sampling. A novel molecular dynamics algorithm (STMD) applicable to complex systems and a Monte Carlo algorithm are developed from this point of view. Accelerated convergence for large energy bins, essential for large systems, is demonstrated in tests on the Ising model, the Lennard-Jones fluid, and bead models of proteins. STMD shows a superior ability to find local minima in proteins and new global minima are found for the 55 bead AB model in two and three dimensions. Calculations of the occupation probabilities of individual protein inherent structures provide new insights into folding and misfolding.     

The kinetic process of non-smooth substrate thin film growth via parallel Monte Carlo method

A Monte Carlo simulation model of thin film growth based on parallel algorithm is presented. Non-smooth substrate with special defect mode is introduced in such a model. The method of regionalizing is used to divide the substrate into sub-regions. This method is supposed to be modulated according to the defect mode. The effects of surface defect mode and substrate temperature, such as the nucleation ratio and the average island size, are studied through parallel Monte Carlo method. The kinetic process of thin film growth in the defect mode is also discussed. Results show that surface defect mode contributes to crystal nucleation. Analyzing parallel simulation results we find that density defect points, substrate temperature and the number of processors contribute decisively to the parallel efficiency and speedup. According to defect mode we can obtain large grain size more feasibly and the parallel algorithm of this model can guide the non-smooth substrate simulation work.     

Overcoming artificial spatial correlations in simulations of superstructure domain growth with parallel Monte Carlo algorithms

We study the applicability of parallelized/vectorized Monte Carlo (MC) algorithms to the simulation of domain growth in two-dimensional lattice gas models undergoing an ordering process after a rapid quench below an order-disorder transition temperature. As examples we consider models with 2×1 andc(2×2) equilibrium superstructures on the square and rectangular lattices, respectively. We also study the case of phase separation (1×1 islands) on the square lattice. A generalized parallel checkerboard algorithm for Kawasaki dynamics is shown to give rise to artificial spatial correlations in all three models. However, only ifsuperstructure domains evolve do these correlations modify the kinetics by influencing the nucleation process and result in a reduced growth exponent compared to the value from the conventional heat bath algorithm with random single-site updates. In order to overcome these artificial modifications, two MC algorithms with a reduced degree of parallelism (hybrid and mask algorithms, respectively) are presented and applied. As the results indicate, these algorithms are suitable for the simulation of superstructure domain growth on parallel/vector computers.     

Irreversible Monte Carlo algorithms for efficient sampling

Equilibrium systems evolve according to Detailed Balance (DB). This principle guided the development of Monte Carlo sampling techniques, of which the Metropolis–Hastings (MH) algorithm is the famous representative. It is also known that DB is sufficient but not necessary. We construct irreversible deformation of a given reversible algorithm capable of dramatic improvement of sampling from known distribution. Our transformation modifies transition rates keeping the structure of transitions intact. To illustrate the general scheme we design an Irreversible version of Metropolis–Hastings (IMH) and test it on an example of a spin cluster. Standard MH for the model suffers from critical slowdown, while IMH is free from critical slowdown.     

Fully parallel code for Monte Carlo simulation

We present a fully parallel version of Monte Carlo simulation of the Ising model using the Metropolis algorithm. In the 3-dimensional version the performance can be enhanced by a factor >20 in 16-bit word processors relative to other multispin codes. This factor could be further increased if implemented in 64-bit word computers.     

Hierarchical Monte Carlo methods for fractal random fields

Two hierarchical Monte Carlo methods for the generation of self-similar fractal random fields are compared and contrasted. The first technique, successive random addition (SRA), is currently popular in the physics community. Despite the intuitive appeal of SRA, rigorous mathematical reasoning reveals that SRA cannot be consistent with any stationary power-law Gaussian random field for any Hurst exponent; furthermore, there is an inherent ratio of largest to smallest putative scaling constant necessarily exceeding a factor of 2 for a wide range of Hurst exponentsH, with 0.30<H<0.85. Thus, SRA is inconsistent with a stationary power-law fractal random field and would not be useful for problems that do not utilize additional spatial averaging of the velocity field. The second hierarchical method for fractal random fields has recently been introduced by two of the authors and relies on a suitable explicit multiwavelet expansion (MWE) with high-moment cancellation. This method is described briefly, including a demonstration that, unlike SRA, MWE is consistent with a stationary power-law random field over many decades of scaling and has low variance.     

A new random-number generator for multispin Monte Carlo algorithms

We develop a novel multispin coded random number generator algorithm to compute bits equal to 1 with probabilityp. Compared to previously used algorithms, this generator is at least equally fast and allows for an arbitrary accuracy of the computed probability without any significant increase in time. An explicit implementation of the algorithm is given for a Cray-1 vector computer, and the modifications for other machines are discussed. Finally, the algorithm is tested by computing the magnetization of the two-dimensional Ising model. The measured speed of the program is 57 million spin-flips per second. The agreement with theoretical values is found to remain very satisfying even when quite close (-0.5%) to the critical temperature.     

Monte Carlo simulation of very large kinetic Ising models

We study the relaxation of Ising models in three and four dimensions aboveT _c , using multi-spin coding for lattices up to 360³ and 40⁴. The nonlinear relaxation time diverges as (T–T _c )^{–1.05±0.04} in three dimensions, where corrections to scaling are taken into account. In four dimensions the effective exponent is about 0.72; logarithmic correction factors make the analysis difficult here. The linear relaxation time for the asymptotic exponential decay is found to be larger, with effective exponents 1.31 (d=2) and 0.97 (d=4). The difference in the linear and nonlinear relaxation exponents is compatible in three dimensions with the orderparameter exponent , as predicted by Racz.Work supported by SFB 125 Aachen-Jülich-KölnWork started at Department de Physique des Systemes Desordonnes, Universite de Provence, Centre St-Jerome, F-13397 Marseille Cedex 13, France     

Off-lattice pattern recognition scheme for kinetic Monte Carlo simulations

We report the development of a pattern-recognition scheme for the off-lattice self-learning kinetic Monte Carlo (KMC) method, one that is simple and flexible enough that it can be applied to all types of surfaces. In this scheme, to uniquely identify the local environment and associated processes involving three-dimensional (3D) motion of an atom or atoms, space around a central atom is divided into 3D rectangular boxes. The dimensions and the number of 3D boxes are determined by the accuracy with which a process needs to be identified and a process is described as the central atom moving to a neighboring vacant box accompanied by the motion of any other atom or atoms in its surrounding boxes. As a test of this method to we apply it to examine the decay of 3D Cu islands on the Cu(100) and to the surface diffusion of a Cu monomer and a dimer on Cu(111) and compare the results and computational efficiency to those available in the literature.     

Polymer depletion interaction between parallel walls--a Monte Carlo study

An off-lattice bead-spring model of self-assembling equilibrium ("living") polymers is used to study the polymer-induced interaction between parallel walls immersed in polydisperse solutions of different concentration by means of Monte Carlo simulation. The two walls form an open slit in contact with an external reservoir so that the confined system may exchange monomers with the surrounding phase and adapt its polydispersity in order to relax the confinement constraint. We find that the properties of the polymers in the constrained system as well as the net force deltaF acting on the walls depend essentially on the polymer concentration in the reservoir which leads to qualitative differences in their behavior with changing inter-planar distance H: In a dilute polymer solution at concentration phi below the semi-dilute threshold phi* the force between the walls is attractive and decreases steadily with growing wall separation H, so that deltaF approximately 0 at H/ Rg> or =3 if H is measured in gyration radii Rg of the unperturbed polymers. The total monomer concentration within the slit is smaller than the concentration in the reservoir and decreases monotonically with H/Rg-->0. The ratio Nin/Nout of mean chain length Nin in the slit to that in the reservoir, Nout, decreases from unity at H-->infinity, goes through a minimum at H/Rg approximately 1, and then rises again to Nin/Nout>1 for wall separations H/Rg<1. In contrast, in a dense solution of equilibrium polymers at phi>phi* one detects no indirect wall-wall interaction, deltaF approximately 0, for H larger than the monomer size. Thus, earlier speculations about the existence of possible depletion interaction between parallel walls even in a dense polymer system cannot be confirmed. Inside the slit the monomer density is found to be always larger than in the reservoir while Nin/Nout<1 and decreases steadily as H/Rg-->0. The depletion force between parallel plates has been determined also in a monodisperse solution of conventional polymers. Qualitatively the force behavior does not differ from that of living polymers.     

Kinetic-diffusion asymptotic-preserving Monte Carlo algorithms for plasma edge neutral simulation

We developed novel Monte Carlo simulation strategies for the neutral model in plasma edge simulations where both low-collisional and high-collisional regimes are present. To maintain accuracy and reduce simulation costs in high-collisional regimes, we use hybridized particles that exhibit both kinetic and diffusive behaviour depending on the local collisionality. The method maintains an asymptotically correct distribution and a correct mean, variance, and time correlation for all values of the collisionality. We apply this scheme to a fusion case with a strongly heterogeneous background, prompting the inclusion of a diffusion-induced drift. Our numerical results show a large increase in efficiency at the expense of a minor bias.