[科普中國]-元胞列表

元胞列表（Cell lists）是分子模擬中常用的一種減少粒子間距離計(jì)算量的方法，由Quentrec, B.與C. Brot提出。此方法使得運(yùn)算時(shí)間與體系粒子數(shù)成正比，與另一種方法韋爾萊表相比適合于大尺度的分子模擬。

算法元胞列表的思想是將體系分解為更小的元胞單元，只需計(jì)算計(jì)算相同和相鄰元胞中的粒子距離而不再需要對整個(gè)體系中所有其他粒子求解，元胞的邊長不小于粒子截?cái)喟霃絳\displaystyle R_{c}}，以此保證所有相互作用著的粒子作用力計(jì)算沒有遺漏。

根據(jù)元胞列表計(jì)算近鄰粒子間非鍵相互作用的基本算法如下：

for all近鄰元胞對do

for alldo

ifthen

end if

計(jì)算與間相互作用。

for alldo

end for

end for

end for

元胞的個(gè)數(shù)取決于模擬體系的尺度和粒子截?cái)喟霃?，每個(gè)元胞內(nèi)粒子數(shù)，與體系大小近似無關(guān)，兩個(gè)元胞間粒子作用計(jì)算的復(fù)雜度為，整體復(fù)雜度為，與未運(yùn)用元胞列表時(shí)的相比有了顯著的降低。

以Fortran描述的構(gòu)建列表的算法如下：

subroutine new_nlist rn = box/int(box/rc) ! 計(jì)算一個(gè)方向上的元胞個(gè)數(shù)。box為體系長度，rc為截?cái)喟霃?do icel=0 , ncel - 1 hoc(icel) = 0 ! 對每一個(gè)元胞的鏈頭置0 end do do i = 1 , npart ! 掃描所有粒子 icel = int(x(i)/rn) ! 確定粒子所在的元胞編號 ll(i) = hoc（icel）! 鏈接icel元胞的鏈頭 hoc(icel) = i ! 將粒子編號i添加到鏈頭 end doend subroutine周期性邊界條件在多數(shù)情況下，模擬的體系都會引入周期性邊界條件以避免不合實(shí)際的邊界。在樸素的算法中，對于每次粒子間距離計(jì)算都要運(yùn)用此條件：

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

造成很大的時(shí)間開銷。元胞列表的引入可改進(jìn)這一問題，主要有“幽靈元胞”和校正向量兩種優(yōu)化方案。1

幽靈元胞幽靈元胞通過在邊界以外復(fù)制一層元胞解決周期性邊界條件問題，這些復(fù)制的元胞擁有與原元胞完全相同的信息，這樣在計(jì)算距離時(shí)就不再需要考慮周期性邊界條件。此做法導(dǎo)致邊界上的粒子的計(jì)算量會增加一倍（元胞在三維盒子的面上）甚至更多（元胞在三維盒子的棱或頂角），但這種方法非常直觀且易于并行。2

校正向量由于元胞的邊界條件和粒子距離的邊界條件是一致的，因此在搜索近鄰元胞對時(shí)可導(dǎo)出一個(gè)向量來校正粒子間距離的計(jì)算。對于屬于兩個(gè)近鄰元胞的兩個(gè)粒子與，它們之間的距離按此式得出：

校正向量可以在掃描元胞時(shí)計(jì)算，也可在初始化時(shí)儲存。此方法單核效率通常高于幽靈元胞，但其實(shí)現(xiàn)相對復(fù)雜，并且將計(jì)算距離的開銷部分轉(zhuǎn)移到掃描元胞中。1

改進(jìn)在最初的元胞列表中，每一個(gè)粒子會與27個(gè)元胞作用，體積為，相較截?cái)喟霃角?img src="https://img-xml.kepuchina.cn/images/newsWire/yjIL4rtGLV25xWILMfz85RvVbHtU6AdtQA4i.jpg" alt="" />，有84%的距離計(jì)算是不必要的。雖然復(fù)雜度從降至，但復(fù)雜度的系數(shù)項(xiàng)不容忽略。一種簡單的改進(jìn)方法是減小元胞長度，取元胞大小為，掃描時(shí)計(jì)算近鄰和次近鄰兩層元胞共個(gè)元胞，則距離計(jì)算包含的體積降為，距離計(jì)算的體積下降了將近一倍。然而，元胞的掃描具有的復(fù)雜度，元胞劃分?jǐn)?shù)進(jìn)一步增大帶來的性能提升很快被掃描元胞的開銷浪費(fèi)掉。

將韋爾萊表與元胞列表聯(lián)合，達(dá)到進(jìn)一步的改進(jìn)。使用元胞列表構(gòu)建韋爾萊表可使后者更新的復(fù)雜度降為，同時(shí)克服了掃描元胞的時(shí)間開銷。1

本詞條內(nèi)容貢獻(xiàn)者為:

曹慧慧 - 副教授 - 中國礦業(yè)大學(xué)