The kinetic Monte Carlo (KMC) method is a Monte Carlo method computer simulation intended to simulate the time evolution of some processes occurring in nature. Typically these are processes that occur with known transition rates among states. These rates are inputs to the KMC algorithm; the method itself cannot predict them. The KMC method is essentially the same as the dynamic Monte Carlo method and the Gillespie algorithm.
Algorithms One possible classification of KMC algorithms is as rejection-KMC (rKMC) and rejection-free-KMC (rfKMC).
Rejection-free KMC
A rfKMC algorithm, often only called KMC, for simulating the time evolution of a system, where some processes can occur with known rates r, can be written for instance as follows:
Set the time t = 0 {\displaystyle t=0} . Choose an initial state k. Form the list of all N k {\displaystyle N_{k}} possible transition rates in the system r k i {\displaystyle r_{ki}} , from state k into a generic state i. States that do not communicate with k will have r k i = 0 {\displaystyle r_{ki}=0} . Calculate the cumulative function R k i = ∑ j = 1 i r k j {\displaystyle R_{ki}=\sum _{j=1}^{i}r_{kj}} for i = 1 , … , N k {\displaystyle i=1,\ldots ,N_{k}} . The total rate is Q k = R k , N k {\displaystyle Q_{k}=R_{k,N_{k}}} . Get a uniform random number u ∈ ( 0 , 1 ] {\displaystyle u\in (0,1]} . Find the event to carry out i by finding the i for which R k , i − 1 < u Q k ≤ R k i {\displaystyle R_{k,i-1}<uQ_{k}\leq R_{ki}} (this can be achieved efficiently using binary search). Carry out event i (update the current state k → i {\displaystyle k\rightarrow i} ). Get a new uniform random number u ′ ∈ ( 0 , 1 ] {\displaystyle u^{\prime }\in (0,1]} . Update the time with t = t + Δ t {\displaystyle t=t+\Delta t} , where Δ t = Q k − 1 ln ( 1 / u ′ ) {\displaystyle \Delta t=Q_{k}^{-1}\ln(1/u^{\prime })} . Note that this time interval represents the time elapsed between the prior event and this one, rather than the time interval between this event and the next one. Return to step 3. (Note: because the average value of ln ( 1 / u ′ ) {\displaystyle \ln(1/u^{\prime })} is equal to unity, the same average time scale can be obtained by instead using Δ t = Q k − 1 {\displaystyle \Delta t=Q_{k}^{-1}} in step 9. In this case, however, the delay associated with transition i will not be drawn from the Poisson distribution described by the rate Q k {\displaystyle Q_{k}} , but will instead be the mean of that distribution.) This algorithm is known in different sources variously as the residence-time algorithm or the n-fold way or the Bortz-Kalos-Lebowitz (BKL) algorithm. The timestep involved is a function of the probability that all events i, did not occur.
Rejection KMC Rejection KMC has typically the advantage of an easier data handling, and faster computations for each attempted step, since the time consuming action of getting all r k i {\displaystyle r_{ki}} is not needed. On the other hand, the time evolved at each step is smaller than for rfKMC. The relative weight of pros and cons varies with the case at hand, and with available resources. An rKMC associated with the same transition rates as above can be written as follows:
… excerpt ends here. Continue reading the full article.
