Verlet neighbour list with skin-radius temporal caching. More...

#include "cell_list.hpp"
#include <vector>
#include <cmath>
#include <utility>

Classes
class	num::VerletList2D< Scalar >

Namespaces
namespace	num

Detailed Description

Verlet neighbour list with skin-radius temporal caching.

Algorithm (CS theory: amortized analysis via skin-radius invariant)

Building a cell list costs O(n + C) every timestep. For large n this is non-trivial. The Verlet list amortizes this over multiple steps:

build() – O(n*k_ext) using the underlying CellList2D Store, for each particle i, all neighbours j within the extended cutoff r_ext = cutoff + skin. Also snapshot positions.

needs_rebuild(pos) – O(n) per timestep If max |Deltar_i| > skin/2 since last build -> return true. Invariant: while max displacement < skin/2, every true neighbour within cutoff is guaranteed to still be in the cached list. (Any particle that has entered the cutoff from outside must have crossed the skin shell first, which triggers a rebuild.)

neighbors(i) – O(1) per query, O(k) inner-loop iteration Returns the cached IntRange for particle i. Caller still checks |r_ij| < cutoff to skip stale far entries.

When does Verlet pay off?

Let tau = steps between rebuilds (determined by skin and particle speed). Cost per step with Verlet: O(n*k_ext / tau + n*k_ext) up build up force eval (same work) Cost per step without Verlet: O(n + C + n*k) up cell list rebuild each step

Verlet wins when tau is large (slow physics, small dt, big skin) and n is large enough that O(n+C) build cost is significant relative to O(n*k) force eval. For SPH with c0=10 m/s, dt=1 ms, h=0.025 m the skin choice ~0.5h gives tau ~= 1-3 steps – borderline. For softer (slower) physics or larger n, the benefit is clear.

Template Parameters

Scalar float or double

Definition in file verlet_list.hpp.

Classes

Namespaces

Detailed Description