Equation of State Calculations by Fast Computing Machines

Last updated

"Equation of State Calculations by Fast Computing Machines" is a scholarly article published by Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller in the Journal of Chemical Physics in 1953. [1] This paper proposed what became known as the Metropolis Monte Carlo algorithm, which forms the basis for Monte Carlo statistical mechanics simulations of atomic and molecular systems. [2]

Contents

Development

Some controversy exists with regard to credit for development of the algorithm. Prior to 2003, there was no detailed account of the algorithm's development. Then, shortly before his death, Marshall Rosenbluth attended a 2003 conference at LANL marking the 50th anniversary of the 1953 publication. At this conference, Rosenbluth described the algorithm and its development in a presentation titled "Genesis of the Monte Carlo Algorithm for Statistical Mechanics". [3] Further historical clarification is made by Gubernatis in a 2005 journal article [4] recounting the 50th anniversary conference. Rosenbluth makes it clear that he and his wife Arianna did the work, and that Metropolis played no role in the development other than providing computer time. Rosenbluth credits Teller with a crucial but early suggestion to "take advantage of statistical mechanics and take ensemble averages instead of following detailed kinematics". Additional clarification of attribution is given in connection with the Metropolis–Hastings algorithm. The Rosenbluths would subsequently publish two additional, lesser-known papers using the Monte Carlo method, [5] [6] while the other authors would not continue to work on the topic. Already in 1953, however, Marshall was recruited to work on Project Sherwood and thereafter turned his attention to plasma physics. Here he laid the foundation for much of modern plasma fluid and kinetic theory, and particularly the theory of plasma instabilities.

Algorithm

Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. In statistical mechanics applications prior to the introduction of the Metropolis algorithm, the method consisted of generating a large number of random configurations of the system, computing the properties of interest (such as energy or density) for each configuration, and then producing a weighted average where the weight of each configuration is its Boltzmann factor, exp(−E/kT), where E is the energy, T is the temperature, and k is Boltzmann's constant. The key contribution of the Metropolis paper was the idea that

Instead of choosing configurations randomly, then weighting them with exp(−E/kT), we choose configurations with a probability exp(−E/kT) and weight them evenly.

— Metropolis et al., [1]
Periodic boundary conditions. When the green particle moves through the top of the central sphere, it reenters through the bottom. Limiteperiodicite.svg
Periodic boundary conditions. When the green particle moves through the top of the central sphere, it reenters through the bottom.

This change makes the sampling focus on the low-energy configurations, which contribute the most to the Boltzmann average, resulting in improved convergence. To choose configurations with a probability exp(−E/kT) that can be weighed evenly, the authors devised the following algorithm: 1) each configuration is generated by a random move on the previous configuration and the new energy is computed; 2) if the new energy is lower, the move is always accepted; otherwise the move is accepted with a probability of exp(−ΔE/kT). When a move is rejected, the last accepted configuration is counted again for the statistical averages and is used as a base for the next attempted move.

The main topic of the article was the numerical calculation of the equation of state for a system of rigid spheres in two dimensions. Subsequent work generalized the method to three dimensions and to fluids using the Lennard-Jones potential. The simulations were done for a system of 224 particles; each simulation consisted of up to 48 cycles, where each cycle consisted of moving each particle once and took about three minutes of computer time using the MANIAC computer at Los Alamos National Lab.

To minimize surface effects, the authors introduced the use of periodic boundary conditions. This means that the simulated system is treated as a unit cell in a lattice, and when a particle moves out of the cell, it automatically comes in through the other side (making the system a topological torus).

According to a perspective published nearly fifty years later by William L. Jorgensen, "Metropolis et al. introduced the samplic method and periodic boundary conditions that remain at the heart of Monte Carlo statistical mechanics simulations of fluids. This was one of the major contributions to theoretical chemistry of the twentieth century." [2] As of 2011, the article has been cited over 18,000 times. [7]

In another perspective, it was said that although "the Metropolis algorithm began as a technique for attacking specific problems in numerical simulations of physical systems [...] later, the subject exploded as the scope of applications broadened in many surprising directions, including function minimization, computational geometry, and combinatorial counting. Today, topics related to the Metropolis algorithm constitute an entire field of computational science supported by a deep theory and having applications ranging from physical simulations to the foundations of computational complexity." [8]

See also

Related Research Articles

In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic behavior of nature from the behavior of such ensembles.

Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle. They are often used in physical and mathematical problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are mainly used in three problem classes: optimization, numerical integration, and generating draws from a probability distribution.

<span class="mw-page-title-main">Metropolis–Hastings algorithm</span> Monte Carlo algorithm

In statistics and statistical physics, the Metropolis–Hastings algorithm is a Markov chain Monte Carlo (MCMC) method for obtaining a sequence of random samples from a probability distribution from which direct sampling is difficult. This sequence can be used to approximate the distribution or to compute an integral. Metropolis–Hastings and other MCMC algorithms are generally used for sampling from multi-dimensional distributions, especially when the number of dimensions is high. For single-dimensional distributions, there are usually other methods that can directly return independent samples from the distribution, and these are free from the problem of autocorrelated samples that is inherent in MCMC methods.

<span class="mw-page-title-main">MANIAC I</span> Early computer

The MANIAC I was an early computer built under the direction of Nicholas Metropolis at the Los Alamos Scientific Laboratory. It was based on the von Neumann architecture of the IAS, developed by John von Neumann. As with all computers of its era, it was a one-of-a-kind machine that could not exchange programs with other computers. Metropolis chose the name MANIAC in the hope of stopping the rash of silly acronyms for machine names, although von Neumann may have suggested the name to him.

<span class="mw-page-title-main">Nicholas Metropolis</span> American mathematician

Nicholas Constantine Metropolis was a Greek-American physicist.

In numerical analysis, stochastic tunneling (STUN) is an approach to global optimization based on the Monte Carlo method-sampling of the function to be objective minimized in which the function is nonlinearly transformed to allow for easier tunneling among regions containing function minima. Easier tunneling allows for faster exploration of sample space and faster convergence to a good solution.

Quantum Monte Carlo encompasses a large family of computational methods whose common aim is the study of complex quantum systems. One of the major goals of these approaches is to provide a reliable solution of the quantum many-body problem. The diverse flavors of quantum Monte Carlo approaches all share the common use of the Monte Carlo method to handle the multi-dimensional integrals that arise in the different formulations of the many-body problem.

<span class="mw-page-title-main">Marshall Rosenbluth</span> American physicist

Marshall Nicholas Rosenbluth was an American plasma physicist and member of the National Academy of Sciences, and member of the American Philosophical Society. In 1997 he was awarded the National Medal of Science for discoveries in controlled thermonuclear fusion, contributions to plasma physics, and work in computational statistical mechanics. He was also a recipient of the E.O. Lawrence Prize (1964), the Albert Einstein Award (1967), the James Clerk Maxwell Prize for Plasma Physics (1976), the Enrico Fermi Award (1985), and the Hannes Alfvén Prize (2002).

In probability theory, the Gillespie algorithm generates a statistically correct trajectory of a stochastic equation system for which the reaction rates are known. It was created by Joseph L. Doob and others, presented by Dan Gillespie in 1976, and popularized in 1977 in a paper where he uses it to simulate chemical or biochemical systems of reactions efficiently and accurately using limited computational power. As computers have become faster, the algorithm has been used to simulate increasingly complex systems. The algorithm is particularly useful for simulating reactions within cells, where the number of reagents is low and keeping track of every single reaction is computationally feasible. Mathematically, it is a variant of a dynamic Monte Carlo method and similar to the kinetic Monte Carlo methods. It is used heavily in computational systems biology.

Path integral Monte Carlo (PIMC) is a quantum Monte Carlo method used to solve quantum statistical mechanics problems numerically within the path integral formulation. The application of Monte Carlo methods to path integral simulations of condensed matter systems was first pursued in a key paper by John A. Barker.

<span class="mw-page-title-main">Umbrella sampling</span> Sampling technique used in physics

Umbrella sampling is a technique in computational physics and chemistry, used to improve sampling of a system where ergodicity is hindered by the form of the system's energy landscape. It was first suggested by Torrie and Valleau in 1977. It is a particular physical application of the more general importance sampling in statistics.

<span class="mw-page-title-main">David Ceperley</span>

David Matthew Ceperley is a theoretical physicist in the physics department at the University of Illinois Urbana-Champaign or UIUC. He is a world expert in the area of Quantum Monte Carlo computations, a method of calculation that is generally recognised to provide accurate quantitative results for many-body problems described by quantum mechanics.

<span class="mw-page-title-main">Berni Alder</span> American physicist (1925–2020)

Berni Julian Alder was a German-born American physicist specialized in statistical mechanics, and a pioneer of computational modelling of matter.

The following timeline starts with the invention of the modern computer in the late interwar period.

The following is a timeline of scientific computing, also known as computational science.

In statistics and physics, multicanonical ensemble is a Markov chain Monte Carlo sampling technique that uses the Metropolis–Hastings algorithm to compute integrals where the integrand has a rough landscape with multiple local minima. It samples states according to the inverse of the density of states, which has to be known a priori or be computed using other techniques like the Wang and Landau algorithm. Multicanonical sampling is an important technique for spin systems like the Ising model or spin glasses.

The following is a timeline of numerical analysis after 1945, and deals with developments after the invention of the modern electronic computer, which began during Second World War. For a fuller history of the subject before this period, see timeline and history of mathematics.

This is a timeline of key developments in computational mathematics.

<span class="mw-page-title-main">Augusta H. Teller</span> American scientist

Augusta Maria "Mici" Teller was a Hungarian-American scientist and computer programmer, involved in the development of the Metropolis algorithm.

<span class="mw-page-title-main">Arianna W. Rosenbluth</span> American physicist and computer scientist (1927-2020)

Arianna Wright Rosenbluth was an American physicist who contributed to the development of the Metropolis–Hastings algorithm. She wrote the first full implementation of the Markov chain Monte Carlo method.

References

  1. 1 2 Metropolis, N.; Rosenbluth, A.W.; Rosenbluth, M.N.; Teller, A.H.; Teller, E. (1953). "Equation of State Calculations by Fast Computing Machines". Journal of Chemical Physics . 21 (6): 1087–1092. Bibcode:1953JChPh..21.1087M. doi:10.1063/1.1699114. OSTI   4390578. S2CID   1046577.
  2. 1 2 William L. Jorgensen (2000). "Perspective on "Equation of state calculations by fast computing machines". Theoretical Chemistry Accounts: Theory, Computation, and Modeling. 103 (3–4): 225–227. doi:10.1007/s002149900053.
  3. ↑ M.N. Rosenbluth (2003). "Genesis of the Monte Carlo Algorithm for Statistical Mechanics". AIP Conference Proceedings . 690: 22–30. Bibcode:2003AIPC..690...22R. doi:10.1063/1.1632112.
  4. ↑ J.E. Gubernatis (2005). "Marshall Rosenbluth and the Metropolis Algorithm". Physics of Plasmas . 12 (5): 057303. Bibcode:2005PhPl...12e7303G. doi:10.1063/1.1887186.
  5. ↑ Rosenbluth, Marshall; Rosenbluth, Arianna (1954). "Further Results on Monte Carlo Equations of State". The Journal of Chemical Physics. 22 (5): 881–884. Bibcode:1954JChPh..22..881R. doi:10.1063/1.1740207.
  6. ↑ Rosenbluth, Marshall; Rosenbluth, Arianna (1955). "Monte Carlo Calculation of the Average Extension of Molecular Chains". The Journal of Chemical Physics. 23 (2): 356–359. Bibcode:1955JChPh..23..356R. doi: 10.1063/1.1741967 .
  7. ↑ ISI Web of Knowledge Cited Reference Search. Accessed 2010-09-22.
  8. ↑ I. Beichl and F. Sullivan (2000). "The Metropolis Algorithm". Computing in Science and Engineering. 2 (1): 65–69. Bibcode:2000CSE.....2a..65B. doi:10.1109/5992.814660. S2CID   42433198.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.