CPS 713

Monte Carlo Simulation for Statistical Physics

Paul Coddington

Northeast Parallel Architectures Center at Syracuse University

• Statistical Mechanics
  • Statistical Physics
  • Stochastic (probabilistic) Processes
  • Systems with Many Degrees of Freedom
  • Applications of Statistical Mechanics
  • Applications of Statistical Mechanics (cont.)
  • Calculations in Statistical Mechanics
• Spin Models
  • Example: Spin Models of Magnetism
  • Magnetic Phase Transitions
  • Simple Model of Magnetism
  • The Ising Model
  • Ising Ferromagnet
  • Solution of the Ising Model
  • Statistical Mechanics of Spin Models
  • The Boltzmann Distribution
• Monte Carlo Methods
  • Review of Monte Carlo Integration
  • Monte Carlo Simulation
  • Calculating the Partition Function
  • Importance Sampling
  • Markov Processes
  • Detailed Balance
  • The Metropolis Algorithm
  • Monte Carlo Algorithms
  • Monte Carlo References
• Computer Simulation
  • The Metropolis Update
  • Metropolis Algorithm for the Ising Model
  • Programming the Metropolis Algorithm
  • Code for Metropolis Algorithm (in C)
  • Measurements
  • Phase Transitions
  • Critical Exponents
• Problems, Subtleties, and Tricks of the Trade
  • Problems and Subtleties in Monte Carlo Simulations
  • Thermalization
  • Thermalization (cont.)
  • Ergodicity
  • Fitting
  • Finite Size Effects
  • Illustration of Finite Size Effects
  • Finite Size Scaling
  • Finite Size Scaling (cont.)
  • Boundary Conditions
  • Tuning the Acceptance
  • Random Number Generators
  • Random Number Generators (cont.)
  • Critical Slowing Down
  • Critical Slowing Down (cont.)
  • Dynamic Critical Exponents
• Other Monte Carlo Algorithms
  • Acceleration Algorithms
  • Cluster Algorithms
  • The Potts Model
  • Percolation
  • The Swendsen-Wang Algorithm
  • The Wolff Algorithm
  • Correlations
  • Connected Component Labeling
  • Parallel Monte Carlo Algorithms
• Parallel Metropolis Algorithms
  • Parallel Metropolis Algorithm
  • Red/Black or Checkerboard Update
  • Parallel Metropolis -- Data Parallel
  • Metropolis Code in a Data Parallel Language
  • Parallel Metropolis -- Message Passing
  • Metropolis Code in a Message Passing Language
  • Efficiency of the Parallel Algorithm
  • Coarse Grained Algorithm
  • Measurements
  • Non-local Measurements
  • Relation to PDE Solvers
• Parallel Cluster Algorithms
  • Parallel Cluster Algorithms
  • The Need for a Parallel Algorithm
  • Regular and Local vs. Irregular and Non-Local
  • Labeling or Growing a Single Cluster
  • Depth-First Search (``Ants-in-the-Labyrinth'')
  • Breadth-First Search (FGHK)
  • Local Label Propagation
  • SIMD Local Propagation
  • MIMD Local Propagation
  • Parallel Labeling for Image Processing
  • Global Equivalencing
  • Hierarchical Method
  • Multigrid Algorithm
  • Get/Send Algorithm (Shiloach-Vishkin)
  • Get/Send Algorithm (cont.)
  • Parallel Wolff Algorithm
  • Problems with Parallel Ants
  • Parallel Ants With Cyclic Data Distribution
  • Independent Parallelism
  • Independent Monte Carlo Simulations
  • ``Hybrid'' Parallelism
  • Message Passing vs Data Parallel
  • Irregular Problems in HPF
• Random Number Generators
  • Pseudo-Random Numbers
  • Essential Properties of a Random Number Generator
  • Further Properties of a Good Random Number Generator
• Types of Generators
  • Multiplicative Linear Congruential Generators
  • Choosing the Parameters for LCGs
  • Some Good Parameter Choices for LCGs
  • Problems with Linear Congruential Generators
  • Combined Linear Congruential Generators
  • Properties of Combined LCGs
  • Lagged Fibonacci Generators
  • Implementation of Lagged Fibonacci Generators
  • Properties of Lagged Fibonacci Generators
  • Problems with Lagged Fibonacci Generators
• Parallel Random Number Generators
  • Requirements for a Parallel Generator
  • Parallel Algorithm using Leapfrog
  • Parallel Algorithm using Splitting
  • Parallel Lagged Fibonacci Generators
  • Parallel Lagged Fibonacci Generators II
• Testing Random Number Generators
  • Statistical Tests of Randomness
  • Monte Carlo Tests of Randomness
  • Recommendations
  • References
• Spin Glasses
  • Spin Models Revisited
  • Frustration
  • A Frustrated Spin Model
  • Spin Glasses
  • Properties of Spin Glasses
  • Monte Carlo Simulation of Spin Glasses
  • Quasi-Ergodicity
  • Thermalization of Spin Glasses
• Simulated Annealing and Optimization
  • Simulated Annealing
  • Finding Ground States
  • Optimization
  • Optimization Using Simulated Annealing
  • Finding an Optimal Solution
  • Advantages of Simulated Annealing
  • Disadvantages of Simulated Annealing
• Examples of Optimization Problems
  • Graph Partitioning
  • A Graph Problem Disguised as a Spin Model
  • The Traveling Salesman Problem
• Implementing Annealing Algorithms
  • The Update Step
  • The Annealing Schedule
  • Simulated Quenching
  • Determining the Annealing Schedule
  • A ``Physical'' Annealing Schedule
  • Parallel Simulated Annealing
  • Simulated Tempering
  • Tempering for Optimization