Physics 420/580 – Fall 2009

Previous iterations of this course: [ Fall 2008 ]

Course outline

Computational Physics / Advanced Topics in Computational Physics
Lecture: CEB 123 MWF 13:00-13:50
Lab: CEB 324 R 14:00-16:50
Syllabus: pdf
Schedule: pdf

Lectures

Class starts on Wednesday, September 2. Hope to see you there.

2. C++ language review [ pdf ]
3. Coarse graining, integer representations, lattices [ pdf ]
4. Cellular automata, lattice gas hydrodynamics
5. Cellular automata, self-organized criticality [ pdf ]
6. Efficient data structures, floating point numbers, carefully written programs [ pdf ]
7. Numerical integration, finite differences, root finding [ pdf ]
8. Ordinary differential equations [ pdf ]
9. Runge-Kutta schemes, second-order ODEs [ pdf ]
10. Boundary-value problems, relaxation and shooting methods [ pdf ]
11. Oscillatory motion, chaos, Lyapunov exponents, strange attractors, period doubling [ pdf ]
12. N-body simulations, Lennard-Jones potential, choice of time step, range truncation, parallel computation, Barnes-Hut algorithm [ pdf ]
13. Time scales, molecular dynamics with constraints (SHAKE) [ pdf ]
14. Wave equation, spectral methods for PDEs
15. Integrating PDEs with finite differences, explicit and explicit schemes, Crank-Nicholson, stencils, Von Neumann stability analysis
16. Quantum mechanics, evolution of energy eigenstates, shooting method and matching method for the time-independent Schrödinger equation in 1D
17. Stability of finite difference schemes for the time-dependent Schrödinger equation
18. Schrödinger equation in higher dimensions, many-body quantum problems, matrix mechanics, ground state projection via the power method, variational principle [ pdf ]
19. Matrices, linking to the BLAS and LAPACK libraries [ pdf ]
20. Random processes, probability distributions [ pdf ]
21. Random walks, enumeration of self-avoiding random walks [ pdf ]
22. Monte Carlo integration, Markov chains
23. Monte Carlo dynamics, detailed balance, measurement taking, thermalization and autocorrelation times
24. Ising model and its critical behaviour, finite-size scaling, Monte Carlo simulation using Metropolis updates, critical slowing down [ pdf ]
25. Duality of (site) clusters and (link) loops for the 2D Ising model, non-local updates, Wolff algorithm
26. Geometric disorder, continuum and lattice percolation, random resistor networks
27. Global optimization, steepest descent, stochastic optimization, simulated annealing, parallel tempering
28. Genetic and swarm algorithms

Only material up to this point will appear on the final exam!

29. Linear inverse problems, X-ray tomography, recommendation engines
30. Parallel computing: MPI, openMP, threads
31. ??
32. Exam review

Assigned reading

1. You should be working your way through the class notes. These will be updated regularly.
2. Many of the lecture topics are covered in greater detail in various textbooks. I encourage you to have a look at the books on reserve in Cameron library.
3. David Goldberg, “What Every Computer Scientist Schould Know Abount Floating-Point Arithmetic,” ACM Computing Surveys 23, 5 (1991). [ pdf ], [ html ]

Exercises

These optional, ungraded problems touch on important issues that aren't addressed explicitly in the labs and assignments.

1. Floating-point numbers
   instructions [ pdf ], source [ tar.gz ]
2. Multiparticle dynamics
   instructions [ pdf ], solutions [ pdf ]

Labs

The first lab is on Thursday, September 10.

1. Lissajous figures, Mandelbrot set
   instructions [ pdf ], solutions [ tar.gz ]
2. Cellular automata
   instructions [ pdf ], source [ tar.gz ], solutions [ tar.gz ]
3. Numerical integration, particle dynamics
   instructions [ pdf ], source [ tar.gz ], solutions [ tar.gz ]
4. Lorentz attractor, chaos
   instructions [ pdf ], source code [ tar.gz ]
5. Laplace and Poisson equations, relaxation methods
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
6. Wave equation, stability of finite-difference methods for PDEs
   instructions [ pdf ], source code [ tar.gz ]
7. Work period for Assignment 3 (or term projects); the TA will be available to answer your questions.
8. Matrix mechanics with LAPACK
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
9. Enumeration of self-avoiding walks
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
10. Percolation
    instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
11. Monte Carlo simulation of the Ising model
    instructions [ pdf ], source code [ tar.gz ]

Lab Access

Detailed instructions can be found here.

Assignments

There will be five assignments (four for students who elect to submit a term project) with one due roughly every two weeks.

1. Lattice gas automata: due Wednesday, September 23
   instructions [ pdf ], source [ tar.gz ], solutions [ tar.gz ]
2. Classical N-body simulations: due Wednesday, October 7
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
3. Dynamics of a quantum wave packet: due Monday, October 26
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
4. Monte Carlo simulation of a polymer chain: due Monday, November 9
   instructions [ pdf ], source code [ tar.gz ]
5. Optimal packing of granular material: due Monday, November 30
   instructions [ pdf ], source code [ tar.gz ]

I would appreciate having your work for assignment n=1…5 submitted as a single tarball named studentLastName_n.tar.gz, sent to as an email attachment. When unpacked, your directory should contain your source code, compilation instructions (or, even better, a makefile), and a short written explanation of what you have done.

$ tar -cf beach_1.tar beach_1
$ gzip beach_1.tar
$ ls -F
beach_1/   beach_1.tar.gz

I encourage students to write up their assignments in LaTeX. I have provided a template file for that purpose. (If you are not already familiar with it, LaTeX is a typesetting language that is widely used in the mathematics and physics communities. There is a brief introduction in the notes.) You are certainly not required to use LaTeX. A plain text file will do nicely. I do, however, want to avoid paper submissions.

Final Exam

Tuesday, December 8, 2009
Written: CEB 123 14:00-15:20
Lab: CEB 324 15:30-17:00

The exam will consist of both a written component (in the usual lecture room) and a programming component (in the lab). The emphasis will be on algorithms and numerical problem-solving strategies, with material drawn from the lectures (up to Lecture 28), labs 1–12, and assignments 1–4. Any material from the online tutorials and exercises is also fair game. Students will be expected to read and write programs in C++ but will not be asked to implement sophisticated class features.

Term project

Project proposal

A single typed page should be sufficient. Commit to a particular topic, and flesh out how you intend to proceed. I want to have some sense of the scope of your project and what numerical techniques you intend to employ. Be sure to discuss what scientific question(s) your numerical study will attempt to answer.

For those of you still making up your mind, I suggest that you take a look at these books, both of which contain many interesting project ideas:

• Computational Physics, T. Pang, 2nd Ed., Cambridge University Press (2006) ISBN-10:0521825695
• An Introduction to Computer Simulation Methods: Applications to Physical Systems, H. Gould, J. Tobochnik, W. Christian, 3rd Ed., Addison Wesley (2006) ISBN-10:0805377581

Waves and normal modes: equipartition of energy and the Fermi-Pasta-Ulam problem; realistic vibrations of strings in musical instruments; mode locking. Chaos: kinetics of chemical reactions, chemical oscillations; measuring the Lyapounov spectrum; billiards on a square table with rounded edges; chaotic scattering. Numerical methods: multigrid relaxation methods; fast fourier transforms; renormalization group. Multiparticle dynamics: gas of hard disks; magic numbers in particle clusters; solar wind; resonances and the asteroid belt; classical helium atom; classical heisenberg model; constant temperature molecular dynamics; dynamics on a spherical surface. Random systems: percolation in three dimensions; conductivity in a random resistor network; fractal scaling in cluster growth models; pattern formation; ising spin glass Monte Carlo: Kosterlitz-Thouless transition in planar spins; cluster methods to overcome critical slowing down.

Oral presentations

The midterm presentation should last no more than 10 minutes. Simply summarize the problem of interest, the goals for the project, and the numerical strategies you plan on using. If possible, show some of your preliminary results; otherwise, discuss your expectations.

The final oral presentation should last no more than 15 minutes. You can presume that I and your classmates remember the basic details from your midterm presentation. Focus on presenting the final numerical results. Try to give the audience a meaningful interpretation of the data and a sense of how your results do or do not resolve the physics propblem you set out to investigate.

Final report

The final report should be type-written (in LaTeX, prefereably) and 15 to 25 pages in length, including figures and references. I have provided a template file that lays out the following structure:

• Introduction
• Model
• Numerical Method
• Implementation
• Benchmark Calculations
• Results
• Discussion
• References

These section headings are just a suggestion. You are free to organize your report as you see fit, so long as it adequately addresses each of these key areas: the motivation and background to the problem, the assumptions underlying the physical modelling, the choice and suitability of the numerical technique(s), the details of the C++ implementation, what tests were carried out to verify the code, and what the final results mean.

The report will be judged in part on the clarity of writing and presentation of data. I will also be looking for evidence that the numerical work was carried out carefully and that the reported results are reliable. In other words, I expect to see something along these line: benchmark results matched against solvable cases, a systematic characterization of the errors, a stability analysis, etc.

Along with the report, be sure to submit your C++ code (in electronic form, and either well-commented or accompanied by an explanatory document). And be absolutely certain that I will be able to compile and run it.