Cell lists on arvau

Wikipedia / Cell lists

Cell lists (also sometimes referred to as cell linked-lists) is a data structure in molecular dynamics simulations to find all atom pairs within a given cut-off distance of each other. These pairs are needed to compute the short-range non-bonded interactions in a system, such as Van der Waals forces or the short-range part of the electrostatic interaction when using Ewald summation.

Algorithm

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.

are computed as follows:

for all do
1. for all do
  1. for all do
    1. if then
      1. .
      end if
    end for
  end for
end for

of each other can be missed.

pairwise distances naively.

Periodic boundary conditions

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.

Ghost cells

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.

Periodic wrapping

is then computed as

needs to be computed/stored).

Improvements

, the cell list algorithm listed above still has some inefficiencies.

. In other words, 84% of all pairwise distance computations are spurious.

of each other (first suggested in and implemented and analysed in and , however, already reduces the number of spurious distance evaluations to 63%.

Another approach is outlined and tested in Gonnet, in which the particles are first sorted along the axis connecting the cell centers. This approach generates only about 40% spurious pairwise distance computations, yet carries an additional cost due to sorting the particles.