Algorithms for Scientific Computing - Summer 18
Jump to navigation
Jump to search
- Term
- Summer 2018
- Lecturer
- Univ.-Prof. Dr. Michael Bader
- Time and Place
- Lecture: Mon 14-16 and Fri 10-12, MI HS 2 (first lecture on Mon, Apr 9)
- Tutorial: Wed 10-12 MI 00.13.009A (first tutorial on Wed, Apr 11)
- Audience
- see module description (IN2001) in TUMonline
- Tutorials
- Jean-Matthieu Gallard, M.Sc., Michael Obersteiner, M.Sc.
- Exam
- written exams (Jul 26 and, pres., Oct 4)
- Semesterwochenstunden / ECTS Credits
- 6 SWS (4V + 2Ü) / 8 Credits
- TUMonline
- https://campus.tum.de/tumonline/wbLv.wbShowLVDetail?pStpSpNr=950349332
Contents
News & Announcements
- The repeat exam review will take place on Tuesday, Oct 16 11:00 - 11:30 in room 02.05.043
- The exam review will take place on Monday, Aug 20, 10:00 am in room 02.07.023
- A Q&A session for exam preparation will be offered on Friday, Jul 20, 10.15 in lecture hall MI HS 2
- No tutorial on Wednesday 25.04, the tutorial will take place on Friday 27.04 in the usual lecture room (MI HS 2).
What's ASC about?
Many applications in computer science require methods of (numerical) mathematics - especially in science and engineering, of course, but also 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. Similar, numerical methods for approximation have become essential techniques for high-dimensional classification problems in data science. Essentially, these methods come down to the question of how to represent and process information or data as (multi-dimensional) continuous functions. "Algorithms for Scientific Computing" thus provides an algorithmically oriented introduction to the foundations of such mathematical methods.
Topics include:
- The fast Fourier transformation (FFT) and some of its variants:
- FCT (Fast Cosine Transform), real FFT, Application for compression of video and audio data
- Hierarchical and recursive methods in scientific computing
- From Archimedes' quadrature to the hierarchical basis
- Classification problems
- From the hierarchical basis to wavelets
- High-demonsional problems
- Sparse grids and the sparse-grid combination technique
- Octrees and Space filling curves (SFCs):
- Tree-structured (hierarchical) adaptivity
- Construction and properies of SFCs
- Application for parallelization and to linearize multidimensional data spaces in data bases
Lecture Slides and Supplementary Materials
Lecture slides are published here successively. For future lectures, the respective slides from summer 2017 will be linked.
- Introduction - Apr 9
Fast Fourier Transform
- Discrete Fourier Transform (DFT) - Apr 9, 13
- Fast Fourier Transform (FFT) - Apr 13, 16
- Further Material: Website of FFTW (a fast library to compute the DFT); in particular, see the chapter on Implementing FFTs in Practice by the FFTW developers
- FFT on real data - Apr 20, 30
- additional info: paper Paul N. Swarztrauber - Symmetric FFTs (access via LRZ proxy necessary, see also the paper on the AMS website)
- Quarter-Wave-Fourier Transform and Discrete Cosine Transform - Apr 23, 30
- matlab central: jpeg compression
- an embarrassingly simple simple JPEG-simulator (Java program)
- The Discrete Cosine Transform by Gilbert Strang (SIAM Review 41(1), p. 135-147) - the article discusses the connection between the Discrete Cosine Transform and eigenvectors of familiar matrices in Scientific Computing
- Discrete Sine Transform - May 4
- Fast Poisson Solvers - May 4
Hierarchical Methods
- Towards Data Mining: Approximation and Classification - May 7
- Archimedes' Quadrature 1D - May 11
- Hierarchical Basis in 1D - May 14, 18
- Wavelets - May 18, 25, 28
- Wavelet transforms versus Fourier transforms by Gilbert Strang (Bull. Amer. Math. Soc. 28 (1993) p.288-305)
- Finite Element Methods (parts I & II) - Jun 1
- additional material: Maple worksheet for Poisson-FEM (and as PDF)
Sparse Grids
- Archimedes Quadrature in d Dimensions - Jun 4,8
- further material (from an older course): Maple worksheet for d-Dim. archimedes (and as PDF)
- Hierarchical Basis in d Dimensions - Jun 8 (intro), 11,15,18 (parts I, II and III)
- "separate proof" for estimating surpluses (outlook)
- Data Structures for Sparse Grids - Jun 18,22
- Finite Element Methods (part III shortly, part IV not covered) - Jun 22
Space-Filling Curves
- From Quadtrees to Space-Filling Order - Jun 25
- Hilbert Curve (Construction, Definition, and Arithmetisation) - Jun 29, Jul 2
- 2D and 3D Space-filling Curves - Jul 2,6 (parts I+II), Jul 9 (part III)
- Space-filling curves and parallelisation - Jul 9
Worksheets and Solutions
| Number | Topic | Worksheet | Tutorial | Solution |
|---|---|---|---|---|
| 1 | Discrete Fourier Transform I | Python Introduction Worksheet 1 Worksheet 1 Notebook template | Apr. 11 | |
| 2 | Discrete Fourier Transform II | Worksheet 2 Worksheet 2 Notebook template | Apr. 18 | |
| 3 | Discrete Cosine Transform |
Worksheet 3 Worksheet 3 Notebook template Template Exercise 2 |
Apr. 27 | |
| 4 | Discrete Fourier Transform III | Worksheet 4 | May 02 | |
| 5 | 1D Classification | Worksheet 5 Worksheet 5 Notebook template | May 09 | |
| 6 | Quadrature | Worksheet 6 Worksheet 6 Notebook template | May 16 | Ws6 solution Notebook |
| 7 | Hierarchical Basis | Worksheet 7 | May 23 | |
| 8 + 9 | Wavelets | Worksheet 8 Worksheet 8 Notebook template | May 30 | |
| 10 | Multi-dimensional Quadrature | Worksheet 10Worksheet 10 notebook Worksheet 10 spreadsheet | Jun. 13 | |
| 11 | Multi-dimensional hierarchization and adaptive sparse grids | Worksheet 11 Worksheet 11 code template Worksheet 11 include files | Jun. 20 | |
| 12 | Grammars for space-filling curves | Worksheet 12 Worksheet 12 code template Notebook template | Jun. 27 | |
| 13 | Arithmetization of space-filling curves | Worksheet 13 code template Notebook template | Jul. 04 | |
| 14 | Refinement trees and space-filling curves | Worksheet 14, Worksheet 14 Notebook template | Jul. 11 | |
| - | Mock Exam | Mock exam | - |
Jupyter Notebook
- If you want to use a local installation of Jupyter Notebook on your laptop or home computer, just refer to the Jupyter Notebook website on how to install Jupyter Notebook on Linux, Windows or MAC platforms (solutions use the python3 version).
Exams
- type: written exam, working time: 120 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
- Exam preparation: a Q&A session will be offered on Friday, Jul 20, 10.15 in lecture hall MI HS 2
First Exam: Thursday, Jul 26
- Time: 16.00-18.00 - Please make sure to be in the lecture hall by 15.45, as the exam will start precisely at 16.00.
- Place: MW 1801 (Ernst-Schmidt-Hörsaal)
- Review: Monday, Aug 20, 10:00 am in room 02.07.023
Second Exam: Thursday, Oct 4
- Time: 8.00-10.00 - Please make sure to be in the lecture hall by 7.45, as the exam will start precisely at 8.00.
- Place: Interim 1
Literature and Additional Material
Books that are labeled as "available as e-book" can be accessed as e-book via the TUM library - see the ebooks website of the library for details on how to access the books.
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
- Sparse Grids in a Nutshell by Jochen Garcke (Univ. Bonn)
- Chapter on Sparse Grids in this book
- A Short Introduction on Sparse Grids by Gerstner and Griebel
Wavelets
- E. Aboufadel, S. Schlicker: Discovering Wavelets, Whiley, New York, 1999 (available as e-book, TUM library).
- Collection of Wavelet tutorials (maintained by E. Aboufadel and S. Schlicker)
- I. Daubechies: Ten Lectures on Wavelets (available as e-book, TUM library)
- 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
Background Material Concerning Scientific and High Performance Computing
- Interactive Educational Modules in Scientific Computing accompanying the book Scientific Computing, An Introductory Survey by Michael T. Heath (may be useful to repeat some fundamentals in Scientific Computing; also contains a module on the Fourier Transform)
- From the lecture HPC - Algorithms and Applications: Fundamentals - Parallel Architectures, Models, and Languages (esp.: Roofline Model, Cache Models, etc.)
- read the related paper: Roofline: An Insightful Visual Performance Model for Floating-Point Programs and Multicore Architectures (technical report by Williams et al.; published in Communications of the ACM 52 (4), 2009, p.65-76)
