2.6 Linked lists

For even larger particle numbers the cell volume $L^{3}$ is divided into $M^{3}$ subcells with side lengths $l \equiv L/M \leq r_{co}$.

Figure 2.6: For a particle $i$ in the shaded subcell, eligible interaction partners $j$ can be only from the subcells marked with a dot

Figure 2.7: To avoid duplication of pair property calculations, only the marked cells should be scanned for partners of a particle in the shaded cell. (But respect periodic b.c.!)

The following description follows the discussion found in Hockney's book [HOCKNEY, EASTWOOD: COMPUTER SIMULATION USING PARTICLES. McGraw-Hill, New York 1981].

Define two pointer arrays defined as follows:

• $hoc[k= 1 \dots M^{3}]$ (for ``head of chain''); its $k$-element contains the largest particle number of all inhabitants of cell $k$.
• $ll[i=1 \dots N]$ ( ``linked list''); number of the next (i.e. lower) particle in the presently treated cell; when $ll[i]=0$ that cell is finished.

Procedure:
In a language-free (but Fortran-like) form, proceed as follows:

	do 100 k=1,ncell // where usually ncell=M^3
100	hoc(k)=0
	do 200 i=1,n
	  icell=1+int(x(i)/cl)  //where cl=l=L/M
	         +int(y(i)/cl)*M
		 +int(z(i)/cl)*M*M
	  ll(i)=hoc(icell)
	  hoc(icell)=i
200	continue

These few quick steps may be performed at each MD or MC step to update the linked-cell pointer arrays. When it comes to calculating interactions, these arrays provide the information about possible partner molecules.

For clarity, consider this example:

Figure 2.8: Note: the cells are numbered from lower left (1) to upper right(9)

After nulling all arrays, the codelet does this:

i=1      icell=5     ll(1)=0     hoc(5)=1
i=2      icell=9     ll(2)=0     hoc(9)=2
i=3      icell=9     ll(3)=2     hoc(9)=3
i=4      icell=6     ll(4)=0     hoc(6)=4
i=5      icell=3     ll(5)=0     hoc(3)=5
i=6      icell=6     ll(6)=4     hoc(6)=6

Later, when it comes to scan the lists (force or energy calculation), we proceed thus:

For a particle (no. $1$) in cell $5$, we have to scan cells $3,(5),6,(8),9$ where the brackets denote those cells which in our example are empty of partners.

icell=3:     hoc(3)=5    --->   compute (1-5)     ll(5)=0

icell=6:     hoc(6)=6    --->   compute (1-6)     ll(6)=4
                         --->   compute (1-4)     ll(4)=0

icell=9:     hoc(9)=3    --->   compute (1-3)     ll(3)=2
                         --->   compute (1-2)     ll(2)=0