Random batch methods (RBM) for interacting particle systems

Shi Jin Shanghai Jiao Tong University Lei Li Shanghai Jiao Tong University Jian-Guo Liu Duke University

Numerical Analysis and Scientific Computing mathscidoc:2103.25003

Journal of Computational Physics, 400, (1), 2020.1
We develop Random Batch Methods for interacting particle systems with large number of particles. These methods use small but random batches for particle interactions, thus the computational cost is reduced from $O(N^2)$ per time step to $O(N)$, for a system with $N$ particles with binary interactions. On one hand, these methods are efficient Asymptotic-Preserving schemes for the underlying particle systems, allowing $N$-independent time steps and also capture, in the $N \to \infty$ limit, the solution of the mean field limit which are nonlinear Fokker-Planck equations; on the other hand, the stochastic processes generated by the algorithms can also be regarded as new models for the underlying problems. For one of the methods, we give a particle number independent error estimate under some special interactions. Then, we apply these methods to some representative problems in mathematics, physics, social and data sciences, including the Dyson Brownian motion from random matrix theory, Thomson's problem, distribution of wealth, opinion dynamics and clustering. Numerical results show that the methods can capture both the transient solutions and the global equilibrium in these problems.
No keywords uploaded!
[ Download ] [ 2021-03-23 14:59:35 uploaded by leili2010 ] [ 455 downloads ] [ 0 comments ]
  • This is a random algorithm that costs O(N) per time step for interacting particle systems and has important applications (ongoing work) in molecular dynamics
  title={Random batch methods (RBM) for interacting particle systems},
  author={Shi Jin, Lei Li, and Jian-Guo Liu},
  booktitle={Journal of Computational Physics},
Shi Jin, Lei Li, and Jian-Guo Liu. Random batch methods (RBM) for interacting particle systems. 2020. Vol. 400. In Journal of Computational Physics. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20210323145935112630756.
Please log in for comment!
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved