Improvements
Despite reducing the computational cost of finding all pairs within a given cut-off distance from to, the cell list algorithm listed above still has some inefficiencies.
Consider a computational cell with edge length equal to the cut-off radius . 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 be less than or equal to . In other words, 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 . The pairwise interactions are then not just computed between neighboring cells, but between all cells within of each other (first suggested in and implemented and analysed in, and ). 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 that need to be inspected for every interaction with a cell, which, for example in 3d, grows cubically with the inverse of the cell edge length. Setting the edge length to, however, already reduces the number of spurious distance evaluations to 63%.
Another approach is outlined and tested in, 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.
Read more about this topic: Cell Lists
Famous quotes containing the word improvements:
“I was interested to see how a pioneer lived on this side of the country. His life is in some respects more adventurous than that of his brother in the West; for he contends with winter as well as the wilderness, and there is a greater interval of time at least between him and the army which is to follow. Here immigration is a tide which may ebb when it has swept away the pines; there it is not a tide, but an inundation, and roads and other improvements come steadily rushing after.”
—Henry David Thoreau (1817–1862)
“... these great improvements of modern times are blessings or curses on us, just in the same ratio as the mental, moral, and religious rule over the animal; or the animal propensities of our nature predominate over the intellectual and moral. The spider elaborates poison from the same flower, in which the bee finds materials out of which she manufactures honey.”
—Harriot K. Hunt (1805–1875)
“A country whose buildings are of wood, can never increase in its improvements to any considerable degree.... Whereas when buildings are of durable materials, every new edifice is an actual and permanent acquisition to the state, adding to its value as well as to its ornament.”
—Thomas Jefferson (1743–1826)