[sdfeu.org] [Aarhus University / Physics / Subatomic physics / Theory]
Practical Programming and Numerical Methods 2023
[ DokuWiki | ./exercises | ./homeworks | ./notes | ./lectures | ./matlib | ./examples | the Book | old homepages ]
[list of examination projects]
[ LinEq | EVD | LeastSq | Splines | ODE | quad | MC | roots | min | optim | ann | δck | fft ]

NB

Schedule

Plan

  1. Introduction.
    • About the course; exercises/homeworks; code repositories; examination.
    • POSIX [→] (UNIX) systems; clusters and supercomputers [CSCAA, top500 supercomuters].
    • The Computer Language Benchmarks Game [→] summary [→].
    • We shall only use open software in this course [copyleft].
    ⊕ Exercise "posix".

  2. Code repositories. Makefiles.
    * Distributed Version Control[→] systems and code repositories; Mercurial[→] (hg) and Git[→] (git);
    * POSIX make utility[→] for managing projects on a computer.
    * C-sharp[→] mono[→] framework for POSIX programming.
    + Reading: note "make", introduction to Git from atlassian[→].
    + Exercises: "git", "hello";
    - Extra reading: Chapter "Introduction To Makefiles"[→] in the "GNU make manual";
    - Extra extra reading: Chapter "make - maintain, update, and regenerate groups of programs", of the POSIX standard [IEEE Std 1003.1-2017 (POSIX.1-2017)]
    + Quiz (you might want to install additional man-pages with the command
    sudo apt-get install manpages-posix manpages-posix-dev):

    1. What is your shell?
    2. In your shell prompt, what do the keys "up", "down", "left", and "right" do?
    3. What are the "~", ".", and ".." directories?
    4. At your shell prompt, what does the command !string do?
    5. At your shell prompt, what does the command !number do?
    6. What are the personal configuration files for your shell?
    7. What do the commands echo, time, and date do?
    8. At your system, are echo and time programs or shell commands?
    9. At your system, does your shell-completion work for the long options and/or Makefile targets?

  3. Basics of C# programming.
    * Structure of a C#-program; Main function.
    * Basic types: int double string complex; Scope of variables; Variable shadowing.
    * Compiling, linking, and running C#-programs with mono.
    * Simple output with System.Console.Write method.
    * Mathematical functions in the System.Math class.
    + Reading: notes "C#-program"[→], "Compile/link/run"[→] "Scope"[→], "Simple output"[→];
    + Reading: Makefile automatic variables[→]: $@ (the target), $< (the first prerequisite), $^ (all prerequisites).
    + Reading: Makefile Functions for Transforming Text[→].
    - Extra reading: C#-syntax / Program structure[→], C#-syntax / Operators[→].
    - Extra reading: Math functions in the System.Math class[→]. the System.Console.Write method[→] method for simple output.
    + Exercises: "math".
    + Quiz
    1. Suppose you have messed something up terribly with the latest (uncommitted) changes to your project. How can you discard all changes you have done to your project since the last commit?
    2. Suppose you have realized that the last commit contained an error. How can you discard the last commit? The last two commits?
    3. Suppose you have committed some changes to your project both at the server (the place where you push) and at your box. What do you do now?
    4. What are the values of the following automatic variables in a Makefile: $@, $<, $^?
    5. What does this statement do in a Makefile recipe: $(filter %.cs,$^) ?
    6. What does this statement do in a Makefile recipe: $(addprefix -reference:,$(filter %.dll,$^)) ?
    7. When defining a macro in a Makefile, what is the difference between "=" and ":="?

  4. More Csharp: conditionals, loops, classes.
    * Conditional if else; Loops for, while, do while; Loop foreach;
    * Arrays; Classes/structs; Value/reference type; Example: "vec" class;
    +Reading: C# conditionals [→]; C# loops [→]; C# arrays [→]; C# classes [→];
    +Exercises: "epsilon", "vec".
    +Quiz:
    1. Rewrite the "for-loop for(init;condition;increment)body" using the while-loop.
    2. Rewrite the while-loop "while(condition)body" using the for-loop.
    3. Rewrite the do-while-loop "do body while(condition)" using the while-loop.
    4. Rewrite this piece of code, "(condition?iftrue:iffalse)", using the "if" statement. Hint: google "ternary conditional".
    5. What is the difference between "class", "static class", and "struct"?
    6. What is the difference between "value type" and "reference type".
    7. Explain the modifier "e16" in WriteLine($"x={x:e16}"); (try google "c# standard numeric format").
    8. Try 
      WriteLine( 0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1 == 8*0.1 );
      Why does it produce "false" result ?
    9. Now, why does 
      WriteLine( 0.125+0.125+0.125+0.125+0.125+0.125+0.125+0.125 == 8*0.125 );
      produce "true" result?

  5. Input/output.
    *Standard streams, redirections, piping; File streams.
    *Command-line arguments to Main function.
    +Reading: note "Input/Output".
    +Exercises: input/output; complex; Wiki.
    -Extra reading: Standard streams [→]; Standard streams in C# [→]; Redirection and piping [→]; Microsoft docs: command line arguments [→].
    +Quiz:
    1. What are the types of the objects System.Console.Out and System.Console.In?
      Hint: try //docs.microsoft.com/dotnet/api/system.console.out and //docs.microsoft.com/dotnet/api/system.console.in
    2. What are the delimiter-charactes in your command-line?
    3. What are the elements of the "args" array in the "Main(string[] args)" function after the command 
      mono main.exe -input:in.txt -output:out.txt -numbers:1e0,2e0,3e0
    4. What is the maximum length of the command-line in your system?
      Hint: try "getconf ARG_MAX" and/or (if you use GNU) "echo|xargs --show-limits".
    5. How can you send the contents of a file into the program's standard input stream?
    6. Explain the syntax `command` and $(command) in bash. Hint: Bash command substitution; POSIX shell command substitution.
    7. How can you send the contents of a file as the argument to the program's Main function?
    8. Why do you need double-dollar, $$(command), in the Makefile? Hint: GNU make: variables in recipes.
    9. What will the following Makefile print (and why)? 
      pwd = a random string
test:
	@echo pwd
	@echo `pwd`
	@echo $(pwd)
	@echo $$(pwd)

  6. More C-sharp: generics; delegates; closures.
    * C-sharp generics;
    * Passing functions around: delegates, anonymous delegates, closures;
    + Reading: note "generics"; note "delegates";
    + Exercise "generic list";
    - Extra reading: C-sharp generics[→]; C-sharp delegates[→]; System.Func delegate[→]; Closures in computer programming[→];
    + Quiz

    1. Suppose we have a function 
      static void set_to_seven(double x){ x=7; }
      Is the argument variable set to seven in the caller's scope (in the scope where the function is called)? Explain.
    2. Suppose we have a function 
      static void set_to_seven(double[] xs){ for(int i=0;i<xs.Length;i++)xs[i]=7; }
      Are the elements of the argument array set to seven in the caller's scope? Explain.
    3. Suppose we have a function 
      static void set_to_seven(double[] xs){
	xs = new double[xs.Length];
	for(int i=0;i<xs.Length;i++)xs[i]=7;
	}
      Are the elements of the argument array set to seven in the caller's scope? Explain.
    4. Suppose we have a function 
      static void set_to_seven(ref double x){ x=7; }
      Is the argument variable set to seven in the caller's scope? Hint: google "csharp call by reference".

  7. Multithreading, multiprocessing, parallel computing.
    * Symmetric multiprocessing; threads;
    * System.Threading.Thread class: preparing, running, and joining threads;
    * Pitfalls in parallelism;
    * make --jobs[=4];
    + Reading: note "multiprocessing";
    + Exercise "multiprocessing";
    - Extra reading: system.threading.thread class [→]; potential pitfalls in parallelism.
    + Quiz

    1. Suppose you calculate the harmonic sum using system's "Parallel.For"[→] loop like this, 

      double sum=0; Parallel.For( 1, N+1, delegate(int i){sum+=1.0/i;} );
      why does it run slower than the ordinary serial loop, 
      double sum=0; for(int i=1; i<N+1; i++) {sum+=1.0/i;}
      despite using more processors? (It does so in my box).

    2. Suppose you've got the following Makefile, 

      TIME1 := time --output $@
TIME2  = time --output $@
test:
	@echo $(TIME1)
	@echo $(TIME2)
      what will it print and why?

  8. Scientific plots with gnuplot/plotutils.
    ⊕ Reading: "plot" command from gnuplot documentation, and/or graph manual.
    ⊕ Exercise "plots";


  9. Systems of linear equations [chapter "Linear equations"] [homework "linear equations"]
    * Triangular systems; back- and forward-substitution.
    * QR-decomposition algorithms: modified Gram-Schmidt orthogonalization, Householder reflections, Givens rotations.
    * LU-decomposition: Doolittle algorithm (→exam).
    * Cholesky decomposition (→exam).
    * Determinant of a matrix.
    * Matrix inverse.

  10. Eigenvalue (EVD) and singular value (SVD) decompositions of matrices. [chapter "Eigenvalues"] [homework "eigenvalues"]
    * Eigenvalues and eigenvectors; Eigenvalue decomposition (diagonalization) of a matrix;
    * Singular value decomposition of a matrix (→exam);
    * QR/QL algorithm; Jacobi eigenvalue algorithm;
    * Rank-1 and Rank-2 updates of an EVD (→exam);
    * Quiz:

  11. Least-squares problem; Ordinary least-squares fit. [chapter "Ordinary least-squares"] [homework "least-squares"]
    • Least-squares problem.
    • Least-squares solution with QR-factorization and with SVD factorization; Pseudoinverse of a matrix (→exam?).
    • Ordinary least-squares fit, fit errors and covariance matrix.

  12. Interpolation 1 [chapter "Interpolation"] [homework "splines"]
    • Polynomial interpolation;
    • Spline interpolation: linear, quadratic, cubic splines;
    • Object oriented and functional programming styles.

  13. Interpolation 2
    •Akima sub-spline (→exam) and monotone cubic interpolants;
    •Rational function interpolation, Berrut interpolants (→exam);
    •Bilinear interpolation on a rectilinear 2D grid (→exam);

  14. Ordinary differential equations (ODE) - 1 ["chapter ODE"] [homework "ODE"]
    • Runge-Kutta (one-step) methods;
    • Local error estimate;
    • Adaptive step-size strategy;

  15. Ordinary differential equations (ODE) - 2
    • Implicit, multi-step, and predictor-corrector steppers;

  16. Numerical integration - 1 [chapter "Integration"] [homework "Integration"]
    • Classical Newton-Cotes quadratures (quadratures with regularly spaced abscissas);
    • Adaptive algorithms with regularly spaced abscissas;

  17. Numerical integration - 2
    • Quadratures with optimized nodes; Gauss and Gauss-Kronrod quadratures;
    • Variable transformation quadratures; Clenshaw-Curtis quadrature;

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

  19. Nonlinear equations / root-finding [chapter "roots"] [homework "roots"]
    • Modified Newton's method with backtracking linesearch;
    • Quasi-Newton methods, rank-1 updates, Broyden's update;

  20. Minimization 1: locally convergent methods [chapter "Minimisation"] [homework "Minimisation"]
    • Modified Newton's method with backtracking linesearch;
    • Quasi-Newton methods: Broyden and SR1 updates of Hessian matrix;
    • Dowhill simplex (Nelder-Mead) method;

  21. Minimization 2: globally convergent methods [chapter "Optimization"]
    • Randomized local minimizers;
    • Simulated annealing;
    • Particle swarm optimization;

  22. 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: supervised and unsupervised learning;

  23. Nonlinear least squares fit: uncertainties of the fitting parameters [chapter "Minimisation"]

  24. Fast Fourier transform and applications [chapter "FFT"]

  25. Eigenvalues: Rayleigh quotient methods; Generalized eigenvalue problems
    • Rayleigh quotient iteration;
    • Lagrange multipliers method;
    • Generalized eigenvalue problems;

  26. Linear algebra: power methods and Krylov subspaces [chapter "Power methods"]
    • Eigenvalues: power and inverse iteration methods (→exam);
    • Eigenvalues: Arnoldi and Lanczos methods (→exam);
    • Linear equations: GMRES (Generalized Minimum RESidual) method;

  27. Numerical methods for solving the few-body (partial differential) Schrödinger equation

References

  1. Gnuplot documentation [→];
  2. Pyxplot user's guide [→];
  3. LATEX wikibook [→];