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

Numeriske Metoder / Numerical methods 2014

[ 2013 home-page ]

NB:
Schedule:
Exercises:
Setup; Hello World; Interpolation; Linear equations; Eigenvalues; Least-Squares fit; Root finding; Optimization; ODEs; Adaptive integration; Check and comment on your partner's homeworks: everything is built, figures and output files indicative enough, makefiles reasonable, no major flaws in the programs, ets...; Monte Carlo integration; FFT; SMP.
Weekly notes:
  1. Introduction:
    • Numerical computations in physics; servers and clusters; POSIX systems; free software; programming languages; programming in POSIX environment; scripts, text editors.
  2. Interpolation [chapter.pdf (June 25 2019)]
    • Polynomial interpolation; spline interpolation: linear, quadratic, cubic splines; other forms of interpolation; multivariate interpolation.
    • The POSIX make utility; homework structure: makefile, main.c, method.c, utils.c → output.txt, illustration.png, ... .
  3. 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.
    • Procedurial, object-oriented, and functional programming styles.
  4. Eigenvalues and eigenvectors (matrix diagonalization) [ chapter.pdf (June 25 2019) ]
    • QR/QL algorithm;
    • Jacobi eigenvalue algorithm;
    • Rank-1 update of a symmetric eigenproblem.
  5. Linear least-squares problem [ chapter.pdf; (June 25 2019) ]
    • Least-squares solution with QR-method; ordinary least-squares fit; fit errors and covariance matrix.
    • Matrix libraries: BLAS, LAPACK, ATLASGSL, Armadillo.
  6. Nonlinear equations (root-finding) [ chapter.pdf; (June 25 2019) ]
    • Modified Newton's method;
    • Broyden's quasi-Newton's method.
  7. 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.
  8. 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.
  9. Numerical integration (quadratures) [ chapter.pdf; (June 25 2019) ]
    • Riemann sums: rectangle and trapezium rules;
    • Quadratures with equally spaced abscissas (Newton-Cotes);
    • Quadratures with optimized abscissas (Gauss);
  10. Numerical integration 2
    • Adaptive algorithms with equally spaced abscissas;
    • Gauss-Kronrod quadratures.
    • Variable substitution quadratures.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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) ]. A paperback copy can be ordered here.
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.
"Copyleft" © 2004-2009 D.V.Fedorov (fedorov at phys dot au dot dk)
x= sin(x)=