Numeriske metoder / Numerical Methods

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

Numeriske Metoder / Numerical methods 2016

[ 2015 home-page | Wiki ]

NB (reversed time ordering):

The examination run on 28-30/6 (from 10:00 to 10:00),
please find your assignments here.
The examination run on 27-29/6 (from 10:00 to 10:00),
1. Niels Kristian Madsen
2. Raul Blázquez García
please find your assignments here.
The examination run on 20-22/6 (from 10:00 to 10:00),
1. Esben Leonhard Kolsbjerg
2. Kasper Tolborg
3. Laura Kaplan
4. Mikkel Berg Christensen
5. Sune Dyrbye
6. Stig Elkjær Rasmussen
please find your assignments here.
The examination run on 17-19/6 (from 10:00 to 10:00),
1. Erik Buch Jørgensen
2. Jesper Hasseriis Mohr Jensen
please find your assignments here.
The examination project should be done in the same place where all your exercises are done, in a separate folder called "exam". I will check it from that place together with your exercises. However, you also need to upload the archive of the "exam" folder to the digital-exam server so that you are registered as having finished the examination.
The official examination will be on 28-30/6 (from 10:00 to 10:00 ?).
Come to this place on 28/6, there will be instructions for the examination.
Ok, the absolute deadline for the exercises is the day before the examination. However, you have to arranged it with your study-partner such that you both have time to check each others exercises.
An earlier examination is also possible, however you will still have to upload your solution to the digital-exam server at the official examination date so that the digital-exam system could correctly register you.
The lifa users nswr, nk93, nroth, jhsq should have no more problems on lifa. You might need to firts delete an erroneously created file ~/public_hmtl and then mkdir ~/public_html.
In the google-spreadsheet you should copy/paste the line with my name and then change the content accordingly. Copy/pasting is essential, because the line is actually a program to calculate your points. You shall give yourself a grade from 0 (nothing done) to 1 (everything is done perfectly) for every sub-exercise. The spreadsheet than multiplies your grades by the weight of the sub-exercise and adds up to your total points.
Having done the hello-world exercise send me an email (fedorov@phys.au.dk) with the subject "numeric 2016" and I will give you the permission to edit the bookkeeping spreadsheet.
Python3 (3.5.1) is installed on lifa as ~efb23/bin/python3
Octave (4.0.0) is installed on lifa as ~efb23/bin/octave
Git (2.6.0) is installed on lifa as ~efb23/bin/git
olek20

Schedule:

Exercises:

Setup; Hello World; Interpolation; Linear equations; Eigenvalues; Least-Squares fit; Root finding; Optimization; ODEs; Adaptive integration; Monte Carlo integration; Check and comment on your partner's homeworks; FFT; SMP.

Weekly notes:

Introduction:
- Numerical computations in physics; servers and clusters; POSIX systems; free software; programming languages; programming in POSIX environment; scripts, text editors.
- The POSIX make utility (here lies the manual); homework structure: makefile, main.c, method.c, utils.c → output.txt, illustration.png, ... .
Interpolation [chapter.pdf (June 25 2019)]
- Polynomial interpolation; spline interpolation: linear, quadratic, cubic splines; other forms of interpolation; multivariate interpolation.
- Procedurial, object-oriented, and functional programming styles.
Linear equations [chapter.pdf (June 25 2019)]
- Triangular systems, back-substitution;
- LU-decomposition: Doolittle algorithm;
- QR-decomposition: modified Gram-Schmidt algorithm, Householder reflection algorithm, Given's rotation algorithm;
- Determinant of a matrix;
- Matrix inverse.
Eigenvalues and eigenvectors, Eigenvalue decomposition (EVD), matrix diagonalization) [ chapter.pdf (June 25 2019) ]
- QR/QL algorithm; Jacobi eigenvalue algorithm.
- Rank-1 and 2 updates of a symmetric eigenproblem.
- Singular value decomposition (SVD) of a matrix.
Linear least-squares problem [ chapter.pdf; (June 25 2019) ]
- Least-squares solution with QR-decomposition; ordinary least-squares fit; fit errors and covariance matrix.
- Least-squares solution with singular value decomposition.
- Matrix libraries: BLAS, LAPACK, ATLAS → GSL, Armadillo.
Nonlinear equations (root-finding) [ chapter.pdf; (June 25 2019) ]
- Modified Newton's method; backtracking line search.
- Quasi-Newton's methods: Broyden's and SR1 updates of the Jacobian matrix.
Multidimensional Minimization [ chapter.pdf; (June 25 2019) ]
- Newton's method; Quasi-Newton's methods: Broyden's and SR1 updates.
- Downhill simplex method.
- Stochastic algorithms: simulated annealing; quantum annealing.
- Evolutionary algorithms: genetic algorithm.
Ordinary differential equations [ chapter.pdf; (June 25 2019) ]
- One-step (Runge-Kutta) methods; multi-step and predictor-corrector methods;
- Error estimates; adaptive step-size strategy.
Numerical integration (quadratures) [ chapter.pdf; (June 25 2019) ]
- Riemann sums: rectangle and trapezium rules;
- Quadratures with equally spaced abscissas (Newton-Cotes);
- Adaptive algorithms with equally spaced abscissas;
Numerical integration 2
- Quadratures with optimized abscissas (Gauss);
- Gauss-Kronrod quadratures.
- Variable substitution quadratures.
Monte Carlo integration [ chapter.pdf; (June 25 2019) ]
- Plain Monte Carlo integration;
- Importance sampling; Stratified sampling;
- Quasi-random numbers: van der Corput and Halton sequences.
Eigenvalues 2: Power methods and Krylov subspace methods [ chapter.pdf; (June 25 2019) ]
- Power methods; inverse iteration method.
- Arnoldi and Lanczos methods; GMRES (Generalized Minimum RESidual) method for solving systems of linear equations.

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.