//Aarhus University / Physics / Subatomic / Theory >

Practical Programming and Numerical Methods 2021.

[Zoom: https://aarhusuniversity.zoom.us/j/4106164110]

NB

(!) Remember to login to the examination server at the official examination date and upload there the link to your repository. Failure to do so will automatically result in "UB" grade (absent from examination). Each year about 2% of students do forget to login.
(!) Remember to make a table with your points for homeworks in your wiki-page. Look at my wiki-page for an example.
(14/6) Your examination projects are online at the link above. Good luck :)
The deadline for the homeworks is when the official examination ends, that is, 29/6/2021 12:00. The examination projects will be assigned to you on this page two weeks before the official examination date.
(7/5) A poll to choose extra chapters is open at our wiki page. τπψΨν
Possible topics for the extra chapter:
1. Calling C-functions from Python;
2. Numerical methods for partial differential equations;
3. Fast Fourier transform and applications;
4. Globally convergent minimization algorithms;
(22/4) The exercises and homeworks must be built (!) in your repository.
(21/4) Added a Clenshaw-Curtis inplementation without nested functions.
(16/4) Remember: in C (and C++,Java,C#) 3/2 evaluates to 1, not to 1.5 (!).
(16/4) Added "figure-8 solution to 3-body Newtonian gravitational problem" to examples folder.
(19/3) Added an example of measuring the CPU-time consumed by a program to the end of homework "linear-equations".
(19/3) In the homeworks you must make your own implementation of the discussed algorithms. GSL's implementations can only be used for testing. However, you may well use BLAS routines for matrix and vector operations.
(13/3) Added contour plot of the complex gamma-function to the examples folder.
(9/3) In the [LaTeX exercise] please explain the purpose of the line
```
if(x>1./8)return pow(ex(x/2),2);
```
in our exponenital function implementation.
(9/3) The exercises and homeworks must be built (!) in your repository.
(9/3) Please put not the code that belongs to a ".c"-file into ".h"-files.
(9/3) PDF files of the chapters and the book are built and can be read now.
(26/2) The "exercises" wil be graded passed/not-passed. If an exercise contains parts A/B/C, the A alone is enough to pass.
The homeworks will be graded with points: 6 points for A, 3 points for B, 1 point for C. At the end one has to accumulate at least 51% of points, which gives 02; 61% gives 4, 71% gives 7, 81% gives 10, and 91% gives 12.
(26/2) In the "./examples" directory (link above) you can find my own solutions to some of the exercises/homeworks.
(23/2) Your repository must have a folder "exercises" where I should be able to find your solutions to the exercises.
(23/2) Make sure that your page at our Wiki lists i) a link to where I can look at your code via a browser, and ii) a command to clone your repository that I can copy/paste into my terminal, for example
```
git clone https://github.com/dcf21/pyxplot9.git
```
(should it be needed for debugging). Check that both actually work.
(12/2) The exercise with INT_MAX must be compiled with the -fwrapv option (wrap signed arithmetics around overflows).
(5/2) The wiki system seems to be working now, see the link above. Please go there to the "List of participants" and put your name and your picture into the table using my entry as a template.
I have added a link to Microsoft's manual for their Windows Subsystem for Linux
(https://docs.microsoft.com/en-us/windows/wsl/)
to the first lecture. It includes a FAQ section which seems to be rather useful.
First meeting: Wednesday 3/1, 08:15, at Zoom at the link above.

Schedule

F	Onsdag	8 - 11	Auditorium D2 (1531-119)	uge 5-12, 14-20
F	Fredag	13 - 16	Auditorium D1 (1531-113)	uge 5-12, 14-20

Plan

Introduction. [→]
POSIX (UNIX) systems; Programming languages for scientific computing; Open software.
- Exercise "posix".

Code repositories. Makefiles. [→]
Distributed version control systems; Code repositories; hg and git; POSIX make utility for managing projects.
- Reading: note "make", Introduction to Git, Distributed Version Control;
- Exercises: exercise "git", exercise "hello"; questions "make";

Basics of C programming.
Structure of a C-program, main function; preprocessing, compiling and linking; basic types int char double complex long double; scope of variables (file, function, block); simple output with printf function; mathematical functions and complex numbers.
- Reading: notes "C-program", "scope", "printf";
- Reading: C program: global structure, Preprocessing, compiling, linking, and execution of a C-program;
- Exercises: exercise "math", questions "basics";
- Hints:
  - In bash prompt, ↑ and ↓ keys scroll over the previously issued commands.
  - In bash prompt, !text runs the latest command that begins with text. Useful for issuing the same command again.
  - Install additional man-pages with the command sudo apt-get install manpages-posix manpages-posix-dev;

More C programming.
Conditional if else and loops for, while, do; Pointers; Arrays; Memory allocation/deallocation with malloc/free; Structs;
- Reading: C-syntax→selection; C-syntax→iterations;
- Reading: notes "pointers", "arrays", "struct";
- Extra reading: Pointers in computer programming; C syntax → Pointers; C syntax → Arrays; C syntax → Structures ~~and Unions~~; C dynamic memory allocation.
- Exercises: exercise "epsilon"; exercise "komplex"; questions "pointers";

Input/output.
Standard streams, redirections, piping; file streams; command-line arguments.
- Reading: notes "streams", "redirect", "cmdline";
- Extra reading: C syntax → Command-line arguments, POSIX getopt, POSIX redirection;
- Extra reading: man stdout, man 3 atoi, man 3 atof, man 3 scanf, man 3 getopt;
- Exercises: exercise "input/output"; questions "stdio";

GNU Scientific Library. Scientific plots with gnuplot/pyxplot/plotutils.
- Reading: GSL manual, chapters Introduction, Using the Library, Special Functions.
- Reading: Pyxplot manual, chapters Introduction, Installation, First steps.
- And/or reading: Gnuplot manual.
- And/or reading: Graph manual.
- Exercises: exercise "plots"; questions "6";

Passing functions as arguments to other functions.
Pointers to functions; function pointers as arguments; function pointers in arrays and structures; pointers to functions with parameters.
GSL integration routines.
- Reading: note "passf";
- Exercise "gsl-integ";

Multiprocessing.
- Reading: note "multiprocessing";
- Extra reading: Livermore National Lab "pthreads tutorial"; Livermore National Lab "OpenMP tutorial";
- Exercises: exercise "multiprocessing"; questions "multiprocessing";

GSL vectors and matrices, BLAS. Printf debugging.
- Reading: GSL manual → Table of Contents for chapters "Vectors and Matrices" and "BLAS support";
- Reading: Wikipedia article "Basic Linear Algebra Subroutines" (BLAS);
- Reading: note "debug";
- Exercises: "gsl-matrix", "debug";

Making scientific reports with LaTeX; LaTex basics, math, figures.
- Reading: chapters "Basics", "Document Structure", and "Importing Graphics" in the LaTeX wikibook.
- Exercise "latex".

Interpolation 1 [chapter.pdf] [Homework "interpolation"]
- Polynomial interpolation;
- Spline interpolation: linear, quadratic, cubic splines;

Interpolation 2
- Sub-splines; Akima (exam project) and Steffen interpolants;
- Rational function interpolation; Barycentric rational interpolation; Berrut interpolant (exam project);
- Bilinear interpolation on a rectilinear 2D grid (exam project);

Linear equations [chapter.pdf] [homework "linear-equations"]
- Triangular systems, back/forward-substitution;
- QR-decomposition: modified Gram-Schmidt algorithm, Householder reflection algorithm, Givens rotation algorithm;
- LU-decomposition: Doolittle algorithm;
- Cholesky decomposition;
- Determinant of a matrix;
- Matrix inverse.

Ordinary least-squares problem [chapter.pdf] [homework "least-squares"]
- Least-squares problem;
- Least-squares solution with QR-decomposition;
- Ordinary least-squares fit; fit errors and covariance matrix.

Eigenvalue decomposition [chapter.pdf] [homework "eigenvalues"]
- Eigenvalues and eigenvectors; Eigenvalue decomposition;
- QR/QL algoritm;
- Jacobi eigenvalue algorithm;
- Rank-1 and Rank-2 updates of symmetric eigenvalue problem;
- Singular value decomposition;
Ordinary differential equations (ODE) - 1 [chapter.pdf] [homework "ODE"]
- One-step (Runge-Kutta) methods;
- Error estimate;
- Adaptive step-size strategy;
Ordinary differential equations (ODE) - 2
- Implicit, multi-step, and predictor-corrector steppers;
Numerical integration (quadratures) - 1 [chapter.pdf] [homework "numerical integration"]
- Quadratures with equally spaced abscissas (Newton-Cotes quadratures);
- Adaptive algorithms with equally spaced abscissas;

A taste of C++: a vec class with operator overloading and garbage collection [examples/c++/matrix]
- Compiling with C++;
- Garbage collector libgc-dev [Boehm garbage collector];
- Classes, methods, operator overloading.

Numerical integration (quadratures) - 2
- Quadratures with optimized nodes; Gauss and Gauss-Kronrod quadratures;
- Variable transformation quadratures; Clenshaw-Curtis quadrature;

Monte Carlo integration [chapter.pdf] [homework "Monte Carlo"]
- Plain Monte Carlo sampling; pseudo- and quasi-random (low discrepancy) sequences
- Importance and Stratified sampling;

Nonlinear equations / root-finding [chapter.pdf] [homework "Roots"]
- Modified Newton's method with backtracking linesearch;
- Quasi-Newton methods: Broyden update;

Minimization [chapter.pdf] [homework "Minimum"]
- Modified Newton's method with backtracking linesearch;
- Quasi-Newton methods: Broyden and SR1 updates;
- Dowhill simplex method (Nelder-Mead);

Power methods and Krylov subspaces (linear algebra) [chapter "Power methods"] [chapter "Eigenvalues"]
- Power and inverse iteration methods;
- Arnoldi and Lanczos methods;
- GMRES (Generalized Minimum RESidual) method for solving systems of linear equations.;

Artificial Neural Networks [chapter "Artificial Neural Networks"] [homework "Neural Network"]
- Artificial neurons and neural networks;
- Three-layer feed-forward neural networks; input, output, and hidden neurons;
- Network training;

Fast Fourier transform and applications [chapter "FFT"]
- Discrete Fourier Transform and applications
- Fast Fourier Transform: Danielson-Lanczos lemma and Cooley-Tukey algorithm;

Numerical methods for solving the Schrödinger (partial differential) equation
- Finite difference method;
- Spectral method (basis expansion);
- Variational method;
- Spectral variational method;
- Artificial neural networks.

References

D.V.Fedorov, Introduction to numerical methods, [1M pdf file].
C syntax [→];
GNU Scientific Library documentation [→];
Gnuplot documentation [→];
Pyxplot user's guide [→];
L^AT_EX wikibook [→];