In this paper we study from a numerical analysis perspective the Fractional
Step Kinetic Monte Carlo (FS-KMC) algorithms proposed in [1] for the parallel
simulation of spatially distributed particle systems on a lattice. FS-KMC are
fractional step algorithms with a time-stepping window $\Delta t$, and as such
they are inherently partially asynchronous since there is no processor
communication during the period $\Delta t$. In this contribution we primarily
focus on the error analysis of FS-KMC algorithms as approximations of
conventional, serial kinetic Monte Carlo (KMC). A key aspect of our analysis
relies on emphasising a goal-oriented approach for suitably defined macroscopic
observables (e.g., density, energy, correlations, surface roughness), rather
than focusing on strong topology estimates for individual trajectories.
One of the key implications of our error analysis is that it allows us to
address systematically the processor communication of different parallelization
strategies for KMC by comparing their (partial) asynchrony, which in turn is
measured by their respective fractional time step $\Delta t$ for a prescribed
error tolerance.
We present a mathematical framework for constructing and analyzing parallel
algorithms for lattice Kinetic Monte Carlo (KMC) simulations. The resulting
algorithms have the capacity to simulate a wide range of spatio-temporal scales
in spatially distributed, non-equilibrium physiochemical processes with complex
chemistry and transport micro-mechanisms. The algorithms can be tailored to
specific hierarchical parallel architectures such as multi-core processors or
clusters of Graphical Processing Units (GPUs). The proposed parallel algorithms
are controlled-error approximations of kinetic Monte Carlo algorithms,
departing from the predominant paradigm of creating parallel KMC algorithms
with exactly the same master equation as the serial one.
Our methodology relies on a spatial decomposition of the Markov operator
underlying the KMC algorithm into a hierarchy of operators corresponding to the
processors' structure in the parallel architecture. Based on this operator
decomposition, we formulate Fractional Step Approximation schemes by employing
the Trotter Theorem and its random variants; these schemes, (a) determine the
communication schedule} between processors, and (b) are run independently on
each processor through a serial KMC simulation, called a kernel, on each
fractional step time-window.
Furthermore, the proposed mathematical framework allows us to rigorously
justify the numerical and statistical consistency of the proposed algorithms,
showing the convergence of our approximating schemes to the original serial
KMC. The approach also provides a systematic evaluation of different processor
communicating schedules.