Efficient implementation of the Barnes-Hut octree algorithm for Monte Carlo simulations of charged systems. (English) Zbl 1321.78006
The authors develop an efficient Barnes-Hut treecode algorithm for electrostatic evaluation in Monte Carlo simulations of Coulomb many-body systems. The proposed algorithm is based on a divide and conquer strategy and fast update of the octree data structure in each trial move through a local adjustment procedure. The accuracy of the tree algorithm is tested, and it is used to perform computer simulations of electric double layer near a spherical interface. The authors are able to show the computational cost of the Monte Carlo method with treecode acceleration scales as \(\log N \) in every move.
Reviewer: Farruh Mukhamedov (Kuantan)
MSC:
| 78A30 | Electro- and magnetostatics |
| 78M31 | Monte Carlo methods applied to problems in optics and electromagnetic theory |
| 81V70 | Many-body theory; quantum Hall effect |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 65C05 | Monte Carlo methods |
References:
| [1] | Allen M P, Tildesley D J. Computer Simulations of Liquids. Oxford: Oxford University Press, 1987 · Zbl 0703.68099 |
| [2] | Appel A. An efficient program for many-body simulations. SIAM J Sci Stat Comput, 1985, 6: 85-103 · doi:10.1137/0906008 |
| [3] | Barnes J, Hut P. A hierarchical O(NlogN) force-calculation algorithm. Nature, 1986, 324: 446-449 · doi:10.1038/324446a0 |
| [4] | Boroudjerdi H, Kim Y W, Naji A, et al. Statics and dynamics of strongly charged soft matter. Phys Rep, 2005, 416: 129-199 · doi:10.1016/j.physrep.2005.06.006 |
| [5] | Cheng H, Greengard L, Rokhlin V. A fast adaptive multipole algorithm in three dimensions. J Comput Phys, 1999, 155: 468-498 · Zbl 0937.65126 · doi:10.1006/jcph.1999.6355 |
| [6] | Darden T A, York D M, Pedersen L G. Particle mesh Ewald: An Nlog(N) method for Ewald sums in large systems. J Chem Phys, 1993, 98: 10089-10092 · doi:10.1063/1.464397 |
| [7] | Deserno M, Jiménez-ángeles F, Holm C, et al. Overcharging of dna in the presence of salt: Theory and simulation. J J Phys Chem B, 2001, 105: 10983-1099 · doi:10.1021/jp010861+ |
| [8] | Duan Z H, Krasny R. An Ewald summation based multipole method. J Chem Phys, 2000, 113: 3492-3495 · doi:10.1063/1.1289918 |
| [9] | Duan Z H, Krasny R. An adaptive treecode for computing nonbonded potential energy in classical molecular systems. J Comput Chem, 2001, 22: 184-195 · doi:10.1002/1096-987X(20010130)22:2<184::AID-JCC6>3.0.CO;2-7 |
| [10] | Ewald P P. Die berechnung optischer und elektrostatischer gitterpotentiale. Ann Phys, 1921, 369: 253-287 · JFM 48.0566.02 · doi:10.1002/andp.19213690304 |
| [11] | French R H, Parsegian V A, Podgornik R, et al. Long range interactions in nanoscale science. Rev Mod Phys, 2010, 82: 1887-1944 · doi:10.1103/RevModPhys.82.1887 |
| [12] | Frenkel D, Smit B. Understanding Molecular Simulation: From Algorithms to Applications. New York: Academic Press, 2002 · Zbl 0889.65132 |
| [13] | Gan Z, Xu Z. Multiple-image treatment of induced charges in Monte Carlo simulations of electrolytes near a spherical dielectric interface. Phys Rev E, 2011, 84: 016705 · doi:10.1103/PhysRevE.84.016705 |
| [14] | Geng W, Krasny R. A treecode-accelerated boundary integral Poisson-Boltzmann solver for electrostatics of solvated biomolecules. J Comput Phys, 2013, 247: 62-78 · Zbl 1349.78084 · doi:10.1016/j.jcp.2013.03.056 |
| [15] | Gibbon P, Speck R, Karmakar A, et al. Progress in mesh-free plasma simulation with parallel tree codes. Plasma Sci IEEE Trans, 2010, 38: 2367-2376 · doi:10.1109/TPS.2010.2055165 |
| [16] | Greengard L, Rokhlin V. A fast algorithm for particle simulations. J Comput Phys, 1987, 73: 325-348 · Zbl 0629.65005 · doi:10.1016/0021-9991(87)90140-9 |
| [17] | Greengard L, Rokhlin V. A new version of the Fast Multipole Method for the Laplace equation in three dimensions. Acta Numer, 1997, 6: 229-269 · Zbl 0889.65115 · doi:10.1017/S0962492900002725 |
| [18] | Grosberg A Y, Nguyen T T, Shklovskii B I. Colloquium: The physics of charge inversion in chemical and biological systems. Rev Mod Phys, 2002, 74: 329-345 · doi:10.1103/RevModPhys.74.329 |
| [19] | Hockney R W, Eastwood J W. Computer Simulation Using Particles. Boca Raton, FL: CRC Press, 1988 · Zbl 0662.76002 · doi:10.1887/0852743920 |
| [20] | Kabadshow, I.; Dachsel, H., The error-controlled fast multipole method for open and periodic boundary conditions, 85-114 (2011), Jülich |
| [21] | Kondrat S, Georgi N, Fedorov M V, et al. A superionic state in nano-porous double-layer capacitors: insights from monte carlo simulations. Phys Chem Chem Phys, 2011, 13: 11359-11366 · doi:10.1039/c1cp20798a |
| [22] | Lashuk I, Chandramowlishwaran A, Langston H, et al. A massively parallel adaptive fast-multipole method on heterogeneous architectures. Commun ACM, 2012, 55: 101-109 · doi:10.1145/2160718.2160740 |
| [23] | Lau A W C, Lukatsky D B, Pincus P, et al. Charge fluctuations and counterion condensation. Phys Rev E, 2002, 65: 051502 · doi:10.1103/PhysRevE.65.051502 |
| [24] | Li P, Johnston H, Krasny R. A Cartesian treecode for screened Coulomb interactions. J Comput Phys, 2009, 228: 3858-3868 · Zbl 1165.78304 · doi:10.1016/j.jcp.2009.02.022 |
| [25] | Lindsay K, Krasny R. A particle method and adaptive treecode for vortex sheet motion in 3-D flow. J Comput Phys, 2001, 172: 879-907 · Zbl 1002.76093 · doi:10.1006/jcph.2001.6862 |
| [26] | Linse P. Simulation of charged colloids in solution. Adv Polym Sci, 2005, 185: 111-162 · doi:10.1007/b136795 |
| [27] | Linse P. Electrostatics in the presence of spherical dielectric discontinuities. J Chem Phys, 2008, 128: 214505 · doi:10.1063/1.2908077 |
| [28] | Lyubartsev A P, Tang J X, Janmey P A, et al. Electrostatically induced polyelectrolyte association of rodlike virus particles. Phys Rev Lett, 1998, 81: 5465-5468 · doi:10.1103/PhysRevLett.81.5465 |
| [29] | Manzanares J, Murphy W, Mafe S, et al. Numerical simulation of the nonequilibrium diffuse double layer in ionexchange membranes. J Phys Chem, 1993, 97: 8524-8530 · doi:10.1021/j100134a023 |
| [30] | Marzouk Y M, Ghoniem A F. K-means clustering for optimal partitioning and dynamic load balancing of parallel hierarchical n-body simulations. J Comp Phys, 2005, 207: 493-528 · Zbl 1176.70005 · doi:10.1016/j.jcp.2005.01.021 |
| [31] | Metropolis N, Rosenbluth A W, Rosenbluth M N, et al. Equation of state calculations by fast computing machines. J Chem Phys, 1953, 21: 1087-1092 · Zbl 1431.65006 · doi:10.1063/1.1699114 |
| [32] | Walker D A, Kowalczyk B, de la Cruz M O, et al. Electrostatics at the nanoscale. Nanoscale, 2011, 3: 1316-1344 · doi:10.1039/c0nr00698j |
| [33] | Winkel M, Speck R, Hübner H, et al. A massively parallel, multi-disciplinary Barnes-Hut tree code for extreme-scale N-body simulations. Comput Phys Comm, 2012, 183: 880-889 · doi:10.1016/j.cpc.2011.12.013 |
| [34] | Xu Z, Cai W. Fast analytical methods for macroscopic electrostatic models in biomolecular simulations. SIAM Rev, 2011, 53: 683-720 · Zbl 1228.92008 · doi:10.1137/090774288 |
| [35] | Xu Z, Cheng X, Yang H. Treecode-based generalized Born method. J Chem Phys, 2011, 134: 064107 · doi:10.1063/1.3552945 |
| [36] | Xu Z, Liang Y, Xing X. Mellin transform and image charge method for dielectric sphere in an electrolyte. SIAM J Appl Math, 2013, 7: 1396-1415 · Zbl 1290.78006 · doi:10.1137/120894348 |
| [37] | Ying L. A pedestrian introduction to fast multipole methods. Sci China Math, 2012, 55: 1043-1051 · Zbl 1259.65187 · doi:10.1007/s11425-012-4392-0 |
| [38] | Ying L, Biros G, Zorin D. A kernel-independent adaptive fast multipole algorithm in two and three dimensions. J Comput Phys, 2004, 196: 591-626 · Zbl 1053.65095 · doi:10.1016/j.jcp.2003.11.021 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
