An efficient algorithm for interacting particle systems (IPS).
- random_batch
- random_batch_replacement
- random_batch_MC
IPS are continuous-time Markov jump processes describing the collective behavior of stochastically interacting components. IPS can be used to describe collective motion and swarm behaviour such as flocking in school of fishes, group of birds, chemotaxis of bacteria, consensus clusters in opinion dynamics. This python project focuses on IPS with binary interactions. The stochastic process for an N-particle IPS with binary interactions is given by
where is the current location of
the i-th particle, V represents the external force, K is the binary interacting kernel, B is the Brownian motion for
randomness.
While direct computation of the fully coupled system could be prohibitively expensive when N is medium or loperatore, RBM is
able to reduce the computational cost significantly from O(N^2) to O(N) per time step. The intuition behind RBM is to
evolve the IPS in small batches of particles, while the law of loperatore number guarantees asymptotic convergence as
under mild conditions. Two RBM
methods are provided in this python project, namely RBM-1 and RBM-replace. RBM-1 shuffles and divides the particles into
small batches per time step. RBM-replace samples random particles with replacement. For more information, please resort
to refeences [1] and [2]. The pseudocode for RBM-1 and RBM-replace are given below (figures taken from reference [1]).
Random batch Monte Carlo (RBMC) is a fast Markov chain Monte Carlo method to sample from the equilibrium distribution for a many-body IPS. The equilibrium state is an N-particle Gibbs distribution (or Boltzmann distribution) given by
where is the current location of N
particles. β is a positive constant. The N-body energy H(X) is composed of two parts, the summation of external
potentials (V) and the summation of all pairwise interaction potentials (U).
where w is the weight. Suppose the pairwise interacting kernel between two particles is singular and long-tailed. RBMC features a splitting strategy, where the interacting kernel can be split into two separate parts, i.e.,
where
and
represent the long range and short range effects, respectively. For each iteration of the RBMC algorithm, a moving step
and an accept-rejection step are carried out in turn. During the moving step, a random chosen particle X^i is updated by
solving the stochastic differential equation with respect to the long range effect. The idea of dividing N particles
into random mini-batches is implemented in the moving step to ease computational complexity. In the accept-rejection
step, short range effect is considered in the calculation of Metropolis acceptance ratio to guarantee convergence to the
invariant distribution. Pseudocode of RBMC algorithm is shown in the figure below. For a thorough explanation, please
resort to reference [3].
- random_batch
- random_batch_replace
- random_batch_MC
Example code for the following examples are provided in folder "./tests". Descriptions are in the same folder.
- Dyson Brownian motion
- Stochastic opinion dynamics
- Jin, S., Li, L., & Liu, J. G. (2020). Random batch methods (RBM) for interacting particle systems. Journal of Computational Physics, 400, 108877.
- Jin, S., & Li, L. (2022). Random batch methods for classical and quantum interacting particle systems and statistical samplings. In Active Particles, Volume 3 (pp. 153-200). Birkhäuser, Cham.
- Li, L., Xu, Z., & Zhao, Y. (2020). A random-batch Monte Carlo method for many-body systems with singular kernels. SIAM Journal on Scientific Computing, 42(3), A1486-A1509.