韋爾萊表

韋爾萊表（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)$。這兩種方法的結合能進一步提高計算效率。