Método de Montecarlo cinético

El método de Monte-Carlo cinético, KMC (de las siglas en inglés kinetic Monte Carlo) es un tipo de Método de Montecarlo de simulación ideado para simular la evolución temporal de algunos procesos que ocurren en la naturaleza con una frecuencia (tasa de ocurrencia) dada. Es importante hacer notar y comprender que dichas tasas son inputs para el algoritmo KMC, i.e. el algoritmo per se no puede predecir la tasa de ocurrencia del proceso.

El método KMC en esencia es equivalente a los métodos dynamic Monte Carlo method y Gillespie algorithm. La principal diferencia entre ellos, parece ser, es la terminología y las áreas de aplicación: KMC se utiliza principalmente en física mientras que dMC o GSA se suelen utilizar en química.

Esquema del algoritmo

En cada iteración, el sistema puede realizar una transición a varios estados finales, siendo supuesto que todas las tasas de transición desde el estado inicial hasta los posibles estados finales son conocidas.

El algoritmo KMC para simular la evolución temporal de un sistema donde ciertos procesos pueden ocurrir con ciertas (conocidas) tasas, r, puede esquematizarse de la forma que sigue:

Elección del estado final: se sortea una variable aleatoria entre 0 y Γ_tot; la probabilidad de que el sistema pase al estado $i$ es proporcional a Γ_i.

1. Fijar el instante inicial $t=0$.
2. Crear una lista de todas las posibles tasas de transición en el sistema $r_{i}$
3. Calcular la función cumulativa $R_{i}=\sum _{j=1}^{i}r_{j}$ para todo $i=1,\ldots ,N$, donde N es el número total de transiciones.
4. Generar un número aleatorio en arreglo a una distribución uniforme, $u\in (0,1]$
5. Encontrar la transición que se llevará a cabo, $i$, siendo $i$ aquel índice para el cual se cumpla $R_{i-1}<uR_{N}\leq R_{i}$ (esta búsqueda puede realizarse eficientemente mediante el uso de una búsqueda binaria, binary search).
6. Llevar a cabo la transición $i$.
7. Generar un nuevo número aleatorio de distribución uniforme, $u^{\prime }\in (0,1]$.
8. Actualizar el tiempo mediante $t=t+\Delta t$, donde $\Delta t=R_{N}^{-1}\ln(1/u^{\prime })$.
9. Recalcular todas las tasas $r_{i}$, dado que éstas pueden haber cambiado debido a la transición ocurrida. Si se diera el caso, eliminar o añadir nuevas transiciones $i$. En consecuencia, actualizar N y la lista de sucesos.
10. Volver al paso 2.

(Nota: dado que el valor medio de $\ln(1/u^{\prime })$ es igual a la unidad, se puede obtener la misma escala temporal promedio usando $\Delta t=R_{N}^{-1}$ en el paso 8. En tal caso, sin embargo, el lapso temporal asociado con la transición $i$ no se extraerá de la distribución de Poisson descrita por $r_{i}$, sino que será en su lugar la media de dicha distribución.)

Este algoritmo puede ser mencionado en diferentes y diversas fuentes como algoritmo de tiempo de residencia (residence-time algorithm) o n-fold way o como el algoritmo Bortz-Kalos-Lebowitz (BKL) o simplemente como algoritmo kinetic Monte Carlo (KMC). Es importante hacer notar que el paso de tiempo involucrado es una función de la probabilidad de que no ocurra ninguno de los sucesos $i$.

Algoritmos con dependencia temporal

En el caso en el que las tasas de transición dependan del tiempo, i.e. $r_{i}(t)$, como resulta evidente el paso 8 en el esquema anterior tiene que modificarse por (Prados 1997):

$\int _{0}^{\Delta t}R_{i}(t')dt'=\ln(1/u^{\prime })$.

En cuyo caso, la transición que tendrá lugar (paso 5) ha de ser elegida después de esto mediante

$R_{i-1}(\Delta t)<uR_{N}(\Delta t)\leq R_{i}(\Delta t)$

Otro algoritmo muy similar a este es el también conocido como el método de primera reacción (First Reaction Method (FRM)), consistente en elegir la primera reacción, lo que significa elegir el menor tiempo $\Delta t_{i}$, y el correspondiente índice de reacción $i$, a partir de la siguiente ecuación

$\int _{0}^{\Delta t_{i}}r_{i}(t')dt'=\ln(1/u_{i})$,

donde $u_{i}\in (0,1]$ son N números aleatorios.

Comentarios sobre el algoritmo

La principal y más importante característica del método KMC (también del método FRM) es que en caso de que las tasas sean correctas, si los procesos considerados son te tipo proceso de Poisson y si los diferentes procesos son estadísticamente independientes ( i.e. no están correlacionados), entonces el algoritmo KMC (o FRM) devuelve una escala temporal realista y correcta para la evolución del sistema simulado.

Si además las transiciones siguen una relación de balance detallado, el algoritmo se puede utilizar para simular el equilibrio termodinámico. Sin embargo, el método KMC normalmente se utiliza para simular procesos de no equilibrio (Meng 1994), en cuyo caso las relaciones de balance detallado no serán satisfechas.

El algoritmo KMC es eficiente en el sentido que cada iteración garantiza una transición. No obstante, en el esquema presentado anteriormente ello requiere $N$ operaciones para cada transición, lo cual no es muy eficiente desde el punto de vista computacional. En muchas ocasiones ésta puede ser mejorada notablemente mediante el agrupamiento de transiciones del mismo tipo en contenedores (bins), y/o formando estructura de datos en árbol de los sucesos. Un algoritmo de este tipo ha sido recientemente publicado y probado en (Slepoy 2008).

La mayor desventaja de los métodos KMC es que para reproducir con fidelidad el sistema bajo consideración se tienen que conocer todas y cada una de las reacciones (transiciones) y sus respectivas tasas de ocurrencia. El método por sí mismo no puede hacer predicciones en este respecto.

Historia

La primera publicación que describió las características básicas del modelo KMC (e.g. usar una función cumulativa para seleccionar una transición y un cálculo de la escala temporal del tipo 1/R) data de 1966 y sus autores Young and Elcock (Young 1966). El algoritmo de tiempo de residencia también se publicó por esa fecha, (Cox 1965).

De forma independiente al trabajo de Young y Elcock, al parecer, Bortz, Kalos and Lebowitz (Bortz 1975) desarrollaron un algoritmo KMC para simular el Modelo de Ising, el cual llamaron n-fold way. Las bases de su algoritmo son las mismas que en el caso de (Young 1996), aunque ellos proporcionaron muchos más detalles sobre el método.

En los años sucesivos, Dan Gillespie publicó lo que hoy en día es conocido como el método de Gillespie para describir sistemas de reacciones químicas (Gillespie, 1976). El algoritmo es muy similar y la técnica de avance temporal es esencialmente la misma que en el KMC.

Desde la fecha de este documento (junio de 2006) no hay un tratado definitivo de la teoría del KMC, aunque Fichthorn y Weinberg han tratado en gran detalle la teoría para simulaciones KMC en equilibrio termodinámico en (Fichthorn 1991). También existe una muy buena introducción al método escrita por Art Voter (Voter 2005),[1] y por A.P.J. Jansen (Jansen 2003),[2]. Por último (Chatterjee 2007) or (Chotia 2008) es un review del tema relativamente reciente.

En marzo de 2006, el primer software comercial que hace uso de KMC para simular la difusión y la activación/desactivación de dopantes en Silicio y materiales tipo Silicio fue liberado por Synopsys, notificado por Martin-Bragado et al. (Martin-Bragado 06).

Variedades de KMC

El método KMC puede ser categorizado por cómo los objetos se mueven o las reacciones tienen lugar. Las siguientes subdivisiones son las más utilizadas:

• Lattice KMC (LKMC) que significa que el método KMC se lleva a cabo en una red atómica. En ocasiones esta variedad también se puede encontrar designada como atomistic KMC (AKMC).

• Object KMC (OKMC) donde KMC se lleva a cabo con defectos or impurezas, las cuales se encuentran saltando bien aleatoriamente, bien en direcciones preferenciales. Tan sólo se incluyen las posiciones de los objetos en movimiento en la simulación, a diferencia de aquellos que forman parte de la red de fondo.

• Event KMC (EKMC) o First-passage KMC (FPKMC) que es una variedad de OKMC donde la siguiente reacción entre objetos (e.g. agrupación de dos, aniquilación por pares, etc.) se elige con un algoritmo KMC, teniendo en cuenta la posición de los objetos (Dalla Torre 2005, Oppelstrup 2006).

Enlaces externos

• 3D lattice kinetic Monte Carlo simulation in 'bit language'
• KMC simulation of the Plateau-Rayleigh instability
• KMC simulation of f.c.c. vicinal (100)-surface diffusion

Referencias

• (Cox 1965): D.R. Cox and H.D. Miller, The Theory of Stochastic Processes (Methuen, London, 1965, pp 6–7.

• (Young 1966): W. M. Young and E. W. Elcock, Proceedings of the Physical Society 89 (1966) 735.

• (Bortz 1975): A. B. Bortz and M. H. Kalos and J. L. Lebowitz, Journal of Computational Physics 17 (1975) 10 Journal of Computational Physics 17 (1975) 10 (needs subscription)

• (Gillespie 1976): D. T. Gillespie, Journal of Computational Physics 22 (1976) 403

• (Fichthorn 1991): K. A. Fichthorn and W. H. Weinberg, Journal of Chemical Physics 95 (1991) 1090 (needs subscription)

• (Meng 1994): B. Meng and W. H. Weinberg, J. Chem. Phys. 100, 5280 (1994).

• (Meng 1996): B. Meng, W.H. Weinberg, Surface Science 364 (1996) 151-163.

• (Prados 1997): A. Prados, J. J. Brey and B. Sanchez-Rey, Journal of Statistical Physics 89, 709-734 (1997)

• (Jansen 2003): A.P.J. Jansen, An Introduction To Monte Carlo Simulations Of Surface Reactions, Condensed Matter, abstract cond-mat/0303028.

• (Dalla Torre 2005): J. Dalla Torre, J.-L. Bocquet, N.V. Doan, E. Adam and A. Barbu, Phil. Mag. 85 (2005), p. 549.

• (Voter 2005): A. F. Voter, Introduction to the Kinetic Monte Carlo Method, in Radiation Effects in Solids, edited by K. E. Sickafus and E. A. Kotomin (Springer, NATO Publishing Unit, Dordrecht, The Netherlands, 2005).

• (Opplestrup 2006): T. Opplestrup, V. V. Bulatov, G. H. Gilmer, M. H. Kalos, and B. Sadigh, First-Passage Monte Carlo Algorithm: Diffusion without All the Hops, Physical Review Letters 97, 230602 (2006)

• (Chatterjee 2007): A. Chatterjee and D. G. Vlachos, An overview of spatial microscopic and accelerated kinetic Monte Carlo methods, J. Computer-Aided Mater. Des. 14, 253 (2007).

• (Chotia 2008): A. Chotia, M. Viteau, T. Vogt, D. Comparat and P. Pillet, Kinetic Monte Carlo modelling of dipole blockade in Rydberg excitation experiment, New Journal of Physics 10 pages 045031 (2008)

• (Martínez 2008): E.Martínez, J.Marian, M.H.Kalos, J.M.Perlado, Synchronous Parallel Kinetic Monte Carlo for Continuum Diffusion-Reaction Systems, Journal of Computational Physics, Volume 227, Issue 8, 1 April 2008, Pages 3804-3823

• (Martin-Bragado 2008): I. Martin-Bragado, S. Tian, M. Johnson, P. Castrillo, R. Pinacho, J. Rubio and M. Jaraiz, Modeling charged defects, dopant diffusion and activation mechanisms for TCAD simulations using kinetic Monte Carlo. Nuclear Instruments and Methods in Physics Research B, 253 (2006) 63-67 (needs subscription).

• (Slepoy 2008): A. Slepoy, A. P. Thompson, and S. J. Plimpton, A constant-time kinetic Monte Carlo algorithm for simulation of large biochemical reaction networks, Journal of Chemical Physics, Volume 128, Issue 20, December 2007, Page 205101

• (Baeurle 2006): S.A. Baeurle, T. Usami and A.A. Gusev, Polymer 47 (2006) 8604 [3].

• (Serebrinsky 2011): S.A. Serebrinsky, Physical time scale in kinetic Monte Carlo simulations of continuous-time Markov chains, Physical Review E, Volume 83, Issue 3, March 2011, Paper no. 037701 [4]

• Datos: Q3333611