标题： 分层分数步近似和并行动力学蒙特卡罗算法 显示英文标题

标题： Hierarchical fractional-step approximations and parallel kinetic Monte Carlo algorithms

摘要： 我们提出了一种数学框架，用于构建和分析用于晶格动力蒙特卡罗（KMC）模拟的并行算法。 这些算法能够模拟空间分布的、非平衡的物理化学过程中广泛的时间和空间尺度，这些过程具有复杂的化学和传输微观机制。 这些算法可以针对特定的分层并行架构进行定制，例如多核处理器或图形处理单元（GPU）集群。 所提出的并行算法是对动力蒙特卡罗算法的误差可控近似，与创建与串行算法具有完全相同主方程的并行KMC算法的主要范式不同。 我们的方法依赖于对KMC算法底层马尔可夫算子的空间分解，将其分解为与并行架构中处理器结构相对应的一系列算子。 基于这种算子分解，我们通过采用Trotter定理及其随机变体来制定分数步近似方案；这些方案，(a) 确定处理器之间的通信计划，以及 (b) 通过在每个分数步时间窗口上运行一个称为内核的串行KMC模拟，在每个处理器上独立运行。 此外，所提出的数学框架使我们能够严格证明所提出算法的数值和统计一致性，表明我们的近似方案收敛到原始的串行KMC。 该方法还提供了一种对不同处理器通信计划的系统评估。 显示英文摘要

摘要： 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.