Cell lists

Cell lists

Cell lists (also sometimes referred to as Cell linked-lists) are a tool for finding all atom pairs within a given cut-off distance of each other in Molecular dynamics simulations. 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.

In its most basic form, the non-bonded interactions for a cut-off distance r_c are computed as follows:

:for all neighbouring cell pairs (C_alpha, C_eta) do::for all p_alpha in C_alpha do:::for all p_eta in C_eta do::::r^2 = | mathbf x [p_alpha] - mathbf x [p_eta] |_2^2::::if r^2 le r_c^2 then:::::Compute the interaction between p_alpha and p_eta.::::end if:::end for::end for:end for

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 cut-off radius (i.e. if N increases, so does the number of cells). The average number of particles per cell overline{c} = N/m therefore does not depend on the total number of particles. The cost of interacting two cells is in 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 N. The total cost of finding all pairwise distances within a given cut-off is in mathcal O(Nc) in mathcal O(N), which is significantly better than computing the mathcal O(N^2) 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 straight-forward to implement and very easy to parallelize, since cells will only interact with their geographical neighbours.

Periodic Wrapping

Instead of creating ghost cells, cell pairs that interact over a periodic boundary can also use a periodic correction vector mathbf q_{alphaeta}. This vector, which can be stored or computed for every cell pair (C_alpha,C_eta) 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 p_alpha in C_alpha and p_eta in C_eta is then computed as

:r^2 = | mathbf x [p_alpha] - mathbf x [p_eta] - mathbf q_{alphaeta} |^2_2.

This approach, although more efficient than using ghost cells, is less straight-forward to implement (the cell pairs need to be identified over the periodic boundaries and the vector mathbf q_{alphaeta} needs to be computed/stored).

Improvements

Despite reducing the computational cost of finding all pairs within a given cut-off distance from mathcal O(N^2) to mathcal O(N), the cell list algorithm listed above still has some inefficiencies.

Consider a computational cell with edge length equal to the cut-off 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 [cite book| first=M. P. | last=Allen | coauthors=D. J. Tildesley | title=Computer Simulation of Liquids | publisher=Clarendon Press | location=Oxford | year=1987] and implemented and analysed in [cite journal | last=Mattson | first=W. | coauthors=B. M. Rice | title=Near-neighbor calculations using a modified cell-linked list method | journal=Computer Physics Communications | year=1999 | volume=119 | pages=135 | doi=10.1016/S0010-4655(98)00203-3 ] , [cite journal | last=Yao | first=Z. | coauthors=Wang, J.-S.; Liu, G.-R.; Cheng, M | title=Improved neighbor list algorithm in molecular simulations using cell decomposition and data sorting method | journal=Computer Physics Communications | year=2004 | volume=161 | pages=27 | doi=10.1016/j.cpc.2004.04.004 ] and [cite journal| last=Heinz | first=T. N. | coauthors=Hünenberger, P. H. | title=A fast pairlist-construction algorithmfor molecular simulations under periodic boundary conditions | journal=Journal of Computational Chem istry | year=2004 | volume=25 | pages=1474 | doi=10.1002/jcc.20071] ). This approach can betaken 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_eta that need to be inspected for every interaction with a cell C_alpha, 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 [cite journal| first=Pedro | last=Gonnet | title=A Simple Algorithm to Accelerate the Computation of Non-Bonded Interactions in Cell-Based Molecular Dynamics Simulations | journal=Journal of Computational Chemistry | volume=28 | issue=2 | pages=570–573 | doi=10.1002/jcc.20563 | year=2007 ] , 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.

ee also

* Software for molecular mechanics modeling

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Cell mobility — generally refers to motility, but may also refer to other ways of activation, such as cell differentiation and cell proliferation. This disambiguation page lists articles associated with the same title. If an internal link led you here, you may… …   Wikipedia

  • Cell (biology) — Allium cells in different phases of the cell cycle …   Wikipedia

  • Lists of health topics — NOTOC Health is the functional and metabolic efficiency of an organism. It is the ability to live long, function well (physically and mentally), and prosper.This collection of lists of health topics collects the names of topics related to health… …   Wikipedia

  • List of Splinter Cell characters — The following is a list of characters found throughout the Splinter Cell series of video games and novels. Contents 1 Major characters 1.1 Lieutenant Commander Samuel Sam Fisher, USN (Ret.) 1.2 Colonel Irving Lambert, USA (KIA) …   Wikipedia

  • List of topics in cell biology — Cell invokes a major branch of theory and research known variously as cell biology, cellular biology or cytology. The study of cell tissues is known as histology. Cell types are often referred to using the suffixes blast, clast, cyte, especially… …   Wikipedia

  • Outline of cell biology — Light micrograph of a moss s leaf cells at 400X magnification. The following outline is provided as an overview of and topical guide to cell biology: Cell biology (formerly cytology, from the Greek kytos, container ) – academic discipline that… …   Wikipedia

  • List of distinct cell types in the adult human body — There are about 210 distinct human cell types,.[1][2][3] There are between 50 and 75 trillion cells in the human body.[citation needed] Cell types can be classified by their tissue of origin. However, it is possible for some cells to have their… …   Wikipedia

  • Topic outline of cell biology — [ micrograph of a moss s leaf cells at 400X magnification.] : For a more comprehensive list, see the List of cell biology topics. Cell biology (formerly cytology, from the Greek kytos , container ) is an academic discipline that studies cells –… …   Wikipedia

  • Glossary of fuel cell terms — The Glossary of fuel cell terms lists the definitions of many terms used within the fuel cell industry. The terms in this glossary may be used by fuel cell industry associations, in education material and fuel cell codes and standards to name but …   Wikipedia

  • Squamous-cell carcinoma — Squamous cell carcinoma, NOS Classification and external resources SCC of the skin tends to arise from pre malignant lesions, actinic keratoses; surface is usually scaly and often ulcerates (as shown here). ICD 10 …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”