王逸梅, 王少云, 童朝暉

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

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

（寧波大學(xué) 物理科學(xué)與技術(shù)學(xué)院, 浙江 寧波 315211）

蒙特卡羅方法; 非局域移動(dòng); 雙向鏈表; 元胞鏈表方法

1 方法和算法

這一部分詳細(xì)描述了基于雙向鏈表的元胞鏈表方法, 并且給出了相應(yīng)的Fortran偽代碼. 首先, 描述了雙向鏈表的構(gòu)造和如何調(diào)用其中的正向鏈表來計(jì)算能量. 然后, 描述粒子刪除和插入后雙向鏈表的更新. 最后, 使用元胞鏈表的方法來實(shí)現(xiàn)Metropolis算法中粒子的隨機(jī)移動(dòng)和非局域移動(dòng).

1.1 構(gòu)建元胞鏈表并計(jì)算體系能量

圖1 二維元胞鏈表方法

1.2 粒子刪除

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

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

1.3 粒子插入

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

圖3 元胞鏈表中粒子插入

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

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

1.4 Metropolis移動(dòng)和非局域移動(dòng)

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

圖4 粒子刪除、插入的數(shù)組變化

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

2 正確性和效率

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

圖7 Lennard-Jones流體在三相點(diǎn)附近的徑向分布函數(shù)

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

圖9 不同粒子數(shù)時(shí)模擬10 000個(gè)蒙特卡羅步的時(shí)間

3 結(jié)論

因?yàn)閂erlet列表方法無法實(shí)現(xiàn)蒙特卡羅模擬中的非局域移動(dòng), 所以本文采用元胞鏈表方法實(shí)現(xiàn)了蒙特卡羅模擬中的非局域移動(dòng). 這是通過將這些移動(dòng)化歸為粒子的插入和刪除過程, 進(jìn)而使用雙向鏈表來實(shí)現(xiàn)的. 此外, 還將該方法應(yīng)用到Metropolis算法中的粒子隨機(jī)移動(dòng), 這說明本方法也適用于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.

寧波大學(xué)學(xué)報(bào)（理工版）網(wǎng)址: http://journallg.nbu.edu.cn/

國家自然科學(xué)基金（21774067）.

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

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

（責(zé)任編輯 韓 超）