WorksPhysics and Astronomy
Molecular simulation from modern statistics: Continuous-time, continuous-space, exact
Abstract
In a world made of atoms, the computer simulation of molecular systems, such as proteins in water, plays an enormous role in science. Software packages that perform these computations have been developed for decades. In molecular simulation, Newton's equations of motion are discretized and long-range potentials are treated through cutoffs or spacial discretization, which all introduce approximations and artifacts that must be controlled algorithmically. Here, we introduce a paradigm for molecular simulation that is based on modern concepts in statistics and is rigorously free of discretizations, approximations, and cutoffs. Our demonstration software reaches a break-even point with traditional molecular simulation at high precision. We stress the promise of our paradigm as a gold standard for critical applications and as a future competitive approach to molecular simulation.
One-sentence summary: A rigorous paradigm for exact non-reversible Markov processes is benchmarked for classical long-range-interacting water.
The fact that all matter consists of atoms has been described as the greatest insight of science [1]. The consequence that matter can be modeled on a computer by following the motion of its atoms leads to the founding paradigm of molecular simulation. It tracks the dynamics and explores the thermodynamic equilibrium of complex molecular systems, for example, a peptide in an explicit water solution with tens of thousands of atoms, all interacting through classical empirical potentials [2]. Molecular simulation is of enormous importance to numerous fields ranging from biology and physics to engineering [3, 4]. Powerful computer packages have been developed over decades [5, 6, 7, 8, 9]. They compute the forces on all atoms at discretized time steps and then update the atomic positions and velocities to integrate the classical equations of motion of molecular dynamics. A voluminous literature is dedicated to the analysis and control of time-discretization errors [see, e.g., Ref. [10]]. Thermostats, understood as “necessary evils” [11], mimic the effect of a coupled thermal reservoir and, in a symptomatic but noncurative treatment, hide the accumulated errors. The limiting factor in molecular dynamics is the computation of forces. The Lennard-Jones interaction is typically cut off beyond a certain distance so that only a few neighbors exert a force on any given atom. The long-range nature of the Coulomb potential, which must be preserved, is usually treated through fast mesh-based Ewald methods [12, 13, 14, 15, 16] that solve the Poisson equation in discretized space. Thermostats and cutoffs as well as the discretizations inherent in long-range interactions introduce approximations and artifacts [11, 17] that complex algorithms aim to keep under control.
We present here an alternative paradigm for molecular simulation that is based on modern concepts in statistics. It is rigorously exact from the start and, by construction, strictly simulates the canonical ensemble without thermostats. Straight-line trajectories of atoms in continuous Monte-Carlo time are interrupted by events. This non-reversible piecewise-deterministic Markov process [18] violates the detailed-balance condition normally associated with thermal equilibrium, but still samples the Boltzmann distribution. Its use has led to spectacular speedups of local Markov chains in statistical physics [19]. Short- and long-range potentials are handled without any cutoffs or discretizations and, as we show in this paper, with competitive efficiency.
The Boltzmann weight (with the inverse temperature and the potential) is expressed as a factorized product of statistically independent factors with factor potentials with that each depend only on a small subensemble of atoms [20]. Every factor stochastically generates a time when the piecewise-deterministic motion must be interrupted. The minimum of these times triggers an event, and determines the initial conditions for the next piece. The total potential and the corresponding forces never need be evaluated, yet the stationary state is rigorously the Boltzmann distribution.
We implement the event-driven paradigm in demonstration software for flexible SPC/Fw water molecules [21] that interact with the long-range Coulomb potential. As a benchmark, we concentrate on the electric polarization [22] (in other words, the total electric dipole moment) that measures the capacity of individual water molecules to rotate and determines the dielectric properties of water. We find that a particular non-reversible Markov process greatly reduces autocorrelation times and overcomes the slow diffusive dynamics of reversible Monte Carlo algorithms, while the factorization does not penalize the dynamics in comparison to molecular dynamics. The polarization decorrelates in a computer time that scales as , similar to mesh-based Ewald methods in molecular dynamics [13] but without their diverging precision-dependent prefactor. Our code reaches a break-even point with respect to a standard molecular-dynamics code much below machine precision, and we point out its great potential for improvement.
Modern-statistics paradigm for SPC/Fw water
In a molecular system with long-range interactions, the force on an atom depends on the position of all other atoms, rendering its evaluation tedious unless one introduces cutoffs or discretizes space. In contrast, we implement a piecewise-deterministic Markov process through the event-chain Monte Carlo algorithm, where a single atom moves at any given moment [20, 23, 24]. The deterministic motion of this atom is interrupted by an event that stops it and sets off a similar motion of a new atom. Factors in the SPC/Fw water model describe O–H bonds, the bending of H–O–H opening angles, O–O intermolecular Lennard-Jones interactions, and the Coulomb interaction between two water molecules. Each factor proposes an independent candidate event time. The minimum over all the candidate event times then realizes the next event, and motion is transferred to another atom contributing to . This succession of events, in which rejections are replaced by transfers, distinguishes our formulation from the usual Metropolis Monte Carlo algorithm [25].
Positions and velocities of atoms define the global state of the physical system. To impose coherency of the physical system, the global state is accessed only through a central mediator [26] that dispatches physically independent computations of candidate events to event handlers. A scheduler weeds through candidate events and identifies the unique event that provides the subsequent transfer of motion, leading to an update of the global state (see Figure 1). The event handlers within the mediator architecture mirror the statistical independence of the factors composing the physical system. This allows us to compose complex interactions in a transparent and independent manner. A number of inequivalent options have been constructed for the update of active particles within event-chain Monte Carlo [27, 28]. Similar flexibility is possible in the updating of velocities [23, 29, 30, 31], as well as in parallelizing [32, 33] it. In this paper, we replace the original straight variant by the substantially more efficient Newtonian event-chain Monte Carlo [29, 31]. It requires no fine-tuning and again exactly samples the canonical Boltzmann distribution. Modern statistics offers an even wider choice of options for the management of events, the choice of factors, and the piecewise-deterministic trajectories, that may well apply to molecular simulation in the approximation-free non-reversible Markov-chain framework.

Figure 1. JELLYFYSH implementation of our Markov-chain paradigm. The mediator splits the global state into statistically independent factors. Factors communicate independent candidate event times, the earliest of which defines the next event. Factors for long-range interactions are bundled, so that the number of event handlers remains limited. Candidate event times are collected by the mediator and then treated in the scheduler. The factor triggering the event then updates the global state, again via the mediator.
Implementation for SPC/Fw water: Cell-veto—Fibonacci sphere
In the event-driven implementation of our method (see Figure 1), a single atom moves among the other atoms and molecules, so that factors are changing with time and in principle yield independent events that would require sorting and managing. Modern statistics allows one to bundle most of these factors and, in the SPC/Fw water model, the mediator interacts with only event handlers that propose candidate event times to the scheduler (see Figure 2A). The bundling allows the processing of each event in constant computer time (for large ) while treating the long-range interactions without approximations.

Figure 2. Long-range interactions with constant computer time per event. (A) The number of candidate events (event handlers) is constant for increasing system sizes. (B) Walker table from which a target cell is sampled according to its cell bound with respect to the active cell containing the moving atom. (C) Different Walker tables for Fibonacci vectors on the unit sphere. The active atom obtains cell bounds from the nearest vector. (D) The thinning procedure confirms (✓) or rejects (✕) the event using the actual event rate of the molecules in the active and target cell.
In the cell-veto algorithm [34], which we use for the bundling, event rates for pairs of molecules interacting with the Coulomb potential are upper-bounded by precomputed, time-independent bounds for these molecules somewhere within a pair of cells (see Figure 2B). The full set of these cell bounds corresponds to the set of bundled factors of the long-range interaction. Walker’s method of aliases [35] conserves the cell bounds in a Walker table. We build separate such tables for multiple directions of the velocity of the moving atom corresponding to Fibonacci vectors on the unit sphere (see Figure 2C). During the simulation, the actual velocity of the moving atom is mapped to the closest Fibonacci vector. The set of cell bounds in the corresponding table provides a single candidate event time for the entire set of bundled factors, and Walker’s method samples an associated single cell bound—and thus a single associated factor—with constant algorithmic complexity. The overestimation of the event rate by the cell bound is corrected in a procedure akin to the thinning of non-homogeneous Poisson processes [36] by confirming the transfer of motion in the event (see Figure 2D). This thinning is performed with the actual positions of the atoms, leading to an exact treatment of the long-range interaction that is independent of the set of cell bounds and the discretization of space.
Benchmarking for SPC/Fw water
For our benchmark, we use JELLYFYSH (32) to sample configurations of SPC/Fw water molecules in a periodic box at standard density and temperature. We implement long-range molecular Coulomb factors with Walker tables that we also adopt for the Lennard-Jones interaction. We find that Newtonian event-chain Monte Carlo, for large , requires a computer time per event that remains constant (see Figure 3A). A large number of unconfirmed events stems from the overestimated cell bounds which, e.g., do not account for the relative orientation of molecules. While the computer time per event is constant, the number of events per Ångström (that is, per unit Monte-Carlo time) increases logarithmically for the Coulomb factors (see Figure 3B), as predicted by theory (28). In summary, our approach requires a computer time scaling as to advance water molecules by a constant distance. This matches the complexity of mesh-based Ewald methods (13), but without their slowdown as the precision is increased.

Figure 3. Event rates and decorrelation in the SPC/Fw water model. (A) Computer time per event in JELLYFYSH. Inset: Number of unconfirmed events per event for different factor types. (B) Event rate in JELLYFYSH for different factor types. (C) Distance to decorrelate the polarization for different sampling algorithms (for molecular dynamics: sum over the average displacements of all atoms per time step).
For concreteness, we compare the decorrelation of the polarization within JELLYFYSH to the LAMMPS software on a single processor with default parameters and a 1 fs time step. To decorrelate this local quantity, both LAMMPS and JELLYFYSH must move the atoms of any water molecule by a characteristic distance, providing a first measure of efficiency (see Figure 3C). Different variants of our method vary in their efficiency, and the recently developed Newtonian event-chain Monte Carlo is an order of magnitude faster than the straight variant. The reversible Metropolis algorithm with single-atom moves [that also reaches an scaling (37) by using a recent variant of the fast multipole method (38)], as implemented in the DL MONTE software package (39), is clearly inferior to our non-reversible methods.
The mesh-based Ewald method implemented in LAMMPS comes with a target accuracy that is based on analytic error estimates obtained from a specific charge distribution [40, 15, 41]. The charges of atoms (which live in continuous space) are mapped onto the grid using an interpolation scheme. Finer grids and higher interpolation orders yield higher target accuracies. We estimate the necessary computer times by changing the grid spacing, using the LAMMPS defaults (see Figure 4A). JELLYFYSH uses the two-atom Coulomb interaction calculated with the historic Ewald summation in continuous space. We tune it to machine precision without any assumptions on the global charge distribution. JELLYFYSH reaches the break-even point to LAMMPS well below machine precision (see Figure 4B), although it has only the status of demonstration software.

Figure 4. LAMMPS–JELLYFYSH benchmark for the SPC/Fw water model. (A) Computer time per step of LAMMPS for different target accuracies of its particle–particle particle–mesh solver. (B) Computer time used by LAMMPS to decorrelate the polarization depends on the target accuracy and the number of water molecules . JELLYFYSH is exact up to machine precision. The break-even precision is indicated.
Discussion
In this paper, we benchmarked an implementation of a modern-statistics paradigm for molecular simulations in the standard SPC/Fw water model. The time dependence of the corresponding Markov process differs from the physical dynamics yet it exactly approaches thermal equilibrium on time scales that are potentially faster than in nature. Its remarkable efficiency (that we expressed as a computer time to decorrelate a local observable, the polarization) 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. In contrast to standard Monte Carlo algorithms that satisfy the detailed-balance condition and only move diffusively, it features finite probability flows, making it capable of moving ballistically. This has already led to considerable speedups in a variety of fields ranging from physics to statistics and machine learning [see, e.g., Refs [24, 42, 43, 44]]. It remains to be seen whether non-local observables, for example large-scale hydrodynamic modes, macroscopic conformations, and order parameters, can similarly benefit from non-reversibility in chemical physics. The second paradox is that in our approach, the Boltzmann distribution is sampled without any approximation yet with great efficiency because the potential (or 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 independent decisions to interrupt the straight-line trajectory into an expression that can be evaluated in constant time. The Walker tables channel long-range Coulomb factors into a single candidate event, which allows us to handle a complex decision (a conjunction of factor-wise decisions of independent factor potentials ) in a few operations, even in the limit.
Our demonstration software is openly available and fully functional. As discussed, it becomes competitive with a traditional molecular-dynamics code at high intrinsic precision. Our method is exact from the very beginning, and future research will be able to concentrate on the most efficient ones among a large choice of cell bounds, factorizations, Fibonacci vectors and variants of the piecewise-deterministic Markov processes. Clearly, more interdisciplinary research from statistics to computational chemistry will clarify whether this provides a sufficiently strong basis for an alternative approach for practical molecular simulation.
With its guarantee for the unbiased sampling of the Boltzmann distributions, our paradigm may serve as a gold standard for molecular simulation in general, capable of identifying artifacts and approximations that may not have been totally eliminated through the symptomatic algorithmic approach to molecular dynamics. Furthermore, given the greater algorithmic freedom for the Markov-chain approach than for molecular dynamics, it may actually become faster than molecular dynamics. Several orders of magnitude in algorithmic speed can certainly be gained by re-engineering our software, which would then be able to tackle the peptide-in-water benchmark problem (2) that has had a major influence over the last decade. The great simplicity of our approach and its present implementation in the JELLYFYSH software may well facilitate further developments.
Acknowledgments
We thank L. Qin for helpful discussions.
Funding: P.H. acknowledges support from the Studienstiftung des deutschen Volkes and from Institut Philippe Meyer. W.K. acknowledges support from the Alexander von Humboldt Foundation.
Author contributions:
Conceptualization: PH, ACM, WK
Formal Analysis: PH
Investigation: PH, ACM
Methodology: PH, ACM, WK
Project administration: ACM, WK Software: PH
Supervision: ACM, WK
Validation: PH, ACM, WK
Visualization: PH
Writing—original draft: PH, WK
Writing—review & editing: PH, ACM, WK
Competing interests: The authors declare that they have no competing interests.
Data and materials availability: The JELLYFYSH software is made available under the GNU GPLv3 license at https://github.com/jellyfysh. All configuration files for the simulations of this paper are part of JELLYFYSH.
Supplementary Materials
Materials and Methods
Supplementary Text
Fig. S1
References (45–63)
Supplementary Materials for Molecular simulation from modern statistics: Continuous-time, continuous-space, exact
Philipp Höllmer; A. C. Maggs; Werner Krauth
The PDF file includes:
Materials and Methods
Supplementary Text

Figure S1. Validation for the SPC/Fw water model. Cumulative distribution function of the absolute value of the electric polarization of SPC/Fw water molecules in a cubic box of side length Å. The simulation protocols of the different sampling methods are described in the Materials and Methods.
Materials and Methods
In this section, we describe the SPC/Fw water model that we studied in this paper. We further specify the simulation protocols for the different sampling algorithms. Finally, we report on our analysis procedure of the time series of the electric polarization.
SPC/Fw Water Model
The atomistic flexible simple point-charge water model SPC/Fw defines a water molecule by three charged interaction sites that represent the oxygen and hydrogen atoms [21]. We treat the canonical ensemble in a cubic box with periodic boundary conditions, i.e., water molecules with atoms in a periodically repeated cubic box of side length at a given temperature K. Within any water molecule , the intramolecular interactions of the SPC/Fw model consist of two harmonic bond potentials and that lead to fluctuations of the O–H bond lengths around their equilibrium length. Likewise, a harmonic bending potential yields a fluctuation of the H–O–H opening angle around an equilibrium value. The intermolecular interactions between two different water molecules and consist of a Lennard-Jones potential between the two oxygen atoms, and a Coulomb potential between all nine pairs of charged atoms. The intermolecular potentials explicitly include the interactions between all periodic images of the two involved water molecules. The total potential of an all-atom configuration is a sum of these factor potentials:
The bond and Lennard-Jones factor potentials depend on two atomic positions; the bending and Coulomb factor potentials depend on three and six atomic positions, respectively (28, Section V A). The empirical parameters of the different potentials of the SPC/Fw water model are as in Ref. [21].
Simulation Protocols—Molecular Dynamics
We use the feature release from February 8, 2023, of LAMMPS [45, 8] for the molecular-dynamics simulations of the SPC/Fw water model in this paper. We use a spherical cut-off for the Lennard-Jones potential. The Coulomb potential is treated by a particle–particle particle–mesh solver [12]. Unless explicitly specified otherwise (as, e.g., in Figure 4B), the solver uses a target accuracy of . Coulomb interactions are partly treated in discretized reciprocal space, whereby the grid size is chosen to meet the target accuracy based on analytic error estimates obtained from a specific global charge distribution [40, 15, 41]. Thermostatting is achieved by integrating Nosé–Hoover-chain equations of motion for the canonical ensemble [46] with a time-reversible measure-preserving Verlet integrator [47]. The time step is 1 fs, and the temperature is relaxed in a timespan of roughly 300 time steps. This simulation protocol for molecular dynamics in LAMMPS is validated by comparing numerical results for SPC/Fw water molecules of all sampling methods of this paper (see Figure S1).
Simulation Protocols—Metropolis Algorithm
We use version 2.07 of the DL_MONTE software package [48, 39, 49] to sample the canonical ensemble of the SPC/Fw water model with the reversible Metropolis algorithm [25], and minimally amended the software to output the electric polarization. We use a spherical cut-off for the Lennard-Jones potential. The Coulomb interaction is treated by an Ewald summation [50] with a target-accuracy tolerance of . The simulations with the event-chain Monte Carlo algorithm in this paper move a single atom at a time. In order to directly compare the dynamics of the reversible Metropolis algorithm with the non-reversible event-chain Monte Carlo algorithm (see Figure 3C), each trial proposes a new position of a single random atom in a proposal cube around its original position. The new position is accepted with the usual Metropolis criterion based on the change of energy. The size of the proposal cube is separately adapted for the hydrogen and oxygen atoms during the simulation to obtain a target acceptance rate of 37%. This simulation protocol for the Metropolis algorithm in DL_MONTE is validated by comparing numerical results for SPC/Fw water molecules of all sampling methods of this paper (see Figure S1).
Simulation Protocols—Event-Chain Monte Carlo
We develop version 2.0 of JELLYFYSH [51, 32] for the event-chain Monte Carlo simulations of the SPC/Fw water model in this paper. In addition to the straight variant implemented in versions , version 2.0 implements the generalized Newtonian event-chain Monte Carlo variant (see Supplementary Text for details). We use the factorization in eq. (1). In particular, we group all the charge–charge Coulomb interactions between two water molecules into a single factor. Theory then predicts an optimal logarithmic increase of the number of events from these molecular Coulomb factors [28] (that is numerically confirmed in Figure 3B).
Straight event-chain Monte Carlo (used in Figure 3C) periodically aligns the unit velocity of the active atom with the coordinate axes. We change the velocity after a chain time of [52]. In an event triggered by a factor , the velocity is transferred to another atom which belongs to . For factors with more than two atoms, the next active atom is chosen according to the ratio lifting scheme [27, 28].
Newtonian event-chain Monte Carlo assigns a velocity label to every atom, but only moves a single one at any time. The velocities are initialized so that the average speed of the active atom during the simulation is approximately one: (see Supplementary Text for details). This is possible because the velocities have no kinematic meaning as they have in molecular dynamics. The physical temperature only rescales the event rates [see eq. (5) in the Supplementary Text]. The velocities are resampled in large time intervals of . This is because Newtonian event-chain Monte Carlo rotates dipoles most efficiently in the limit , while a finite value of ensures irreducibility [53, 31]. Although our generalized Newtonian event-chain Monte Carlo can consider a general mass matrix of the atoms in its events, we set the masses of all atoms to be equal. Then, the events of factors of two atoms can be treated in a deterministic way in which the two involved velocities and the active atom always change. For factors of more than two atoms, we apply a stochastic scheme that corresponds to a generalized ratio lifting scheme (see the Newtonian-pair and Newtonian-general schemes in the Supplementary Text).
The events of the bond factors are computed exactly [see eq. (6) in the Supplementary Text], while the bending factors are treated with a piecewise-linear bounding potential followed by a Poisson thinning procedure [see (32, Section 4.4.5)]. The cell-veto algorithm [34] bundles most molecular Coulomb factors and relies on a cell-occupancy system that tracks the molecular barycenters [we generally adapt the setup described in Ref. (32, Section 5.3.4)]. Very close molecule pairs or surplus molecules in the cell-occupancy system are separately treated with a piecewise-linear bounding potential. The cell bounds for 10 different Fibonacci vectors (see Supplementary Text for details) are estimated by varying the position of an atom in one cell, and the position of a dipole in the other cell. Here, the dipole is aligned with the direction of the gradient of the charge–dipole Coulomb interaction. The maximum event rate multiplied by an empirical prefactor yields the cell bound. During the simulation, the cell bounds in the Walker table are rescaled to the actual speed and charge of the active atom. Events from the cell-veto algorithm are confirmed with a Poisson thinning procedure that compares the actual event rate of the Coulomb interaction between two molecules with the sampled cell bound. To compute the real event rate, we compute the gradients of the Coulomb potential between the nine pairs of charged atoms [see also eq. (5) in the Supplementary Text] with an Ewald summation [50] that is tuned to machine precision without any assumption on the global charge distribution. We also use the cell-veto algorithm to treat most Lennard-Jones factors, although we cut off the interaction beyond the closest images for consistency with the other sampling algorithms. We carefully checked that an alternative spherical cut-off does not change the results of this paper. The cell-veto algorithm for the Lennard-Jones interaction relies on a cell-occupancy system that tracks the oxygens. Very close or surplus oxygen pairs are treated directly [see eq. (6) in the Supplementary Text]. The cell bounds for 10 different Fibonacci vectors are estimated by varying the oxygen positions evenly in the two cells, and again including an empirical prefactor. The parameters of the cell-occupancy systems, as the cell sizes and the number of nearby cells that are excluded from the cell-veto algorithm, are tuned to minimize computer time. As a rule of thumb, the largest possible cells that do not yield any surplus water molecules, and two excluded layers are found to be a good choice. These simulation protocols for straight and Newtonian event-chain Monte Carlo in JELLYFYSH are validated by comparing numerical results for SPC/Fw water molecules of all sampling methods of this paper (see Figure S1).
Simulation Protocols—Creation of Initial Configurations
We create initial configurations in the range from to SPC/Fw water molecules with hydrogen mass Da and oxygen mass Da at a density of using the software package PLAYMOL [54] (commit 67eb56c from 26 November 2019). Initial configurations are equilibrated using a molecular-dynamics simulation of LAMMPS in the isothermal–isobaric ensemble at pressure atm. Similar to thermostatting, barostatting is achieved by integrating the appropriate Nosé–Hoover-chain equations of motion with a Verlet integrator [46, 47] with a time step of 1 fs. This results in initial configurations for the simulations in the canonical ensemble with the different sampling algorithms at slightly different densities for different . We confirmed that these small density variations do not influence the results of this paper.
Analysis of the Electric Polarization
We sample the electric polarization (or the total electric dipole moment , where is the molecular dipole moment of the water molecule ) of the SPC/Fw water system with the different sampling algorithms. The generated “time”-series (where the “time” only has a a physical meaning in molecular dynamics) yields the normalized autocorrelation function
where we explicitly assume that for . The first part of each trajectory in the canonical ensemble is not considered in the equilibrium average. We observe an exponential decay in all sampling algorithms and fit an exponential to extract the time constant and its standard error [see also Ref. (21)]. We naïvely parallelize the Metropolis and event-chain Monte Carlo algorithms by running 20 to 50 independent simulations (where the number of runs grows with ). For every , we then compute the median autocorrelation function and estimate its error with the bootstrap method. These errors are then considered in the least-squares fit.
The units of the autocorrelation time for the different sampling algorithms are physical time for molecular dynamics, Monte-Carlo trials for the Metropolis algorithm, and continuous Monte-Carlo time for the event-chain Monte Carlo algorithms. As a first measure of efficiency of the different dynamics, we compare the autocorrelation distances (see Figure 3C). It gives the average cumulative distance moved by the atoms in each of the sampling schemes. Since only a single atom moves in our implementation of the event-chain Monte Carlo algorithm, it follows that , where is the average speed of the active atom during the simulation. For molecular dynamics, we can compute the average speed of the hydrogen and oxygen atoms with the Maxwell–Boltzmann distribution:
which yields . In the Metropolis algorithm, each trial samples a random displacement vector for a random atom, where is tuned independently for the oxygen and hydrogen atoms to accept the displacement with probability . We can compute the average length of the sampled displacement vector as
Neglecting correlations between rejection probability and the displacement for this first measure of efficiency, we get .
Finally, the computer autocorrelation time of our generalized Newtonian event-chain Monte Carlo algorithm (see Figure 4B) is obtained by combining the autocorrelation distance (see Figure 3C), the event rates (see Figure 3B), and the computer time per event in JELLYFYSH (see Figure 3A).
Similarly, we measure the computer time per time step of molecular dynamics in LAMMPS for different target accuracies of its particle–particle particle–mesh solver (see Figure 4A). This is then combined with the autocorrelation time in the number of time steps.
Supplementary Text
In this supplementary text, we generalize Newtonian event-chain Monte Carlo to smooth factor potentials depending on an arbitrary number of atoms. We further prove that this algorithm satisfies the necessary global-balance condition. Finally, we report on our generation of Fibonacci vectors on the unit sphere.
Generalized Newtonian Event-Chain Monte Carlo
Newtonian event-chain Monte Carlo was originally formulated for the hard-sphere model that contains peculiar stepwise-changing two-body factor potentials [29]. Among various event-chain Monte Carlo variants, it was shown to escape faster from sparse hard-disk packings [53] and to produce favorable rotation dynamics in tethered hard-disk dipoles [31]. Its superiority is confirmed for the rotation dynamics of SPC/Fw water molecules in this paper, but requires its generalization to smooth factor potentials that depend on an arbitrary number of atom positions.
We follow the initial introduction of non-reversible event-chain Monte Carlo as a lifted continuous-time Markov process [20] [see also the formulation as a piecewise-deterministic Markov process in Ref. [55]]. For Newtonian event-chain Monte Carlo for three-dimensional atoms, the lifting framework [56, 57] [see also Refs [24] and (58, Appendix A)] extends the physical all-atom configuration to , with auxiliary lifting variables that represent an all-atom velocity and an activity label , respectively. The physical sample space is thus extended to the lifted sample space , where the set of atom indices, and with a positive-definite symmetric mass matrix and total kinetic energy . The Markov process targets the lifted stationary distribution that separates into the factorized Boltzmann distribution , and the uniform distributions on , and on .
Given a lifted configuration at time , Newtonian event-chain Monte Carlo continuously moves the single active atom starting from its position with its constant velocity up to an event at time , which interrupts the motion: for . The velocities of all other atoms in the all-atom velocity are, at this point, hypothetical, that is, mere labels. The time-dependent event rate , that is, the probability density to interrupt the piecewise-deterministic motion of the active atom , is given by a sum of factor event rates :
Every factor can be considered as statistically independent. Each of them stochastically generates a candidate event time in an inhomogeneous Poisson process based on its factor event rate (that is only nonzero for factor potentials that are actually changed by the motion of the active atom):
Here, is a uniformly distributed random number between 0 and 1 that is drawn separately for each factor . In eq. (6), the cumulative increments of the factor potential under the motion of the active atom with its velocity since are equal to an exponentially distributed random number with mean at the time . If the computation of from eq. (6) is tedious or even impossible, a Poisson thinning procedure may yield candidate event times (36).
At the event time , the motion of the active atom is interrupted at the lifted configuration . An event changes the lifting variables and sets the initial lifted configuration for the next piece in the piecewise-deterministic Markov process.
The event is realized by a unique event-factor . Generalized Newtonian event-chain Monte Carlo proposes an update of the all-atom velocity at time with a force kick in the direction of the gradient of the event-factor potential:
This force kick leaves the kinetic energy invariant and applying it twice yields the original [59]. The event-factor potential only acts on a small subensemble of atoms, and thus only the velocities of these contributing atoms are possibly modified. For the simple choice of an identity mass matrix , eq. (7) may be written as
In Newtonian event-chain Monte Carlo, only a single active atom moves with its velocity at any time. At an event, it must choose the next active atom from the event factor. It also chooses to either change the velocity of all contributing atoms according to eq. (7), or to keep the all-atom velocity constant . Generalized Newtonian event-chain Monte Carlo offers two schemes to treat events. The Newtonian-general scheme applies to general mass matrices and factors that depend on an arbitrary number of atoms. The Newtonian-pair scheme only applies to distance-dependent pair potentials and identity mass matrix .
In the Newtonian-general scheme, the probability for each possible choice or of the lifting variables is given by or , respectively. Here, is a common normalization factor. If the force kick is not applied and stays constant, the active atom always changes because the factor event rate was positive at the time of the event [see eqs. (5) and (6)]. Likewise, if the event-factor potential only depends on a single atom (as for external potentials), the force kick is always applied.
In the Newtonian-pair scheme for distance-dependent pair potentials between two atoms and , and an identity mass matrix , we alternatively exploit the inherent translational invariance to treat the event deterministically. We always apply the force kick in eq. (8) to modify both and , and always change the active atom within the event factor. In this case, eq. (8) is equivalent to an elastic Newtonian collision between two particles of equal mass, and this alternative scheme recovers the original formulation of Newtonian event-chain Monte Carlo for the hard-sphere model [29].
Samples of all-atom configurations that can be used to compute observables are taken at periodic time intervals [29]. Furthermore, Newtonian event-chain Monte Carlo requires resamplings of the all-atom velocity and the active atom in periodic time intervals to become irreducible [31]. We sample and from their respective stationary distributions and . For , this is equivalent to sampling a multivariate Gaussian distribution with mean and covariance matrix , followed by corrections of the total velocity and . The activity label is sampled uniformly from the the set .
Proof of Correctness of Generalized Newtonian Event-Chain Monte Carlo
In order to prove the correctness of the Newtonian event-chain Monte Carlo algorithm for general smooth interactions, we must show that the global balance condition is satisfied. The total probability flow into any lifted configuration consists of a physical flow and a lifting flow and must equal its statistical weight :
The physical flow into stems from the continuous movement of the active atom that was not interrupted by an event with the event rate given in eq. (5). With $\mathbf{x}' = (\mathbf{x}_1,\ldots,\mathbf{x}_{i- … , we get
where the second line uses the detailed-balance property of the factorized Metropolis filter that yields the event rates in eq. (5) and allows to treat all factors as statistically independent [20].
The lifting flow into stems from interrupted motions of lifted configurations with different lifting variables and but the same configuration :
Here, is the probability to change the lifting variables to . For every factor , the lifting flow in eq. (11) exactly cancels the physical flow in eq. (10) so that the global-balance condition in eq. (9) is satisfied. A trivial (inefficient) solution would be to simply invert the velocity of the active atom in an event while keeping it active:
We presented two schemes for the update of the lifting variables in an event of generalized Newtonian event-chain Monte Carlo. The first stochastic Newtonian-general scheme applies for a general number of atoms on the event factor. The second deterministic Newtonian-pair scheme exploits the translational invariance of distance-dependent pair potentials. For the Newtoniangeneral scheme, we get
where the first term applies the force kick, while the second does not. From the necessary condition
it follows that
Here, the second rewriting follows from expressing the trivial equality
as a sum over and from grouping the positive and negative terms separately. The normalization factor in is the same for every possible next active atom . Because of the -functions in eq. (12), the normalization factor can also be written in terms of the velocity after the force kick by replacing in eq. (14). This yields
where we used that the velocity and activity label are uniformly distributed over their sample spaces and , respectively. Eq. (16) concludes the proof that the presented Newtonian-general scheme for the update of the lifting variables in an event by a general factor potential satisfies the global-balance condition of eq. (9). The reflective (23) and forward (30) event-chain Monte Carlo variants can likewise be generalized to factor potentials depending on an arbitrary number of atoms.
For the Newtonian-pair scheme for distance-dependent pair potentials and identity mass matrix , we get
With and , this yields
Here, we again used the uniform distributions of and and the translational invariance . Thus, also the Newtonian-pair scheme satisfies the global-balance condition of eq. (9). We note that it always applies the force kick.
Fibonacci Vectors
The cell-veto algorithm was previously only used for the straight variant of event-chain Monte Carlo [34, 28, 32]. Its finite set of possible velocities of the single active atom allows to set up a Walker table for every velocity . For instance, for factor pair potentials between the active atom and another atom at positions and , , every cell bound for the pair of cells and in the Walker table may be written as
In principle, a Walker table must be precomputed for every velocity and for every possible cell of the active atom. Symmetries, such as a translational invariance of the factor potential, may heavily reduce the necessary number of Walker tables [28]. During the straight event-chain Monte Carlo simulation, the relevant Walker table is determined by the cell of the currently active atom and its velocity. The generalization of eq. (19) to more complex factors is straightforward. For example, in order to treat the Coulomb interaction between two water molecules in the SPC/Fw water model, the position and orientation of the water molecule containing the active atom may be varied in , while the position and orientation of the other molecule is varied in . From a practical point of view, the cell bounds are usually not computed exactly but rather approximated, e.g., by considering a finite set of positions and , and including a corrective multiplicative prefactor [32]. As long as the approximated cell bound satisfies , a Poisson thinning procedure [36] corrects any overestimate. The quality of , however, does influence the performance because higher cell bounds in the cell-veto algorithm yield more events per unit distance that have to be confirmed by computing the actual event rate.
The inherent discretization of continuous space in eq. (19) can be translated to a continuous velocity space, as it appears, e.g., in Newtonian event-chain Monte Carlo. Consider a finite number of unit vectors on the two-dimensional unit sphere, and let be the associated Voronoi cells under some distance function. We can then formally compute the cell bounds for every Voronoi cell as
The results are used to precompute Walker tables for every Voronoi cell and for every cell , where symmetries may again heavily reduce the number of actually necessary tables. During the Newtonian event-chain Monte Carlo simulation, the relevant Walker table is determined by finding the cell of the currently active atom and the Voronoi cell of its normalized velocity . We can then correct all cell bounds in the relevant Walker table to the actual speed of the active atom by multiplying them with .
In this paper, as proof of concept, we map a generalized Fibonacci lattice onto a two-dimensional unit sphere by the Lambert cylindrical equal-area projection to generate unit vectors .
where and
with the golden ratio [60, 61, 62]. The empirical choice of the parameter optimizes the average nearest-neighbor distance of the Fibonacci vectors . As a distance function to construct the Voronoi cells , we use the quick-to-evaluate cosine distance. Eqs. (21) and (22) efficiently generate an arbitrary number of Fibonacci vectors with a nearly uniform distribution. However, there is no efficient inverse mapping from a general velocity to the closest Fibonacci vector . This is not a problem in this paper because we choose small. Then, can be found by brute force. If considerably larger values of become necessary, other point configurations on the two-dimensional unit sphere may be considered [62, 63]. For the uniform SPC/Fw water systems in this paper, the Walker tables do not strongly depend on the respective Fibonacci vector. The proper discretization of velocity space will, however, impact the performance of Newtonian event-chain Monte Carlo in nonuniform systems.
References
- [1]R. Feynman, R. Leighton, M. Sands, The Feynman Lectures on Physics, Vol. 1: Mainly Mechanics, Radiation, and Heat, vol. 1 of The Feynman Lectures on Physics (Addison-Wesley Publishing Company, 1963).
- [2]D. E. Shaw, et al., Atomic-Level Characterization of the Structural Dynamics of Proteins, Science 330, 341 (2010).DOI
- [3]T. Schlick, Molecular Modeling and Simulation: An Interdisciplinary Guide (Springer-Verlag, 2002).
- [4]M. Karplus, Development of Multiscale Models for Complex Chemical Systems: From H + H₂ to Biomolecules (Nobel Lecture), Angew. Chem. Int. Ed. 53, 9992 (2014).
- [5]D. A. Case, et al., The Amber biomolecular simulation programs, J. Comput. Chem. 26, 1668 (2005).
- [6]B. R. Brooks, et al., CHARMM: The biomolecular simulation program, J. Comput. Chem. 30, 1545 (2009).
- [7]H. Berendsen, D. van der Spoel, R. van Drunen, GROMACS: A message-passing parallel molecular dynamics implementation, Comput. Phys. Commun. 91, 43 (1995).DOI
- [8]A. P. Thompson, et al., LAMMPS - a flexible simulation tool for particle-based materials modeling at the atomic, meso, and continuum scales, Comput. Phys. Commun. 271, 108171 (2022).
- [9]J. C. Phillips, et al., Scalable molecular dynamics on CPU and GPU architectures with NAMD, J. Chem. Phys. 153, 044130 (2020).DOI
- [10]K. D. Hammonds, D. M. Heyes, Shadow Hamiltonian in classical NVE molecular dynamics simulations: A path to long time stability, J. Chem. Phys. 152, 024114 (2020).DOI
- [11]J. Wong-ekkabut, M. Karttunen, The good, the bad and the user in soft matter simulations, Biochim. Biophys. Acta - Biomembr. 1858, 2529 (2016).
- [12]R. W. Hockney, J. W. Eastwood, Computer Simulation Using Particles (CRC Press, 1988).
- [13]T. Darden, D. York, L. Pedersen, Particle mesh Ewald: An N · log(N) method for Ewald sums in large systems, J. Chem. Phys. 98, 10089 (1993).
- [14]U. Essmann, et al., A smooth particle mesh Ewald method, J. Chem. Phys. 103, 8577 (1995).
- [15]H. G. Petersen, Accuracy and efficiency of the particle mesh Ewald method, J. Chem. Phys. 103, 3668 (1995).
- [16]B. Kohnke, C. Kutzner, H. Grubmüller, A GPU-Accelerated Fast Multipole Method for GROMACS: Performance and Accuracy, J. Chem. Theory Comput. 16, 6938 (2020).DOI
- [17]C. L. Wennberg, T. Murtola, B. Hess, E. Lindahl, Lennard-Jones Lattice Summation in Bilayer Simulations Has Critical Effects on Surface Tension and Lipid Properties, J. Chem. Theory Comput. 9, 3527 (2013).
- [18]M. H. A. Davis, Piecewise-Deterministic Markov Processes: A General Class of Non-Diffusion Stochastic Models, J. R. Stat. Soc. Series B Stat. Methodol. 46, 353 (1984).
- [19]E. P. Bernard, W. Krauth, Two-Step Melting in Two Dimensions: First-Order Liquid-Hexatic Transition, Phys. Rev. Lett. 107, 155704 (2011).
- [20]M. Michel, S. C. Kapfer, W. Krauth, Generalized event-chain Monte Carlo: Constructing rejection-free global-balance algorithms from infinitesimal steps, J. Chem. Phys. 140, 054116 (2014).DOI
- [21]Y. Wu, H. L. Tepper, G. A. Voth, Flexible simple point-charge water model with improved liquid-state properties, J. Chem. Phys. 124, 024503 (2006).
- [22]S. W. de Leeuw, J. W. Perram, E. R. Smith, Simulation of electrostatic systems in periodic boundary conditions. I. Lattice sums and dielectric constants, Proc. R. Soc. A 373, 27 (1980).
- [23]E. P. Bernard, W. Krauth, D. B. Wilson, Event-chain Monte Carlo algorithms for hard-sphere systems, Phys. Rev. E 80, 056704 (2009).
- [24]W. Krauth, Event-Chain Monte Carlo: Foundations, Applications, and Prospects, Front. Phys. 9, 229 (2021).
- [25]N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller, Equation of State Calculations by Fast Computing Machines, J. Chem. Phys. 21, 1087 (1953).
- [26]E. Gamma, R. Helm, R. Johnson, J. M. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software (Addison-Wesley Professional, 1994).
- [27]J. Harland, M. Michel, T. A. Kampmann, J. Kierfeld, Event-chain Monte Carlo algorithms for three- and many-particle interactions, EPL 117, 30001 (2017).
- [28]M. F. Faulkner, L. Qin, A. C. Maggs, W. Krauth, All-atom computations with irreversible Markov chains, J. Chem. Phys. 149, 064113 (2018).
- [29]M. Klement, M. Engel, Efficient equilibration of hard spheres with Newtonian event chains, J. Chem. Phys. 150, 174108 (2019).
- [30]M. Michel, A. Durmus, S. Sénécal, Forward Event-Chain Monte Carlo: Fast Sampling by Randomness Control in Irreversible Markov Chains, J. Comput. Graph. Stat. 29, 689 (2020).
- [31]P. Höllmer, A. C. Maggs, W. Krauth, Hard-disk dipoles and non-reversible Markov chains, J. Chem. Phys. 156, 084108 (2022).
- [32]P. Höllmer, L. Qin, M. F. Faulkner, A. Maggs, W. Krauth, JeLLyFysh-Version1.0 — a Python application for all-atom event-chain Monte Carlo, Comput. Phys. Commun. 253, 107168 (2020).
- [33]B. Li, S. Todo, A. Maggs, W. Krauth, Multithreaded event-chain Monte Carlo with local times, Comput. Phys. Commun. 261, 107702 (2021).
- [34]S. C. Kapfer, W. Krauth, Cell-veto Monte Carlo algorithm for long-range systems, Phys. Rev. E 94, 031302 (2016).
- [35]A. J. Walker, An Efficient Method for Generating Discrete Random Variables with General Distributions, ACM Trans. Math. Softw. 3, 253 (1977).
- [36]P. A. W. Lewis, G. S. Shedler, Simulation of nonhomogeneous Poisson processes by thinning, Nav. Res. Logist. Q. 26, 403 (1979).
- [39]J. Purton, J. Crabtree, S. Parker, DL_MONTE: a general purpose program for parallel Monte Carlo simulation, Mol. Simul. 39, 1240 (2013).
- [40]J. Kolafa, J. W. Perram, Cutoff Errors in the Ewald Summation Formulae for Point Charge Systems, Mol. Simul. 9, 351 (1992).
- [41]M. Deserno, C. Holm, How to mesh up Ewald sums. II. An accurate error estimate for the particle–particle–particle-mesh algorithm, J. Chem. Phys. 109, 7694 (1998).
- [42]P. Vanetti, A. Bouchard-Côté, G. Deligiannidis, A. Doucet, Piecewise-Deterministic Markov Chain Monte Carlo, arXiv: 1707.05296 [stat.ME] (2018).arxiv.org/abs/1707.05296
- [43]P. Fearnhead, J. Bierkens, M. Pollock, G. O. Roberts, Piecewise Deterministic Markov Processes for Continuous-Time Monte Carlo, Statist. Sci. 33, 386 (2018).
- [44]J. Bierkens, S. Grazzi, K. Kamatani, G. Roberts, Proceedings of the 37th International Conference on Machine Learning, H. Daumé III, A. Singh, eds. (PMLR, 2020), vol. 119 of Proceedings of Machine Learning Research, pp. 908–918.
- [45]S. Plimpton, A. Thompson, S. Moore, A. Kohlmeyer, R. Berger, LAMMPS, Feature release 8 February 2023, https://www.lammps.org (2023). Last accessed: 31 May 2023.
- [46]W. Shinoda, M. Shiga, M. Mikami, Rapid estimation of elastic constants by molecular dynamics simulation under constant stress, Phys. Rev. B 69, 134103 (2004).
- [47]M. E. Tuckerman, J. Alejandre, R. López-Rendón, A. L. Jochim, G. J. Martyna, A Liouville-operator derived measure-preserving integrator for molecular dynamics simulations in the isothermal–isobaric ensemble, J. Phys. A: Math. Gen. 39, 5629 (2006).
- [48]A. Brukhno, et al., DL_MONTE, version 2.07, https://gitlab.com/dl_monte/user-hub/-/wikis/home (2020). Last accessed: 31 May 2023.
- [49]A. V. Brukhno, et al., DL_MONTE: a multipurpose code for Monte Carlo simulation, Mol. Simul. 47, 131 (2021).
- [50]P. P. Ewald, Die Berechnung optischer und elektrostatischer Gitterpotentiale, Ann. Phys. 369, 253 (1921).
- [51]P. Höllmer, A. C. Maggs, W. Krauth, JeLLyFysh, version 2.0, https://github.com/jellyfysh/JeLLyFysh (2023). Last accessed: 01 June 2023.
- [52]L. Qin, Application of irreversible Monte Carlo in realistic long-range systems, Phd thesis, Université Paris Sciences et Lettres (2020).
- [53]P. Höllmer, N. Noirault, B. Li, A. C. Maggs, W. Krauth, Sparse Hard-Disk Packings and Local Markov Chains, J. Stat. Phys. 187 (2022).
- [54]C. R. A. Abreu, Playmol, commit 67eb56c from 26 November 2019, http://atoms.peq.coppe.ufrj.br/playmol/index.html (2019). Last accessed: 01 June 2023.
- [55]A. Monemvassitis, A. Guillin, M. Michel, PDMP Characterisation of Event-Chain Monte Carlo Algorithms for Particle Systems, J. Stat. Phys. 190, 66 (2023).
- [56]F. Chen, L. Lovász, I. Pak, Lifting Markov Chains to Speed up Mixing, Proceedings of the 17th Annual ACM Symposium on Theory of Computing p. 275 (1999).
- [57]P. Diaconis, S. Holmes, R. M. Neal, Analysis of a nonreversible Markov chain sampler, Ann. Appl. Probab. 10, 726 (2000).
- [59]E. A. J. F. Peters, G. de With, Rejection-free Monte Carlo sampling for general potentials, Phys. Rev. E 85, 026703 (2012).
- [60]M. Roberts, How to evenly distribute points on a sphere more effectively than the canonical Fibonacci Lattice, https://web.archive.org/web/20230527141637/http://extremelearning.com.au/how-to-evenly-distribute-points-on-a-sphere-more-effectively-than-the-c (2020). Last accessed: 30 May 2023.
- [61]Y. Feng, An effective energy-conserving contact modelling strategy for spherical harmonic particles represented by surface triangular meshes with automatic simplification, Comput. Methods Appl. Mech. Eng. 379, 113750 (2021).
- [62]D. P. Hardin, T. J. Michaels, E. B. Saff, A Comparison of Popular Point Configurations on S², arXiv: 1607.04590 [math.NA] (2016).arxiv.org/abs/1607.04590
- [63]B. Keinert, M. Innmann, M. Sänger, M. Stamminger, Spherical Fibonacci Mapping, ACM Trans. Graph. 34, 193 (2015).