Algorithms of Scientific Computing - Summer 13
- Term
- Summer 13
- Lecturer
- Michael Bader
- Time and Place
- Mondays 8:30-10:00 (MI HS 3) and Thursdays 10-12, room MI 01.10.011, starting April 15
- Tutorial: Wednesdays 10:15-11:45, room MI 02.07.023
- Audience
- see TUMonline
- Tutorials
- Gerrit Buse, Denis Jarema
- Exam
- written repeat exam: Friday, Oct 18, 2013, 16:30-18:15 (Interimshörsaal 2), 1 handwritten DinA4 page (both sides) is the only allowed aid
- repeat exam review: see below under News
- Semesterwochenstunden / ECTS Credits
- 6 SWS (4V + 2Ü) / 8 Credits
- TUMonline
- Algorithms of Scientific Computing
Contents
News & Announcements
- Instead of a last tutorial, there will be a Q&A session with both tutors on Wednesday, July 17, 10-11.30am
- The time and place of the exam are announced above.
- On July 10/11, lecture and tutorial will be switched:
- July 10, 10-12: lecture in MI 02.07.023
- July 11, 10-12: tutorial in MI 01.10.011
- The lecture on Thursday, May 2, will take place in seminar room MI 02.07.023, as the regular seminar room is occupied by another lecture.
- repeat exam review: date (Mo October 28, 2013), time (13.00-14.00), room (02.07.023)
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.
Fast Fourier Transform
- Discrete Fourier Transform (DFT) - Apr 15,18
- Fast Fourier Transform (FFT) - Apr 18, 22
- 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 22, 29
- additional info: paper Paul N. Swarztrauber - Symmetric FFTs (access via LRZ proxy necessary, or see the preprint on the NCAR website)
- Quarter-Wave-Fourier Transform and Discrete Cosine Transform - Apr 29, May 2,6
- matlab central: jpeg compression
- an embarrassingly simple simple JPEG-simulator (Java program)
- Discrete Sine Transform - May 6
- Fast Poisson Solvers - May 6, 13
Hierarchical Methods
- Archimedes' Quadrature 1D - May 13
- Hierarchical Basis in 1D - May 16, 23 ("separate proof")
- Cost and Accuracy - May 16, 23
- Archimedes Quadrature in d Dimensions - May 23, 27
- Hierarchical Basis in d Dimensions - May 27, Jun 3
- Data Mining with Sparse Grids - Jun 6
- Data Structures for Sparse Grids - Jun 6
- Finite Element Methods - Jun 10, 13
- Wavelets - Jun 17, 20
Space-Filling Curves
- From Quadtrees to Space-Filling Curves - June 24
- Hilbert Curve (Construction, Definition, and Grammars - Jun 24, 26
- Hilbert Curve (Arithmetization) - Jul 1, 4
- Approximating Polygons and Fractals - Jul 8
- 3D Space-filling Curves - Jul 10
Worksheets and Solutions
Number | Topic | Worksheet | Date | Solution |
---|---|---|---|---|
1 | Discrete Fourier Transform I | Worksheet 1 Python Introduction | 17.4.2013 | solution pallas1 pallas2 |
2 | Discrete Fourier Transform II | Worksheet 2 | 25.4.2013 | solution |
3 | Discrete Cosine Transformation | Worksheet 3 | 8.5.2013 | solution |
4 | Numerical Quadrature for One-dimensional Functions | Worksheet 4 py/ipynb | 15.5.2013 | IPyNb solution |
5 | Norms of Functions | Worksheet 5 py/ipynb | 22.5.2013 | solution5.pdf IPyNb solution |
6 | Multi-dimensional Quadrature | Worksheet 6, exercise6.ods | 29.5.2013 | solution6.pdf |
7 | Hierarchization in Higher Dimensions, Combination Technique | Worksheet 7 py/ipynb | 5.6.2013 | solution7.pdf IPyNb solution |
8 | Adaptive Sparse Grids, Orthogonality | Worksheet 8 | 12.6.2013 | solution8.pdf |
9 | Scaling Functions, The Haar Wavelet Family | Worksheet 9 py/ipynb | 20.6.2013 | IPyNb solution |
10 | Space-filling Curves, Warm up | Worksheet 10 | 26.6.2013 | --- |
11 | Grammars for Space-filling Curves | Worksheet 11 py(template) | 3.7.2013 | solution 11 py(solution) |
12 | Arithmetization of Space-filling Curves | Worksheet 12 py(template) | 10.7.2013 | solution 12 py(solution) |
IPython Notebook
- If you want to use a local installation of IPython Notebook on your laptop or home computer, just refer to the IPython Notebook website on how to install IPython Notebook on Linux, Windows or MAC platforms
- If you install IPython Notebook for Windows, it might happen that starting it from the "Start" menue will open an IPython server website, but that you cannot create or import any new Python notebooks. In that case, try to start IPython Notebook from the command line via "ipython notebook --notebook-dir=.\" (from the directory where you want to store the Python notebooks); you can also create a batch file for this (download example, place it in the desired directory).
Exam
- written repeat exam, duration: 90 min
- time, date, room: Fri Oct 18, 2013, 16.30-18.15 (Interim 2 - in the black building in front of FMI)
- note that the exam will start precisely on 16.30; please be in the exam room by 16.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
- please make sure that you register in TUMonline
- exam review: t.b.a. (probably around 1 week after the repeat exam)
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 (available as e-book).
- 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