Optimal search methods for selecting distributed species in Gillespie-based kinetic Monte Carlo

Abstract Monte Carlo modeling has emerged as a powerful tool to describe system state variations in many engineering systems. If distributed species are involved, the so-called Gillespie-based kinetic Monte Carlo (kMC) simulations are very promising, provided that the search method to identify individual population members is properly chosen. A comparative study is therefore performed on the most promising search methods, using the stochastic simulation algorithm and considering system size variations from 102 to 106 employing 107 randomly selected targets. Attention is paid to already applied search methods as well as novel ones based on recent insights. It is demonstrated that for smaller systems the execution time of the linear search method is the lowest, and for larger systems the quaternary tree-based and tetrasection search methods are most suited. The tests are interpreted based on the search/modification times and an analysis based on iteration numbers is addressed.