[ Search | Site Map | Contact ]

Center for Scientific Computation and Mathematical Modeling

Research Activities > Programs > Nonequilibrium Interface Dynamics > Tutorials

Nonequilibrium Interface Dynamics:
Theory and Simulation from Atomistic to Continuum Scales

CSIC Building (#406), Seminar Room 4122.
Directions: home.cscamm.umd.edu/directions

Fast Methods for Sampling from a Dynamic pdf
Part I: Fast Methods, Some up-front Cost.

Dr. Isabel Beichl


Abstract:   This pair of talks will cover some basic algorithms for accelerating dynamic Monte Carlo, meaning Monte Carlo for cases in which the probability distribution sampled changes as a consequence of sampling.

Let M be the number of possible MC events (or state transitions), and let ri be the rate at which the ith event should occur. The total rate is R = ∑Mi=1 ri. For an accurate simulation, event i should occur with probability ri/R. (For equilibrium MC done according to BKL, the calculations are the same, but the {ri} are transition probabilities, not rates.) If the rates are updated in the obvious, naive way, the cost per step is O(M) which could be prohibitive for a large M. We explain how to use a dynamic binary tree to reduce this cost to O(log2 M) per step. There is a one-time cost for establishing the dynamic tree. However, for all but very small values of M, this cost is easily re-couped in the per-step savings.