针对自然界或者社会科学里广泛存在的非常重要的多体粒子系统，本论文里提出的Random Batch Method算法能将模拟的单步计算复杂度从O(N^2)降低到O(N)。该方法是通过简单漂亮的随机分组实现的，和机器学习里的随机梯度下降算法在思想上有共通之处。基于时间上的大数定律式的机制，该论文给出了该算法的误差估计。 与著名的快速多极展开相比，该算法适用于更一般的具有平移不变、不衰减的长程相互重用势，该方法可以适用于广泛的从物理化学到生物和社会科学群体行为以及机器学习中随机采样等重要领域，能够吸引大量的的后续工作。
The interacting many-body systems are ubiquitous in nature and social sciences. Naive discretization costs $O(N^2)$ per iteration. In this paper (by INS faculty Lei Li together with Prof. Shi Jin and Prof. Jian-Guo Liu), the proposed “Random Batch Method” can reduce the cost per iteration from $O(N^2)$ to $O(N)$.
The method makes use of the random shuffling and grouping to achieve the cost reduction, and shares similarity in spirit with the Stochastic Gradient Descent in machine learning. The convergence of the method is due to a certain “Law of Large Numbers in time”, and a rigorous proof of the convergence for some cases are provided in the paper. Compared with the famous Fast Multipole Method, the proposed method can be applied for general interacting kernels that do not necessarily decay and may not have translational invariance. It can be applied to sampling problems in data science, and also to collective behaviors arising from physics, chemistry, biology, socials sciences etc. This work could motivate a lot of subsequent works in these areas.
The “Guo Ben-Yu Young Scholar Outstanding Paper Award” is to celebrate outstanding young talents and their academic contributions in the field of computational mathematics and its applications in Shanghai. The award is initiated by the organizing committee of Shanghai Scientific and Engineering Computing Method Symposium，E-Institute of Computing Science, Shanghai University and Shanghai Key Laboratory of Scientific Computing in 2016. It is selected once a year, recognizing first class and the second class prize. It is awarded to three winners each year which can be vacant. Applicants are required to be no more than 32 years old.