Transcript MonteCarlo Method Course - Computer Science Department

Monte Carlo Methods and Grid
Computing
Yaohang Li
Department of Computer Science
North Carolina A&T State University
Textbook

Monte Carlo Methods
– By J. M. Hammersley and D. C. Handscomb

Markov Chain Monte Carlo in Practice
– By Gilks, Richardson, and Spiegelhalter
Course Goals

Let the students master the theory of the Monte
Carlo methods in Computational Science
 Enable the students to apply the Monte Carlo
methods to simulate and solve real-life problems
 Allow the students to use the parallel and
distributed platform such as the grid to perform
large-scale Monte Carlo simulation
Course Design

Methods
– Basic Monte Carlo Methods
– Analysis of Monte Carlo Methods

Simulation Applications
–
–
–
–
–


Biology
Nuclear Physics
Materials
Engineering
Chemistry
Applications on the Grid
Course Projects
– Understand the theory behind Monte Carlo methods
– Apply Monte Carlo methods to solve real-life problems
– Using the Grid as the computational platform

Term Papers
– Survey of the development of Monte Carlo methods
Course Outline

Monte Carlo Methods

– Nuclear Physics
– Radiation Shielding and
– The General Nature of Monte Carlo
Methods
– Short Resume of Statistical Terms
– Random Number Generation


–
Pseudorandom Number Generation
Quasirandom Number Generation
–
– General Principles of the Monte
–
–
–
–
Carlo Methods
Conditional Monte Carlo
Direct Simulation
Solution of Linear Operator
Equations
Metropolis Method
Simulation Applications
–
–

Reactor Criticality
Polymer Science
– Long Polymer Molecules
Statistical Mechanics
– Markov Chain
Computational Biology
– Protein Folding
– Protein Docking
Material Science
– Ab initio Monte Carlo
Grid Computing
– Characteristics of Grid Computing
– Grid-based Monte Carlo
Applications
Introduction to Monte Carlo Methods

What is Monte Carlo method?
– Experimental mathematics


Experiments on random numbers
General Nature of Monte Carlo Methods
– Understand sophisticated problems
– Extensive use in Simulation






Operational research
Nuclear physics
Chemistry
Biology
Medicine
Engineering
– According to word of mouth, about 50% of CPU time of
Department of Energy is spent on Monte Carlo
Computation
Short Resume of Statistical Terms

Recall the basic terms and theories in statistics and
probability
– Random events and probability
– Random variables


Discrete random variable
Continuous random variable
– Distribution



Probability density function
Cumulative distribution function
Various Distributions
–
–
–
–
–
Uniform distribution
Rectangular distribution
Binomial distribution
Poisson distribution
Normal Distribution
– Expectation
Random Number Generation (I)

Generating high-quality random numbers is critical in Monte Carlo
applications
– How random numbers will affect the accuracy of Monte Carlo applications

Generating Pseudorandom Numbers
– Requirement of Pseudorandom Numbers
 Randomness
 Reproducibility
 Efficiency
 Uniformity
– Pseudorandom Number Generator
 LCG
 LFG
 ICG
– Test of Pseudorandom Number Generator

Quasirandom Number Generator
– What are the advantages of quasirandom number generator?
– Types of Quasirandom Number Generators
 Van der Corput Generator
 Halton Generator
 Faure Generator
 Sobol’ Generator
Random Number Generator (II)

Sampling from non-rectangular distributions
– Using the inverse function
– Using the acceptance-rejection method

Class Project 1
– Build a Pseudorandom Number Generator
– Test the Randomness of this Random Number
Generator
– Generating Gaussian Samples using the Pseudorandom
Number Generator
– Build a Quasirandom Number Generator
Direct Simulation

Direct Simulation Methods
– Base on a probabilistic problem
– Build a Monte Carlo model
– Simple general structure

Miscellaneous examples of Direct Simulations
– Operational research problem

Comparative Simulation
 Course Project II
– Develop a Buffon’s Needle Applet to calculate 
General Principles of the
Monte Carlo Method

Crude Monte Carlo Method
– Integral Estimation
 Expectation and variance
 Convergence rate O(cN-1)
 Error estimation
 Avoiding the curse of dimentionality
– Compare with the deterministic numerical
methods
– Compare with hit-or-miss Monte Carlo
Variance Reduction Techniques

Theory Behind Variance Reduction Techniques
– Reduce the constant c of the convergence rate O(cN-1)
of crude Monte Carlo

Variance Reduction Techniques
– Importance Sampling
– Control Variates
– Antithetic Variates
– Regression Methods
– Use of Orthonormal Functions
Course Project III

Develop a program using Crude Monte
Carlo to estimate an integral
ex 1
0 e  1 dx
1

Compare with deterministic methods as
dimension increases
 Apply a variance reduction technique to
compare the convergence rate
Conditional Monte Carlo

Theory of Conditional Monte Carlo
– A special case of the foregoing theory
– Conditional Monte Carlo
– Compare Conditional Monte Carlo with direct
simulation
Solution of Linear Operation Equation

Simultaneous Linear Equations
– x = a + Hx
– Condition of convergence
– von Neumann and Ulam’s random walk method





Sequential Monte Carlo
Fredholm integral equations of the second kind
The Dirichlet Problem
Eigenvalue problems
Course Project IV
– Use the random walk method to develop a program to
simulate the Google search for finding the eigenvector
corresponding to largest eigenvalue
Radiation Shielding and Reactor Criticality

The Shielding Problem
– When a thick shield of absorbing material is exposed to
-radiation (photons), of specified energy and angle of
incidence, what is the intesity and energy-distribution
of the radiation that penetrates the shield?
– Special Handling

The Criticality Problem
– When a pulse of neutrons is injected into a reactor
assembly, will it cause a multiplying chain reaction or
will it be absorbed, and, in particular, what is the size of
the assembly at which the reaction is just able to sustain
itself?
– Eigenvalue Problem

Matrix Method
Problems in Statistical Mechanics

Markov Chains
– Definition of Markov Chains
– Characteristics of Markov Chains
– Categorizing Markov Chains

Problems in equilibrium statistical mechanics
– Thermal equilibrium
– Statistical mechanics system
– Order-disorder phenomena
– Quantum statistics
Exploring the Equilibrium States

Global Minimum and Local Minimum
 Equilibrium States
 Markov Chain Monte Carlo (MCMC)
–
–
–
–
Metropolis-Hastings Method
Simulated Annealing
Simulated Tempering
Accelerated Simulated Tempering (AST)

Developed by Yaohang Li et al.
– Parallel Tempering
– Accelerated Parallel Tempering (APT)

Developed by Yaohang Li et al.
Course Project V





Develop a Program using Metropolis-Hastings
Method to Explore a rough 1-dimensional energy
landscape
Extend the program using a simulated annealing
method
Extend the program using a simulated tempering
method
Analyze the algorithms when dimension increases
Analyze the algorithms when the landscape
becomes rougher
Long Polymer Molecules

Self-avoiding Random Walks
– Walks on a mesh
– Walks in continuous space

Crude Sampling
 Generation of very long walks
 Recent development
– Protein Folding and Docking
Monte Carlo Method in
Material Science

Monte Carlo Process resembles a Physical
Process
– Ab initio Monte Carlo
– Ising Model
– Complex System
High Performance Monte
Carlo Simulation

Characteristics of Monte Carlo Simulation
 Parallel Random Number Generation
 Natural Parallel Monte Carlo Simulation
 High Performance Monte Carlo Simulation
Monte Carlo Applications
and Grid Computing

Grid Computing
– Widely distributed
– Large-scale resource sharing
– Issues


Performance
Trustworthiness

Monte Carlo Applications
– Approximate solutions to a
variety of mathematical
problems

Performing statistical
sampling experiments
– Slow convergence rate,
approximately O(N-1/2)
– Computationally intensive
and naturally parallel
Grid-based Monte Carlo
Applications

Issues in Grid Computing
– From application point of view



Performance
Trustworthiness
Our Approaches
– Address issues from application level
– Analyze characteristics of Monte Carlo applications


Statistical nature
Cryptographic aspect of underlying random number generator
– Develop strategies and tools
Techniques for Grid-based
Monte Carlo Applications

Improve Performance
– N-out-of-M Strategy
– Bio-inspired Scheduling
– Lightweight Checkpoint

Improve Trustworthiness
– Partial Result Validation Scheme
– Intermediate Value Checking
Conclusion
Stimulate the students’ interest in computational
science
 Allow the students to master the methods and
techniques of high performance statistical
simulation
 Develop interdisciplinary research and educational
areas
 Encourage the students to apply the computational
techniques to real-life applications
