Algorithms of Scientific Computing - Summer 12

From Sccswiki
Revision as of 11:25, 6 June 2012 by Buse (talk | contribs)
Jump to navigation Jump to search
Term
Summer 12
Lecturer
Michael Bader, Dirk Pflüger
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)
Audience
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)
Tutorials
Gerrit Buse, Kaveh Rahnema
Exam
written exam at the end of the semester (details will follow)
Semesterwochenstunden / ECTS Credits
6 SWS (4V + 2Ü) / 8 Credits
TUMonline
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

News

Material

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

Fast Fourier Transform

Hierarchical Methods

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

Literature

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: