Algorithms for Scientific Computing

Discrete Fourier transform and related transforms
- FFT: derivation and implementation
- Fast discrete cosine/sine transforms: derivation and implementation via FFT
- Applications: multi-dimensional data (images, video, audio) and FFT-based solvers for linear systems of equations

Space-filling curves
- Peano- and Hilbert curves: representation by algebraic and grammatical means
- Applications: organisation of multi-dimensional data; parallel, adaptive, and cache oblivious algorithms

Hierarchical numerical methods
- Hierarchical bases for one- and multi-dimensional problems
- Computational cost versus accuracy; Sparse Grids
- Adaptive representation of continuous data
- Applications: numerical quadrature, differential equations
- Outlook: multigrid methods, wavelets

At the end of the module, students are able to identify, explain, and implement selected methods that are of particular interest to the informatical aspects of scientific computing because of their algorithmic structure and their significance for practical applications.
Participants can analyse and judge the efficiency of such methods by deriving statements about the required computational cost and - where applicable - the achieved accuracy and by comparing them with corresponding results for other methods.
The students are able to transfer the methodology to new methods for related problems.

keine Angabe

This module comprises lectures and accompanying tutorials. The contents of the lectures will be taught by talks and presentations.
Students will be encouraged to study literature and to get involved with the topics in depth. In the tutorials, concrete problems will be solved - partially in teamwork - and selected examples will be discussed.

Slides, whiteboard, exercise sheets

- W.L. Briggs, Van Emden Henson, The DFT - An Owner's Manual for the Discrete Fourier Transform, SIAM, 1995
- Charles van Loan, Computational Frameworks for the Fast Fourier Transform, SIAM, 1992
- M. Bader, Space-Filling Curves - An Introduction with Applications to Scientific Computing, Springer-Verlag, 2013
- H. Sagan, Space-Filling Curves, Springer-Verlag, 1994
- H.-J. Bungartz, Skript Rekursive Verfahren und hierarchische Datenstrukturen in der numerischen Analysis, http://www5.in.tum.de/lehre/vorlesungen/algowiss/Bungartz_HierVerf.ps.gz
- H.-J. Bungartz, M. Griebel: Sparse Grids, Acta Numerica, Volume 13, p. 147-269. Cambridge University Press, May 2004

Prüfungsart: Klausur

Die Prüfungsleistung wird in Form einer Klausur erbracht. In dieser soll nachgewiesen werden, dass in begrenzter Zeit ein Problem erkannt wird und Wege zu einer Lösung gefunden werden können. Die Prüfungsfragen gehen über den gesamten Vorlesungsstoff. Die Antworten erfordern eigene Formulierungen. Darüberhinaus können kurze Rechenaufgaben gestellt werden.