From Werner KRAUTH

Jump to: navigation, search

Return to the "Current Research" section


Cell-veto Monte Carlo algorithm for long-range systems

Particle-based simulation (on the left) and cell-based simulation (on the right).
In a recent paper, together with Sebastian Kapfer, we have presented what we think might be a new start idea for the notoriously difficult simulation of long-ranged systems (such as the Coulomb 1/r interaction). Usually it poses problems, because the evaluation of the energy is so difficult: In a long-ranged system of N particles, the interactions are basically of everybody with everybody else. This makes that the evaluation of the energy becomes complicated, and the energy is needed in 99.99% of all simulation algorithms (Monte Carlo or Molecular dynamics). In our new algorithm (an application of the event-chain method), one does not compute the system energy in order to decide on a change of the physical system, but rather looks at all the interactions separately. So, if a particle a (the active particle) wants to move, it has to ask all its partners t_1, t_2, .... (the target particles). If there is only a single veto, the move is rejected. In the cell-veto algorithm (see the right side of the figure), the identification of the rejecting particle is preceeded by that of a veto cell. The advantage of this is that cell vetos can be identified immediately (in a constant number of operations, that is, in O(1)), and then instantly confirmed or infirmed on the particle level.

Event-chain algorithm for continuous spin systems: XY & Heisenberg models, spin glasses

Event-chain algorithm for spin systems
In past years, several of our key results, for example about two-dimensional melting for hard disks but also the melting scenario for soft-disk systems, have relied on the new event-chain algorithm, that applies to both systems, hard-core and soft-core. More recently, we realized that the event-chain algorithm could also be made to work for continuum spin systems. Earlier in 2015, work started with Manon Michel and Johannes Maier, PhD candidate and ENS-ICFP master student, respectively. The first simulations were followed by a period of hectic activity: We had discovered that the event-chain algorithm was about 100 times faster that the local Monte Carlo algorithm. Our findings were written up, during the month of August 2015, in a manuscript entitled Event-chain Monte Carlo for classical continuous spin models. Only six weeks later (!), Manon Michel and I submitted another manuscript, together with our colleagues Yoshihiko Nishikawa and Koji Hukushima, from the University of Tokyo, entitled Event-chain algorithm for the Heisenberg model: Evidence for z ≃ 1 dynamic scaling. This new finding (that still awaits confirmation for larger systems than the ones we could simulate quickly), has had an electrifying effect on us: For the first time, we see the kind of maximum speed-up that can be realized by irreversible Markov chains using the lifting paradigm, if we suppose that the recent mathematical theories apply to the algorithms we have been developing. Of course, we now hope to find the z=1 scaling in Heisenberg spin glasses and related systems and, why not, in the original hard-sphere models, in two dimensions as well as in three.

Soft-disk melting: From liquid-hexatic coexistence to continuous transitions

Melting of hard disks
By the way: the term melting of hard disks does not relate to the irreversible memory loss when your computer hard disk catches fire (left figure), but to a fundamental phase transition in the model of two-dimensional hard spheres, that is, billiard balls without friction and without inner structure (center and right figures). The possibility that two-dimensional systems with continuous degrees of freedom could melt was discovered in 1962, by Alder and Wainwright, but the nature of the transition remained a mystery for several decades (until we solved it).

In a recent paper with Sebastian Kapfer, in Physical Review Letters (2015), we discuss phase transitions in two-dimensional socalled soft-disk systems with repulsive power-law pair interactions ∝r^(−n), using the recent generalization of Event-Chain Monte Carlo to continuous potentials. The recently established melting scenario for hard disks (corresponding to n=∞) is preserved for finite n, and first-order liquid-hexatic and continuous hexatic-solid transitions are identified. The density difference between the coexisting hexatic and liquid is non-monotonous as a function of n. For smaller n, the coexisting liquid shows extremely long orientational correlations, and positional correlations in the hexatic become extremely short. For n≲6, the liquid-hexatic transition is continuous, with correlations consistent with the KTHNY scenario.

Phase diagram of soft disks.
The graph on the left provides the main result of our paper (x-axis: density/ pure hexatic; y-axis: power n): We see a large region with liquid-hexatic coexistence.

Efimov-driven phase transitions of the unitary Bose gas

In a recent article with Swann Piatecki, published in Nature Communications 5, 3503 (2014), we discuss Efimov trimers: bound configurations of three quantum particles that fall apart when any one of them is removed. They open a window into a rich quantum world that has become the focus of intense experimental and theoretical research, as the region of ‘unitary’ interactions, where Efimov trimers form, is now accessible in cold-atom experiments. We use a path-integral Monte Carlo algorithm backed up by theoretical arguments to show that unitary bosons undergo a first-order phase transition from a normal gas to a superfluid Efimov liquid, bound by the same effects as Efimov trimers. A triple point separates these two phases and another superfluid phase, the conventional Bose–Einstein condensate, whose coexistence line with the Efimov liquid ends in a critical point. We discuss the prospects of observing the proposed phase transitions in cold-atom systems.

Here are pictures of three bosons on an permutation cycle.
Here you see three bosons, in path integral representation, and with a certain pseudopotential interaction that is described in more detail in the paper. On the left side, the particles are slightly repulsive, on the right side, they are attractive (so that two particles simple get together and bind into a dimer, whereas the third particle just sits around. In the center, you see the particles at the unitary point: pair interactions are very weak, so pairs get together, but unbind. After a little while, another pair forms, etc etc. The final outcome is that ensembles of two particles fall apart, but three particles stay together, just like Borromean rings...
Here are pictures of three Borromean rings.

Generalized event-chain Monte Carlo: Rejection-free global-balance algorithms from infinitesimal steps

Our 2009 event-chain algorithm for hard spheres, with Etienne Bernard and David Wilson, is a new paradigm for Monte Carlo simulations. For a while, it was unclear whether it could be generalized to general potentials, and an earlier attempt was rather awkward. This is what we succeeded in doing, with Manon Michel and Sebastian C. Kapfer, in a 2014 paper in Journal of Chemical Physics. In the paper, we introduce a factorized Metropolis filter and the concept of infinitesimal Monte Carlo moves to design a rejection-free Markov-chain Monte Carlo algorithm for interacting particle systems that breaks detailed balance yet satisfies global balance. This event-driven algorithm generalizes the recent hard-sphere event-chain Monte Carlo method without introducing any discretizations in time or in space. We demonstrate considerable speed-ups of this method with respect to the classic local Metropolis algorithm. The new algorithm generates a continuum of samples of the stationary probability density. This allows us to derive an exact formula for the pressure that is obtained as a byproduct of the simulation without any additional computations. The generalized event-chain algorithm is really simple to implement, and it showed all its usefulness, for example in recent simulations with Sebastian C. Kapfer.

Sampling from a polytope and hard-disk Monte Carlo

Polytopes and constraint graph

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. In a recent preprint with Sebastian Kapfer, we were able to 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. In the paper, 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.

Hard-disk equation of state: First-order liquid-hexatic transition in two dimensions with three simulation methods

Move of one particle in the Event-driven MC algorithm
Spring and summer of 2012 was partly spent on a project with colleagues Michael Engel, Joshua Anderson, and Sharon Glotzer from the University of Michigan, Masaharu Isobe from the Nagoya Institute of Technology, and Etienne Bernard from MIT. We were interested in checking our earlier results on the melting transition of hard disks in two dimensions which predicted the existence of a first-order liquid-hexatic phase transition - a big surprise after hundreds of other papers had fought over two other scenarios for melting in two dimensions. Our confirmation preprint finally came out in November 2012, and it was published in April 2013 in Physical Review E, which in 2018 recognized it as its milestone paper for that year. Using three completely independent algorithms (massively parallel local Monte Carlo, molecular dynamics, event-chain Monte Carlo), we confirmed our earlier data (see figure to the left). We are all happy about this independent verification, and Etienne Bernard and I are quite relieved, as so much can go wrong with numerical simulations, especially if they take an eternity, almost, to run.

The figure to the left shows the equation of state for hard disks (the equilibrium pressure as a function of the density (or the volume), with the characteristic loop which indicates the presence of two phases - a minority phase that forms a bubble inside the majority phase. The three curves stand for the simulation methods: different algorithms, different computers, even continents produce the same equation of state, the one that noone else has produced before! The inset gives the difference between the old data (from last year) and the new ones. Let me note that, if the simulation is nontrivial, the calculation of the pressure is quite tricky also, especially in Monte Carlo calculations, as an extrapolation of the pair-correlation function is involved. Those of us in the team who computed the pressure from Monte Carlo were much relieved to see the nice agreement with the molecular dynamics pressure, obtained with Masaharu Isobe's code, which is computed simply by counting the number of collisions taking place over a months-long simulation. For more details, take a look at the paper.

Event-driven Monte Carlo algorithm for general potentials

In recent works, as for example on the melting transition in two dimensions, the event-chain algorithm has proven quite helpful. This hard-sphere Monte Carlo method runs a lot faster than earlier methods although the speed-uo remains constant for large system sizes. Nevertheless, gaining a factor of about 100 is not so bad for run-times (with the new algorithm) on the order of a few months... we got our results before it was time to retire.

Move of one particle in the Event-driven MC algorithm
Recently, in 2012, Etienne Bernard (now at MIT) and I were able to extend the event-chain algorithm to continuous potentials, and we are now quite excited: The algorithm allows to break detailed balance, it is (hopefully) much faster than local Monte Carlo algorithms, and it is extremely easy to program, to parallelize (hopefully), to modify and, why not, to improve. Technically, we work with stepped potentials (see the figure, similar approaches exist for molecular dynamics), but there is no problem going to finer and finer discretizations: the algorithm doesn't even slow down as we crank up the number of steps. This is explained in a section of the wiki page dedicated to our recent paper. But lots of things need to be done to understand this new approach, to check out possible applications, etc, and we are right now extremely busy.

Two-dimensional melting: First-order liquid-hexatic transition

Here, I show the key figure of a recent paper, published in Physical Review Letters in 2011, with Etienne Bernard, on the melting transition in hard disks. The main picture shows the orientations of a configuration with 1024x1024 disks, and two different regions are clearly visible: To the left, disks have more or less the same orientation, whereas to the right, the orientations vary (and the local densities are lower). This clearly indicates the presence of a first-order transition (for details see the paper). In our paper, we show not only that the transition is of first order, but also that it is between the liquid and a hexatic phase. Our melting scenario differs from what hundreds of earlier papers seemed to indicate, namely that the two-dimensional melting transition either followed the famous KTHNY scenario or was a direct transition from the liquid to the solid state, as in three dimensions. The fight for truth between these two groups raged for several decades. Using much better simulation methods, we could show that both were off, and the scenario adopted by nature is not what was imagined for so long.

To produce the picture, we used the event-chain algorithm, a Monte Carlo method that we developed a few years ago, with David Wilson. This algorithm is really the first one to outperform, by about two orders of magnitude in speed, the classic Metropolis method from 1953. For a long time, I have been interested in the hard-disk melting problem, but an earlier attempt to speed up the extremely slow converge of numerical methods for this problem, the cluster algorithm that I developed with C. Dress, had failed.
Return to the "Current Research" section

Personal tools