元胞列表

元胞列表（Cell lists）是分子模拟中常用的一种减少粒子间距离计算量的方法，由Quentrec, B.与C. Brot提出。^[1]此方法使得运算时间与体系粒子数成正比，与另一种方法韦尔莱表相比适合于大尺度的分子模拟。

算法

元胞列表的思想是将体系分解为更小的元胞单元，只需计算计算相同和相邻元胞中的粒子距离而不再需要对整个体系中所有其他粒子求解，元胞的边长不小于粒子截断半径${\displaystyle R_{c}}$ ，以此保证所有相互作用着的粒子作用力计算没有遗漏。

根据元胞列表计算近邻粒子间非键相互作用的基本算法如下：

for all 近邻元胞对 ${\displaystyle (C_{\alpha },C_{\beta })}$  do

for all ${\displaystyle p_{\alpha }\in C_{\alpha }}$  do

for all ${\displaystyle p_{\beta }\in C_{\beta }}$  do

${\displaystyle r^{2}=\|\mathbf {x} [p_{\alpha }]-\mathbf {x} [p_{\beta }]\|_{2}^{2}}$ 

if ${\displaystyle r^{2}\leq r_{c}^{2}}$  then

计算${\displaystyle p_{\alpha }}$ 与${\displaystyle p_{\beta }}$ 间相互作用。

end if

end for

end for

end for

元胞的个数取决于模拟体系的尺度和粒子截断半径，每个元胞内粒子数${\displaystyle {\overline {c}}=N/m}$ ，与体系大小近似无关，两个元胞间粒子作用计算的复杂度为${\displaystyle {\mathcal {O}}({\overline {c}}^{2})}$ ，整体复杂度为${\displaystyle {\mathcal {O}}(Nc)\in {\mathcal {O}}(N)}$ ，与未运用元胞列表时的${\displaystyle {\mathcal {O}}(N^{2})}$ 相比有了显著的降低。

以Fortran描述的构建列表的算法如下：^[2]

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 do end subroutine 

周期性边界条件

在多数情况下，模拟的体系都会引入周期性边界条件以避免不合实际的边界。在朴素的算法中，对于每次粒子间距离计算都要运用此条件：

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

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

幽灵元胞

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

校正向量

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

${\displaystyle r^{2}=\|\mathbf {x} [p_{\alpha }]-\mathbf {x} [p_{\beta }]-\mathbf {q} _{\alpha \beta }\|_{2}^{2}}$ .

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

改进

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

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

参见

• 韦尔莱表

参考资料

1. Quentrec, B. and C. Brot (1973). "New method for searching for neighbors in molecular dynamics computations." Journal of Computational Physics 13(3): 430-432.
2. [荷]Frenkel & Smit 汪文川等译. Understanding Molecular Simulation -- From Algorithms to Applications [分子模拟-从算法到应用]. 北京: 化学工业出版社. 2002 [1996]. ISBN 7-5025-3952-2. 
3. Allen, M. P.; D. J. Tildesley. Computer Simulation of Liquids. Oxford: Clarendon Press. 1987. 
4. Mattson, W.; B. M. Rice. Near-neighbor calculations using a modified cell-linked list method. Computer Physics Communications. 1999, 119 (2-3): 135. Bibcode:1999CoPhC.119..135M. doi:10.1016/S0010-4655(98)00203-3. 
5. Yao, Z.; Wang, J.-S.; Liu, G.-R.; Cheng, M. Improved neighbor list algorithm in molecular simulations using cell decomposition and data sorting method. Computer Physics Communications. 2004, 161: 27. Bibcode:2004CoPhC.161...27Y. arXiv:physics/0311055  . doi:10.1016/j.cpc.2004.04.004. 
6. Heinz, T. N.; Hünenberger, P. H. A fast pairlist-construction algorithm for molecular simulations under periodic boundary conditions. Journal of Computational Chem istry. 2004, 25 (12): 1474–86. PMID 15224391. doi:10.1002/jcc.20071.