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, later generalized as the Metropolis–Hastings 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 the Boltzmann 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).

Review and reception

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. Sometimes called statistical physics or statistical thermodynamics, its applications include many problems in the fields of physics, biology, chemistry, neuroscience, computer science, information theory and sociology. Its main purpose is to clarify the properties of matter in aggregate, in terms of physical laws governing atomic motion.

<span class="mw-page-title-main">Monte Carlo method</span> Probabilistic problem-solving algorithm

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. The name comes from the Monte Carlo Casino in Monaco, where the primary developer of the method, mathematician Stanislaw Ulam, was inspired by his uncle's gambling habits.

<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. New samples are added to the sequence in two steps: first a new sample is proposed based on the previous sample, then the proposed sample is either added to the sequence or rejected depending on the value of the probability distribution at that point. The resulting sequence can be used to approximate the distribution or to compute an integral.

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

Parallel tempering, in physics and statistics, is a computer simulation method typically used to find the lowest energy state of a system of many interacting particles. It addresses the problem that at high temperatures, one may have a stable state different from low temperature, whereas simulations at low temperatures may become "stuck" in a metastable state. It does this by using the fact that the high temperature simulation may visit states typical of both stable and metastable low temperature states.

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

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.

Free-energy perturbation (FEP) is a method based on statistical mechanics that is used in computational chemistry for computing free-energy differences from molecular dynamics or Metropolis Monte Carlo simulations.

<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> American theoretical physicist (born 1949)

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.

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.