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 are computed as follows:
- for all neighbouring cell pairs do
- for all do
- for all do
- if then
- Compute the interaction between and .
- end if
- if then
- end for
- for all do
- end for
- for all do
- end for
Since the cell length is at least in all dimensions, no particles within of each other can be missed.
Given a simulation with particles with a homogeneous particle density, the number of cells is proportional to and inversely proportional to the cut-off radius (i.e. if 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 . The total cost of finding all pairwise distances within a given cut-off is in, which is significantly better than computing the pairwise distances naively.
Read more about this topic: Cell Lists