Monte Carlo-simuloinnit / Monte Carlo simulations

53006-4 Monte Carlo-simuloinnit, 3 ov / Monte Carlo simulations, 3 sw

Sisältökuvaus

Opetusajankohta: 20.1 - 6.5 2004; Ti, To 10-12. Ensimmäinen luento 20.1 kello 10.15.

Paikka: Kiihdytinlaboratorion seminaarihuone (Pietari Kalmin katu 2)

Laajuus: 3 ov

Kesto: 14 viikkoa

Ajankohta opintojen ajoitusmallissa: erikoistumisvaihe

Esitiedot: Tieteellisen laskennan peruskurssi ja jatkokurssi. Fortran-, C- tai java-kielen perusteiden tuntemus.

Simple forest fire MC simulation

Sisältö:

Kurssilla käsitellään useilla fysiikan aloilla hyvin tärkeitä Monte Carlo-simulointimenetelmiä. Näissä menetelmissä ratkaistaan jotakin fysikaalista ongelmaa lähtien satunnaisluvuista ja tekemällä tietokonesimulointeja. Kurssilla käsitellään simulointien tilastollisia perusteita, satunnaislukujen generointia, Monte Carlo-integrointia, Ising-malli, Geneettiset algoritmit, ja annetaan sovellusesimerkkejä fysiikan eri aloilta.

Suoritustapa:

Lasku/ohjelmointiharjoitukset ja loppukoe.

Kirjallisuus:

Luentomonisteet.

Tukena voi käyttää useitakin kirjoja, kts. englanninkielinen osuus alla.

Kommentteja:

Kurssi pidetään englanniksi pyydettäessä. Laskuharjoituksiin ja kokeisiin voi vastata suomeksi, ruotsiksi, englanniksi tai saksaksi.

Description

Lecturing time: 20.1 - 6.5 2004; Tue, Thu 10-12 First lecture Jan 20

Place: Kiihdytinlaboratorion seminaarihuone (Pietari Kalmin katu 2)

Lecturer: Prof. Kai Nordlund

Extent of course: 3 sw, 6 ECTS credits

Duration: 14 weeks

Normal year to be taken: specialization phase, third year and up.

Prerequisites: Introductory courses in computational physics, basic numerical methods. Knowledge of the Fortran, C or java programming language.

Language of instruction: English, or Finnish if everyone understands Finnish. The exercises and exams can in any case be solved in Finnish, Swedish, English or German.

Course description:

During the course we will give an introduction to the so called Monte Carlo simulation methods which are very important in many branches of modern physics. In these methods, some physical problem is solved beginning from random numbers and doing computer simulations. During the course we will at least discuss the statistical basis of stochastic simulations, generation of random numbers, Monte Carlo integration, the Ising model, and give examples of applications from different branches of physics.

Exercises

Programming and mathematical exercises are given during the course, but not every week. They are graded by the lecturer For the more demanding exercises more than 1 week of solution time is given.

The programming exercises should be preferably solved in an Unix environment, but also solutions written under other environments in strict adherence to the Fortran90, ANSI C or java standards (so that they can be compiled anywhere) are acceptable.

Evaluation:

Exercises (50 %)
Final exam (50 %)

Literature:

Lecture notes.

Some parts of the material are well described in

W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C; The Art of Scientific Computing, Cambridge University Press, New York, second edition, 1995
M. P. Allen and D. J. Tildesley, Computer Simulation of Liquids, Oxford University Press, Oxford, England, 1989
Gould, Tobochnik: An Introduction to Computer Simulation Methods : Applications to Physical Systems, Harvey Gould, et al

but acquiring any of these is not necessary for the course.

Further comments:

Lecture notes in postscript

I will try to put out the lecture notes here at least one day before the lecture. After the lecture I may still correct errors and put a new version here 'for the record'.

1. General information = this web page.

[PDF] [PS 2up] [PS notes] [PS 4up] 2. Overview of computational physics

[PDF] [PS 2up] [PS notes] [PS 4up] 3. History, definition.

[PDF] [PS 2up] [PS notes] [PS 4up] 4. Generating random mumbers

[PDF] [PS 2up] [PS notes] [PS 4up] 5. Monte Carlo integration

[PDF] [PS 2up] [PS notes] [PS 4up] 6. MC analysis of experiments

[PDF] [PS 2up] [PS notes] [PS 4up] 7. Random walks

[PDF] [PS 2up] [PS notes] [PS 4up] 8. Kinetic Monte Carlo

[PDF] [PS 2up] [PS notes] [PS 4up] 9. Thermodynamic (Metrpolis) MC.

[PDF] [PS 2up] [PS notes] [PS 4up] 10. Simulated annealing

[PDF] [PS 2up] [PS notes] [PS 4up] 10.b. Quantum MC

[PDF] [PS 2up] [PS notes] [PS 4up] 11. Cellular automata

[PDF] [PS 2up] [PS notes] [PS 4up] 12. Repetition

Exercises

To be handed in by email to the lecturer.

Exercise 1: random number generators

Exercise 2: nonuniform random numbers

Data file bimodal.dat

Exercise 3: MC integration, synthetic data

Data file dsa_nonegative.dat

Exercise 4: Random walks

Exercise 5: KMC on defects in Si

Exercise 6: The traveling salesman

Exercise 7: Cellular automata

Coordinates for 20 largest Finnish cities (needed for exercise 6)

Exam

Final exam: Tue 11.5 10-14 pm Accelerator lab seminar room

Exercise solutions

Only solution codes are given here. To get the descriptions you have to come to the exercise session.

1.2

1.3

1.4

1.5

2.1

2.2

2.3

3.1

3.2

3.3

3.4

4.1

4.2

4.3

4.4

5.1

6.1

7.2

7.4

Exercise points

Person Exercise 1 2 3 K 4 5 6 7 SUM % Total 1 2 3 4 5 1 2 3 ------------- --------- ------ ---- --- ---- ---- ---- ----- ----- ------- Max Maksimus 4 6 6 6 6 6 6 12 6 6 18 12 0 6 6 12 18 40 32 6 12 6 18 250 0.5 Otso Alho 4 1 3 3 0 - 6 9 6 6 6 12 - 6 6 6 18 30 22 6 11 6 0 167 0.334 Esko Arajärvi - 5 4 4 6 - 5 12 6 6 - - 6 6 6 9 9 - 29 113 0.226 Tommi Järvi 4 4 6 6 6 2 5 - 6 6 11 12 - 6 6 9 18 35 29 - - - - 171 0.342 Matti Kalliokoski - - - - - 0 0 - - - - - - - - - - - - 0 0.000 Eero Kesälä 4 4 4 4 6 6 6 12 6 6 - 6 6 6 6 4 - 40 11 6 11 6 15 175 0.350 Simo Kilponen - 0 3 2 0 6 5 11 6 4 - - - - - - - - - 37 0.074 Jani Kotakoski 4 4 6 5 6 6 6 12 6 6 11 6 6 6 6 12 18 38 32 5 0 6 12 219 0.438 Juha Kummu 4 4 6 6 0 6 6 12 6 6 - 6 - 6 6 9 0 25 - 108 0.216 Juho Lintuvuori - - - - - 6 6 12 6 6 4 12 6 6 6 3 18 38 32 6 9 6 18 200 0.400 Ossi Lehtinen 4 4 4 4 6 6 6 12 6 6 - 10 6 6 6 8 9 33 32 5 12 6 15 206 0.412 Olli Lehtonen 4 6 6 6 6 6 6 12 6 6 18 12 6 5 6 9 18 40 32 5 11 6 18 250 0.500 Peter Majorin 4 0 6 6 6 6 6 10 - - - - - 6 6 6 - - 31 5 - 6 9 113 0.226 Fredrik Oljemark 4 6 6 5 6 4 3 - 6 0 0 9 6 6 6 6 6 40 12 5 10 6 18 170 0.340 Arto Sakko 4 4 5 5 6 6 6 10 6 6 18 0 6 6 6 9 18 40 32 5 11 6 6 221 0.442 Juha Samela 4 6 6 5 6 6 6 12 6 6 18 12 6 6 6 9 18 39 25 5 11 6 15 239 0.478 Ville Weijo 4 6 6 6 6 - 5 7 6 4 15 10 - 6 6 6 18 35 11 5 12 6 - 180 0.360 Antti Westerlund 4 5 6 6 6 - - - 6 6 - - - 6 6 6 6 20 - 83 0.166 /pre>

Sum: expand | awk '{ s=0; for(i=3;i<=NF;i++) s+=$i; print s }'

Notes on point giving (based on most common mistakes):

1.2: if floats or doubles used in comparison, 2 points off. If floats compared to int, 4 points off. If long used on 64-bit computer so that it gave wrong answers, 1 point off.

1.2 and 1.3 and 1.4: If only one generator used, 2 p off.

2.1. 2 points if integration wrong, code right

2.3. 2 points off if interval between maxima not good.

3.3: a-b 3 points, c-e) 4 points

3.4: if solution given but uncertainties clearly wrong: 6 p; if distribution shifted and answer hence wrong: 9 p

4.3: if solution has finite answer to b, no points for part b. If solver realized the average has problems, but does not prove the answer is infinite, 3 points for part b.

4.4: 6 points if solution code sent which looks in the right direction, but answer not given or not right.

Planned timetable

Week	Tuesday 10-12	Thursday 10-12
4:	20.1: Lecture1: Startup, Overview	22.1: -
5:	27.1: Lecture2: History, generating 1	29.1: -
6:	3.2: Lecture3: generating 2	5.2: Exercise1
7:	10.2: Lecture4: MC integration	12.2: Exercise2
8:	17.2: - (travel)	19.2: Lecture5
9:	24.2: Lecture6	26.2: -
10:	2.3: Lecture7	4.3: Exercise3
11:	9.3: Lecture8	11.3: Exercise 4 (Random walks)
12:	16.3: No lecture	18.3: - (Physics days)
13:	23.3: Lecture9: MMC 1	25.3: - (TULE seminar)
14:	30.3: Lecture10: MMC 2	1.4: Exercise 5 (KMC)
15:	6.4: Lecture11: Sim. ann.	8.4: -
16:	13.4: Lecture12: Simple quantum MC	15.4: -
17:	20.4: Lecture13: Cellular automata	22.4: Exercise 6: Sim. ann.
18:	27.4: Lecture14: Cellular automata2	29.4: -
19:	4.5: Lecture15: Repetition and Exercise 7: Cellular automata	-

Preliminary list of contents

Introduction (1/2 hours)
- Times, lectures, exercises
Overview of important computational physics methods (1 1/2 hours)
- What is computational physics? Role in physics.
- Numerical methods
- FEM
- MD simulations: motion of objects
- Genetic algorithms
- Electronic structure calculations
- Monte Carlo simulations
- Lattice QCD
- Cellular automata
Monte Carlo - introduction (1 hour)
- Definition
- History: first MC simulation
- Confusing terminology, and trying to avoid it
- Even most MD is sort of MC!
- List of some varieties of MC
Generating random numbers (4 hours)
- Importance of doing this well
- Testing generators: 2D, MC simulation, etc...
- Generating a uniform distribution
- Generating non-uniform distributions
  - Analytical approach
  - von Neumann rejection method
  - Special case: Gaussian distribution
- Generating points on a surface of a sphere: the infamous pitfall
- Non-random random numbers: these may sometimes be better
Monte Carlo integration (2-3 hours)
- MC integration of many-dimensional functions
- When is this advantageous compared to a grid?
- Weight functions
MC simulation of experimental data (2 hours)
- Quick-and-dirty: the bootstrap method
- Test: how good is this actually?
- Simulation of physical process
Random walks: introduction (2 hours)
- Drunken sailor in 1 and 2D
- Relation to diffusion
- Lattice gas
- Length of polymers
Kinetic Monte Carlo (2 hours)
- Motion of activated objects
- Trivial and residence-time algorithm
- Lattice and non-lattice
- Example: defect migration in Si
MC simulation of ensembles (4 hours)
- MC and statistical physics
- Simulating atomic systems
- Metropolis algorithm: NVT
- Demon algorithm: NVE
- NPT and muPT algorithms
- Calculating thermodynamic quantities
Simulated annealing (1 hour)
- Basic idea: Metropolis + T lowering (as in metals annealing)
- example: Annealing a metal
- example: Traveling salesman problem
- Exercise: solve the salesman problem
Cellular automata (2-4 hours)
- Basic concepts
- Applications: sand piles, forest fires etc.
Time permitting and according to attendees interests possibly also some of the following:
Ising model (1-2 hours) ?
- Definition of problem, algorithm
- Computer code
Solving equations (2-6 hours) ?
- Linear sets of equations
- Integral equations
Quantum Monte Carlo ?
- Solving the Schrödinger equation
- Random walk QMC (see e.g. Gould-Tobochnik)
Transport simulations (4-8 hours) ?
- Relation to radiation effects
- Simulating ionic collisions