Lecture WS 17/18 Numerical Algorithms
Broad overview and understanding of propositions, relations and methods from the area of numerical algorithms. Competence to evaluate the scope, utility, and limits of the methods and techniques and to independently apply abstract mathematical results to concrete problems. Competence to place the results in a more general mathematical context. Overview of connections to other areas and ability to arrive at rigorous mathematical proofs starting from heuristic considerations.
The selection of topics is based on the module handbook for the Master programme in mathematics.
In particular, we will introduce and discuss the h-,p- and hp-versions of the finite element method (FEM) and its application to conservation equations.
- Repetition of classical finite element method (FEM) and functional analysis: h-FEM on regular meshes
- Fast solvers: Multigrid, Domain Decomposition
- High order FEM and isogeometric analysis (IGA): p-FEM, k-FEM
- Adaptive FEM: h-, hp-adaptive FEM
- Enriched Approximations: extended FEM (XFEM), generalized FEM (GFEM), partition of unity methods (PUM)
- Discontinuous Galerkin: Elliptic problems, conservation laws
- From smooth/regular problems and solutions
- to general/irregular/non-smooth/singular/discontinuous solutions
- Braess, Finite Elemente: Theorie, schnelle Löser und Anwendungen in der Elastizitätstheorie
- Braess, Finite Elements: Theory, fast solvers, and applications in solid mechanics
- Brenner, Scott: The mathematical theory of finite element methods
- Hackbusch: Elliptic Differential Equations: Theory and numerical treatment
- Hackbusch: Theorie und Numerik elliptischer Differentialgleichungen
- Hackbusch: Multigrid methods and applications
- Melenk: hp-finite element methods for singular perturbations
- Schwab: p- and hp-finite element methods: theory and applications in solid and fluid mechanics
- LeVeque: Numerical methods for conservation laws
- Xu: Iterative methods by Space Decomposition and Subspace correction (accessible in University network)
- Schweitzer: Meshfree and Generalized Finite Element Methods (Chapter 1, Section 2.2 for MLS)
- Carl de Boor: B(asic)-Spline Basics
Some of these books are also available in German/English, as ebook or in another edition in the library. The essay of Carl de Boor on B-Spline Basics is available as PDF.
Prerequisites for this lecture are the topics and exercises of the preceding lectures Algorithmische Mathematik I (V1G5), Algorithmische Mathematik II (V1G6), V2E1 Einführung die Grundlagen der Numerik (V2E1).
These prerequisite topics include:
- Calculus, multidimensional differentiation and integration and Taylor expansion
- Elementary combinatorics and probability theory
- Structured programming, in particular C, Python
- Polynomial Interpolation
- Least Squares Approximation
- Conditioning of problems, Stability of algorithms
- Inner products, Orthogonality, Hilbert Spaces, Best approximation in Hilbert spaces
- Orthogonalization, Gram-Schmidt, Orthogonal Polynomials
- Numerical Integration, Quadrature
- Solution of systems of linear equations: Gauss elimination, LU decompostion, Cholesky decomposition, QR decomposition
- Solution of nonlinear equations: bisection, Newton
- Classical iterative methods for systems of linear equations: Jacobi, Gauss-Seidel, Richardson, SOR
- Krylov subspaces, Krylov subspace methods: Gradient descent, CG, PCG, MINRES, GMRES
- Preconditioning of iterative methods: PCG
- Eigenvalues, Eigenvectors, Bounds for the spectrum, Power iteration, Lanczos, Arnoldi, QR algorithm
Dates: Tuesday 10:15 – 11:45, Thursday 08:30 – 10:00
Location: Wegelerstraße 6 - Seminarraum 6.020 6th floor, last room on right, heading southwest
Registration for tutorials in the first lecture on Tuesday. Only one tutorial in either the morning or late afternoon timeslot will be given. Please, be present in the first lecture for poll and choice of timeslot.
Admittance for oral exam based on homework assignments requiring
- 50% of points from theory assignments
- 50% of points from programming assignments
Worksheets with homework assignments are distributed and put on the website Thursdays. Please, submit your homework assignments Thursdays right before and at the beginning of the lecture one week after handout. Submit programming assignments as plain text Python files.
Programming exercises will be based mainly in Python/NumPy/matplotlib. Please send in your solutions to programming exercises via mail to your tutorial’s teaching assistant.
This combination is a very useful for quick implementation. Algorithms can be put into code fast. Plots can be produced with little effort. Much of what is needed for the lecture can be found in the following examples.
Some Documentation and Tutorials can be found at the following links.
One easy way to obtain all necessary Python packages is Anaconda.
- exercise_sheet_04.pdf Exercise 13 (b) was corrected
- exercise_sheet_08.pdf Typo in 26c) It’s and , not and
- Graded oral exam, length 30 minutes in Besprechungszimmer, 6.007, Wegelerstraße 6
- Please do not forget to sign up for the exam via BASIS
- Registration for exam slots, first come first served, via lists at the end of the term
- successful participation in tutorials required for admittance to examination
Note: Lists for the registration to the exam are available now, and were passed during the lecture on 12-19-2017.
If you did not register yet, please contact the assistant Denis Duesseldorf.