Cell lists

Cell lists work by subdividing the simulation domain into cells with an edge length greater than or equal to the cut-off radius of the interaction to be computed. The particles are sorted into these cells and the interactions are computed between particles in the same or neighbouring cells.

In its most basic form, the non-bonded interactions for a cut-off distance ${\displaystyle r_{c}}$ are computed as follows:

for all neighbouring cell pairs ${\displaystyle (C_{\alpha },C_{\beta })}$ do

for all ${\displaystyle p_{\alpha }\in C_{\alpha }}$ do

for all ${\displaystyle p_{\beta }\in C_{\beta }}$ do

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

if ${\displaystyle r^{2}\leq r_{c}^{2}}$ then

Compute the interaction between ${\displaystyle p_{\alpha }}$ and ${\displaystyle p_{\beta }}$.

end if

end for

end for

end for

Since the cell length is at least ${\displaystyle r_{c}}$ in all dimensions, no particles within ${\displaystyle r_{c}}$ of each other can be missed.

Given a simulation with ${\displaystyle N}$ particles with a homogeneous particle density, the number of cells ${\displaystyle m}$ is proportional to ${\displaystyle N}$ and inversely proportional to the cut-off radius (i.e. if ${\displaystyle N}$ increases, so does the number of cells). The average number of particles per cell ${\displaystyle {\overline {c}}=N/m}$ therefore does not depend on the total number of particles. The cost of interacting two cells is in ${\displaystyle {\mathcal {O}}({\overline {c}}^{2})}$. The number of cell pairs is proportional to the number of cells which is again proportional to the number of particles ${\displaystyle N}$. The total cost of finding all pairwise distances within a given cut-off is in ${\displaystyle {\mathcal {O}}(Nc)\in {\mathcal {O}}(N)}$, which is significantly better than computing the ${\displaystyle {\mathcal {O}}(N^{2})}$ pairwise distances naively.

Summarize Timeline Fact Check

In most simulations, periodic boundary conditions are used to avoid imposing artificial boundary conditions. Using cell lists, these boundaries can be implemented in two ways.

In the ghost cells approach, the simulation box is wrapped in an additional layer of cells. These cells contain periodically wrapped copies of the corresponding simulation cells inside the domain.

Although the data—and usually also the computational cost—is doubled for interactions over the periodic boundary, this approach has the advantage of being straightforward to implement and very easy to parallelize, since cells will only interact with their geographical neighbours.

Instead of creating ghost cells, cell pairs that interact over a periodic boundary can also use a periodic correction vector ${\displaystyle \mathbf {q} _{\alpha \beta }}$. This vector, which can be stored or computed for every cell pair ${\displaystyle (C_{\alpha },C_{\beta })}$, contains the correction which needs to be applied to "wrap" one cell around the domain to neighbour the other. The pairwise distance between two particles ${\displaystyle p_{\alpha }\in C_{\alpha }}$ and ${\displaystyle p_{\beta }\in C_{\beta }}$ is then computed as

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

This approach, although more efficient than using ghost cells, is less straightforward to implement (the cell pairs need to be identified over the periodic boundaries and the vector ${\displaystyle \mathbf {q} _{\alpha \beta }}$ needs to be computed/stored).