Main Page

From Werner KRAUTH

Jump to: navigation, search
50px
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: LE110 How to access my office


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

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

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


Contents

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

Announcement poster of SMAC2016  Click here for a High-definition version
Announcement poster of SMAC2016 Click here for a High-definition version

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.


Multithreaded event-chain Monte Carlo with local times

Dipole with two atoms.

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

Coincidence table for two threads.

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

TheJeLLyFysh logo.

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

Mixing time scales for local Markov chains in 1d
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

Here is the schedule of past events

Text book

 Cover of a book I wrote in 2006 Here is the book's website
Cover of a book I wrote in 2006 Here is the book's website


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

Editorial "Coming home from a MOOC", about teaching a Massive Open Online Course (MOOC) (October 2014)

Grande conférence scientifique "Du déterminisme au stochastique : du hasard classique à l'aléatoire quantique", for the incoming science students at ENS (in French, September 2015)

"The largest Lecture Hall in the world", Article in "Physik Journal" on MOOCs, and in particular on my own MOOC (in German, March 2017)

A picture book of algorithms

Direct-sampling algorithm for ideal bosons in a trap (see article with M. Holzmann). Adapted for interacting bosons, this algorithm was used in a variety of articles.
Direct-sampling algorithm for ideal bosons in a trap (see article with M. Holzmann). Adapted for interacting bosons, this algorithm was used in a variety of articles.
Event-chain Monte Carlo algorithm for hard spheres and related systems (see article with E. P. Bernard and D. B. Wilson, including Python implementation). This (fantastic) algorithm, about two orders of magnitude faster than local Monte Carlo, was used in our discovery of the first-order liquid-hexatic phase transition in hard disks. The method can be generalized to continuous potentials, and we used it to map out the phase diagrams of soft-disk systems. Look here for an implementation of the event-chain algorithm
Event-chain Monte Carlo algorithm for hard spheres and related systems (see article with E. P. Bernard and D. B. Wilson, including Python implementation). This (fantastic) algorithm, about two orders of magnitude faster than local Monte Carlo, was used in our discovery of the first-order liquid-hexatic phase transition in hard disks. The method can be generalized to continuous potentials, and we used it to map out the phase diagrams of soft-disk systems. Look here for an implementation of the event-chain algorithm


Exact diagonalization algorithm for Dynamical mean field theory (see article with M. Caffarel). This algorithm has been instrumental in our discovery of a first-order Mott transition in the Hubbard model in infinite dimensions. Much of our early work in the field is written up in our review with Georges, Kotliar, and Rozenberg
Exact diagonalization algorithm for Dynamical mean field theory (see article with M. Caffarel). This algorithm has been instrumental in our discovery of a first-order Mott transition in the Hubbard model in infinite dimensions. Much of our early work in the field is written up in our review with Georges, Kotliar, and Rozenberg
Rejection-free cluster algorithm for dimers  (see article with R. Moessner). This algorithm was used for our discovery of a critical phase in three-dimensional dimer models (paper with Huse, Sondhi, and Moessner). Note that dimers flip about a symmetry axis between one valid configuration and another.
Rejection-free cluster algorithm for dimers (see article with R. Moessner). This algorithm was used for our discovery of a critical phase in three-dimensional dimer models (paper with Huse, Sondhi, and Moessner). Note that dimers flip about a symmetry axis between one valid configuration and another.
Alder and Wainwright's event-driven Molecular Dynamics algorithm (1957). (Animation by Maxim Berman).
Alder and Wainwright's event-driven Molecular Dynamics algorithm (1957). (Animation by Maxim Berman).


Personal tools