Transcription
MCMs: Early History and The BasicsMonte Carlo Methods:Early History and The BasicsProf. Michael MascagniDepartment of Computer ScienceDepartment of MathematicsDepartment of Scientific ComputingFlorida State University, Tallahassee, FL 32306 USAE-mail: mascagni@fsu.edu or mascagni@math.ethz.chURL: http://www.cs.fsu.edu/ mascagni
MCMs: Early History and The BasicsOutline of the TalkEarly History of Probability Theory and Monte Carlo MethodsEarly History of Probability TheoryThe Stars Align at Los AlamosThe ProblemsThe PeopleThe TechnologyMonte Carlo MethodsThe BirthGeneral Concepts of the Monte Carlo MethodReferences
MCMs: Early History and The BasicsEarly History of Probability Theory and Monte Carlo MethodsEarly History of Probability TheoryEarly History of Probability TheoryIProbability was first used to understand games of chance1. Antoine Gombaud, chevalier de Méré, a French nobleman calledon Blaise Pascal and Pierre de Fermat were called on to resolve adispute2. Correspondence between Pascal and Fermat led to Huygenswriting a text on “Probability"3. Jacob Bernoulli, Abraham de Moivre, and Pierre-Simon, marquisde Laplace, led development of modern “Probability"4. 1812: Laplace, Théorie Analytique des Probabilités
MCMs: Early History and The BasicsEarly History of Probability Theory and Monte Carlo MethodsEarly History of Probability TheoryEarly History of Monte Carlo: Before Los AlamosIBuffon Needle Problem: Early Monte Carlo (experimentalmathematics)1. Problem was first stated in 1777 by Georges-Louis Leclerc, comtede Buffon2. Involves dropping a needle on a lined surface and can be used toestimate3. Note: Union Capt. Fox did this while in a CSA prison camp, andproduced good results that later turned out to be “fudged”IIn the 1930’s, Fermi used sampling methods to estimatequantities involved in controlled fission
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe Stars Align at Los AlamosILos Alamos brought together many interesting factors to givebirth to modern Monte Carlo algorithms1. The Problems: Simulation of neutron histories (neutronics),hydrodynamics, thermonuclear detonation2. The People: Enrico Fermi, Stan Ulam, John von Neumann, NickMetropolis, Edward Teller, .3. The Technology: Massive human computers using handcalculators, the Fermiac, access to early digital computersIThe Name: Ulam’s uncle would borrow money from the family bysaying that “I just have to go to Monte Carlo”
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe ProblemsThe ProblemsISimulation of neutron histories (neutronics)1. Given neutron positions/momenta, geometry2. Compute flux, criticality, fission yieldIIHydrodynamics due to nuclear implosionSimulation of thermonuclear reactions: ignition, overall yield1. All these problems were more easily solved using MonteCarlo/Lagrangian methods2. Geometry is problematic for deterministic methods but not for MC
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe PeopleThe PeopleIILos Alamos brought together many interesting people to work onthe fission problem:The Physicists1. Enrico Fermi: experimental Nuclear Physics and computationalapproaches2. Nick Metropolis: one of the first “computer programmers” for theseproblems3. Edward Teller: more interested in the “super”
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe PeopleThe PeopleIThe Mathematicians1. Robert Richtmyer: ran the numerical analysis activities at LosAlamos2. Stanislaw (Stan) Ulam: became interested in using “statisticalsampling” for many problems3. John von Neumann: devised Monte Carlo algorithms and helpeddevelop digital computers
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe TechnologyThe TechnologyIISimulation via computation was necessary to make progress atLos AlamosMany different computational techniques were in used1. Traditional digital computation: hand calculators used by efficienttechnicians2. Analog computers including the Fermiac (picture to follow)3. Shortly after the war, access to digital computers: ENIAC atPenn/Army Ballistics Research Laboratory (BRL)4. Continued development and acquisition of digital computers byMetropolis including the MANIAC
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe TechnologyAn Analog Monte Carlo Computer: The FermiacINeutronics required simulating exponentially distributed flightsbased on material cross-sectionsIMany neutron histories are required to get statisticsIFermiac allows simulation of exponential flights inputting thecross-section manuallyIFermiac is used on a large piece of paper with the geometrydrawn for neutronics simulationsIFermiac allows an efficient graphical simulation of neutronicsIParallelism is achievable with the Fermiac
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe TechnologyAn Analog Monte Carlo Computer: The FermiacFigure: A Fermiac at the Bradbury Science Museum in Los Alamos
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe TechnologyAn Analog Monte Carlo Computer: The FermiacFigure: The Fermiac in Action
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe TechnologyAn Early Digital Computer: The ENIACIENIAC: Electronic Numerical Integrator And ComputerIFunded by US Army with contract signed on June 5, 1943IBuilt in secret by the University of Pennsylvania’s Moore Schoolof Electrical EngineeringICompleted February 14, 1946 in Philadelphia and used untilNovember 9, 1946IMoved (with upgrade) to Aberdeen Proving Grounds and beganoperations July 29, 1947IRemained in continuous operation at the Army BRL until 1955
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe TechnologyAn Early Digital Computer: The ENIACIIENIAC is a completely programmable computer using first a plugpanelENIAC first contained (military rejects!)1.2.3.4.5.17,468 vacuum tubes7,200 crystal diodes1,500 relays, 70,000 resistors10,000 capacitorsabout 5 million hand-soldered jointsIClock was 5KHzIEnded up with a 100-word core memoryIMetropolis would go to BRL to work on the “Los Alamos” problemon the ENIAC
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe TechnologyAn Early Digital Computer: The ENIACFigure: The ENIAC at the University of Pennsylvania
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe TechnologyAn Early Digital Computer: The ENIACFigure: Programming the ENIAC
MCMs: Early History and The BasicsThe Stars Align at Los AlamosThe TechnologyAn Early Digital Computer: The ENIACFigure: Tubes from the ENIAC
MCMs: Early History and The BasicsMonte Carlo MethodsThe BirthThe Birth of Monte Carlo MethodsIAfter the was digital computer was perfect for “statisticalsampling”1. Individual samples were often very simple to program2. Small memory was not a big constraint for these methods3. A much better use for digital vs. human computersIEarly Monte Carlo Meetings1. 1952, Los Angeles: RAND Corp., National Bureau of Standards(NIST), Oak Ridge2. 1954, Gainesville, FL: University of Florida Statistical Lab
MCMs: Early History and The BasicsMonte Carlo MethodsThe BirthOther Early Monte Carlo ApplicationsINumerical linear algebra based on sums: S PNi 1ai1. PDefine pi 0 as the probability of choosing index i, withMi 1 pi 1, and pi 0 whenever ai 6 02. Then ai /pi with index i chosenwith {pi } is an unbiased estimate of PMaiS, as E[ai /pi ] i 1 p pi SiIICan be used to solve linear systems of the form x Hx bConsider the linear system: x Hx b, if H H 1, thenthe following iterative method converges:x n 1 : Hx n b, x 0 0,Pk 1and in particular we have x k i 0 H i b, and similarly theNeumann series converges:N XH i (I H) 1 , X N i 0Ii 0 1Formally, the solution is x (I H)b H i Xi 0Hi 11 H
MCMs: Early History and The BasicsMonte Carlo MethodsThe BirthOther Early Monte Carlo ApplicationsIMethods for partial differential and integral equations1. Integral equation methods are similar in construction to the linearsystem methods2. PDEs can be solved by using the Feynman-Kac formula3. Note Kac and Ulam both were trained in Lwów
MCMs: Early History and The BasicsMonte Carlo MethodsGeneral Concepts of the Monte Carlo MethodMonte Carlo Methods: Numerical Experimental thatUse Random NumbersIA Monte Carlo method is any process that consumes randomnumbers1. Each calculation is a numerical experimentIIISubject to known and unknown sources of errorShould be reproducible by peersShould be easy to run anew with results that can be combined toreduce the variance2. Sources of errors must be controllable/isolatableIIProgramming/science errors under your controlMake possible RNG errors approachable3. ReproducibilityIIIMust be able to rerun a calculation with the same numbersAcross different machines (modulo arithmetic issues)Parallel and distributed computers?
MCMs: Early History and The BasicsMonte Carlo MethodsGeneral Concepts of the Monte Carlo MethodEarly Random Number Generators on DigitalComputersIMiddle-Square method: von Neumannx21. 10 digit numbers: xn 1 b 10n5 c (mod 1010 )2. Multiplication leads to good mixing3. Zeros in lead to short periods and cycle collapseILinear congruential method: D. H. LehmerIxn 1 axn c (mod m)IGood properties with good parametersIHas become very popular
MCMs: Early History and The BasicsReferencesReferences[M. Mascagni and H. Chi (2004)]Parallel Linear Congruential Generators with Sophie-GermainModuli,Parallel Computing, 30: 1217–1231.[M. Mascagni and A. Srinivasan (2004)]Parameterizing Parallel Multiplicative Lagged-FibonacciGenerators,Parallel Computing, 30: 899–916.[M. Mascagni and A. Srinivasan (2000)]Algorithm 806: SPRNG: A Scalable Library for PseudorandomNumber Generation,ACM Transactions on Mathematical Software, 26: 436–461.
MCMs: Early History and The BasicsReferencesQuestions?
MCMs: Early History and The BasicsReferencesc Michael Mascagni, 2015
Monte Carlo Methods The Birth The Birth of Monte Carlo Methods I After the was digital computer was perfect for "statistical sampling" 1.Individual samples were often very simple to program 2.Small memory was not a big constraint for these methods 3.A much better use for digital vs. human computers I Early Monte Carlo Meetings
