Listas de celdas

Las listas de celdas (también conocidas como listas enlazadas de celdas ) son una estructura de datos utilizada en simulaciones de dinámica molecular para encontrar todos los pares de átomos que se encuentran dentro de una distancia de corte determinada. 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 al utilizar la suma de Ewald .

Las listas de celdas funcionan subdividiendo el dominio de simulación en celdas con una longitud de arista mayor o igual al 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 que se encuentran en la misma celda o en celdas vecinas.

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

para todos los pares de células vecinas${\displaystyle (C_{\alpha },C_{\beta })}$hacer

a pesar de${\displaystyle p_{\alpha }\in C_{\alpha }}$hacer

a pesar de${\displaystyle p_{\beta }\in C_{\beta }}$hacer

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

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

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

fin si

fin para

fin para

fin para

Dado que la longitud de la célula es al menos${\displaystyle r_{c}}$en todas las dimensiones, no hay partículas dentro${\displaystyle r_{c}}$Se puede pasar por alto la presencia del otro.

Dado un simulacro con${\displaystyle N}$partículas con una densidad de partículas homogénea, el número de células${\displaystyle m}$es proporcional a${\displaystyle N}$y inversamente proporcional al radio de corte (es decir, si${\displaystyle N}$A medida que aumenta, también lo hace el número de células. El número promedio de partículas por célula${\displaystyle {\overline {c}}=N/m}$Por lo tanto, no depende del número total de partículas. El costo de interactuar dos células es en${\displaystyle {\mathcal {O}}({\overline {c}}^{2})}$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.${\displaystyle N}$El costo total de encontrar todas las distancias por pares dentro de un límite dado es de${\displaystyle {\mathcal {O}}(Nc)\in {\mathcal {O}}(N)}$, lo cual es significativamente mejor que calcular el${\displaystyle {\mathcal {O}}(N^{2})}$distancias por pares ingenuamente.

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

En el método de celdas fantasma, la caja 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 que superan el 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 vecinas geográficas.

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

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

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

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

• Lista de Verlet