PHY 604: Computational Methods in
Physics and Astrophysics II
Spring 2017
Note: the only prerequisite for this class is that you are
able to program in the language of your choice. You do not
need to have taken PHY 504 (part I of the sequence).
This class was formerly offered as a special topics class (PHY 688).
Course Information
- Instructor: Michael Zingale
- Syllabus: syllabus.pdf
Homework:
There will be 7–9 homework assignments throughout the semester.
Grades are posted in the Blackboard gradebook
Lecture notes and online material (by lecture topic):
Notes will be updated throughout the semester, approximately 1 week before each topic is covered.
Course Overview
- Lecture Notes: overview.pdf
Basics of Computation
- Lecture Notes: basics-of-computation.pdf
- Readings
- What every computer scientist should know about floating-point arithmetic by D. Goldberg
- Wikipedia page on the Floating Point
- Wikipedia page on the Kahan Summation Algorithm—a demonstration of the effects of roundoff error and the associative property.
- Lecture notes by R. Leveque on High Performance Scientific Computing
- Examples
- A simple example of integer overflow in Fortran: overflow.f90
- Determining machine epsilon in python: precision.py
- Demonstration of python's variable-sized integers: fac.py
Programming Practices
- Lecture Notes: practices.pdf
- Readings
- Reliability in the Face of Complexity; The Challenge of High-End Scientific Computing by G. Ferland
- Best Practices for Scientific Computing by G. Wilson et al.
- Good Enough Practices in Scientific Computing by G. Wilson et al.
- Best Fortran Practices
- Git Tutorial
- Another git tutorial
- How to Scale a Code in the Human Dimension by Matt Turk
- Practices in source code sharing in astrophysics by L. Shamir et al.
- Examples
- A git-walkthrough (based on the tutorial) and some sample files: git.txt example.f90 README
- Compiler checks for uninitialized variables / invalid floating point operations: compiler_checks.tar
- Makefile examples of increasing complexity: makefiles.tar
Differentiation / integration / order-of-accuracy
- Lecture Notes: differentiation-integration.pdf
- Readings
- Examples
Interpolation / root-finding
- Lecture Notes: interpolation-roots.pdf
- Readings
- Examples
- Lagrange interpolation example: lagrange.py
- Cubic spline interpolation example: cubic-spline.py
- Root finding example (bisection, Newton, and secant): roots.py
- Newton's method animation
- Bisection animation
ODEs
- Lecture Notes: ODEs.pdf
- Readings
- Deterministic Nonperiodic Flow by E. N. Lorenz
- Stiff ODE Solvers: A Review of Current and Coming Attractions, by G. D. Byrne & A. C. Hindmarsh (1986)
- Examples
- Different ODE integrators for the orbit problem: orbit.py (the main class module), orbit-compare.py (compare methods), orbit-eccentric.py (eccentric orbits)
- Adaptive timestepping example for 4th-order Runge-Kutta: orbit_adaptive.py (the main class module), orbit-rk4-adapt.py (adaptive integration of highly elliptical orbit), orbit-rk4-noadapt.py (non-adaptive case)
- Two-point boundary value problem via shooting: shoot.py
- Stiff problems:
- Adaptive RK4 for a scalar stiff equation: stiff-rk4-adapt.py
- Implicit example for a scalar stiff equation: stiff.py
- Implicit example for a linear stiff ODE system: stiff-linear.py
- Stiff non-linear system solved with VODE: stiff-nonlinear.py
- Eigenvalue problems:
- Schrodinger equation infinite potential well: infinite-well.py
- Finite potential well: schrodinger.py (the main class module), finite-well.py (the driver)
- More complicated potential: complex-well.py (the driver; uses schrodinger.py above)
Linear algebra
- Lecture Notes: linear-algebra.pdf
- Readings
- Examples
- Matrix-vector multiply: matmul.py
- Gaussian elimination with pivoting: gauss.py (main module), gauss-test.py (test routine)
- Tridiagonal linear system solver + cublic spline example driver: tridiag.py cubic-spline-tri.py
- Invert a matrix through Gaussian elimination: inverse.py
- Jacobi iteration solution to the cubic spline interpolation problem: cubic-spline-iterate.py
FFTs
- Lecture Notes: ffts.pdf
- Readings
- The NumPy FFT page
- Examples
- A discrete Fourier transform: dft.py
- Some simple examples of FFT and inverse FFT using the numpy FFT routines. These all take real-valued functions as input: fft-simple-examples.py
- Simple example of filtering in frequency space: simple-filter.py
- Simple example of filtering in frequency space: pendulum.py
- Some examples of a two-dimensional FFT and image processing: fft2d.py luna_bw.png (image used in the examples)
- A fast Fourier transform: fft.py
Fitting
- Lecture Notes: fitting.pdf
- Readings
- Data analysis recipes: Fitting a model to data by Hogg et al.
- Examples
- Linear regression example: linear-regression.py
- General linear least squares example: general-linear.py
- Nonlinear fitting example: nonlinear-fit.py
- Nonlinear fitting through SciPy: nonlinear-scipy.py
Advection / hyperbolic PDEs
- Lecture Notes: pde-overview.pdf advection.pdf
- Readings
- notes on computational hydrodynamics (see the chapters finite-volume, advection, and Burgers' equation)
- Examples
- Simple finite-difference advection (both upwind or FTCS): fdadvect.py
- Convergence for the finite-difference upwind advection: fdupwind.py fdupwind_converge.py
- Second-order finite-volume method (piecewise linear reconstruction) for linear advection:
fv_advection.py
(alternately, here's a Fortran verison that also does piecewise parabolic reconstruction: advect.f90) - Second-order finite-volume method for Burger's equation: burgers.py
Laplace & Poisson equations / elliptic PDEs
- Lecture notes: elliptic-multigrid.pdf
- Readings
- notes on computational hydrodynamics (see the chapter on multigrid)
- Examples
- Simple (Gauss-Seidel) smoothing in 1-d: smooth-separate.py
- A 1-d multigrid solver for Poisson and constant-coefficient Helmholtz equations: multigrid.py patch1d.py mg_test.py (a sample driver)
- Multigrid in action animation
- FFT solution of Poisson's eq: poisson_FFT.py
Diffusion / parabolic PDEs and multiphysics
- Lecture Notes: diffusion.pdf
- Readings
- notes on computational hydrodynamics (see the chapter on diffusion)
- On the Construction and Comparison of Difference Schemes by G. Strang (1968)
- Examples
- Time-explicit diffusion on a cell-centered grid: diffexplicit.py
- Backward-difference (implicit) diffusion: diffimplicit.py
- Crank-Nicolson differenced diffusion (direct solve): diffCNimplicit.py
- Multigrid solution of diffusion (C-N discretization): diffMG.py
- Diffusion-reaction equation, using Strang-splitting (this can be thought of as a model for a flame): diffusion-reaction.py
- Viscous burgers equation (2nd-order piecewise linear f-v method for advection + 2nd-order implicit method for diffusion): burgersvisc.py
- A cell-centered approximate projection: project.py
Computational fluid dynamics
- Lecture Notes: CFD.pdf
- Readings
- notes on computational hydrodynamics (see the chapter on the Euler equations)
- Examples
- SymPy notebook deriving the eigenstructure of the primitive variable Euler matrix: euler.ipynb
- Phase diagram (u-p plane) of the Riemann problem: riemann-phase.py
- pyro: hydro by example—A python-based teaching code we'll use
- hydro1d: A simple, 1-d, finite-volume, gamma-law hydrodynamics solver
Monte Carlo methods
- Lecture Notes: monte-carlo.pdf
- Readings
- Introduction to Markov Chain Monte Carlo by C. J. Geyer
- Examples
- Linear congruential method for uniformly distributed random numbers: random_test.py
- Radioactive decay models:
- using uniform random number generator: simple_continuous.py
- using a transform to produce exponentially-distributed random numbers: transform_random.py
- Monte Carlo integration:
- simple 1-d integral: MC_integral.py
- mean-value integration: mean_value_integral.py
- multi-d example, volume of a hypersphere: hypersphere_volume.py
- importance sampling: naive_sampling.py importance_sampling.py
- MC calculation of poker odds: poker.py
- Markov Chain Monte Carlo example for ideal gas: ideal_gas.py
- Simulated annealing:
- traveling salesman: traveling_salesman.py
- function minimization: function_minimization.py
Parallel computing
- Lecture notes: parallel.pdf
- Readings
- High-Performance Computing by Dowd and Severance. This book is old, but fantastic, and available via a Creative Commons License
- Examples
- Simple shell script to farm out analysis tasks as resources become available: parallel
- OpenMP:
- OpenMP hello, world: hello-omp.f90
- Matrix multiplication with OpenMP loops: matmul.f90
- Example of OpenMP reduction: reduce.f90
- OpenMP relaxation code (pure smoothing for a fixed number of iterations): relax.f90
- MPI:
- MPI hello, world: hello_mpi.f90
- MPI pi calculation: pi.f90
- MPI send/recv and sendrecv examples: send_recv.f90 sendrecv.f90
- MPI relaxation example: relax_mpi.f90
- OpenACC:
- OpenACC example of relaxation: relax-openacc.f90
- python Monte Carlo example: poker-mpi.py
Genetic algoritms
- Lecture Notes: genetic.pdf
- Readings
- Binary versus real coding for genetic algorithms: A false dichotomy? by Gaffney et al.
- Examples
- binary algorithm:
- encoding / decoding example: encode_decode.py
- assembling a chromosome: chromosome.py
- Thomsom problem: thomson.py genetic.py; for plotting: thomsom_plot.py
- continuous algorithm:
- Thomsom problem: thomson_continuous.py genetic_continuous.py; for plotting: thomsom_plot.py
- binary algorithm:
What did we learn?
- Lecture Notes: summary.pdf
- Readings
- The Best of the 20th Century: Editors Name Top 10 Algorithms by B. A. Cipra, in SIAM News
- Examples