Fast electrostatic solvers for kinetic Monte Carlo simulations. (English) Zbl 1436.65009

Summary: Kinetic Monte Carlo (KMC) is an important computational tool in theoretical physics and chemistry. In contrast to standard Monte Carlo, KMC permits the description of time dependent dynamical processes and is not restricted to systems in equilibrium. Compared to Molecular Dynamics, it allows simulations over significantly longer timescales. Recently KMC has been applied successfully in modelling of novel energy materials such as Lithium-ion batteries and organic/perovskite solar cells. Motivated by this, we consider general solid state systems which contain free, interacting particles which can hop between localised sites in the material. The KMC transition rates for those hops depend on the change in total potential energy of the system. For charged particles this requires the frequent calculation of electrostatic interactions, which is usually the bottleneck of the simulation. To avoid this issue and obtain results in reasonable times, many studies replace the long-range potential by a phenomenological short range approximation. This, however, leads to systematic errors and unphysical results. On the other hand standard electrostatic solvers such as Ewald summation or fast Poisson solvers are highly inefficient in the KMC setup or introduce uncontrollable systematic errors at high resolution.
In this paper we describe how the Fast Multipole Method by Greengard and Rokhlin can be adapted to overcome this issue by dramatically reducing computational costs. We exploit the fact that each update in the transition rate calculation corresponds to a single particle move and changes the configuration only by a small amount. This allows us to construct an algorithm which scales linearly in the number of charges for each KMC step, something which had not been deemed to be possible before.
We demonstrate the performance and parallel scalability of the method by implementing it in a performance portable software library, which was recently developed in our group. We describe the high-level Python interface of the code which makes it easy to adapt to specific use cases.


65C05 Monte Carlo methods
78M16 Multipole methods applied to problems in optics and electromagnetic theory
Full Text: DOI arXiv


[1] Young, W.; Elcock, E., Monte Carlo studies of vacancy migration in binary ordered alloys: I, Proc. Phys. Soc., 89, 3, 735 (1966)
[2] Bortz, A.; Kalos, M.; Lebowitz, J., A new algorithm for Monte Carlo simulation of Ising spin systems, J. Comput. Phys., 17, 1, 10-18 (1975)
[3] Gillespie, D., A general method for numerically simulating the stochastic time evolution of coupled chemical reactions, J. Comput. Phys., 22, 4, 403-434 (1976)
[4] Gillespie, D., Exact stochastic simulation of coupled chemical reactions, J. Phys. Chem., 81, 25, 2340-2361 (1977)
[5] Cuppen, H. M.; Karssemeijer, L. J.; Lamberts, T., The kinetic Monte Carlo method as a way to solve the master equation for interstellar grain chemistry, Chem. Rev., 113, 12, 8840-8871 (2013)
[6] Morgan, B. J., Lattice-geometry effects in garnet solid electrolytes: a lattice-gas Monte Carlo simulation study, R. Soc. Open Sci., 4, 11, Article 170824 pp. (2017)
[7] Groves, C., Simulating charge transport in organic semiconductors and devices: a review, Rep. Prog. Phys., 80, 2, Article 026502 pp. (2016)
[8] Thompson, I. R.; Coe, M. K.; Walker, A. B.; Ricci, M.; Roscioni, O. M.; Zannoni, C., Microscopic origins of charge transport in triphenylene systems, Phys. Rev. Materials, 2, 6, Article 064601 pp. (2018)
[9] Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E., Equation of state calculations by fast computing machines, J. Chem. Phys., 21, 6, 1087-1092 (1953) · Zbl 1431.65006
[10] Hastings, W. K., Monte Carlo sampling methods using Markov chains and their applications · Zbl 0219.65008
[11] Meng, L.; Zhang, Y.; Wan, X.; Li, C.; Zhang, X.; Wang, Y.; Ke, X.; Xiao, Z.; Ding, L.; Xia, R.; Yip, H.-L.; Cao, Y.; Chen, Y., Organic and solution-processed tandem solar cells with 17.3
[12] Peplow, M., Perovskite progress pushes tandem solar cells closer to market, Chem. Eng. News, 96, 24 (2018)
[13] Ewald, P. P., Die Berechnung optischer und elektrostatischer Gitterpotentiale, Ann. Phys., 369, 3, 253-287 (1921) · JFM 48.0566.02
[14] Hockney, R. W.; Eastwood, J. W., Computer Simulation Using Particles (1988), CRC Press · Zbl 0662.76002
[15] Deserno, M.; Holm, C., How to mesh up Ewald sums. I. A theoretical and numerical comparison of various particle mesh routines, J. Chem. Phys., 109, 18, 7678-7693 (1998)
[16] Greengard, L.; Rokhlin, V., A fast algorithm for particle simulations, J. Comput. Phys., 73, 2, 325-348 (1987) · Zbl 0629.65005
[17] Greengard, L., The Rapid Evaluation of Potential Fields in Particle Systems (1988), MIT Press · Zbl 1001.31500
[18] Greengard, L.; Rokhlin, V., A new version of the fast multipole method for the Laplace equation in three dimensions, Acta Numer., 6, 229-269 (1997) · Zbl 0889.65115
[19] Li, H.; Brédas, J.-L., Modeling of actual-size organic electronic devices from efficient molecular-scale simulations, Adv. Funct. Mater., 28, 29, Article 1801460 pp. (2018)
[20] Casalegno, M.; Raos, G.; Po, R., Methodological assessment of kinetic Monte Carlo simulations of organic photovoltaic devices: the treatment of electrostatic interactions, J. Chem. Phys., 132, 9, Article 094705 pp. (2010)
[21] Hermet, J.; Bottin, F.; Dezanneau, G.; Geneste, G., Kinetic Monte Carlo study of protonic diffusion and conduction in Gd-doped BaCeO3, Solid State Ion., 252, 48-55 (2013)
[22] Li, H.; Brédas, J.-L., Kinetic Monte Carlo modeling of charge carriers in organic electronic devices: suppression of the self-interaction error, J. Phys. Chem. Lett., 8, 11, 2507-2512 (2017)
[23] Van der Holst, J.; Van Oost, F.; Coehoorn, R.; Bobbert, P., Monte Carlo study of charge transport in organic sandwich-type single-carrier devices: effects of Coulomb interactions, Phys. Rev. B, 83, 8, Article 085206 pp. (2011)
[24] Kordt, P.; van der Holst, J. J.; Al Helwi, M.; Kowalsky, W.; May, F.; Badinski, A.; Lennartz, C.; Andrienko, D., Modeling of organic light emitting diodes: from molecular to device properties, Adv. Funct. Mater., 25, 13, 1955-1971 (2015)
[25] Saunders, W. R.; Grant, J.; Müller, E. H., A domain specific language for performance portable molecular dynamics algorithms, Comput. Phys. Commun., 224, 119-135 (2018)
[26] Saunders, W. R.; Grant, J.; Müller, E. H., Long range forces in a performance portable molecular dynamics framework, (Parallel Computing is Everywhere (2018)), 37-46
[27] Frenkel, D.; Smit, B., Understanding Molecular Simulation: From Algorithms to Applications, vol. 1 (2001), Academic Press: Academic Press San Diego, London
[28] Allen, M. P.; Tildesley, D. J., Computer Simulation of Liquids (1989), Oxford University Press: Oxford University Press Oxford · Zbl 0703.68099
[29] Amisaki, T., Precise and efficient Ewald summation for periodic fast multipole method, J. Comput. Chem., 21, 12, 1075-1087 (2000)
[30] Walls, T. J., Kinetic Monte Carlo simulations of perovskite crystal growth with long range Coulomb interactions (1999), College of William and Mary, PhD thesis
[31] Trottenberg, U.; Oosterlee, C. W.; Schuller, A., Multigrid (2000), Elsevier
[32] van der Kaap, N.; Koster, L. J.A., Massively parallel kinetic Monte Carlo simulations of charge carrier transport in organic semiconductors, J. Comput. Phys., 307, 321-332 (2016) · Zbl 1351.82099
[33] Blanchard, P.; Bramas, B.; Coulaud, O.; Darve, E.; Dupuy, L.; Etcheverry, A.; Sylvand, G., ScalFMM: a generic parallel fast multipole library, (SIAM Conference on Computational Science and Engineering (SIAM CSE 2015) (2015))
[34] Yokota, R.; Barba, L. A., A tuned and scalable fast multipole method as a preeminent algorithm for exascale systems, Int. J. High Perform. Comput. Appl., 26, 4, 337-346 (2012)
[35] Yokota, R.; Barba, L. A.; Narumi, T.; Yasuoka, K., Petascale turbulence simulation using a highly parallel fast multipole method on GPUs, Comput. Phys. Commun., 184, 3, 445-455 (2013)
[36] Lashuk, I.; Chandramowlishwaran, A.; Langston, H.; Nguyen, T.-A.; Sampath, R.; Shringarpure, A.; Vuduc, R.; Ying, L.; Zorin, D.; Biros, G., A massively parallel adaptive fast-multipole method on heterogeneous architectures, (Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (2009), ACM), 58
[37] Gimbutas, Z.; Greengard, L., Computational software: simple FMM libraries for electrostatics, slow viscous flow, and frequency-domain wave propagation, Commun. Comput. Phys., 18, 2, 516-528 (2015) · Zbl 1388.65003
[38] Zhang, B.; Huang, J.; Pitsianis, N. P.; Sun, X., RECFMM: recursive parallelization of the adaptive fast multipole method for coulomb and screened coulomb interactions, Commun. Comput. Phys., 20, 2, 534-550 (2016) · Zbl 1373.78001
[39] DeBuhr, J.; Zhang, B.; Tsueda, A.; Tilstra-Smith, V.; Sterling, T., Dashmm: dynamic adaptive system for hierarchical multipole methods, Commun. Comput. Phys., 20, 4, 1106-1126 (2016) · Zbl 1373.70002
[40] Malhotra, D.; Biros, G., PVFMM: a parallel kernel independent FMM for particle and volume potentials, Commun. Comput. Phys., 18, 3, 808-830 (2015) · Zbl 1388.65169
[41] Yokota, R., Fast multipole methods (2015), (webpage)
[42] Gunn, D. S.; Allan, N. L.; Purton, J. A., Adaptive kinetic Monte Carlo simulation of solid oxide fuel cell components, J. Mater. Chem. A, 2, 33, 13407-13414 (2014)
[43] Plimpton, S.; Battaile, C.; Chandross, M.; Holm, L.; Thompson, A.; Tikare, V.; Wagner, G.; Webb, E.; Zhou, X.; Cardona, C. G., Crossing the mesoscale no-man’s land via parallel kinetic Monte Carlo, Sandia Report SAND2009-6226
[44] Leetmaa, M.; Skorodumova, N. V., KMCLib: a general framework for lattice kinetic Monte Carlo (KMC) simulations, Comput. Phys. Commun., 185, 9, 2340-2349 (2014)
[45] Liu, F.; van Eersel, H.; Xu, B.; Wilbers, J. G.; de Jong, M. P.; van der Wiel, W. G.; Bobbert, P. A.; Coehoorn, R., Effect of Coulomb correlation on charge transport in disordered organic semiconductors, Physical Review B, 96, 20, Article 205203 pp. (2017)
[46] Simbeyond, B. V., Bumblebee code
[47] Saunders, W. R.; Grant, J.; Mueller, E. H.; Thompson, I., Code and data release: fast electrostatic solvers for kinetic Monte Carlo simulations (May 2019), https://doi.org/10.5281/zenodo.2677704
[48] Plimpton, S., Fast parallel algorithms for short-range molecular dynamics, J. Comput. Phys., 117, 1, 1-19 (1995) · Zbl 0830.65120
[49] Smith, W.; Forester, T., DL_POLY_2.0: a general-purpose parallel molecular dynamics simulation package, J. Mol. Graph., 14, 3, 136-141 (1996)
[50] Todorov, I. T.; Smith, W.; Trachenko, K.; Dove, M. T., DL_POLY_3: new dimensions in molecular dynamics simulations via massive parallelism, J. Mater. Chem., 16, 1911-1918 (2006)
[51] Saunders, W. R., Development of A Performance-Portable Framework For Atomistic Simulations (2018), University of Bath, PhD thesis
[52] Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables, vol. 55 (1965), Courier Corporation
[53] Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P., Numerical Recipes. The Art of Scientific Computing (2007), Cambridge University Press · Zbl 1132.65001
[54] Massé, A.; Friederich, P.; Symalla, F.; Liu, F.; Nitsche, R.; Coehoorn, R.; Wenzel, W.; Bobbert, P. A., Ab initio charge-carrier mobility model for amorphous molecular semiconductors, Physical Review B, 93, Article 195209 pp. (2016)
[55] Agullo, E.; Bramas, B.; Coulaud, O.; Darve, E.; Messner, M.; Takahashi, T., Task-based FMM for multicore architectures, SIAM J. Sci. Comput., 36, 1, C66-C93 (2014) · Zbl 1323.78017
[56] B. Bramas, O. Coulaud, private communications, 2019.
[57] Purton, J.; Crabtree, J. C.; Parker, S., Dl_monte: a general purpose program for parallel monte carlo simulation, Mol. Simul., 39, 14-15, 1240-1252 (2013)
[58] (2018), Online
[59] Amdahl, G. M., Validity of the single processor approach to achieving large scale computing capabilities, (Proceedings of the April 18-20, 1967, Spring Joint Computer Conference, AFIPS ’67 (Spring) (1967), ACM: ACM New York, NY, USA), 483-485
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.