Integral Screening

The above boxing scheme is O(N), yet it is still inefficient. Figure 7.1 compares all those interactions considered with those that are actually significant.

  

Figure 7.1: The significant and computed interactions

With an interaction distance of R (which is WS+1 for the above implementation) a shell-pair in a box will interact with 26 neighbouring interaction-boxes and the current interaction-box (where an interaction-box is defined as the cube of boxes with a total sidelength of WS+1). Thus each shell-pair will interact with all others over a volume of 27 R³. Yet only those shell-pairs within a distance R of the current point need to be calculated. This produces a sphere of volume $\frac{4}{3}\pi R^{3}$.

If the efficiency of a method is defined to be
$$\begin{align}\epsilon = \frac{\mathrm{Number \; of \; significant \; interactions}}{\mathrm{Number \; of \; interactions \; computed}}, \end{align}$$
then the efficiency of the algorithm described above is only 15%! (It should be noted that in lower dimensions the efficiency is greater, 35% for 2D and 67% for 1D). This is an inherent deficiency of the linked-cell method.

There are several ways that the linked-cell method can be improved. One way is to order all particles by an increasing co-ordinate. Then, once the inter-shell-pair difference in this coordinate becomes greater than the interaction distance, interactions can be ignored. This requires sorting work and work to check the inter-shell-pair difference along this coordinate. This dramatically increases the efficiency in lower dimensions (100% and 52% for 1D and 2D respectively), but only yields a modest 23% efficiency for three-dimensional systems.

A second method is to change the basic cell structure. It has been suggested that the rhombic dodecahedron and truncated octahedron be used to tessellate space [201]. This allows a better approximation of a sphere than the cubes, but the cube is almost always used due to its geometric simplicity.

A third technique for increasing the efficiency is to reduce the basic cell size, increasing WS by a corresponding amount. This will allow better approximation of the sphere as the outlying corners of the interaction cube can be completely neglected. The trouble with this technique is that, in addition to a small amount of extra computational work, the vector loop lengths are drastically reduced.

A more useful compromise is to introduce a pre-screening routine. Just before looping over all shell-pairs to be interacted with a given shell-pair, the $\mathrm{T}_{\omega}$ values for all primitive shell-quartets are calculated, and if all are greater than T_crit the contracted shell-quartet does not need to be included, and so is removed from the interaction list. Thus, after the screening, only significant interactions will remain. This does introduce extra work (the calculated $\mathrm{T}_{\omega}$ values are not stored for the later integral calculation), but the possibility of removing 85% of the integrals makes this well worthwhile.