[sdfeu.org] [Aarhus University / Physics / Subatomic physics / Theory]

Practical Programming and Numerical Methods 2024

[ Wiki (backup) | ./c++ | ./python | ./exercises | ./homeworks | ./notes | ./lectures | ./matlib | ./examples | the Book | old homepages ]
[(preliminary) list of examination projects]
[ LinEq | EVD | LeastSq | Splines | ODE | quad | MC | roots | min | optim | ann | δck | fft | Krylov ]

NB

Schedule

Plan

  1. Introduction.
    • About the course; exercises/homeworks; code repositories; examination.
    • POSIX (UNIX) systems []; supercomputers and clusters [top500 supercomuters, CSCAA].
    • The Computer Language Benchmarks Game [] (summary []).
    • We shall only use "open software" in this course [Free software].
    ⊕ 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.
    + Quiz:

    1. What is your shell?
    2. At your shell prompt, what do the keys "up", "down", "left", and "right" do?
    3. In your shell, 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. In your system, are "echo" and "time" programs or shell commands?
    9. In your system, does your shell-completion work for the long options and/or Makefile targets?

    You might want to install additional man-pages with the command

    sudo apt-get install manpages-posix manpages-posix-dev

  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", "wiki",
    + Quiz:
    1. Suppose you have messed your project up terribly with the latest (uncommitted) changes to your project. How can you discard all changes that 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 at the server (the place where you push) and at the same time some other changes at your box. What do you do now? Hint: merge.
    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 ":="?
    8. In you shell, what is the meaning of the following shell variables: $HOME, $PATH, $PWD ?
    9. In you shell, what is the difference between the single quote, double quote, and backquote signs? Hint: try
      echo '$HOME'
      echo "$HOME"
      echo '"$HOME"'
      echo "'$HOME'"
      echo `pwd` 

  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 try
      WriteLine( 0.125+0.125+0.125+0.125+0.125+0.125+0.125+0.125 == 8*0.125 ); 
      Why does this one 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.
    -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-characters 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"; complex.
    - 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_arg_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_arg_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_arg_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".
    5. Why is "int.MaxValue" equal to "2³¹-1"?

  7. Scientific plots with gnuplot/plotutils.
    ⊕ Reading: "plot" command from gnuplot documentation, and/or graph manual.
    ⊕ Exercise "plots";
    + Quiz:
    1. Suppose you've got the following Makefile,

      T1 := target: $@
      T2  = target: $@
      test:
      	@echo $(T1)
      	@echo $(T2)
      what will it print and why?


  8. 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;
      System.Threading.Tasks.Parallel.For(1,N+1,delegate(int i){sum+=1.0/i;});
      why does it run slower (and produces wrong (and somewhat random) results) 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).

  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;
    * QR/QL algorithm; Jacobi eigenvalue algorithm;
    * Rank-1 and Rank-2 updates of an EVD (→exam);
    * One-sided and two-sided Jacobi SVD algorithms(→exam);
    * Quiz:

  11. Ordinary Least-squares problem; Ordinary least-squares fit. [chapter "Ordinary least-squares"] [homework "least-squares"]
    • Least-squares problem and applications;
    • Least-squares solution of overdetermined systems with QR-factorization and with SVD; 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;
    • Sub-splines, Akima sub-spline;
    • Rational function interpolation, Berrut interpolants;
    • Multivariate interpolation, bilinear interpolation;
    • Object oriented and functional programming styles.


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

  14. Ordinary differential equations (ODE) - 2
    • Multi-step and predictor-corrector steppers;
    • Implicit steppers and stiff equations;

  15. Numerical integration - 1 [chapter "Integration"] [homework "Integration"]
    • Recursive adaptive algorithms (similar to driver and stepper in ODE);
    • Classical Newton-Cotes quadratures with regularly spaced nodes;

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

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

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

  19. 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;

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

  21. 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;

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

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

  24. Linear algebra: power methods and Krylov subspaces [chapter "Power methods"]
    • Power and inverse power methods for eigenvalues;
    • Krylov subscpace, Arnoldi and Lanczos iterations;
    • GMRES (Generalized Minimum RESidual) method for linear equations;

  25. Rayleigh quatient methods for eigenvalues; Eigenvalues of updated matrix;
    • Rayleigh quotient and locally optimized steepest descent method;
    • Eigenvalues of rank-1(2) updated matrix;

  26. Generalized eigenvalue problem
    • Generalized eigenvalue problem in quantum and classical mechanics;
    • Solution using diagonalization, Cholesky decomposition, Rayleigh quotient, inverse iteration.

  27. Applications of the ordinary least-squares problems
    • Over-determined and under-determined linear systems;
    • Extrapolation (linear prediction) of (correlated) data;
    • Smoothing of noisy data;
    • Missing data recovery (error concealment);
    • Signal declipping;
    • Signal deconvolution;

  28. Numerical methods for solving few-body (partial differential) Schrödinger equations

References

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