Lesson 2.6 · 14 min

Neighbour lists

Even with a cutoff, checking every pair still costs N². Neighbour lists remember who is close, and cell lists find them in linear time. Together they make large simulations possible.

The idea

A cutoff (Lesson 2.5) tells us which pairs to compute, but to know which pairs are inside rc we still measure all N(N−1)/2 distances. At N = 100,000 that is 5 × 109 tests per step, almost all of them for atoms far apart.

Verlet list. Atoms move only about 0.01σ per step. So once in a while, list every pair closer than rc + skin, and for the next steps test only those pairs. The list is still correct as long as no atom has moved more than skin/2 since it was built. (Two atoms moving towards each other by skin/2 each close the gap of one skin.) When any atom passes skin/2, rebuild.

Cell list. Divide the box into cells at least rc wide. A neighbour of an atom must then be in its own cell or one of the adjacent cells: 9 cells in 2D, 27 in 3D. Each cell holds a fixed number of atoms at fixed density, so the search costs O(N) instead of O(N²).

Both together. Real codes build the Verlet list with a cell list (cells of size rc + skin), then reuse the list for 10–20 steps. LAMMPS: neighbor 0.3 bin and neigh_modify every 1 delay 0 check yes. GROMACS: cutoff-scheme = Verlet, with nstlist and an automatic buffer (rlist).

Key idea. Build a list of pairs within rc + skin using cells (O(N)), reuse it until some atom moves skin/2, then rebuild. A skin of about 0.3σ (0.1–0.2 nm in force fields) is typical.

The algorithm

Inside the MD loop:

every step:
    if list is empty or max |pos - pos_at_build| > skin / 2:
        put atoms into cells of size ≥ rc + skin
        list = []
        for each cell, for each of its 27 neighbour cells:
            for each pair i < j in these two cells:
                if |min_image(pos[i] - pos[j])| < rc + skin:
                    list.append((i, j))
        pos_at_build = pos
    for (i, j) in list:                  # forces only from the list
        if r2(i, j) < rc2: add LJ force
  1. Cells need at least 3 per side, so the box must be at least 3(rc + skin) wide. For small boxes, fall back to all pairs.
  2. Measure displacements with the minimum image, since atoms wrap through the walls.
  3. Too small a skin: rebuilds every few steps. Too large: a long list full of pairs outside rc. Test a few values and pick the fastest.
  4. Always check: forces with the list must match an all-pairs calculation. A skin that is too small, or skipping the check, silently loses pairs.

See it inside LAMMPS

The same idea in the real code, run live in your browser and checked by hand.