Main Page

From Werner KRAUTH

(Difference between revisions)
Jump to: navigation, search
Revision as of 22:19, 5 November 2018
Werner (Talk | contribs)
(→Thermodynamic phases in two-dimensional active matter)
← Previous diff		 Current revision
Werner (Talk | contribs)
(→Upcoming events)
Line 1: Line 1:
[[Image:WK caverne des brigands2.jpg|left|50px]] [[Image:WK caverne des brigands2.jpg|left|50px]]
Werner Krauth Werner Krauth
- Laboratoire de Physique Statistique+ Laboratoire de Physique
École normale supérieure École normale supérieure
24 rue Lhomond 24 rue Lhomond
- 75231 Paris Cedex 05+ 75005 Paris
France France
- Tel +33 (0)1 44 32 34 94 
werner.krauth@ens.fr werner.krauth@ens.fr
- Office: LE110 (first floor) 
<br clear="all" /> <br clear="all" />
-CNRS Research Director (Theoretical Physics).+CNRS Research Director - Theoretical Physics (Directeur de recherche CNRS - classe exceptionnelle).
-Adjunct Professor Ecole normale supérieure (professeur attaché à l'ENS).+Visiting Professor in Physics - University of Oxford (2023 - 26).
-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).+Keeley Visiting Fellow - [https://www.wadham.ox.ac.uk Wadham College] (Oxford, UK) (October 2023 - March 2024).
-In 2018, I was a recipient of the Humboldt research award (Alexander von Humboldt Foundation)+Distinguished Visiting Professor, Simons Center for Computational Physical Chemistry, New York University, New York (NY, USA) - April, May 2024
-__FORCETOC__+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).
-=ICFP Master 2018, Course on Statistical Physics=+In 2018, I was a recipient of the Humboldt research award (Alexander von Humboldt Foundation).
-see [[ICFP_Stat_Physics_2018|this page]] for tutorials and homeworks, syllabus, and lecture notes.+
-=Third MOOC Statistical Mechanics: Algorithms and Computations - Now self-paced=+__FORCETOC__
-[[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]]]+<!--
 +Here is hidden text
 +-->
 +=Oxford Lectures 2025=
-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'.+Since 2023, I have enjoyed myself tremendously as Visiting Professor in Physics at the University of Oxford where, again this year, I spend several months. I'm heavily engaged in research within an incredibly active and collaborative environment. I also give a set of public lectures on [https://www.physics.ox.ac.uk/events/algorithms-and-computations-theoretical-physics-set-lectures Algorithms and Computations in theoretical physics] (see the announcement for a syllabus). [[Oxford_Lectures_2025|Lecture notes are made available]] step by step, or rather [https://www.collinsdictionary.com/dictionary/french-english/au-fil-de-l-eau "with the flow of the water"], as we say in French.
-The 3rd edition of SMAC comes with two major changes: +I am very grateful to the Department and the University to have arranged for me to lecture on one of my favorite subjects, and also to have made these lectures "public". Anyone can attend: Students at the Oxford Physics department (or not), postdocs (or not), young and old, from all walks of life. This year's lectures started on 21 January 2025, and they take place (or rather: they took place) every Tuesday afternoon at 2pm until 11 March 2025.
-<ul>+[[Image:OxfordLectures2025.png|100px|right|frame|Public Lectures at University of Oxford, Tuesdays 2-4pm, 21 January through 11 March 2025 ]]
-<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" /> <br clear="all" />
 +
 +=Research over the ages=
 +A (big) number of months ago, in 1988-89 (sic!), we were fascinated by a certain problem in the then new field of neural-networks research, namely the binary perceptron. The question was about the storage capacity of the now famous Hopfield model that, in a certain continuous case, had long been proven to be 2N, a result due to Thomas M.
 +Cover (1965) and reinterpreted by E. Gardner (1987). We found this result depressing, as it stated that you needed (with, here on the website, a few shortcuts) N real numbers in order to store 2N single bits 0 and 1. This is like paying N gold coins (floats) to buy 2N copper dimes (single bits), clearly a bad deal. So we were very interested in finding out what would happen in the '''binary''' perceptron where, instead of N real numbers (the weights of one row of the Hopfield net) you had N bits (the weights of the binary Hopfield net). Together with Manfred Opper, who then visited ENS (where I did my thesis) from the University of Giessen in Germany, [https://iopscience.iop.org/article/10.1088/0305-4470/22/11/012 we wrote a computational paper], which quite clearly showed that the capacity was reduced from 2 (Cover's result) to a strange number very close to 0.82. At the time, we were quite proud of the two tricks which made our approach work namely, on the one hand, that we approximated the binary patterns with Gaussians patterns (which greatly improved the finite-size scaling) and, on the other hand, that we used [https://en.wikipedia.org/wiki/Gray_code the Gray code] for a certain enumeration job. A few months later, again in 1989, with Marc Mézard, [https://doi.org/10.1051/jphys:0198900500200305700 we conjectured], based on a one-step replica-symmetry-breaking calculation, that the critical capacity had to be equal to 0.833, a known function. In the conclusion of our 1989 paper, we speculated that our solution might well be exact
 +[[Image:KrauthMezard1989RED.png|100px|right|frame|... conclusions of a 1989 paper...]]
 +<br clear="all" />
 +As I mentioned above, this was in 1989, before the bicentennial celebration of the French Revolution and many other events. For a fair number of years (months, I should say), the question of the critical capacity of the binary perceptron fascinated physicists, mathematicians and computer scientists, as it had first fascinated us. But it always appeared that "some more work" was "needed". Then finally, early in 2024, [https://arxiv.org/abs/2404.18902 a keystone paper] was written by Brice Huang, a MIT graduate student in Mathematics. He completed an enormous body of previous works, actually showed that our 0.833 had been correct all along. Brice was awarded the very prestigious [https://lids.mit.edu/news-and-events/news/brice-huang-receives-machtey-award-best-student-paper-focs-2024 Machtey award for best student paper in 2024]. Bravo, congratulations, and celebrations, Brice --- the long wait was worth it and, indeed, "'''some''' more analytical work had been required..."!
=Milestone Research= =Milestone Research=
Line 41: Line 45:
=Video recordings of research talks= =Video recordings of research talks=
 +[https://www.youtube.com/watch?v=b55shxMUFv0 Hard-disk packings and two phase transitions of two-dimensional particle systems] Invited talk at the workshop "Optimal Point Configurations on Manifolds", [https://www.esi.ac.at/ Erwin Schrödinger International Institute for Mathematics and Physics], University of Vienna, Vienna (Austria), 2021 (online talk)
[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) [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= =Current research=
- +[[PastResearchNotices| Go to Past Research Notices]]
I am deeply interested in statistical and condensed-matter physics, often in connection to computation and algorithms. 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. 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.
 +==Fast, approximation-free molecular simulation of the SPC/Fw water model using non-reversible Markov chains==
-==All-atom Coulomb simulations with irreversible Markov chains==+Many fields of computational science concern the sampling of configurations x from a distribution pi(x) which can often be written as pi(x) = exp[-beta E(x)] (that is, as a Boltzmann distribution). The configuration x then refers to the positions of thousands or millions of atoms with complicated, often long-ranged, interactions. Over the years, I have been interested in sampling methods which do not evaluate the energy E (or the difference of energies, or the gradient of E) in order to sample pi(x) = exp[-beta E(x)]. This is possible because of our use of the factorized Metropolis filter within the framework of the event-chain Monte Carlo algorithm. In July 2024, finally, the manuscript [[https://doi.org/10.1038/s41598-024-66172-0 "Fast, approximation-free molecular simulation ... "]] on which I had worked together with Philipp Höllmer and A. C. Maggs was published in the Journal "Scientific Reports". It actually proves that one can simulate large water systems (in our case, the SPC/Fw water model) without any approximation. We generate millions of samples, but absolutely do not know what is the energy of our configurations.
-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 'Confirmation 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==+The remarkable efficiency of our simulation method is rooted in three paradoxes.
-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 are written up [[Klamser Kapfer Krauth 2018| in this paper, and they will appear shortly in Nature Communications]].+First, the Markov process is non-reversible (that is, effectively out-of-equilibrium), yet its steady state coincides
 +with the equilibrium Boltzmann distribution. Second, the Boltzmann distribution exp(−βU) is sampled
 +without any approximation and with great efficiency although the total potential U and its derivatives, the forces,
 +are never evaluated. This sidesteps all the problems with limited-precision calculations of energies and forces.
 +The third paradox is the bundling of O(N) independent decisions to interrupt the straight-line trajectory of the
 +piecewise-deterministic Markov process into an expression that can be evaluated in constant time. The paper is openly accessible, and even all the computer code has been rendered open-source.
-==Irreversible local Markov chains with rapid convergence towards equilibrium==+==Fast, approximation-free molecular simulation of the SPC/Fw water model using non-reversible Markov chains==
-[[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" />+
-==Cell-veto Monte Carlo algorithm for long-range systems== 
-[[Image:Kapfer Krauth Cell Schema.png|left|600px|border|Particle-based simulation (on the left) and cell-based simulation (on the right).]] [[Kapfer_Krauth_2016|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. 
 +==Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains==
 +In recent years, my colleagues and I have worked on a multitude of computational algorithms which improve on the classical methods. Specifically, we have worked on Monte Carlo algorithms based on non-reversible Markov chains. Such algorithms have had successes in applications but are generally difficult to analyze, resulting in a scarcity of exact results. In a recent manuscript [[Essler_Krauth_2023|Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains]], now [https://doi.org/10.1103/PhysRevX.14.041035 published in Physical Review X] with my colleague [https://www.physics.ox.ac.uk/our-people/essler Fabian Essler (Oxford)], we introduce the “lifted” TASEP (totally asymmetric simple exclusion process) as a paradigm for non-reversible Markov chains. Our model can be viewed as a second-generation lifting of the reversible Metropolis algorithm on a one-dimensional lattice and is exactly solvable by an unusual kind of coordinate Bethe ansatz. We establish the integrability of the model and present strong evidence that the lifting leads to relaxation on shorter timescales than in the KPZ (Kardar–Parisi–Zhang) universality class.
-==Event-chain algorithm for continuous spin systems: XY & Heisenberg models, spin glasses==+Here the "Popular Summary" that accompanied our paper:
-[[Image:Michel Mayer Krauth fig3.png|left|600px|border|Event-chain algorithm for spin systems]] In past years, several of our key results, for example about [[Bernard_Krauth_2011|two-dimensional melting for hard disks]] but also the [[Kapfer_Krauth_2014|melting scenario for soft-disk systems]], have relied on the new ''event-chain'' algorithm, that applies to both systems, [[Bernard_Krauth_Wilson_2009|hard-core]] and [[Michel_Kapfer_Krauth_2013|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 [http://www.phys.ens.fr/spip.php?rubrique284&lang=en 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 [[Michel_Mayer_Krauth_2015|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 [[Nishikawa_Michel_Krauth_Hukushima_2015|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.+Markov-chain Monte Carlo (MCMC) algorithms formulate the sampling problem for complex probability distributions as a simulation of fictitious physical systems in equilibrium, where all motion is diffusive and time reversible. But nonreversible algorithms can, in principle, sample distributions much more efficiently. In recent years, a class of “lifted” Markov chains has implemented this idea in practice, but the resulting algorithms are extremely difficult to analyze. In this work, we introduce an exactly solvable paradigm for nonreversible Markov chains.
-<br clear="all" />+
-==Soft-disk melting: From liquid-hexatic coexistence to continuous transitions==+Our paradigm, which we term the lifted totally asymmetric simple exclusion process (TASEP), describes a particular type of nonreversible dynamics for particles on a one-dimensional lattice. We show that this dynamics allows for polynomial speedups in particle number compared to the famous Metropolis MCMC algorithm. The lifted-TASEP dynamics is, in fact, faster than that of any other known class of models. To arrive at our conclusions, we combine exact methods from the theory of integrable models with extensive numerical simulations. In particular, we prove that the lifted TASEP is integrable and determine the scaling of its relaxation and mixing times with system size.
-[[Image:Hard disk melting.jpg|left|100px|border|thumb|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 ([[Bernard_Krauth_2011|until we solved it]]).+Our work opens the door to obtaining mathematically rigorous results for speedups of nonreversible MCMC algorithms, and more generally, of lifted Markov chains arising in interacting many-particle systems.
-<br clear="all" />+
- +[[PastResearchNotices| Continue with Past Research Notices]]
-In a recent [[Kapfer_Krauth_2014|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 [[Bernard_Krauth_Wilson_2009|Event-Chain Monte Carlo]] to [[Michel_Kapfer_Krauth_2013|continuous potentials]]. The recently established [[Bernard_Krauth_2011|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.+
- +
-[[Image:Soft_disks_diagram.png|left|600px|border|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.+
-<br clear="all" />+
- +
-==Efimov-driven phase transitions of the unitary Bose gas==+
-In a recent [[Piatecki Krauth 2013|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.+
- +
-[[Image:Trimers path integral.jpg|left|600px|border|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...+
-[[Image:Borromean_Rings.png|left|600px|border|Here are pictures of three Borromean rings.]]+
-<br clear="all" />+
- +
-==Generalized event-chain Monte Carlo: Rejection-free global-balance algorithms from infinitesimal steps==+
-[[Bernard Krauth Wilson 2009|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 [[Bernard Krauth 2012|earlier attempt]] was rather awkward. This is what we succeeded in doing, with Manon Michel and Sebastian C. Kapfer, in a [[Michel Kapfer Krauth 2013| 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 [[Kapfer Krauth 2014|recent simulations]] with Sebastian C. Kapfer.+
- +
-==Sampling from a polytope and hard-disk Monte Carlo==+
- +
-[[Image:Polytope ballistics plus graph2.jpg|left|100px|border|thumb|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 [[Kapfer Krauth 2013|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. +
-<br clear="all" />+
- +
-==Hard-disk equation of state: First-order liquid-hexatic transition in two dimensions with three simulation methods==+
- +
- +
-[[Image:Eqofstate.jpg|left|200px|border|thumb|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 [[Bernard_Krauth_2011|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. [[Anderson et al 2012| 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 [https://journals.aps.org/pre/collections/pre-25th its milestone paper] for that year. Using three completely independent algorithms ([http://arxiv.org/abs/1211.1646v1 massively parallel local Monte Carlo], molecular dynamics, [[Bernard_Krauth_Wilson_2009|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, [[Anderson et al 2012| take a look at the paper]]. +
- +
-<br clear="all" />+
- +
-==Event-driven Monte Carlo algorithm for general potentials==+
-In recent works, as for example on the [[Bernard_Krauth_2011|melting transition in two dimensions]], the [[Bernard_Krauth_Wilson_2009|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.+
- +
-[[Image:Event stepped move.jpg|left|400px|border|thumb|Move of one particle in the Event-driven MC algorithm]] Recently, in 2012, Etienne Bernard (now at MIT) and I were able to [[Bernard_Krauth_2012| 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 [[Bernard_Krauth_2012#Sophisticated_Python_implementation| 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.+
-<br clear="all" />+
- +
-==Two-dimensional melting: First-order liquid-hexatic transition==+
-[[Image:Phase separation sample.jpg|left|50px]] Here, I show the key figure of [[Bernard_Krauth_2011| 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 +
-[[Bernard_Krauth_Wilson_2009|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, [[Dress_Krauth_1995| the cluster algorithm that I developed with C. Dress]], had failed. +
-<br clear="all" />+
=Upcoming events= =Upcoming events=
- +* Dresden (Germany), [https://www.pks.mpg.de/ Max Planck Institute for the Physics of Complex Systems], [https://www.pks.mpg.de/odcd25 One Dimension, Countless Directions, International Focus Workshop] 20 - 21 November 2025
- +* Trieste (Italy), [https://www.ictp.it/ International Centre for Theoretical Physics], [https://indico.ictp.it/event/10860 School on Quantum Dynamics of Matter, Light and Information] 30 August - 5 September 2025 (Invited lecture series "The second Markov-chain revolution)
- +* Roscoff (France), CECAM workshop "[https://www.cecam.org/workshop-details/crystallization-and-self-assembly-from-soft-matter-to-pharmaceuticals-to-biomineralisation-1420 Crystallization and Self-Assembly: from Soft Matter to Pharmaceuticals to Biomineralisation]" 5 - 7 May 2025 (Invited talk: [https://www.lps.ens.fr/%7Ekrauth/images/0/03/Roscoff.pdf Markov-chain sampling for long-range systems without evaluating total energies / forces])
-* [https://www.mpipks-dresden.mpg.de/ Max Planck Institute for the Physics of Complex Systems], Dresden, Germany, 1 January-30 June 2018 ([https://www.pks.mpg.de/research/divisions-and-groups/martin-gutzwiller-fellow/ Gutzwiller fellow]).+* University of Florence (Italy), [https://www.ggi.infn.it/ Galileo Galilei Institute for Theoretical Physics], Winter School [https://www.ggi.infn.it/showevent.pl?id=493 SFT 2025 Lectures on Statistical Field Theories] 10 - 14 February 2025 (Lecture course: The second Markov-chain revolution).
-* [https://www.aps.org/meetings/march/about.cfm American Physical Society March Meeting], Los Angeles, USA, 5-9 March 2018 (invited talk)+* University of Tokyo, Komaba (Japan) 9th Workshop on Physics between ENS and UTokyo, 11-12 December 2024 (Co-organizer, Talk: Hamiltonian MC vs. event-chain MC: Sampling strategies beyond the diffusive regime)
-* [https://www.physics.hu-berlin.de/en/kolloquium-en/colloquia/institutskolloquium-prof-dr-werner-krauth-lps-ens-paris-und-mpipks-dresden Humboldt-University, Department of Physics], Berlin, Germany, 08 May 2018 (invited institute colloquium)+* University of Cambridge (UK), Isaac Newton Institute for Mathematical Sciences, Workshop: [https://www.newton.ac.uk/event/ssdw04/ Monte Carlo sampling: beyond the diffusive regime] 25 November - 29 November 2024 (Invited talk: Hamiltonian Monte Carlo vs. event-chain Monte Carlo: Synopsis, benchmarks, prospects).
-* [http://www.cvent.com/events/38th-cnls-annual-conference-rate-theory-and-long-timescale-simulations/custom-17-640d136330a74dbcbab25172d9cc600c.aspx CNLS 38th Annual Conference on Rate theory and long timescale Simulations], Santa Fe, New Mexico, USA, 29 May - 1 June 2018 (invited talk) +* University of Oxford (UK), Research stay 15 October - 11 December 2024
-* [http://www.iris-adlershof.de/de/IRIS2018.html IRIS (Integrative Research Institute for the Sciences (IRIS) Symposium 2018] Humboldt-University Berlin, Germany, 21 June 2018 (invited talk).+* Beg Rohu, Brittany (France), Summer School Concepts and Methods of Statistical Physics" 3 - 15 June 2024 (Lecture course: [[BegRohu_Lectures_2024|The second Markov-chain revolution]])
-* [https://www.cecam.org/workshop-1537.html Summer School on Classical and Quantum Monte Carlo methods for Material Science, Nanotechnology and Biophysics], SISSA, Trieste, Italy, 26 June - 13 July 2018 (invited lecture series (12 hours)).+* New York, NY (USA), D. E. Shaw Research, 28 May 2024 (Invited Seminar: [http://www.lps.ens.fr/%7Ekrauth/images/6/6a/DEShaw.pdf Lifted Markov chains---from solvable models to applications in chemical physics])
-* [http://indico.ictp.it/event/8331/overview Summer School on Collective Behaviour in Quantum Matter], International Centre for Theoretical Physics, Trieste, Italy, 27-31 August 2018 (invited lecture series (8 hours)).+* New York University (USA), Simons Center for Computational Physical Chemistry, 21 May 2024 (Seminar: [http://www.lps.ens.fr/%7Ekrauth/images/1/1a/NYU_Simons.pdf Lifted Markov chains---from solvable models to applications in chemical physics])
-* [http://csp2018.ac.ru/key-speakers.html International Conference on Computer Simulation in Physics and beyond], Moscow, Russia, 24 - 27 September 2018 (invited plenary talk).+* Flatiron Institute, Center for Computational Mathematics (New York, NY (USA) 10 May 2024 (Seminar: [http://www.lps.ens.fr/%7Ekrauth/images/3/3e/FlatIronSeminar.pdf Lifted Markov chains---from solvable models to applications in chemical physics]).
-* [http://www.itp.ac.ru/en/http://www.itp.ac.ru/en/ Landau Institute for Theoretical Physics], Chernogolovka, Russia, 28 September 2018 [http://www.itp.ac.ru/en/seminars/scientific-council/#1190 invited Department seminar])+* Stony Brook University (Stony Brook (NY) (USA) Institute for Advanced Computational Science 26 April 2024 (Invited Seminar [http://www.lps.ens.fr/%7Ekrauth/images/9/9d/StonyBrookSeminar.pdf Mixing, stopping, coupling, lifting, and other keys to the second Markov-chain revolution])
-* [http://www.physik.uni-leipzig.de/~janke/CompPhys18/ 19th International NTZ-Workshop on New Developments in Computational Physics], Leipzig, Germany, 29 November - 01 December 2018+* New York University (USA), Simons Center for Computational Physical Chemistry, 1 April - 31 May 2024 (Distinguished Visiting Professor).
-* [https://iciam2019.org International Congress on Industrial and Applied Mathematics] 15-19 July 2019 (Invited talk, mini-symposium on molecular simulation)+* King's College London (UK), Department of Physics, 5 February 2024 (Invited talk: Thermodynamic Integration, fermion sign problem, and real-space renormalization).
-* Conference: Molecular and materials simulation at the turn of the decade: Celebrating 50 years of CECAM, Lausanne, Switzerland, 09 - 12 September 2019 (invited plenary talk)+* University of Cambridge (UK), Department of Physics, 1 February 2024 (Blackboard talk: Thermodynamic Integration, fermion sign problem, and real-space renormalization).
 +* University of Cambridge (UK), Department of Physics, 31 January 2024 ( [http://www.lps.ens.fr/%7Ekrauth/images/1/1e/ColloquiumCambridge.pdf Cavendish Quantum Colloquium: Mixing, stopping, coupling, lifting, and other keys to the second Markov-chain revolution]).
 +* University of Bristol (UK), Department of Mathematics, 25-26 January 2024 ( [https://www.bristolmathsresearch.org/seminar/werner-krauth/ Invited seminar: Lifted TASEP, an integrable example of non-reversible Markov chains]).
 +* University of Bonn (Germany), Fachgruppe Physik/Astronomie, 8 December 2023 (Physikalisches Kolloquium [http://www.lps.ens.fr/%7Ekrauth/images/c/c3/PhysikKolloquium.pdf Mixing, stopping, coupling, lifting, and other keys to the second Monte Carlo revolution]).
 +* University of Bonn (Germany), Institute for applied Mathematics, 7 December 2023 (Invited "Ober"seminar) [http://www.lps.ens.fr/%7Ekrauth/images/3/3b/OberseminarBonn.pdf "The lifted TASEP, an integrable example of non-reversible Markov chains"].
 +* University of Oxford (UK), Department of Physics, CMT Forum, 8 November 2023 [http://www.lps.ens.fr/%7Ekrauth/images/9/9c/Oxford_CMT.pdf Mixing, stopping, lifting, and other keys to the second Markov-chain revolution].
 +* [https://qft.physik.hu-berlin.de/solving-quantum-field-theories-matthiasfest/ Solving Quantum Field theories] (Humboldt University, Berlin) 13-14 September 2023 (Invited talk "Integrability in the PGB Triangle: Souvenirs and Projects")
 +* [https://www.cecam.org/workshop-details/1256 CECAM Conference: "Computational statistical physics in the 21st century: The legacy of Kurt Binder"], Mainz (Germany), 11-13 September 2023 (Participation).
 +* IUPAP Conference on Computational Physics (CCP2023, Kobe, Japan) (Invited keynote talk).
 +* Nogoya Institute of Technology (Nagoya, Japan), Seminar
 +* University of Tokyo (Tokyo, Japan) (Research visit within the NOREMIA Research project framework).
 +* The University of Melbourne (Australia) ([https://www.matrix-inst.org.au/about-us/ MATRIX Institute], Creswick) (26 June-7 July, 2023) Program: [https://www.matrix-inst.org.au/events/monte-carlo-algorithms-in-statistical-mechanics/ Monte Carlo Algorithms in Statistical Mechanics] (Invited participation).
 +* CIRM Marseille
 +* Rutgers University, Piscataway, NJ (USA) 123rd (18-20 December 2022) [https://cmsr.rutgers.edu/news-events-cmsr/statistical-mechanics-conference/icalrepeat.detail/2022/12/18/1959/-/123rd-statistical-mechanics-conference 123rd Statistical Mechanics Conference] (invited talk: Lifted non-reversible Markov chains: From solvable models to real-life applications)
 +* University of Kent, Canterbury (UK) (14-17 November 2022) Invited Lecture series: "Markov-chain Monte Carlo, a modern primer"
 +* International Centre for Theoretical Physics (ICTP), Trieste (Italy) (04-10 September 2022) Summer school "Quantum Dynamics: From Electrons to Qbits" (Invited lecture series "Markov-chain Monte Carlo: A modern primer")
 +* Rudolf Peierls Centre for Theoretical Physics, University of Oxford, Oxford (UK) (01 July 2022) Seminar [http://www.lps.ens.fr/%7Ekrauth/images/6/69/Oxford_Phys_Talk.pdf Fast non-reversible Markov chains for one-dimensional particle systems]
 +* London Mathematical Society, Clay Mathematics Institute and Heilbronn Institute for Mathematical Research, London (UK) 27 June-1 July 2022) Summer school "Point Configurations: Deformations and Rigidity" (distinguished plenary lecture: [http://www.lps.ens.fr/%7Ekrauth/images/c/c0/LondonMath1.pdf Markov-chain Monte Carlo and the hard-disk Universe]).
 +* CECAM, Lausanne (Switzerland) 10-13 May 2022, [https://members.cecam.org/workshops/1124/view Machine Learning Augmented Sampling for the Molecular Sciences] (Invited talk [http://www.lps.ens.fr/%7Ekrauth/images/2/22/CECAM_Tutorial1.pdf Markov-chain Monte Carlo: A modern primer Part 1] [http://www.lps.ens.fr/%7Ekrauth/images/a/ab/CECAM_Tutorial2.pdf Part 2]
 +* King's College London (UK) (28 February-3 March 2022) Masterclass: "Markov-chain Monte Carlo: A modern primer"
 +* [https://www.esi.ac.at/ Erwin Schrödinger International Institute for Mathematics and Physics], University of Vienna (Austria) (17-21 January 2022) workshop "Optimal Point Configurations on Manifolds", (Invited talk [http://www.lps.ens.fr/%7Ekrauth/images/b/b0/ViennaVirtual.pdf Hard-disk packings, fast Markov chains, and the two phase transitions of two-dimensional particle systems] (online talk)
[[Past_Events |Here is the schedule of past events]] [[Past_Events |Here is the schedule of past events]]
Line 167: Line 148:
-[[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:Boson trap fast.gif|100px|right|frame|[[Direct N bosons.py|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: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]] ]]

Current revision

50px
Werner Krauth
Laboratoire de Physique
École normale supérieure
24 rue Lhomond
75005 Paris
France
werner.krauth@ens.fr


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

Visiting Professor in Physics - University of Oxford (2023 - 26).

Keeley Visiting Fellow - Wadham College (Oxford, UK) (October 2023 - March 2024).

Distinguished Visiting Professor, Simons Center for Computational Physical Chemistry, New York University, New York (NY, USA) - April, May 2024

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

[edit]

Oxford Lectures 2025

Since 2023, I have enjoyed myself tremendously as Visiting Professor in Physics at the University of Oxford where, again this year, I spend several months. I'm heavily engaged in research within an incredibly active and collaborative environment. I also give a set of public lectures on Algorithms and Computations in theoretical physics (see the announcement for a syllabus). Lecture notes are made available step by step, or rather "with the flow of the water", as we say in French.

I am very grateful to the Department and the University to have arranged for me to lecture on one of my favorite subjects, and also to have made these lectures "public". Anyone can attend: Students at the Oxford Physics department (or not), postdocs (or not), young and old, from all walks of life. This year's lectures started on 21 January 2025, and they take place (or rather: they took place) every Tuesday afternoon at 2pm until 11 March 2025.

Public Lectures at University of Oxford, Tuesdays 2-4pm, 21 January through 11 March 2025
Public Lectures at University of Oxford, Tuesdays 2-4pm, 21 January through 11 March 2025


[edit]

Research over the ages

A (big) number of months ago, in 1988-89 (sic!), we were fascinated by a certain problem in the then new field of neural-networks research, namely the binary perceptron. The question was about the storage capacity of the now famous Hopfield model that, in a certain continuous case, had long been proven to be 2N, a result due to Thomas M. Cover (1965) and reinterpreted by E. Gardner (1987). We found this result depressing, as it stated that you needed (with, here on the website, a few shortcuts) N real numbers in order to store 2N single bits 0 and 1. This is like paying N gold coins (floats) to buy 2N copper dimes (single bits), clearly a bad deal. So we were very interested in finding out what would happen in the binary perceptron where, instead of N real numbers (the weights of one row of the Hopfield net) you had N bits (the weights of the binary Hopfield net). Together with Manfred Opper, who then visited ENS (where I did my thesis) from the University of Giessen in Germany, we wrote a computational paper, which quite clearly showed that the capacity was reduced from 2 (Cover's result) to a strange number very close to 0.82. At the time, we were quite proud of the two tricks which made our approach work namely, on the one hand, that we approximated the binary patterns with Gaussians patterns (which greatly improved the finite-size scaling) and, on the other hand, that we used the Gray code for a certain enumeration job. A few months later, again in 1989, with Marc Mézard, we conjectured, based on a one-step replica-symmetry-breaking calculation, that the critical capacity had to be equal to 0.833, a known function. In the conclusion of our 1989 paper, we speculated that our solution might well be exact

... conclusions of a 1989 paper...
... conclusions of a 1989 paper...


As I mentioned above, this was in 1989, before the bicentennial celebration of the French Revolution and many other events. For a fair number of years (months, I should say), the question of the critical capacity of the binary perceptron fascinated physicists, mathematicians and computer scientists, as it had first fascinated us. But it always appeared that "some more work" was "needed". Then finally, early in 2024, a keystone paper was written by Brice Huang, a MIT graduate student in Mathematics. He completed an enormous body of previous works, actually showed that our 0.833 had been correct all along. Brice was awarded the very prestigious Machtey award for best student paper in 2024. Bravo, congratulations, and celebrations, Brice --- the long wait was worth it and, indeed, "some more analytical work had been required..."!

[edit]

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.

[edit]

Video recordings of research talks

Hard-disk packings and two phase transitions of two-dimensional particle systems Invited talk at the workshop "Optimal Point Configurations on Manifolds", Erwin Schrödinger International Institute for Mathematics and Physics, University of Vienna, Vienna (Austria), 2021 (online talk)

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

[edit]

Current research

Go to Past Research Notices

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.

[edit]

Fast, approximation-free molecular simulation of the SPC/Fw water model using non-reversible Markov chains

Many fields of computational science concern the sampling of configurations x from a distribution pi(x) which can often be written as pi(x) = exp[-beta E(x)] (that is, as a Boltzmann distribution). The configuration x then refers to the positions of thousands or millions of atoms with complicated, often long-ranged, interactions. Over the years, I have been interested in sampling methods which do not evaluate the energy E (or the difference of energies, or the gradient of E) in order to sample pi(x) = exp[-beta E(x)]. This is possible because of our use of the factorized Metropolis filter within the framework of the event-chain Monte Carlo algorithm. In July 2024, finally, the manuscript ["Fast, approximation-free molecular simulation ... "] on which I had worked together with Philipp Höllmer and A. C. Maggs was published in the Journal "Scientific Reports". It actually proves that one can simulate large water systems (in our case, the SPC/Fw water model) without any approximation. We generate millions of samples, but absolutely do not know what is the energy of our configurations.

The remarkable efficiency of our simulation method is rooted in three paradoxes. First, the Markov process is non-reversible (that is, effectively out-of-equilibrium), yet its steady state coincides with the equilibrium Boltzmann distribution. Second, the Boltzmann distribution exp(−βU) is sampled without any approximation and with great efficiency although the total potential U and its derivatives, the forces, are never evaluated. This sidesteps all the problems with limited-precision calculations of energies and forces. The third paradox is the bundling of O(N) independent decisions to interrupt the straight-line trajectory of the piecewise-deterministic Markov process into an expression that can be evaluated in constant time. The paper is openly accessible, and even all the computer code has been rendered open-source.

[edit]

Fast, approximation-free molecular simulation of the SPC/Fw water model using non-reversible Markov chains

[edit]

Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains

In recent years, my colleagues and I have worked on a multitude of computational algorithms which improve on the classical methods. Specifically, we have worked on Monte Carlo algorithms based on non-reversible Markov chains. Such algorithms have had successes in applications but are generally difficult to analyze, resulting in a scarcity of exact results. In a recent manuscript Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains, now published in Physical Review X with my colleague Fabian Essler (Oxford), we introduce the “lifted” TASEP (totally asymmetric simple exclusion process) as a paradigm for non-reversible Markov chains. Our model can be viewed as a second-generation lifting of the reversible Metropolis algorithm on a one-dimensional lattice and is exactly solvable by an unusual kind of coordinate Bethe ansatz. We establish the integrability of the model and present strong evidence that the lifting leads to relaxation on shorter timescales than in the KPZ (Kardar–Parisi–Zhang) universality class.

Here the "Popular Summary" that accompanied our paper:

Markov-chain Monte Carlo (MCMC) algorithms formulate the sampling problem for complex probability distributions as a simulation of fictitious physical systems in equilibrium, where all motion is diffusive and time reversible. But nonreversible algorithms can, in principle, sample distributions much more efficiently. In recent years, a class of “lifted” Markov chains has implemented this idea in practice, but the resulting algorithms are extremely difficult to analyze. In this work, we introduce an exactly solvable paradigm for nonreversible Markov chains.

Our paradigm, which we term the lifted totally asymmetric simple exclusion process (TASEP), describes a particular type of nonreversible dynamics for particles on a one-dimensional lattice. We show that this dynamics allows for polynomial speedups in particle number compared to the famous Metropolis MCMC algorithm. The lifted-TASEP dynamics is, in fact, faster than that of any other known class of models. To arrive at our conclusions, we combine exact methods from the theory of integrable models with extensive numerical simulations. In particular, we prove that the lifted TASEP is integrable and determine the scaling of its relaxation and mixing times with system size.

Our work opens the door to obtaining mathematically rigorous results for speedups of nonreversible MCMC algorithms, and more generally, of lifted Markov chains arising in interacting many-particle systems.



Continue with Past Research Notices

[edit]

Upcoming events

Here is the schedule of past events

[edit]

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


[edit]

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)

[edit]

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


Retrieved from "http://www.lps.ens.fr/~krauth/index.php/Main_Page"
Personal tools