To use all functions of this page, please activate cookies in your browser.
my.chemeurope.com
With an accout for my.chemeurope.com you can always see everything at a glance – and you can configure your own website and individual newsletter.
 My watch list
 My saved searches
 My saved topics
 My newsletter
Cell listsCell lists (also sometimes referred to as Cell linkedlists) are a tool for finding all atom pairs within a given cutoff distance of each other in Molecular dynamics simulations. These pairs are needed to compute the shortrange nonbonded interactions in a system, such as Van der Waals forces or the shortrange part of the electrostatic interaction when using Ewald summation.
Additional recommended knowledge
AlgorithmCell lists work by subdividing the simulation domain into cells with an edge length greater than or equal to the cutoff 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 nonbonded interactions for a cutoff distance r_{c} are computed as follows:
Since the cell length is at least r_{c} in all dimensions, no particles within r_{c} of each other can be missed. Given a simulation with N particles with a homogeneous particle density, the number of cells m is proportional to N and the cutoff radius (i.e. if N increases, so does the number of cells). The average number of particles per cell therefore does not depend on the total number of particles. The cost of interacting two cells is in . The number of cell pairs is proportional to the number of cells which is again proportional to the number of particles N. The total cost of finding all pairwise distances within a given cutoff is in , which is significantly better than computing the pairwise distances naively. Periodic Boundary ConditionsIn 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 CellsIn 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 WrappingInstead of creating ghost cells, cell pairs that interact over a periodic boundary can also use a periodic correction vector . This vector, which can be stored or computed for every cell pair (C_{α},C_{β}) 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 and is then computed as
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 needs to be computed/stored). ImprovementsDespite reducing the computational cost of finding all pairs within a given cutoff distance from to , the cell list algorithm listed above still has some inefficiencies. Consider a computational cell with edge length equal to the cutoff radius r_{c}. The pairwise distance between all particles in the cell and in one of the neighbouring cells is computed. The cell has 26 neighbours: 6 sharing a common face, 12 sharing a common edge and 8 sharing a common corner. Of all the pairwise distances computed, only about 16% percent will actually less or equal r_{c}. Otherwise put, 84% of all pairwise distance computations are spurious. One way of overcoming this inefficiency is to partition the domain into cells of edge length smaller than r_{c}. The pairwise interactions are then not just computed between neighboring cells, but between all cells within r_{c} of each other (first suggested in ^{[1]} and implemented and analysed in ^{[2]}, ^{[3]} and ^{[4]}). This approach can be taken to the limit wherein each cell holds at most one single particle, therefore reducing the number of spurious pairwise distance evaluations to zero. This gain in efficiency, however, is quickly offset by the number of cells C_{β} that need to be inspected for every interaction with a cell C_{α}, which grows cubically with the inverse of the cell edge length. Setting the edge length to r_{c} / 2, however, already reduces the number of spurious distance evaluations to 63%. Another approach outlined in ^{[5]}, where 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. References
Categories: Molecular dynamics  Computational chemistry  Molecular physics 

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Cell_lists". A list of authors is available in Wikipedia. 