Algorithms of Scientific Computing - Summer 12

From Sccswiki
Jump to navigation Jump to search
Summer 12
Michael Bader
Time and Place
Mondays 10:15-11:45 and Thursdays 8:45-10:15, room MI 02.07.023, starting 16/04/2012
Tutorial: Wednesdays 10:15-11:45, room MI 02.07.023 (on Wed 18/04/2012 lecture instead of tutorial)
Modul IN2001
Informatik Diplom: Wahlpflichtfach im Bereich theoretische Informatik
Informatik Master: Wahlfach im Fachgebiet "Algorithmen und Wissenschaftliches Rechnen"
Informatik Master: Elective topic, subject area "Algorithms and Scientific Computing"
Informatik/Wirtschaftsinformatik Bachelor: Wahlfach
Studierende der Mathematik/Technomathematik, Natur- und Ingenieurwissenschaften
Students of CSE (Application Catalogue E1)
Gerrit Buse, Kaveh Rahnema
written exam
Semesterwochenstunden / ECTS Credits
6 SWS (4V + 2Ü) / 8 Credits
Algorithms of Scientific Computing

What's ASC about?

Many applications in computer science require methods of (prevalently numerical) mathematics - especially in science and engineering, of course, but as well in surprisingly many areas that one might suspect to be directly at the heart of computer science:

Consider, for example, Fourier and wavelet transformations, which are indispensable in image processing and image compression. Space filling curves (which have been considered to be "topological monsters" and a useless theoretical bauble at the end of the 19th century) have become important methods used for parallelization and the implementation of data bases. Numerical methods for minimization and zero-setting are an essential foundation of Neural Networks in machine learning.

Essentially, these methods come down to the question of how to represent and process information or data as (multi-dimensional) continuous functions. Algorithms of Scientific Computing (former Algorithmen des Wissenschaftlichen Rechnens) provides a generally understandable and algorithmically oriented introduction into the foundations of such mathematical methods. Topics are:

  • The fast Fourier transformation (FFT) and some of its variants:
    • FCT (Fast Cosine Transform), real FFT, Application for compression of video and audio data
  • Space filling curves (SFCs):
    • Construction and properies of SFCs
    • Application for parallelization and to linearize multidimensional data spaces in data bases
  • Hierarchical and recursive methods in scientific computing
    • From Archimede's quadrature to the hierarchical basis
    • Cost vs. accuracy
    • Sparse grids, wavelets, multi-grid methods

Repeat Exam

  • written exam, duration: 90 min
  • time, date, room: Tue, Oct 9, 10.00-11.30, in room MW 2050
    • note that the exam will start on 10.00; please be in the exam room by 9.45, at the latest!
  • helping material:
    • you may use one hand-written sheet of paper (size A4, front and back may be used)
    • no other helping material of any kind is allowed
  • please make sure that you register in TUMonline


Lecture slides and worksheets will be published here as soon as they become available.

Fast Fourier Transform

Hierarchical Methods

Space-Filling Curves

Worksheets and Solutions

Number Topic Worksheet Date Solution
1 Discrete Fourier Transform I Worksheet 1 25.4.2012 solution pallas1 pallas2
2 Discrete Fourier Transform II Worksheet 2 30.4.2012 solution
3 Fast Poisson Solver Worksheet 3 9.5.2012 solution
4 Numerical Quadrature for One-dimensional Functions Python Introduction, Worksheet 4, exercise4.tgz 16.5.2012 solution4.tgz
5 Norms of Functions Worksheet 5, exercise5.tgz 23.5.2012 solution5.pdf solution5.tgz
6 Multi-dimensional Quadrature Worksheet 6, exercise6.ods 30.5.2012 solution6.pdf
7 Hierarchization in Higher Dimensions, Combination Technique Worksheet 7, exercise7.tgz 6.6.2012 solution7.pdf solution7.tgz
8 Adaptive Sparse Grids, Orthogonality Worksheet 8 13.6.2012 solution8.pdf
9 Scaling Functions, The Haar Wavelet Family Worksheet 9 20.6.2012 solution9.tgz
10 Space-filling Curves, Warm up Worksheet 10 27.6.2012 ---
11 Grammars for Space-filling Curves Worksheet 11 4.7.2012 solution 11 solution11.tar
12 Arithmetization of Space-filling Curves Worksheet 12 11.7.2012 solution 12

Literature and Additional Material

Fast Fourier Transform:

The lecture is oriented on:

  • W.L. Briggs, Van Emden Henson: The DFT - An Owner's Manual for the Discrete Fourier Transform, SIAM, 1995
  • Thomas Huckle, Stefan Schneider: Numerische Methoden - Eine Einführung für Informatiker, Naturwissenschaftler, Ingenieure und Mathematiker, Springer-Verlag, Berlin-Heidelberg, 2.Auflage 2006 (German only)
  • Charles van Loan: Computational Frameworks for the Fast Fourier Transform, SIAM, 1992

Hierarchical Methods and Sparse Grids


Space-filling Curves:

  • Michael Bader: Space-Filling Curves - An introduction with applications in scientific computing, Texts in Computational Science and Engineering 9, Springer-Verlag, 2012 (to appear end of this year)
  • Hans Sagan: Space-Filling Curves, Springer-Verlag, 1994
  • Lecture notes of Prof. Bader (German only)