Algorithms for Scientific Computing - Summer 17
- Term
- Summer 2017
- Lecturer
- Univ.-Prof. Dr. Michael Bader
- Time and Place
- Lecture: Mon 8:30-10:00, Fri 10:15-11:45, MI Hörsaal 2 (1st lecture: Mon, Apr 24)
- Tutorial: Wed 10:15-11:45, MI 00.13.09A
- Audience
- see module description (IN2001) in TUMonline
- Tutorials
- Emily Mo-Hellenbrand, M.Sc., Jean-Matthieu Gallard, M.Sc.
- Exam
- Mon, Aug 7, 10.30 in lecture hall MI HS 1 (F.L. Bauer Hörsaal)
- Semesterwochenstunden / ECTS Credits
- 6 SWS (4V + 2Ü) / 8 Credits
- TUMonline
- https://campus.tum.de/tumonline/wbLv.wbShowLVDetail?pStpSpNr=950290914
Contents
News & Announcements
- As pointed out by some, there are confusions regarding WS6 ex1. Therefore, I reformulated the question and WS6 is updated. Please check.
- The tutorial on Wednesday 12.07 will include the beginning of the lecture on space-filling curve.
- The Mock Exam and its solution is now posted in the "Worksheets and Solutions" table. Please note:
- Disclaimer: this mock exam merely serves the purpose of giving you some ideas/hints on what to expect in the actual exam (e.g., exam format, possible questions, difficulty levels). Please do NOT assume that you will get the same (or very similar) questions in the actual exam, as there are many ways to ask a question on the same subject!
- Exam coverage: You should prepare for all 4 topics, i.e., FFT, Hier. methods, Sparse grids, SFC. And you should expect questions from all lecture slides (except for Red parts) and worksheet exercises. Pseudo code questions are possible to appear.
- Preparation hint: Try to solve & understand all the exercises in the worksheets and the mock exam.
- The supplement material of transforming the regularization formula into a linear system (Lecture July 10, slide 18) is uploaded.
- Worksheet 9 code template is updated (fixed compatibility issues with Python 3). Please re-download the template zip. NOTE: you need the files supplied in the template zip to run the Worksheet 9 code solution.
- Worksheet 7 solution is updated (mistake in ex4 corrected). Please re-check the solution!
- please re-check the solution of exercise 1 on worksheet 4; this has been corrected!
- as an exception, the lecture on Fri, May 19, will start at 10.30 (until 12.00)
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 2016 will be linked.
- Introduction - Apr 24
Fast Fourier Transform
- Discrete Fourier Transform (DFT) - Apr 24, 28
- Fast Fourier Transform (FFT) - Apr 28, May 5
- 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 - May 8, 12
- 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 - May 12, 15
- matlab central: jpeg compression
- an embarrassingly simple simple JPEG-simulator (Java program)
- Discrete Sine Transform - May 19
- Fast Poisson Solvers - May 22
Hierarchical Methods
- Towards Data Mining: Approximation and Classification - May 26
- Archimedes' Quadrature 1D - May 29
- Hierarchical Basis in 1D - Jun 2, 9
- Wavelets - Jun 9, 12, 16
- Finite Element Methods (parts I & II) - Jun 19
- additional material: Maple worksheet for Poisson-FEM (and as PDF)
Sparse Grids
- Archimedes Quadrature in d Dimensions - Jun 23
- further material (from lecture in 2012): Maple worksheet for d-Dim. archimedes (and as PDF)
- Hierarchical Basis in d Dimensions - Jun 26 (intro and part I), 30 (parts II and III)
- "separate proof" for estimating surpluses (outlook)
- Finite Element Methods (part III and slight outlook on part IV) - July 3, 7
- Data Structures for Sparse Grids - July 10
Space-Filling Curves
- From Quadtrees to Space-Filling Order - July 7 (octrees), 14
- Hilbert Curve (Construction, Definition, and Arithmetisation) - July 14, 17
- 2D and 3D Space-filling Curves - Jul 17, 21
- Space-filling curves and parallelisation - Jul 24
Worksheets and Solutions
Number | Topic | Worksheet | Tutorial | Solution |
---|---|---|---|---|
1 | Discrete Fourier Transform I | Worksheet 1Python Introduction | Apr. 26 | |
2 | Discrete Fourier Transform II | Worksheet 2 Worksheet 2 Notebook template | May 3 | |
- | - | - | May 10 | tutorial cancelled due to student assembly |
3 | Discrete Cosine Transform | Worksheet 3 Worksheet 3 Notebook template Template Exercise 1 | May 17 | |
4 | Discrete Fourier Transform III | Worksheet 4 | May 24 | |
5 | Numerical Quadrature 1D | Worksheet 5 Worksheet 5 Notebook template | May 31 | |
6 | Hierarchical Basis | Worksheet 6 | Jun. 07 | |
7-Part1 | Function Approximation and Wavelet | Ex1-3: Worksheet 7 Worksheet 7 Notebook template | Jun. 14 | |
7-Part2 | Function Approximation and Wavelet | Ex4-5: See above | Jun. 21 | See above |
8 | Multi-dimensional Quadrature | Worksheet 8 Worksheet 8 template | Jun. 28 | |
9 | Multi-dimensional hierarchization and adaptive sparse grids | Worksheet 9 Worksheet 9 code template | Jul. 05 | |
10 | Grammars for space-filling curves | Worksheet 10 Worksheet 10 code template Notebook template | Jul. 12 | |
11 | Arithmetization of space-filling curves | Worksheet 11 code template Notebook template | Jul. 19 | |
12 | Refinement trees and space-filling curves | Worksheet 12, Worksheet 12 Notebook template | Jul. 26 | |
13 | Q&A session (exercises) | Aug. 02 | ||
- | 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.
Exam
- type: written exam, duration: 100 min
- time, date, room: Mon, Aug 7, 2017, 10.30-12.10 (MI HS 1, Friedrich L. Bauer Hörsaal)
- note that the exam will start precisely on 10.30; please be in the exam room by 10.15, 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
- extra session for questions: t.b.a.
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)