蒙特卡罗模拟中基于双向链表的元胞链表方法

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

较之分子动力学,蒙特卡罗能够实现非局域的粒子移动,从而解决一些分子动力学不容易模拟的问题.非局域的粒子移动主要包括模拟化学反应时粒子产生和消失的过程,高分子模拟时的扭折-跳跃、绕枢轴转动和蠕动以及位形偏倚蒙特卡罗中链的回溯和再生.然而在蒙特卡罗方法处理非局域移动时,并不存在一种计算短程作用的计算复杂度为■(N)的算法,从而限制了蒙特卡罗方法的应用.本文基于双向链表的数据结构,发展了蒙特卡罗模拟中因粒子删除和插入而引起的短程势能变化的计算复杂度为■(N)的元胞链表方法.所有非局域的粒子移动可以转化为粒子的删除和插入,因此该方法适用于上述所有情形.此外,由于Metropolis算法中给某粒子一个随机位移的过程可以看成旧位置粒子的删除以及新位置粒子的插入,因此该方法也适用于Metropolis算法中粒子的随机移动.

Compared with molecular dynamics,Monte Carlo method involves some nonlocal moves which accelerate the simulation.These nonlocal moves include kink-jump,pivot,reptation move in polymer simulation,the retrace and regrowth of chains in configurational biased Monte Carlo,and the breaking and generating of bonds in chemical reaction and acid/base ionization.However,there lacks an algorithm with computational complexity■(N) in calculation of the short-range potential because Verlet lists method fails for nonlocal moves.In this paper,a cell lists method based on doubly linked lists and with complexity ■(N)is developed for particle deletion and insertion in Monte Carlo simulation.Because the random moves in Metropolis algorithm can be reduced to particle deletion at old position and particle insertion at new position,this method can also be used in Metropolis algorithm.In addition,the method is verified by comparing the simulation results obtained using the presented method with the one using Verlet lists method.Finally,the space and time complexity of the proposed method is also discussed.