Algorithms of Scientific Computing - Summer 11
- Term
- Summer 11
- Lecturer
- 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
- 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
- Tutorials
- Gerrit Buse, Thomas Auckenthaler
- Exam
- August 8, 2011
- Semesterwochenstunden / ECTS Credits
- 6 SWS (4V + 2Ü) / 8 Credits
- TUMonline
- {{{tumonline}}}
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
News
- The exam date is now fixed: August 8, 2011, 10:00-12:00
Please register for the exam until June 30, 2011 in TUMonline. - On Monday, July 4, there is our Chair's excursion; more details on this page: Lehrstuhlausflug_2011. Please come and join us!
- This and next week, the tutorial will be on Thursday each (7.7., 14.7.)
Material
Introduction
Fast Fourier Transform
- Discrete Fourier Transform (DFT) - 02.05. + 05.05.11
- Fast Fourier Transform (FFT) - 05.05. + 09.05.11
- FFT on Real-valued Data - 09.05. + 12.05.11
- additional info: paper Paul N. Swarztrauber - Symmetric FFTs (access via LRZ proxy necessary)
- Quarter-Wave-Fourier Transform and Discrete Cosine Transform - 12.05. + 19.05.11
- Discrete Sine Transform - 19.05.11
Hierarchical Methods
- Archimedes' Quadrature (one-dimensional) - 26.05.11
- The Maple worksheet (or non-executable in HTML)
- Cost and Accuracy - 30.05.11
- Hierarchical Decomposition, 1d - 05.06.11, 08.06.11; proof for the integral representation
- Archimedes' Quadrature (d-dimensional) - 08.06.11, 15.06.11
- The Maple-Worksheet (or non-executable in HTML)
- The recursive call tree als Mindmap for Freemind ("Free"mind, as it's free) and the HTML export
- Hierarchical decomposition, d-dimensional - 15.06.11, 16.06.11, 22.06.11;
Update 20.06.: new slide -81-, corrected two errors on slide -88- (former -87-) - Intermezzo: Finite Elements - 30.06.11
- Algorithms and Data Structures - 04.07.11, 06.07.11, 11.07.11
- Sparse Grid Classification - 11.07.11
- Printable version 8 slides per page up to current state
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 (not yet) | 18.7. |
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
- 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
Space-filling Curves:
- Hans Sagan: Space-Filling Curves, Springer-Verlag, 1994
- Lecture notes of Prof. Bader (German only)