Accelerated Stochastic Simulation Algorithms

Stochastic simulations of reaction-diffusion processes are frequently used for the modeling of physical phenomena ranging from biology and social sciences to ecosystems and materials processing. In this work we focus on the stochastic modeling and simulation of spatial dynamics of chemical kinetics intrinsic to physical phenomena ranging from morphogenesis and pedestrian traffic to epitaxial growth and epidemics.

LeSS - Leaping Stochastic Simulation: R-Leaping and D-Leaping
The time evolution of stochastic  systems is modeled  using the Stochastic Simulation Algorithm (SSA). We have developed several novel algorithms which accelerate these simulations. R-leaping [1] accelerates the simulation of these systems by reaction leaps. The algorithm is particularly suitable for systems with disparate reaction rates. D-leaping [4] accelerates the handling of reactions with delays for leaping algorithms. 
These algorithms have been implemented in the LeSS package, available on our software repository.

Adaptive Mesh Refinement for Spatial SSA:
The SSA has become increasingly important in the analysis of cellular systems in biology, where small molecular populations of species can lead to substantial deviations from deterministic simulations. For spatially inhomogeneous systems, SSA is associated with a high computational cost.  To resolve this issue, we are currently extending the R-leaping algorithm for  a nonuniform discretization of the domain in the spirit of Adaptive Mesh Refinement [2]. This enables the efficient use of computational elements, since more elements can be placed in areas of the domain that are associated with fine spatial scales.

Comparison of continuum (left) and stochastic (right) multiresolution simluations of diffusion

Stochastic multiresolution simluation of diffusion (enlargement of an arbitrary region on the right)

  1. Bayati B., Chatelain P., Koumoutsakos P., Adaptive mesh refinement for stochastic reaction-diffusion processes, J. of Computational Physics, 230, 13-26, 2011 (Abstract) (pdf)
  2. Auger A., Chatelain P. and Koumoutsakos P., R-leaping: Accelerating the stochastic simulation algorithm by reaction leaps. J. Chemical Physics, 125, 84103, 2006 (Abstract) (pdf)
  3. Bayati B., Chatelain P., Koumoutsakos P., Multiresolution Stochastic Simulations of Reaction-Diffusion Processes, Physical Chemistry Chemical Physics, 10, 5963-5966, 2008 (Abstract) (pdf)
  4. Rossinelli D., Bayati B., Koumoutsakos P., Accelerated Stochastic and Hybrid Methods for Spatial Simulations of Reaction-Diffusion Systems, Chemical Physics Letters, 451, 1-3, 136-140, 2008. (Abstract) (pdf)
  5. Bayati B., Chatelain P., Koumoutsakos P., D-leaping: Accelerating stochastic simulation algorithms for reactions with delays, J. of Computational Physics, 228, 5908-5916, 2009 (Abstract) (pdf)

People: Basil Bayati, Diego Rossinelli, Philippe Chatelain

Funding: ETH Zürich, SystemsX
Student Projects: Multiresolution Stochastic Simulations of Reaction-Diffusion Processes