Sampling from a polytope and hard-disk Monte Carlo

24th IUPAP Conference on Computational Physics

物理学;计算机科学

Kapfer, Sebastian C.^1 ; Krauth, Werner^1

Laboratoire de Physique Statistique, Ecole Normale Supérieure, CNRS, 24 rue Lhomond, 75231 Paris Cedex 05, France^1

关键词: Computational physics;    Convergence properties;    Hard spheres;    High-dimensional;    Markov Chain Monte-Carlo;    Monte carlo algorithms;    Parallelization strategies;    Random Walk;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/454/1/012031/pdf
DOI  :  10.1088/1742-6596/454/1/012031

学科分类：计算机科学（综合）

来源: IOP

【 摘 要 】

The hard-disk problem, the statics and the dynamics of equal two-dimensional hard spheres in a periodic box, has had a profound influence on statistical and computational physics. Markov-chain Monte Carlo and molecular dynamics were first discussed for this model. Here we reformulate hard-disk Monte Carlo algorithms in terms of another classic problem, namely the sampling from a polytope. Local Markov-chain Monte Carlo, as proposed by Metropolis et al. in 1953, appears as a sequence of random walks in high-dimensional polytopes, while the moves of the more powerful event-chain algorithm correspond to molecular dynamics evolution. We determine the convergence properties of Monte Carlo methods in a special invariant polytope associated with hard-disk configurations, and the implications for convergence of hard-disk sampling. Finally, we discuss parallelization strategies for event-chain Monte Carlo and present results for a multicore implementation.