韦尔莱表

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

思想

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

算法

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

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

不足与改进

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