Algorithms of Scientific Computing - Summer 12
From Sccswiki
- Term
- Summer 12
- Lecturer
- 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)
- 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
- Semesterwochenstunden / ECTS Credits
- 6 SWS (4V + 2Ü) / 8 Credits
- TUMonline
- Algorithms of Scientific Computing
Contents |
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
Material
Lecture slides and worksheets will be published here as soon as they become available.
Fast Fourier Transform
- Discrete Fourier Transform (DFT) - Apr 18
- Fast Fourier Transform (FFT) - Apr 19
- Further Material: Website of FFTW (a fast library to compute the DFT); see also a chapter on Implementing FFTs in Practice by the FFTW developers
- FFT on real-valued data - Apr 23
- additional info: paper Paul N. Swarztrauber - Symmetric FFTs (access via LRZ proxy necessary)
- Quarter-Wave-Fourier Transform and Discrete Cosine Transform - Apr 26, May 3
- matlab central: jpeg compression
- an embarrassingly simple simple JPEG-simulator (Java program)
- Discrete Sine Transform - May 3
- Fast Poisson Solvers - May 7
Hierarchical Methods
- Archimedes' Quadrature 1D,Cost and Accuracy - May 10
- Maple worksheet for 1D archimedes (and as PDF),
Cost and Accuracy - May 14 - Hierarchical Basis in 1D - May 21, 24,
("separate proof") - Archimedes Quadrature in d Dimensions - May 24
- Hierarchical Basis in d Dimensions - May 31, Jun 4
- Data Mining with Sparse Grids - Jun 4
- Data Structures for Sparse Grids - Jun 11
- Wavelets - Jun 11, 14, 18
- Finite Element Methods - Jun 21, 25
Space-Filling Curves
- From Quadtrees to Space-Filling Curves - June 28
- Hilbert Curve (Construction, Definition, and Grammars - Jul 2, Jul 9
- Hilbert Curve (Arithmetization) - Jul 2, Jul 4
- Approximating Polygons and Fractals - Jul 9
- 3D Space-filling Curves - Jul 12
- Maple worksheet for 3D Hilbert curve (also as PDF)
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
- 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)
