韦尔莱表

韦尔莱表（Verlet table 或 Verlet list）是分子模拟中常用的一种减少粒子间距离计算量的方法，由法国物理学家卢普·韦尔莱（英语：Loup Verlet）首先提出。^[1]

思想

分子模拟中，为减少计算量，通常为体系中每一个粒子规定一个“截断半径”，对于一个粒子，只有当某个其他粒子与其距离处于截断半径以内时才计算它们之间的相互作用。由于粒子间作用力通常都是短程力，这种近似广泛用于蒙特卡洛方法和分子动力学模拟中。然而，当模拟的体系进一步增大时，计算每两个粒子间的距离变得非常耗时，韦尔莱表应运而生。 韦尔莱提出为每一个粒子建立一个列表，用来保存在它截断半径之内的其他粒子的编号，这个列表就称为韦尔莱表。为使韦尔莱表不必每个模拟步长都需要更新，韦尔莱表的构建引入“第二截断半径”'R_v'大于粒子的截断半径'R_c'。例如，对于蒙特卡洛方法，此值为${\displaystyle R_{v}=R_{c}+2nd}$ ，其中${\displaystyle n}$ 为韦尔莱表更新步长间隔，${\displaystyle d}$ 为一步中粒子的最大移动距离，以此保证所有应当计算的粒子都得到统计。更新韦尔莱表的时间复杂度为${\displaystyle O(N^{2})}$ （N为粒子总数），对于蒙特卡洛方法经优化可达到${\displaystyle O(N^{5/3})}$ 。

算法

以下是以Fortran描述的构建韦尔莱表的算法。^[2]

subroutine new_list do i = 1 , npart ! 初始化列表，npart为体系中粒子总数  nlist(i) = 0  xv(i) = x(i) end do do i = 1 , npart - 1  do j = i + 1 , npart ! 遍历所有粒子对  xr = x(i) - x(j) ! 计算两粒子距离  call period_condition(xr) ! 依周期性边界条件校正粒子距离  if(abs(xr) .lt. rv) then ! 找到符合条件的粒子对  ! 往韦尔莱表中添加信息  nlist(i) = nlist(i) + 1  nlist(j) = nlist(j) + 1 ! MC模拟中每个粒子独自考虑，故ij均保留完全的列表。而MD中可只保留粒子i的列表，粒子j的作用力由牛顿第三定律求算。  list(i,nlist(i)) = j  list(j,nlist(j)) = i  end if  end do end do 

不足与改进

韦尔莱表的${\displaystyle O(N^{2})}$ 复杂度使其在体系增大时耗时骤增，直至成为整个模拟中最耗时的步骤。在更大的体系时，通常采用“元胞列表”（Cell lists）的方法，其复杂度为${\displaystyle O(N)}$ 。^[3]这两种方法的结合能进一步提高计算效率。^[4]

参考资料

1. Verlet, L. Computer 'experiments' on classical fluids. I. Thermodynamical properties of Lennard-Jones molecules. Phys. Rev. 1967, 159: 98–103. doi:10.1103/physrev.159.98. 
2. [荷]Frenkel & Smit 汪文川等译. Understanding Molecular Simulation -- From Algorithms to Applications [分子模拟-从算法到应用]. 北京: 化学工业出版社. 2002 [1996]. ISBN 7-5025-3952-2. 
3. Quentrec, B. and C. Brot. New method for searching for neighbors in molecular dynamics computations.. Journal of Computational Physics. 1973, 13 (3): 430-432. 
4. Yao, Z.; et al. Improved neighbor list algorithm in molecular simulations using cell decomposition and data sorting method.. Computer Physics Communications. 2004, 1161 ((1-2)): 27-35. doi:10.1016/j.cpc.2004.04.004.  引文格式1维护：显式使用等标签 (link)