# Main Page

### From Werner KRAUTH

Revision as of 14:40, 19 January 2022Werner (Talk | contribs) ← Previous diff |
Revision as of 14:41, 19 January 2022Werner (Talk | contribs) Next diff → |
||

Line 21: |
Line 21: | ||

=Advanced topics in Markov-chain Monte Carlo= | =Advanced topics in Markov-chain Monte Carlo= | ||

- | Here is the TD1 of my 2022 lecture course Advanced topics in Markov-chain Monte Carlo [http://www.lps.ens.fr/%7Ekrauth/images/4/45/TD01_ICFP_ADV_MCMC.pdf] | + | [http://www.lps.ens.fr/%7Ekrauth/images/4/45/TD01_ICFP_ADV_MCMC.pdf Here is the TD1] of my 2022 lecture course Advanced topics in Markov-chain Monte Carlo |

__FORCETOC__ | __FORCETOC__ |

## Revision as of 14:41, 19 January 2022

Werner Krauth Laboratoire de Physique É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: GH216

CNRS Research Director - Theoretical Physics (Directeur de recherche CNRS - classe exceptionnelle).

From January to June 2018, I was the 2018 Martin-Gutzwiller fellow at the Max-Planck-Institute for the Physics of Complex Systems in Dresden (Germany).

In 2018, I was a recipient of the Humboldt research award (Alexander von Humboldt Foundation).

# Advanced topics in Markov-chain Monte Carlo

Here is the TD1 of my 2022 lecture course Advanced topics in Markov-chain Monte Carlo

# Workshop on ECMC and related subjects

An informal workshop on ECMC and related subjects took place on Tuesday 11 May 2021 8:30am - 12:30pm Paris time. 30 researchers participated, from the University of Dortmund (Germany), FAU-University of Erlangen (Germany), University of Bonn (Germany), University of Tokyo (Japan), Nagoya Institute of Technology (Japan), University Clermont-Auvergne (France), ESPCI Paris (France) and ENS Paris (France).

# Join our group

Please check out my group page if you are interested in joining my group.

# Fast irreversible Markov chains in statistical physics

This was the title of an invited plenary talk (slides) that I gave on September 10, 2019 at the CECAM50 conference celebrating the 50 years of this European Center for atomic and molecular computing.

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

# Milestone Research

A paper, on a **first**-order transition in **two** dimensions, by a collaboration on **three** continents (!) that I published a few years ago in Physical Review E together with M. Engel, J. A. Anderson, S. C. Glotzer, M. Isobe, and E. P. Bernard, was chosen as the milestone article for 2013 by the journal's editorial board. This 2013 paper confirmed research published in 2011, in Physical Review Letters, with Etienne Bernard, on what really goes on in two-dimensional melting. See here for the story of the paper.

# Video recordings of research talks

Fast stochastic sampling with irreversible, totally asymmetric, Markov chains (Invited talk at Institute for Pure & Applied Mathematics, UCLA, Los Angeles (USA), 2017)

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

## Event-Chain Monte Carlo: Foundations, Applications, and Prospects

In the last decade, I've been very interested in non-reversible Markov chains, and in the event-chain Monte Carlo. What started (for us) as an ad-hoc Monte Carlo algorithm for hard spheres has morphed into a general method, with the conceptual underpinnings coming out clearer with time. In June 2021, my review *Event-Chain Monte Carlo: Foundations, Applications, and Prospects* was published in Frontiers in Physics. Access is *open*.

## Fast sequential Markov chains

As many people know, the Markov-chain Monte Carlo method in the form of the Metropolis algorithm for reversible Markov chains, was discovered in 1953, by Metropolis, Rosenbluth, Rosenbluth (sic), Teller, and Teller (sic) in a landmark paper. But the authors not only discovered reversible Markov chains, they also implemented the first non-reversible Markov chain! The difference may be a bit difficult to understand here, on a website, but for a reversible Markov chain a move and its inverse must always be likely. This is realized if, in a system of N particles, at each time step, one picks a random particle and moves it through a random displacement (see my book for an explanation). But Metropolis et al. didn't implement it this way: At time 1, they moved particle 1, then at time 2, they moved particle 2, and so on until, at time N+1, the first particle is moved again. This is manifestly non-reversible, but still samples the Boltzmann distribution. In later research, over the decades, it was found that whether one uses the sequential algorithm or chooses particles randomly doesn't make a great deal of a difference. No big deal!

In June 2020, Liang Qin (Laboratoire de Physique, ENS), Philippe Hoellmer (University of Bonn) and I looked into a variant of the sequential Markov chain algorithm, but instead of going sequentially through particle indices, we go sequentially through the directions. In practice, all particles first move (for a long time) along the x-axis, then with an inclination of 1 degree, then 2 degrees, etc (see the above figure). We studied this not for hard disks (as Metropolis et al in 1953), but a simple model of an elastic dipole. What we found was really surprising: By sequentially going through the directions, one induces very persistent counter-clockwise rotation but then, after a while, another very persistent clockwise rotation follows. We were able to prove rigorously that if we replace the 1 degree change by an angle Delta Phi, then in the limit of small Delta Phi, the rolled-out angle diverges! However, we could also prove that the net rotation of the clockwise and counter-clockwise rotations adds up to exactly zero. Finally, we showed numerically that the sequential Markov-chain algorithm is much faster than what we did before. The story is told in this paper.

## Multithreaded event-chain Monte Carlo with local times

In the last few years, our delocalized group has worked on a new paradigm of Markov-chain Monte Carlo methods that break detailed balance yet sample the equilibrium Boltzmann distribution. The algorithms go by the name of 'event-chain Monte Carlo', and as the name indicates, they are event-driven (this means: they hop from event to event, rather than from femto-second timestamp to femto-second timestamp). One of the problem of event-driven algorithms is that they were never successfully parallelized. Looking at today's computer architectures, which are massively parallel (either on GPUs or on shared-memory CPUs), this long provided a bleak outlook for the practical applications of ECMC.

However, in a paper that recently appeared in Computer Physics Communications, Botao Li (from ENS), Synge Todo (from University of Tokyo), A. C. Maggs (from ESCPI Paris) and myself were able to present a multithreaded event-chain Monte Carlo algorithm for hard spheres. Threads synchronize at infrequent breakpoints and otherwise scan for local horizon violations. On x86 and ARM processors, a C++ (OpenMP) implementation that uses compare-and-swap primitives for data access achieves considerable speed-up with respect to single-threaded code. The paper appeared in a computer physics journal, and there is a lot of computer-nerdy content in it (everything is open-source and all our C++ and Python programs are open-source and available on github) . However, there is also a lot of math in the paper, including real lemmas and their proofs, which at the beginning were not at all clear to us. We present a total of six algorithm (the final one goes really fast), and one of them (Algorithm 5) is rigorously proven to be without bugs, as we can map it onto an absorbing Markov chain with 3670 states, that we can analyze exactly (the picture gives a visual impression of the proof).

PS: This is the first paper of Botao Li, first-year (now second-year) graduate student at ENS, and we are all very happy.

## JeLLyFysh-Version1.0 -- a Python application for all-atom event-chain Monte Carlo

For the last few years, the development of irreversible-Markov-chain methods for physics applications has been at a focus of our group's interest. Although we have constantly thought about algorithms (in particular about the event-chain algorithm), no general code was available. This changed during the week of 29 July 2019 where, on Monday, we posted a 50-page manuscript, that has since been accepted by Computer Physics Communications, and on Thursday (1 August 2019), when we pushed to first Version of the associated open-source Python application to GitHub (see https://github.com/jellyfysh, some 15,000 lines of Python3 code). Both works are authored by Philipp Höllmer, Liang Qin, Michael F. Faulkner, A. C. Maggs, and me, and we are all quite proud to have finished. The code is 100% open access (it suffices to go onto the GitHub website and to fork it by clicking on a button). By the way, the program's name is JeLLyFysh (because we think that it will be very helpful to treat systems mostly with water, and some other stuff).

## All-atom Coulomb simulations with irreversible Markov chains

In a nutshell, classical molecular-dynamics simulations consist in computing the forces on particles, at discretized time steps, and in moving these particles in accordance with Newton's law of motion, the famous **F**=m**a**. Likewise (in a nutshell), classical Monte Carlo calculations consist in proposing a move, then in computing the change of the total system energy, and then accepting or rejecting the move with a probability given by the Metropolis filter. How to compute the forces (for molecular dynamics) or the energies (for Monte Carlo) is a science in its own right, whenever the interactions are long-ranged, as for the Coulomb potential. Much used elaborate methods go by the names of *PP* (for particle-particle) or *PPPM* (for particle-particle / particle-mesh), or else *particle-mesh* Ewald etc. They have in common that much ingenuity is applied to compute a quantity (force / energy) that, as we claimed a few years ago, is not needed to drive the system forward! For a recent article in Journal of Chemical Physics, I teamed up with Michael Faulkner, Liang Qin, and Anthony C. Maggs, to show how this can be done in practice. In what, internally, we call our 'Proof-of-Concept paper', we explicitly show how to set up a highly efficient algorithm to simulate a model of liquid water. We indeed confirm that it is possible to sample the Boltzmann distribution (which involves the Boltzmann weight, and therefore the system energy), without computing the energy. As often, the difference lies in the subtle difference between the concepts of 'sampling' (that is, obtaining examples of a certain distribution) and of 'computing' (for example computing the energy). Technically, we succeed in drawing independent samples with a complexity 'N' log 'N' (just like the best PPPM algorithms but, we think, much faster). Now, of course, after the first excitement of our 'confirmation paper', we are all excited by the forthcoming 'benchmark paper', where we will compare not only complexities, but actual running times.

## Thermodynamic phases in two-dimensional active matter

Active matter (for example the collective dynamics of flocks of birds, of schools of fish, etc) is a very *active* field of research in statistical physics. However, active matter cannot really be described by equilibrium statistical theory where the state of what is called *the system* is fully characterized by two numbers (for example the volume and the pressure), and where the statistical weight of each configuration can be attributed an energy E, and a statistical Boltzmann weight exp(-beta E) which depends on the energy alone. Many active materials are two-dimensional (ranging from sheep on a meadow to bacterial colonies to artificial *Janus particles* on a glass place. As we are so much interested in *regular* two-dimensional particle systems (that are described by equilibrium statistical physics), we posed the question of whether there was some kind of continuous passage between the two types of models. Teaming up with Juliane U. Klamser and Sebastian C. Kapfer, we studied this question in detail. Our conclusions were published, in November 2018, in Nature Communications.

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

Continue with Past Research Notices

# Upcoming events

- Ecole normale supérieure, Paris (France) (22 January 2020) Colloquium in memory of Loup Verlet (invited talk: Computer simulation, statistics, and truth, A conversation with the author of Chimères et paradoxes (2007))
- Julius-Maximilians-Universität Würzburg (Germany) (03 February 2020) Department of Physics (Invited Department colloquium)
- University of Tokyo, Institute of Industrial Sciences, Tokyo (Japan) (9 - 12 March 2020) Conference: Grand Views on Soft and Liquid Matter Physics (invited talk, conference canceled)
- University of Tokyo, Physics Department, Tokyo (Japan) (16 - 19 March 2020) (Research visit, Prof. S. Todo, visit candeled)
- Rutgers University, Piscataway, NJ (USA) (10 - 12 May 2020) 123rd Statistical Mechanics Conference (invited talk, conference canceled)
- Lorentz Center, University of Leiden, (Leiden, Netherlands) (27-31 July 2020) Workshop on non-reversible Markovian Monte Carlo (Invited participation)
- Recife, Brazil (25 - 27 October 2020) 35th Meeting of the Brazilian Physical Society (invited plenary 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