First-Passage Monte Carlo Algorithm: Diffusion without All the Hops

We present a novel Monte Carlo algorithm for $N$ diffusing finite particles that react on collisions. Using the theory of first-passage processes and time dependent Green’s functions, we break the difficult $N$-body problem into independent single- and two-body propagations circumventing numerous diffusion hops used in standard Monte Carlo simulations. The new algorithm is exact, extremely efficient, and applicable to many important physical situations in arbitrary integer dimensions.

Figure 1

Diffusing particles (small closed circles) numbered 1 to 7 are protected by nonoverlapping PDs (larger open circles). Particle 7 is propagated to the surface of its PD because its arrival time (${\tau }_7$) is shortest among all particles. It is moved to a random position on its protective circle, a new nonoverlapping protective circle is drawn around its new position and the time is advanced to ${\tau }_7$.

Figure 2

Comparison between the standard KMC calculations (crosses) and the first-passage KMC (circles) results. (a) Discrete-time discrete-space simulations of $A+A\Rightarrow A$ coalescence reaction in 1D. (b) Continuous-time continuum-space simulations of $A+A\Rightarrow 0$ annihilation reaction in 3D. Note that each circle is filled with a cross, indicating agreement.

Figure 3

(a) Computational performance as a function of particle density measured in six independent realizations of $A+A\Rightarrow 0$ annihilation reaction in 3D performed on a single CPU workstation using the standard KMC calculations with a finite hop distance (upper symbols) and the new algorithm (lower symbols). The dashed and dotted lines are theoretical estimates with slopes of 1 for the standard KMC calculations and $1/3$ for the new algorithm. (b) Kinetics of $A+A\Rightarrow 0$ annihilation reaction in 1D, using replication. The inset is the logarithmic derivative of the kinetic curve taken over the same time interval reproducing the theoretical exponent $\alpha =0.5$ for this reaction.

Figure 4

A thin slice through the domain structure formed in a simulation of $A+B\Rightarrow 0$ reaction in 3D. The boundaries of the $A$-rich (red) and $B$-rich (blue) domains are identified with the sides of Voronoi polyhedra shared by unlike particles. The two domains are complementary and fill the space when brought together.