Algorithms for Scientific Computing
Module IN2001
This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.
Module version of WS 2011/2
There are historic module descriptions of this module. A module description is valid until replaced by a newer one.
| available module versions | ||
|---|---|---|
| WS 2017/8 | SS 2012 | WS 2011/2 |
Basic Information
IN2001 is a semester module in English language at Bachelor’s level and Master’s level which is offered in summer semester.
This Module is included in the following catalogues within the study programs in physics.
- Catalogue of non-physics elective courses
| Total workload | Contact hours | Credits (ECTS) |
|---|---|---|
| 240 h | 90 h | 8 CP |
Content, Learning Outcome and Preconditions
Content
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
- 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
Learning Outcome
At the end of the module, students are able to identify, explain, and implement selected hierarchical 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.
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.
Preconditions
no info
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
| Type | SWS | Title | Lecturer(s) | Dates |
|---|---|---|---|---|
| VI | 6 | Algorithms for Scientific Computing (IN2001) |
Gallard, J.
Obersteiner, M.
Responsible/Coordination: Bader, M. |
Fri, 10:00–12:00, MI HS2 Mon, 14:00–16:00, MI HS2 Wed, 12:00–14:00, MI 00.13.009A and singular or moved dates |
Learning and Teaching Methods
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.
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.
Media
Slides, whiteboard, exercise sheets
Literature
- 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
- 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
Module Exam
Description of exams and course work
Type of Assessment: The exam takes the form of a 120 minutes written exam.
The examination consists of a written exam of 120 minutes in which students show that they are able to find solutions for algorithmic problems arising in the field of scientific computing in a limited time. Questions and small tasks concerning code are used to test the student´s knowledge on known and related hierarchical methods as well as their ability to implement them. Example algorithms and questions are used to examine the capability of analyzing the efficiency of algorithms and the accuracy of a given method.
The examination consists of a written exam of 120 minutes in which students show that they are able to find solutions for algorithmic problems arising in the field of scientific computing in a limited time. Questions and small tasks concerning code are used to test the student´s knowledge on known and related hierarchical methods as well as their ability to implement them. Example algorithms and questions are used to examine the capability of analyzing the efficiency of algorithms and the accuracy of a given method.
Exam Repetition
The exam may be repeated at the end of the semester.