Course Outline: Monte Carlo Methods
I. Introduction
A. What are Monte Carlo methods
(MCMs)?
B. A review of relevant
elementary probability and statistics
C. An example: numerical
integration
1.
The curse of dimensionalitycomputational complexity
2.
Computational complexity vs. deterministic methods
3.
Convergence and variance
a. Introduction to variance reduction
i. Crude Monte Carlo
ii. Stratified sampling
iii. Importance sampling
iv Control variates
v. Antithetic variates
vi. Other methods for integration
b. Accelerating rates of convergence via random numbers
i. Overview of pseudorandom number generation
ii. Quasirandom number generation and convergence acceleration
II. MCMs and Linear Operators
A. Linear algebra
1. Approximate summation
2. Approximate matrix-vector multiplication
a. Application to linear system solution via Neumann series
i. Reduction to fixed-point form
ii. Truncation error and absorbing walks
iii. Computational complexity
iv. Advantages and disadvantages
b. Application to eigenvalue problems
i. Power method
ii. Approximate inverse iteration
iii. Computational complexity
iv. Advantages and disadvantages
c. Sequential Monte Carlo and residual correction
3. Open problems
B. Integral equations
1. Integral equations of the second kind
a. Continuous random walks
b. Neumann series and scoring
c. Truncation error and absorbing walks
2. The Boltzmann equation
3. Importance sampling
C. Green's Function Monte
Carlo
1. The Schrödinger equation
2. Random walks
3. Importance sampling
III. Advanced Topics
A. Functional integration
and Brownian motion
1. Brownian motion introduction
2. Measures on infinite dimensional spaces
3. Functional integration
4. The Feynman-Kac formulas
a. Linear parabolic partial differential equations (PDEs)
b. Linear elliptic PDEs
c. Boundary conditions
i. Dirichlet
ii. Neumann
iii. Mixed conditions
B. Solution of PDEs
via stochastic differential equation (SDE) methods
1. Numerical solution of SDEs
2. Functional evaluation
C. Acceleration
techniques
1. Walk on spheres (WOS)
a. Spherical means and Greens theorem
b. Thickening the boundary: the
epsilon-boundary layer
i. The O(epsilon) error introduced
ii. Expected number of steps in the random walk and epsilon
c. Computational complexity
2. Walk on the boundary
a. Convex domains
b. Extensions
3. Greens Function First Passage (GFFP)
a. Extension of WOS
b. Elimination of the epsilon-boundary layer
c. Creation of a Greens function library
d. The simulation-tabulation method
D.
Applications
1. Permeability computations
a. Penetration depth
b. Relationship with capacitance
c. Open problem: anisotropic computations
2. Electrostatics
a. Poisson/Laplace equations
i. Computing the capacitance
ii. Computing charge density
iii. Singular computations
b. Biological electrostatics: the Poisson-Boltzmann equation (PBE)
i. The linearized PBEs
ii. The nonlinear PBE
iii. Boundary conditions
iv. Derivatives
Return to class homepage.