Algorithms of Scientific Computing - Summer 14
- Term
- Summer 2014
- Lecturer
- Michael Bader
- Time and Place
- t.b.a.
- Tutorial: t.b.a.
- Audience
- see TUMonline
- Tutorials
- Kilian Röhner, Denis Jarema
- Exam
- written exam
- Semesterwochenstunden / ECTS Credits
- 6 SWS (4V + 2Ü) / 8 Credits
- TUMonline
- see last year's lecture: 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
Material
Lecture slides and worksheets will be published here as soon as they become available.
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 (available as e-book)
- 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 (available as e-book)
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.
- Collection of Wavelet tutorials (maintained by E. Aboufadel and S. Schlicker)
- 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
( available as eBook, also in the TUM library) - Hans Sagan: Space-Filling Curves, Springer-Verlag, 1994