Werner KRAUTH
https://www.lps.ens.fr/~krauth/index.php/Main_Page
MediaWiki 1.6.12
first-letter
Media
Special
Talk
User
User talk
Werner KRAUTH
Werner KRAUTH talk
Image
Image talk
MediaWiki
MediaWiki talk
Template
Template talk
Help
Help talk
Category
Category talk
Main Page
1
3702
2022-03-14T21:22:42Z
Werner
1
/* Markov-chain Monte Carlo: A modern primer */
[[Image:WK caverne des brigands2.jpg|left|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: GH216
<br clear="all" />
CNRS Research Director - Theoretical Physics (Directeur de recherche CNRS - classe exceptionnelle).
From January to June 2018, I was the [https://www.pks.mpg.de/fileadmin/user_upload/MPIPKS/Research/Gutzwiller_Fellows/laudatio_Krauth.pdf 2018 Martin-Gutzwiller fellow] at the [https://www.pks.mpg.de/ 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).
=Markov-chain Monte Carlo: A modern primer=
This is the title of a [[KingsCollege_Masterclass_2022| Masterclass]] that I gave from 28 February through 3 March 2022 at the [https://www.kcl.ac.uk/noneqsys/seminars-and-videos/past-seminars-and-videos Faculty of Natural & Mathematical Sciences at King's College London] (Great Britain). The Masterclass was organized into six separate lectures that treated everything from the foundations of MCMC (Markov-chain Monte Carlo) to modern lifted Markov chains, the concepts of perfect sampling (with practical applications), meta algorithms and, to wrap up: consensus sampling. The wonderful week at King's and in central London was my first physics trip since February 2020. While at King's College London, I also gave a talk [http://www.lps.ens.fr/%7Ekrauth/images/1/1c/KingsSeminar.pdf Fast non-reversible Markov chains in statistical physics], that included some of our most recent work.
__FORCETOC__
<!--
Here is hidden text
-->
=Workshop on ECMC and related subjects=
An informal [[Workshop_ECMC_11_May_2021|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 [[Group_WK|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 ([http://www.lps.ens.fr/%7Ekrauth/images/b/be/CECAM50Krauth.pdf slides]) that I gave on September 10, 2019 at the [https://cecam50.cecam.org 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=
[[Image:Poster Statistical Mechanics 2016.jpg|left|frame|Announcement poster of SMAC2016 [http://www.lps.ens.fr/%7Ekrauth/images/0/03/POSTER_Statistical_Mechanics_2016.pdf Click here for a High-definition version]]]
The 3rd edition of the [http://en.wikipedia.org/wiki/Massive_open_online_course Massive open online course (MOOC)] on [https://www.coursera.org Coursera]: [https://www.coursera.org/course/smac 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. [[Krauth_2014|Look here]] for an editorial that I wrote after 'coming home from a MOOC'.
The 3rd edition of SMAC comes with two major changes:
<ul>
<li>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.</li>
<li>There will be no more certificate, as ENS was unable to keep the certificate free of charge. </li>
</ul>
<br clear="all" />
=Milestone Research=
A [[Engel_et_al_2013| 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 [https://journals.aps.org/pre/collections/pre-25th milestone article for 2013] by the journal's editorial board. This 2013 paper confirmed [[Bernard Krauth 2011| research published in 2011, in Physical Review Letters]], with Etienne Bernard, on what really goes on in two-dimensional melting. See [[Main_Page#Hard-disk_equation_of_state:_First-order_liquid-hexatic_transition_in_two_dimensions_with_three_simulation_methods| here]] for the story of the paper.
=Video recordings of research talks=
[http://www.ipam.ucla.edu/abstract/?tid=14269&pcode=ELWS2 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==
[[Image:Event chain movie small.gif|100px|left|frame|Event-chain Monte Carlo algorithm for hard spheres and related systems (see [[Bernard Krauth Wilson 2009|article with E. P. Bernard and D. B. Wilson]]).
]]
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, [[Krauth_2021| my review ''Event-Chain Monte Carlo: Foundations, Applications, and Prospects'']] was published in Frontiers in Physics. Access is ''open''.
==Fast sequential Markov chains==
[[Image:ConfigurationDipole.png|left|600px|border|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 [https://doi.org/10.1063%2F1.1699114 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 [[Qin_Hoellmer_Krauth_2020| this paper]].
==Multithreaded event-chain Monte Carlo with local times==
[[Image:Coincidence_table_small.jpg|left|600px|border|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 [[Li_Todo_Maggs_Krauth_2020| 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==
[[Image:JeLLyFysh.png|left|600px|border|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 [[Hoellmer Qin Faulkner Maggs Krauth 2019| 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 [[Kapfer_Krauth_2016| we claimed a few years ago]], is not needed to drive the system forward! [[Faulkner_Qin_Maggs_Krauth_2018|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, [[Klamser Kapfer Krauth 2018|in Nature Communications]].
==Irreversible local Markov chains with rapid convergence towards equilibrium==
[[Image:Figure1_Kapfer_Krauth_2017a.jpg|left|600px|border|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 [[Kapfer_Krauth_2017a|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 [[Bernard_Krauth_Wilson_2009|event-chain algorithm]], that we used a lot during the last years.
<br clear="all" />
[[PastResearchNotices| Continue with Past Research Notices]]
=Upcoming events=
* Ecole normale supérieure, Paris (France) (22 January 2020) [https://verlet2020.sciencesconf.org/ Colloquium in memory of Loup Verlet] ([http://www.lps.ens.fr/%7Ekrauth/images/3/38/ENS_Verlet.pdf 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) [https://www.physik.uni-wuerzburg.de/aktuelles/veranstaltungen-aus-der-physik/physikalisches-kolloquium/ Department of Physics] (Invited Department colloquium)
* University of Tokyo, Institute of Industrial Sciences, Tokyo (Japan) (9 - 12 March 2020) [http://stat.scphys.kyoto-u.ac.jp/gvslmp/index.html 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) [https://cmsr.rutgers.edu/news-events-cmsr/statistical-mechanics-conference/icalrepeat.detail/2020/05/10/1959/-/123rd-statistical-mechanics-conference 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) [http://www.sbfisica.org.br/~efnne/xxxiv/index.php/pt/ 35th Meeting of the Brazilian Physical Society] (invited plenary talk)
[[Past_Events |Here is the schedule of past events]]
=Text book=
[[Image:Smac_cover.jpg|1px|center|frame| Cover of a book I wrote in 2006 [http://www.smac.lps.ens.fr/ Here is the book's website] ]]
<br clear="all" />
=Interview, Popular story, video conference=
[http://www.ens.fr/spip.php?article1552&lang=fr 2012 interview at Ecole normale supérieure (in French)]
CNRS special on our work on two-dimensional melting (June 2013) [http://www.cnrs.fr/inp/spip.php?article1799 (in French)] [http://stat.fm.nitech.ac.jp/~isobe/2D_melting_Japanese.htm in Japanese (!)]
[http://savoirsenmultimedia.ens.fr/expose.php?id=962 2012 Conference on time's arrow (video, in French)] in the framework of the Festival "acceleration" [http://www.dhta.ens.fr/recherches/sacre-sciences-art-creation-et/article/appel-a-candidature-doctorat-sacre?lang=fr Sacre Doctoral school]
[https://www.coursera.org/course/smac Video presentation of the Massive Open Online course at ENS]
[[Krauth_2014| Editorial "Coming home from a MOOC", about teaching a Massive Open Online Course (MOOC) (October 2014)]]
[http://www.savoirs.ens.fr/expose.php?id=2206 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)]
[http://www.pro-physik.de/details/physikjournalArticle/10474044/Der_groesste_Hoersaal_der_Welt.html "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=
[[Image:Boson trap fast.gif|100px|right|frame|Direct-sampling algorithm for ideal bosons in a trap (see [[Holzmann Krauth 1999|article with M. Holzmann]]). Adapted for interacting bosons, this algorithm was used in a variety of articles.]]
[[Image:Event chain movie small.gif|100px|left|frame|Event-chain Monte Carlo algorithm for hard spheres and related systems (see [[Bernard Krauth Wilson 2009|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 [[Bernard Krauth 2011|discovery of the first-order liquid-hexatic phase transition in hard disks]]. The method can be generalized to [[Michel_Kapfer_Krauth_2013|continuous potentials]], and we used it to [[Kapfer_Krauth_2014|map out the phase diagrams of soft-disk systems]]. Look [[Event chain.py|here for an implementation of the event-chain algorithm]] ]]
[[image:Exact_diag.jpg|100px|center|frame|Exact diagonalization algorithm for Dynamical mean field theory (see [[Caffarel Krauth 1994|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 [[Georges_Kotliar_Krauth_Rozenberg_1996|review with Georges, Kotliar, and Rozenberg]]]]
[[image:Dimer_cluster.gif|100px|right|frame|Rejection-free cluster algorithm for dimers (see [[Krauth Moessner 2003|article with R. Moessner]]). This algorithm was used for our discovery of a critical phase in three-dimensional dimer models ([[Huse Krauth Moessner Sondhi 2003|paper with Huse, Sondhi, and Moessner]]). Note that dimers flip about a symmetry axis between one valid configuration and another.]]
[[Image:Event_chain_box.gif|100px|left|frame|Alder and Wainwright's event-driven Molecular Dynamics algorithm (1957). (Animation
by Maxim Berman).]]
<br clear="all" />