Algorithms of Scientific Computing - Summer 13

Term

Summer 13

Lecturer

Michael Bader

Time and Place

???days 10:15-11:45 and ???days 8:45-10:15, room MI 02.07.023, starting ???

Tutorial: Wednesdays 10:15-11:45, room MI 02.07.023

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, ???

Exam

written exam

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

Repeat Exam

• written exam, duration: 90 min
• 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

Material

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

• Introduction

Worksheets and Solutions

Number	Topic	Worksheet	Date	Solution

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

• Skript of H.-J. Bungartz for the lecture "Rekursive Verfahren und hierarchische Datenstrukturen in der numerischen Analysis" (German only)
• General overview paper on Sparse Grids
• Chapter on Sparse Grids in this book

Wavelets

• E. Aboufadel, S. Schlicker: Discovering Wavelets, Whiley, New York, 1999.
• J.S. Walker: A Primer on Wavelets and their Scientific Applications, Second Edition, Chapman and Hall/CRC, 2008.
• J.S. Walker: Wavelet-based Image Compression (download as PDF)

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)