Algorithms of Scientific Computing - Summer 11

From Sccswiki
Jump to navigation Jump to search
Summer 11
Tobias Neckel, Dirk Pflüger
Time and Place
Mondays 10:15-11:45 and Thursdays 8:45-10:15, room MI 02.07.023
Tutorial: Wednesdays 10:15-11:45, room MI 02.07.023, starting 11/05/2011
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
Gerrit Buse, Thomas Auckenthaler
October 4, 2011, 9:30 (room 01.06.020) , see TUMonline
Semesterwochenstunden / ECTS Credits
6 SWS (4V + 2Ü) / 8 Credits

What's ASC (former AWR) 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.

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


  • On Monday, July 4, there is our Chair's excursion; more details on this page: Lehrstuhlausflug_2011. Please come and join us!
  • Monday 1.8., 10.15-11am, room 02.07.023: Use this chance to ask questions about the topics of the lecture before the exam!
  • Repeat exam is October 4, 2011, 9:30 (room 01.06.020)
    • Two pages (a single sheet of paper, both sides) in A4 of handwritten notes are allowed in the exam.



Fast Fourier Transform

Hierarchical Methods

Space-Filling Curves

Worksheets and Solutions

Number Topic Worksheet Date Solution
1 Discrete Fourier Transform Worksheet 1 11.5. Solution 1 pallas1.mws pallas2.mws
2 Discrete Fourier Transform Worksheet 2 16.5. Solution 2
3a Fast Poisson Solver Worksheet 3a 23.5. Solution 3a
3b Discrete Cosine Transform Worksheet 3b 25.5. Solution 3b
4 Numerical Quadrature for One-dimensional Functions Python Introduction, Worksheet 4, exercise4.tgz 1.6. solution4.tgz
5 Adaptivity, Norms of Functions Worksheet 5, exercise5.tgz 9.6. solution5.pdf, solution5.tgz
6 Multi-dimensional Quadrature Worksheet 6, arch2d_exercise.ods 20.6. Solution 6
7 Regular Sparse Grids, Combination Technique Worksheet 7, exercise7.tgz 29.6. Solution 7, solution7.tgz
8 Orthogonality Worksheet 8 7.7. Solution 8
9 Multigrid Worksheet 9, exercise9.tgz 18.7. solution9.tgz
10 Grammars for Space-filling Curves Worksheet 10, exercise10.tar 21.7. Solution 10, solution10.tar
11 Arithmetization of Space-filling Curves Worksheet 11, exercise11.tar 27.7. Solution 11, solution11.tar


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: