元胞列表

subroutine new_nlist    rn = box/int(box/rc) ! 计算一个方向上的元胞个数。box为体系长度，rc为截断半径    do icel=0 , ncel - 1         hoc(icel) = 0    ! 对每一个元胞的链头置0    end do    do i = 1 , npart     ! 扫描所有粒子        icel = int(x(i)/rn)  ! 确定粒子所在的元胞编号        ll(i) = hoc（icel）! 链接icel元胞的链头        hoc(icel) = i        ! 将粒子编号i添加到链头    end doend subroutine

dx = dx - Lx*ANINT(dx/Lx)dy = dy - Ly*ANINT(dy/Ly)dz = dz - Lz*ANINT(dz/Lz)

造成很大的时间开销。元胞列表的引入可改进这一问题，主要有“幽灵元胞”和校正向量两种优化方案。

幽灵元胞通过在边界以外复制一层元胞解决周期性边界条件问题，这些复制的元胞拥有与原元胞完全相同的信息，这样在计算距离时就不再需要考虑周期性边界条件。此做法导致边界上的粒子的计算量会增加一倍（元胞在三维盒子的面上）甚至更多（元胞在三维盒子的棱或顶角），但这种方法非常直观且易于并行。

由于元胞的边界条件和粒子距离的边界条件是一致的，因此在搜索近邻元胞对时可导出一个向量${\displaystyle {\mathbf{q}}_{\mathrm{\alpha <!--\; \alpha \; -->}\mathrm{\beta <!--\; \beta \; -->}}}$来校正粒子间距离的计算。对于属于两个近邻元胞的两个粒子${\displaystyle p_{\mathrm{\alpha <!--\; \alpha \; -->}}\in <!--\; \in \; -->C_{\mathrm{\alpha <!--\; \alpha \; -->}}}$与${\displaystyle p_{\mathrm{\beta <!--\; \beta \; -->}}\in <!--\; \in \; -->C_{\mathrm{\beta <!--\; \beta \; -->}}}$，它们之间的距离按此式得出：

校正向量可以在扫描元胞时计算，也可在初始化时储存。此方法单核效率通常高于幽灵元胞，但其实现相对复杂，并且将计算距离的开销部分转移到扫描元胞中。

在最初的元胞列表中，每一个粒子会与27个元胞作用，体积为${\displaystyle 27r_c^3}$，相较截断半径球${\displaystyle \frac{4}{3}\mathrm{\pi <!--\; \pi \; -->}{r}_c^3}$，有84%的距离计算是不必要的。虽然复杂度从${\displaystyle \mathcal{O}(N^2)}$降至${\displaystyle \mathcal{O}(N)}$，但复杂度的系数项不容忽略。一种简单的改进方法是减小元胞长度，取元胞大小为${\displaystyle \frac{1}{2}{r}_c}$，扫描时计算近邻和次近邻两层元胞共${\displaystyle (2\ast <!--\; \ast \; -->2+1{)}^3=125}$个元胞，则距离计算包含的体积降为${\displaystyle \frac{125}{8}{r}_c^3}$，距离计算的体积下降了将近一倍。然而，元胞的扫描具有${\displaystyle O(N_{div}^6)}$的复杂度，元胞划分数进一步增大带来的性能提升很快被扫描元胞的开销浪费掉。(最早提出：，详细讨论：)

将韦尔莱表与元胞列表联合，达到进一步的改进。使用元胞列表构建韦尔莱表可使后者更新的复杂度降为${\displaystyle O(N)}$，同时克服了扫描元胞的时间开销。