# Main Page

### From Werner KRAUTH

←Older revision | Newer revision→

Werner Krauth Laboratoire de Physique Statistique École normale supérieure 24 rue Lhomond 75231 Paris Cedex 05 France Tel +33 (0)1 44 32 34 94 werner.krauth@ens.fr Office: LE110 (first floor)

CNRS Research Director (Theoretical Physics)

Adjunct Professor Ecole normale supérieure (professeur attaché à l'ENS).

# ICFP Master 2017, Course on Statistical Physics

see this page for tutorials and homeworks, syllabus, and lecture notes.

# Third MOOC Statistical Mechanics: Algorithms and Computations - Now self-paced

The 3rd edition of the Massive open online course (MOOC) on Coursera: Statistical Mechanics: Algorithms and Computations has started on February 29, 2016 (participation is free of charge, and open to everyone). The first edition of the MOOC, in 2014, drew 30,000 registered students from 160 countries. Videos were viewed 250,000 times, there were close to 6000 forum posts, and students had a great time. Look here for an editorial that I wrote after 'coming home from a MOOC'.

The 3rd edition of SMAC comes with two major changes:

- Statistical Mechanics: Algorithms and Computations is now a self-paced course, just like all other courses on Coursera. I will be curious to see how it will turn out, especially whether the individual pace still allows some kind of group experience. In any case, we put in a lot of effort to make our popular course accessible to an even larger community of students. We will continue to be very present on the forum! So let's all have fun with the third edition of SMAC.
- There will be no more certificate, as ENS was unable to keep the certificate free of charge.

# Current research

I am deeply interested in statistical and condensed-matter physics, often in connection to computation and algorithms.
Current interests are in hard spheres, mainly the melting transition in two-dimensional disks and in two-dimensional melting, bosons (in collaboration with the experimental groups at ENS), and the theory of convergence and of coupling in Markov chains. Recent work in my research group has led to the redefinition of the dominant Markov-chain Monte Carlo paradigm, namely the Metropolis algorithm. This has already allowed us to propose powerful algorithms for particle systems, continuous spin models and long-range systems, and to obtain important physical results. Research on the *beyond-Metropolis* paradigm, together with applications in classical and quantum physics and its interfaces will likely be a focus of my research activity in the next few years.

## Irreversible local Markov chains with rapid convergence towards equilibrium

Monte Carlo algorithms, generally satisfy the detailed balance condition, which prescribes that in the limit of infinite times, the*probability flow*from a configuration

**a**to a configuration

**b**equals the flow from

**b**to

**a**. This may seem terrible abstract, but it simply means that if, in a room full of air molecules, each molecule moves to the left and to the right with the same probability (and sometimes does not move at all, because there is already another particle where it wants to go), the density of air will be more or less uniform. In a recent paper with Sebastian Kapfer, in Physical Review Letters, we systematically studied irreversible local Markov chain, that is, Monte Carlo algorithms which only satisfy the global balance condition, but not the detailed balance (in the example of the air-filled room, this corresponds to algorithms where the molecules are much more likely to move in one direction than the other, but where the asymptotic density is still uniform). We considered the case of hard-sphere gases in one spatial dimension with periodic boundary conditions and, to our greatest surprise, came up with Markov chains such as the 'forward Metropolis algorithm' or the 'lifted forward Metropolis algorithm', or even the 'lifted forward Metropolis algorithm with restart' that mix much faster than the usual methods, although they reach exactly the same steady state in the limit of infinite times. We even made contact with the vast research literature on the TASEP (totally asymmetric simple exclusion process), a discrete variant of our Markov chains. We are all the more excited that the algorithms studied are but special versions of the event-chain algorithm, that we used a lot during the last years.

## Cell-veto Monte Carlo algorithm for long-range systems

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

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

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.

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 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...

## 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

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

Spring and summer of 2012 was partly spent on a project with colleagues Joshua Anderson, Michael Engel 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 Physical Review E, in April 2013. 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.

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, from 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.

# Upcoming events

- University of Tokyo, Japan, 16 January 2017 - 29 March 2017 (invited professor). Cf Toyko Lectures on hard disks
- National Taiwan University, Taipei, Taiwan, 29 March - 03 April 2017 (invited seminars).
- Hong Kong University of Science and Technology, Hong Kong, China 03 - 13 April 2017 (invited lecture series).
- Workshop "Numerical aspects of nonequilibrium dynamics" (Institut Henry Poincaré, Paris, France 25-27 April, 2017) (invited talk).
- Natal, State of Rio Grande do Norte, Brazil 21-26 August, 2017, IX Brazilian Meeting on Simulational Physics (invited talk and tutorial).
- Bad Herrenalb, Germany, 11-15 September 2017, Conference: Geometry and Physics of Spatial Random Systems (Invited keynote speaker).
- Ilheus, Bahia, Brazil, 17-20 September 2017, 2nd Brazilian Meeting on Statistical Physics (Invited plenary speaker).
- University of California, Los Angeles, USA, 16-20 October 2017, Workshop: Stochastic Sampling and Accelerated Time Dynamics on Multidimensional Surfaces (invited talk).
- University of Oxford, UK, 24 - 27 October 2017, Physics Departement (Invited visit and seminar)
- University of Tokyo, Japan, 15-17 November 2017 (ENS-UT annual workshop).
- Max Planck Institute for the Physics of Complex Systems, Dresden, Germany, 1 January-30 June 2018 (Gutzwiller fellow).
- American Physical Society March Meeting, Los Angeles, USA, 5-9 March 2018 (invited talk)
- 2nd International Workshop on Critical Behavior in Lattice Models (CBLM 2018), Anqing Normal University (AQNU) China, 4-9 April 2018 (invited talk)

Here is the schedule of past events

# Text book

# Interview, Popular story, video conference

2012 interview at Ecole normale supérieure (in French)

CNRS special on our work on two-dimensional melting (June 2013) (in French) in Japanese (!)

2012 Conference on time's arrow (video, in French) in the framework of the Festival "acceleration" Sacre Doctoral school

Video presentation of the Massive Open Online course at ENS

# A picture book of algorithms