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

NIST

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 r_i be the rate at which the i^th event should occur. The total rate is R = ∑^M_i=1 r_i. For an accurate simulation, event i should occur with probability r_i/R. (For equilibrium MC done according to BKL, the calculations are the same, but the {r_i} 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(log₂ 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.

[PRESENTATION SLIDES]