Sampling from a polytope and hard-disk Monte Carlo
arXiv:1301.4901 · doi:10.1088/1742-6596/454/1/012031
Abstract
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.
References in corpus (11)
- Two-step melting in two dimensions: First-order liquid-hexatic transition
- Shortcomings of the Bond Orientational Order Parameters for the Analysis of Disordered Particulate Matter
- Hard-disk equation of state: First-order liquid-hexatic transition in two dimensions with three simulation methods
- Event-chain Monte Carlo algorithms for hard-sphere systems
- Computer simulations of the two-dimensional melting transition using hard disks
- Large-Scale Simulations of the Two-Dimensional Melting of Hard Disks
- How to Couple from the Past Using a Read-Once Source of Randomness
- Massively parallel Monte Carlo for many-particle simulations on GPUs
- Simple and efficent algorithm for large scale molecular dynamics simulation in hard disk systems
- Proof of the Boltzmann-Sinai Ergodic Hypothesis for Typical Hard Disk Systems
- Convergence and coupling for spin glasses and hard spheres
Cited by in corpus (14)
- 2D Melting: From Liquid-Hexatic Coexistence to Continuous Transitions
- Generalized event-chain Monte Carlo: Constructing rejection-free global-balance algorithms from infinitesimal steps
- Hard-sphere melting and crystallization with event-chain Monte Carlo
- Event-chain Monte Carlo: foundations, applications, and prospects
- Event-chain Monte Carlo for classical continuous spin models
- Fast MCMC sampling algorithms on polytopes
- All-atom computations with irreversible Markov chains
- Efficient Irreversible Monte Carlo samplers
- JeLLyFysh-Version1.0 -- a Python application for all-atom event-chain Monte Carlo
- Parallelized event chain algorithm for dense hard sphere and polymer systems
- Multithreaded event-chain Monte Carlo with local times
- Large-scale dynamics of event-chain Monte Carlo
- Sparse hard-disk packings and local Markov chains
- Computational Methods toward Ultrastable Glasses