Binning for efficient stochastic multiscale particle simulations

M. D. Michelotti, M. T. Heath, and M. West

Multiscale Modeling & Simulation 11(4), 1071-1096, 2013.

Gillespie's Stochastic Simulation Algorithm (SSA) is an exact procedure for simulating the evolution of a collection of discrete, interacting entities, such as coalescing aerosol particles or reacting chemical species. The high computational cost of SSA has motivated the development of more efficient variants, such as Tau-Leaping, which sacrifices the exactness of SSA. For models whose interacting entities can be characterized by a continuous parameter, such as a measure of size for aerosol particles, we analyze strategies for accelerating these algorithms by aggregating particles of similar size into bins. We show that for such models an appropriate binning strategy can dramatically enhance efficiency, and in particular can make SSA computationally competitive without sacrificing exactness. These strategies are especially effective for highly multiscale problems. We formulate binned versions of both the SSA and Tau-Leaping algorithms and analyze and demonstrate their performance.

DOI: 10.1137/130908038

Full text: MiHeWe2013.pdf