Numeriske metoder / Numerical Methods

/ Aarhus University / Physics / Subatomic Physics / Nuclear Theory >

Numeriske Metoder / Numerical methods F12

NB:

I am sure I told you that the system rand() is not thread-safe. For multi-processing you need to use a thread-safe random number generator from the GSL library.
People without a student number shall use their sequence number from the spreadsheet.
Due to the 12h disruption of the internet at AU on 22/06 the second run people get 24h extention of the run, that is until noon 26/06.
At the moment I will only give you (in the srpeadsheet) the marks "passed"/"not-passed" (in order to save you from fearful apprehensions). The actual characters will appear later after the last group finishes – that is, sometime in the mid July. Contact me if you need your character asap.
Examination:
- Examination will be done in three runs, 72 hours each, starting at noon 1/06, 22/06, and 26/06. You have to sign up for a run at the spreadsheet by indicating the date of your run.
- After (!) the start of your run you go to this page and look at the examination projects below. I will randomize the sequence of projects just before the start of the run. Your project number is equal
  a modulo n
  (the remainder of division) where a is your årskortnummer (your student number) and n is the total number of examination projects. Note that if numbering starts from zero, the total number of projects is equal the number of the last project plus one.
- Hint: in C/C++ the modulo operation is a%n; in Fortran it is modulo(a,n) (I think).
- The examination projects are formulated without the usual items A, B, C, and D – you have to make them (or something similar) up yourself (individually). The *.out.txt files and the *.png figures should be a (substantial) bit more informative and self-explanatory (as compared to those in the obligatory exercises).
- A README or README.txt file with a summary is not strictly necessary, but won't hurt.
- It goes without saying that make clean; make should build the project anew.
As a part of learning to program you will have to look at other peoples' makefiles and codes. Each of you must find a partner to check each other's exercises. The names of the partners should be marked with the same (otherwise arbitrary) color in the bookkeeping spreadsheet. After the deadline of the exercise has passed (or indeed any earlier time agreed between the partners) the partners check each other's makefiles, illustrations, and results according to the requirements for the exercises. If you deem your partner's self-evaluation points fair, you mark the corresponding cells with your color.

Schedule:

Lectures: Monday, 08:15, 3131-303 (Forskerprk.); Wednesday, 11:15, 1532-116 (Aud. G1); Σ
Exercises: Wednesday, 13:15, 1525-319 (team 1); and Friday, 14:15, 1525-319 (team 2).

Exercises:

Setup, Hello World(due:29/04), Interpolation(due:7/05), Linear equations (QR)(due:11/05), Least-Squares fit(due:14/05), Eigenvalues(due:18/05), ODEs(due:21/05), Root finding(due:25/05), Optimization(due:28/05), Adaptive integration(due:31/05), Monte Carlo integration(due:31/05), FFT, SMP.

Examination projects:

Here they are. Note that counting starts (hopefully) from 0.

Weekly notes:

Introduction: Numerical computations in physics; servers and clusters; POSIX systems; free software; programming languages; programming in POSIX environment;
Interpolation [ pdf; page1.png; page2.png; page3.png; page4.png; page5.png; (June 25 2019)]
- The POSIX make utility; homework structure: makefile, main.c, method.c, utils.c → output.txt, illustration.png, ... .
- Polynomial interpolation; spline interpolation: linear, quadratic, cubic splines; other forms of interpolation; multivariate interpolation.
Linear equations [ pdf; page1.png; page2.png; page3.png; page4.png; page5.png; (June 25 2019) ]
- Procedurial, object-oriented, and functional programming styles.
- Triangular systems, back-substitution; LU-decomposition: Doolittle algorithm; QR-decomposition: modified Gram-Schmidt algorithm, Householder reflection algorithm; determinant of a matrix; matrix inverse.
Linear least-squares problem [ pdf; page1.png; page2.png; page3.png; (June 25 2019) ]
- Matrix libraries: BLAS, LAPACK, ATLAS → GSL, Armadillo.
- Least-squares solution with QR-method; ordinary least-squares fit; fit errors and covariance matrix.
Eigenvalues and eigenvectors [ pdf; page1.png; page2.png; page3.png; (June 25 2019) ]
- QR/QL algorithm;
- Jacobi eigenvalue algorithm;
Eigenvalues 2: Power methods and Krylov subspace methods [ pdf; page1.png; page2.png; (June 25 2019) ]
- Power methods; inverse iteration method.
- Arnoldi and Lanczos methods; GMRES (Generalized Minimum RESidual) method for solving systems of linear equations.
Ordinary differential equations [ pdf; page1.png; page2.png; page3.png; page4.png; (June 25 2019) ]
- One-step (Runge-Kutta) methods; multi-step and predictor-corrector methods;
- Error estimates; adaptive step-size strategy.
Nonlinear equations [ pdf; page1.png; page2.png; page3.png; (June 25 2019) ]
- Modified Newton's method;
- Broyden's quasi-Newton's method.
Multidimensional Minimization [ pdf; page1.png; page2.png; page3.png; page4.png; (June 25 2019) ]
- Newton's method. Quasi-Newton's methods: Broyden's and SR1 updates;
- Downhill simplex method.
Numerical integration (quadratures)
[ pdf; page1.png; page2.png; page3.png; page4.png; page5.png; page6.png; page7.png; page8.png; page9.png; (June 25 2019) ]
- Riemann sums: rectangle and trapezium rules;
- Quadratures with equally spaced abscissas (Newton-Cotes);
- Quadratures with optimized abscissas (Gauss);
Numerical integration 2
- Adaptive algorithms with equally spaced abscissas;
- Gauss-Kronrod quadratures.
- Variable substitution quadratures.
Monte Carlo integration [ pdf; page1.png; page2.png; page3.png; page4.png; (June 25 2019) ]
- Plain Monte Carlo integration;
- Importance sampling; Stratified sampling;
- Quasi-random numbers: van der Corput and Halton sequences.
Multiprocessing [ pdf; page1.png; (June 25 2019) ]
- Processes and threads; multiprocessing and multithreading; POSIX threads (pthreads).
- Open Multi-Processing specification (OpenMP, OMP) for multiprocessing in C/C++ and Fortran:
  - Header file: omp.h; CFLAGS += -fopenmp; LDFLAGS += -lgomp;
  - OpenMP tutorial from llnl.gov
  - parallel work-sharing:
    - #pragma omp parallel for
    - #pragma omp parallel sections
- Examples can be found here.

Fast Fourier transform and applications
[ pdf; page1.png; page2.png; (June 25 2019) ]
Discrete Fourier Transform and applications; Fast Fourier Transform: Danielson-Lanczos lemma and Cooley-Tukey algorithm.

Last bits:

More on multi-threading: thread safety.
Calculations of the complex valued special functions. [ png, pdf ]

Literature:

D.V.Fedorov, Introduction to Numerical Methods, lecture notes [1M PDF file (June 25 2019) ].

Evaluation:

Project and exercises, 7-scale grade.

Useful links:

[ Linuxbog.dk | GNU scientific library | Computer Language Benchmarks ]

Servers:

IFA's servers are lifa.phys.au.dk. From outside the firewall you login to lifa with RSA-keys; from inside – with NFIT password. VPN effectively brings you inside the firewall.
We also have a dedicated server for numerical methods, molveno, which is a two-processor box running the current Ubuntu. You can only login into molveno from inside the firewall. That is, from home you have to login first into lifa.phys.au.dk and then to molveno. molveno box is better updated and has more software installed.

Program examples

can be found here.

Homeworks:

Is now located at the Wiki at AULA