Listas de celdas

Las listas de celdas (también denominadas a veces listas enlazadas de celdas ) son una estructura de datos en simulaciones de dinámica molecular para encontrar todos los pares de átomos dentro de una distancia de corte dada entre sí. Estos pares son necesarios para calcular las interacciones no enlazadas de corto alcance en un sistema, como las fuerzas de Van der Waals o la parte de corto alcance de la interacción electrostática cuando se utiliza la suma de Ewald .

Algoritmo

Las interacciones por pares de una sola partícula se pueden calcular a) calculando la interacción con todas las demás partículas o b) dividiendo el dominio en celdas con una longitud de borde de al menos el radio de corte del potencial de interacción y calculando la interacción entre la partícula y todas las partículas en la misma celda (roja) y en las adyacentes (verde).

Las listas de celdas funcionan subdividiendo el dominio de simulación en celdas con una longitud de borde mayor o igual que el radio de corte de la interacción que se va a calcular. Las partículas se clasifican en estas celdas y se calculan las interacciones entre partículas en la misma celda o en celdas vecinas.

En su forma más básica, las interacciones no enlazadas para una distancia de corte se calculan de la siguiente manera: ${\displaystyle r_{c}}$

para todos los pares de celdas vecinas ${\displaystyle (C_{\alpha },C_{\beta })}$

para todos hacer ${\displaystyle p_{\alpha }\in C_{\alpha }}$

para todos hacer ${\displaystyle p_{\beta }\in C_{\beta }}$

${\displaystyle r^{2}=\|\mathbf {x} [p_{\alpha }]-\mathbf {x} [p_{\beta }]\|_{2}^{2}}$

Si entonces ${\displaystyle r^{2}\leq r_{c}^{2}}$

Calcular la interacción entre y . ${\displaystyle p_{\alpha }}$ ${\displaystyle p_{\beta }}$

terminar si

fin para

fin para

fin para

Dado que la longitud de la celda es al menos en todas las dimensiones, no se puede perder ninguna partícula dentro de las otras. ${\displaystyle r_{c}}$ ${\displaystyle r_{c}}$

Dada una simulación con partículas con una densidad de partículas homogénea, el número de células es proporcional e inversamente proporcional al radio de corte (es decir, si aumenta, también lo hace el número de células). Por lo tanto, el número promedio de partículas por célula no depende del número total de partículas. El costo de interactuar dos células está en . El número de pares de células es proporcional al número de células, que a su vez es proporcional al número de partículas . El costo total de encontrar todas las distancias por pares dentro de un corte dado está en , lo que es significativamente mejor que calcular las distancias por pares de manera ingenua. ${\displaystyle N}$ ${\displaystyle m}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle {\overline {c}}=N/m}$ ${\displaystyle {\mathcal {O}}({\overline {c}}^{2})}$ ${\displaystyle N}$ ${\displaystyle {\mathcal {O}}(Nc)\in {\mathcal {O}}(N)}$ ${\displaystyle {\mathcal {O}}(N^{2})}$

Condiciones de contorno periódicas

En la mayoría de las simulaciones, se utilizan condiciones de contorno periódicas para evitar imponer condiciones de contorno artificiales. Mediante listas de celdas, estos límites se pueden implementar de dos maneras.

Células fantasma

Las condiciones de límite periódicas se pueden simular envolviendo el cuadro de simulación en una capa adicional de celdas (sombreadas en naranja) que contienen copias periódicas de las celdas de límite (partículas azules).

En el enfoque de celdas fantasma, el cuadro de simulación se envuelve en una capa adicional de celdas. Estas celdas contienen copias envueltas periódicamente de las celdas de simulación correspondientes dentro del dominio.

Aunque los datos (y normalmente también el coste computacional) se duplican para las interacciones fuera del límite periódico, este enfoque tiene la ventaja de ser sencillo de implementar y muy fácil de paralelizar, ya que las células solo interactuarán con sus vecinos geográficos.

Envoltura periódica

En lugar de crear células fantasma, los pares de células que interactúan sobre un límite periódico también pueden utilizar un vector de corrección periódica . Este vector, que se puede almacenar o calcular para cada par de células , contiene la corrección que se debe aplicar para "envolver" una célula alrededor del dominio para que quede vecina de la otra. La distancia por pares entre dos partículas se calcula entonces como ${\displaystyle \mathbf {q} _{\alpha \beta }}$ ${\displaystyle (C_{\alpha },C_{\beta })}$ ${\displaystyle p_{\alpha }\in C_{\alpha }}$ ${\displaystyle p_{\beta }\in C_{\beta }}$

${\displaystyle r^{2}=\|\mathbf {x} [p_{\alpha }]-\mathbf {x} [p_{\beta }]-\mathbf {q} _{\alpha \beta }\|_{2}^{2}}$.

Este enfoque, aunque es más eficiente que el uso de células fantasma, es menos sencillo de implementar (los pares de células deben identificarse en los límites periódicos y el vector debe calcularse/almacenarse). ${\displaystyle \mathbf {q} _{\alpha \beta }}$

Mejoras

A pesar de reducir el costo computacional de encontrar todos los pares dentro de una distancia de corte dada de a , el algoritmo de lista de celdas mencionado anteriormente aún tiene algunas ineficiencias. ${\displaystyle {\mathcal {O}}(N^{2})}$ ${\displaystyle {\mathcal {O}}(N)}$

Considere una celda computacional en tres dimensiones con una longitud de borde igual al radio de corte . Se calcula la distancia por pares entre todas las partículas en la celda y en una de las celdas vecinas. La celda tiene 26 vecinas: 6 que comparten una cara común, 12 que comparten un borde común y 8 que comparten una esquina común. De todas las distancias por pares calculadas, solo alrededor del 16% será en realidad menor o igual a . En otras palabras, el 84% de todos los cálculos de distancia por pares son espurios. ${\displaystyle r_{c}}$ ${\displaystyle r_{c}}$

Una forma de superar esta ineficiencia es dividir el dominio en celdas con una longitud de borde menor que . Las interacciones por pares no solo se calculan entre celdas vecinas, sino entre todas las celdas entre sí (sugerido por primera vez en ^[1] e implementado y analizado en ^{[2] [3]} y ^[4] ). Este enfoque se puede llevar al límite en el que cada celda contiene como máximo una sola partícula, reduciendo así el número de evaluaciones de distancia por pares espurias a cero. Sin embargo, esta ganancia en eficiencia se ve rápidamente compensada por el número de celdas que deben inspeccionarse para cada interacción con una celda , que, por ejemplo en tres dimensiones, crece cúbicamente con la inversa de la longitud del borde de la celda. Sin embargo, establecer la longitud del borde en , ya reduce el número de evaluaciones de distancia espurias al 63%. ${\displaystyle r_{c}}$ ${\displaystyle r_{c}}$ ${\displaystyle C_{\beta }}$ ${\displaystyle C_{\alpha }}$ ${\displaystyle r_{c}/2}$

^{En Gonnet [5]} se describe y prueba otro enfoque en el que las partículas se clasifican primero a lo largo del eje que conecta los centros de las celdas. Este enfoque genera solo alrededor del 40 % de cálculos de distancia por pares espurios, pero conlleva un costo adicional debido a la clasificación de las partículas.

Véase también

• Lista de Verlet

Referencias

1. Allen, MP; DJ Tildesley (1987). Simulación por computadora de líquidos . Oxford: Clarendon Press.
2. Mattson, W.; BM Rice (1999). "Cálculos de vecinos cercanos utilizando un método de lista de celdas enlazadas modificado". Computer Physics Communications . 119 (2–3): 135. Bibcode :1999CoPhC.119..135M. doi :10.1016/S0010-4655(98)00203-3.
3. Yao, Z.; Wang, J.-S.; Liu, G.-R.; Cheng, M (2004). "Algoritmo de lista de vecinos mejorado en simulaciones moleculares utilizando el método de descomposición celular y ordenamiento de datos". Computer Physics Communications . 161 (1–2): 27–35. arXiv : physics/0311055 . Bibcode :2004CoPhC.161...27Y. doi :10.1016/j.cpc.2004.04.004. S2CID  7686860.
4. Heinz, TN; Hünenberger, PH (2004). "Un algoritmo rápido de construcción de listas de pares para simulaciones moleculares en condiciones de contorno periódicas". Journal of Computational Chemistry . 25 (12): 1474–86. doi :10.1002/jcc.20071. PMID  15224391. S2CID  10464744.
5. Gonnet, Pedro (2007). "Un algoritmo simple para acelerar el cálculo de interacciones no enlazadas en simulaciones de dinámica molecular basadas en células". Journal of Computational Chemistry . 28 (2): 570–573. doi :10.1002/jcc.20563. PMID  17183605. S2CID  31993082.