蒙特卡羅模擬中基于雙向鏈表的元胞鏈表方法

王逸梅, 王少云, 童朝暉

蒙特卡羅模擬中基于雙向鏈表的元胞鏈表方法

王逸梅, 王少云, 童朝暉*

（寧波大學 物理科學與技術學院, 浙江 寧波 315211）

蒙特卡羅方法; 非局域移動; 雙向鏈表; 元胞鏈表方法

1 方法和算法

這一部分詳細描述了基于雙向鏈表的元胞鏈表方法, 并且給出了相應的Fortran偽代碼. 首先, 描述了雙向鏈表的構造和如何調用其中的正向鏈表來計算能量. 然后, 描述粒子刪除和插入后雙向鏈表的更新. 最后, 使用元胞鏈表的方法來實現Metropolis算法中粒子的隨機移動和非局域移動.

1.1 構建元胞鏈表并計算體系能量

圖1 二維元胞鏈表方法

1.2 粒子刪除

表1 算法1、2、3的Fortran偽代碼

圖2 元胞鏈表中的粒子刪除

1.3 粒子插入

現在考慮粒子插入后如何更新鏈表. 例如, 在圖3的元胞4中插入粒子7. 此時, 需要增加粒子7指向粒子5的箭頭, 即list(7)=5, 并且粒子7成為起始粒子, 即head(4)=7. 在反向鏈表中, 粒子5指向7, 即inv_list(5)=7, 粒子7指向0, 即inv_list(7)= 0. 對于一般情況, 在元胞中插入一個粒子時, 插入前正向鏈表的頭粒子是head(), 插入后變為了. 需要建立現頭粒子和原頭粒子的連接, 即list()=head(), 以及更改頭粒子head()=. 對于反向鏈表, 插入前最后一個粒子head()需要指向插入粒子, 即inv_list(head())=, 并且粒子成為最后一個粒子, 即inv_list()=0.

圖3 元胞鏈表中粒子插入

此外, 在元胞中不存在粒子的情況下, 插入的粒子也是反向鏈表的頭粒子, 所以inv_head數組也將更改. 這些情況的具體實現詳見算法5(表2).

表2 算法4、5的Fortran偽代碼

1.4 Metropolis移動和非局域移動

圖2和圖3中數組的變化如圖4所示, 黑體數字表示粒子插入刪除前后變化的元素. 一旦通過元胞鏈表方法實現了粒子的插入和刪除, 就可以利用此方法來實現Metropolis算法中粒子的隨機移動(圖5(a)), 以及其他蒙特卡羅方法中的非局域移動(圖5(b～d)).

圖4 粒子刪除、插入的數組變化

對于Metropolis算法中粒子隨機移動, 粒子從一個元胞移動到另一個元胞的情形如圖6所示. 粒子從元胞4移動到元胞5(圖6(a))可化歸為在元胞4中刪除粒子并在元胞5中插入粒子(圖6(b)). 因此, 可以通過粒子刪除和粒子插入的正向鏈表和反向鏈表的更新來實現Metropolis算法中粒子的隨機移動. 同樣, 對于繞樞軸轉動或位形偏倚蒙特卡羅中的鏈回溯以及鏈再生, 可將其化歸為粒子逐個刪除和粒子逐個插入. 最后, 對于蠕動, 則可化歸為一個末端的粒子刪除以及另一個末端的粒子插入.

2 正確性和效率

現在來驗證元胞鏈表方法的正確性. 采用元胞鏈表方法和Verlet列表方法分別模擬NVT系綜中Lennard-Jones流體. 勢函數選取為Lennard- Jones勢, 其表達式為[1]:

圖7 Lennard-Jones流體在三相點附近的徑向分布函數

另外, 還比較了狀態方程. 體系的壓強可以使用Virial公式[1]得到, 其形式為

圖9 不同粒子數時模擬10 000個蒙特卡羅步的時間

3 結論

因為Verlet列表方法無法實現蒙特卡羅模擬中的非局域移動, 所以本文采用元胞鏈表方法實現了蒙特卡羅模擬中的非局域移動. 這是通過將這些移動化歸為粒子的插入和刪除過程, 進而使用雙向鏈表來實現的. 此外, 還將該方法應用到Metropolis算法中的粒子隨機移動, 這說明本方法也適用于Verlet列表方法能夠適用的情形. 綜上, 元胞鏈表方法的適用性比Verlet列表方法更廣.

[1] Frenkel D, Smit B. Understanding molecular simulation: from algorithms to applications[M]. 2nd ed. San Diego: Academic, 2002.

[2] Allen M P, Tildesley D J. Computer simulation of liquids [M]. 2nd ed. Oxford: Oxford University Press, 2017.

[3] Hockney R W, Eastwood J W. Computer simulation using particles[M]. New York: McGraw-Hill, 1981.

[4] Heath Turner C, Brennan J K, Lísal M, et al. Simulation of chemical reaction equilibria by the reaction ensemble Monte Carlo method: a review[J]. Molecular Simulation, 2008, 34:119-146.

[5] Reed C E, Reed W F. Monte Carlo study of titration of linear polyelectrolytes[J]. The Journal of Chemical Physics, 1992, 96(2):1609-1620.

[6] Landsgesell J, Holm C, Smiatek J. Simulation of weak polyelectrolytes: a comparison between the constant pH and the reaction ensemble method[J]. The European Physical Journal Special Topics, 2017, 226:725-736.

[7] Carmesin I, Kremer K. The bond fluctuation method: a new effective algorithm for the dynamics of polymers in all spatial dimensions[J]. Macromolecules, 1988, 21: 2819-2823.

[8] Kremer K, Binder K. Monte Carlo simulation of lattice models for macromolecules[J]. Computer Physics Reports, 1988, 7:259-310.

[9] Sadus R J. Molecular Simulation of Liquids: Theory, Algorithms and Objection-Orientation[M]. Amsterdam: Elsevier, 2002.

[10] Siepmann J I, Frenkel D. Configurational bias Monte Carlo: A new sampling scheme for flexible chains[J]. Molecular Physics, 1992, 75:59-70.

[11] Mazzeo M D, Ricci M, Zannoni C. The linked neighbour list (LNL) method for fast off-lattice Monte Carlo simulations of fluids[J]. Computer Physics Communications, 2010, 181:569-581.

[12] Drozdek A. Data structures and algorithms in C++[M]. 4th ed. Boston: Cengage Learning, 2013.

[13] Welling U, Germano G. Efficiency of linked cell algorithms[J]. Computer Physics Communications, 2011, 182:611-615.

[14] Heinz T N, Hünenberger P H. A fast pairlist-construction algorithm for molecular simulations under periodic boundary conditions[J]. Journal of Computational Chemistry, 2004, 25:1474-1486.

[15] Gonnet P. A simple algorithm to accelerate the computationof non-bonded interactions in cell-based molecular dynamics simulations[J]. Journal of Computational Chemistry, 2007, 28:570-573.

[16] Mattson W, Rice B M. Near-neighbor calculations using a modified cell-linked list method[J]. Computer Physics Communication, 1999, 119:135-148.

Cell lists method based on doubly linked lists for Monte Carlo simulation

WANG Yimei, WANG Shaoyun, TONG Chaohui*

( School of Physical Science and Technology, Ningbo University, Ningbo 315211, China )

Monte Carlo method; nonlocal move; cell lists method; doubly linked lists

O411.3

A

1001-5132（2021）04-0086-07

2020?12?08.

寧波大學學報（理工版）網址: http://journallg.nbu.edu.cn/

國家自然科學基金（21774067）.

王逸梅（1994－）, 女, 安徽淮北人, 在讀碩士研究生, 主要研究方向: 高分子物理. E-mail: wangyimei0817@163.com

童朝暉（1968－）, 男, 湖南常德人, 教授, 主要研究方向: 聚電解質理論. E-mail: tongchaohui@nbu.edu.cn

（責任編輯 韓 超）