Scientific Computing II - Summer 16

Term

Summer 2016

Lecturer

Michael Bader

Time and Place

Lecture: tba

Tutorial: tba

Audience

see module description (IN2001) in TUMonline

Tutorials

Kilian Röhner, Denis Jarema

Exam

repeat exam (written) on Thursday, Sep 24, 14.00 (MW 0350), 1 handwritten DinA4 page (both sides) is the only allowed helping material

Semesterwochenstunden / ECTS Credits

6 SWS (4V + 2Ü) / 8 Credits

TUMonline

Algorithms of Scientific Computing

---

News & Announcements

• due to the student assembly, the tutorial on Apr 29 will be skipped

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. For future lectures, the respective slides from summer 2014 will be linked.

• Introduction - Apr 13

Fast Fourier Transform

• Discrete Fourier Transform (DFT) - Apr 17
• Fast Fourier Transform (FFT) - Apr 17, 20
  • 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 24, 27
  • 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 27, May 4
  • matlab central: jpeg compression
  • an embarrassingly simple simple JPEG-simulator (Java program)
• Discrete Sine Transform - May 4
• Fast Poisson Solvers - May 8

Hierarchical Methods

• Towards Data Mining: Approximation and Classification - May 11
• Archimedes' Quadrature 1D - May 15
• Hierarchical Basis in 1D - May 18
• Wavelets - May 18, 22, 27
• Finite Element Methods (parts I-III) - May 29
  • additional material: Maple worksheet for Poisson-FEM (and as PDF)

Space-Filling Curves

• From Quadtrees to Space-Filling Order - June 1
  • IPython Notebook script for Hilbert curve grammar
• Hilbert Curve (Construction, Definition, and Arithmetisation) - Jun 5
  • IPython Notebook script for Hilbert curve arithmetization
• 2D and 3D Space-filling Curves - Jun 8, 12
• Space-filling curves and parallelisation - Jun 15, 19
  • IPython Notebook script Hilbert curve on a quadtree

Sparse Grids

• Archimedes Quadrature in d Dimensions - Jun 22, 26
  • further material (from lecture in 2012): Maple worksheet for d-Dim. archimedes (and as PDF)
• Hierarchical Basis in d Dimensions - Jun 26, 29
  • "separate proof" for estimating surpluses (outlook, Jun 29)
• Data Structures for Sparse Grids - Jul 6
• Finite Element Methods (part IV) - Jul 10

Worksheets and Solutions

Number	Topic	Worksheet	Date	Solution
1	Discrete Fourier Transform I	Worksheet 1 Python Introduction	15.4.2015	solution 1 IPyNb solution 1
2	Discrete Fourier Transform II	Worksheet 2 IPyNb template 2	22.4.2015	solution 2 IPyNb solution 2
3	Discrete Cosine Transformation	Worksheet 3 IPyNb template 3	6.5.2015	solution 3 IPyNb solution 3
4	Discrete Sine Transformation Numerical Quadrature for One-dimensional Functions	Worksheet 4a Worksheet 4b py/ipynb	13.5.2015	solution 4a solution 4b
5	Archimedes Quadrature and Haar Wavelets	Worksheet 5 py/ipynb	20.5.2015	solution 5 Archimedes solution 5 Haar Wavelets
7	Grammars for Space-filling Curves	Worksheet 7 IPyNb template 7	3.6.2015	solution 7 IPyNb solution 7
8	Arithmetization of Space-filling Curves	Worksheet 8 IPyNb template 8	10.6.2015	solution 8 IPyNb solution 8
9	Refinement Trees and Parallelization with Space-Filling Curves	Worksheet 9 IPyNb template 9	17.6.2015	solution 9 IPyNb solution 9
10	Multi-dimensional Quadrature	Worksheet 10, exercise10.ods	24.6.2015	solution10.pdf
11	Hierarchization in Higher Dimensions, Spatial Adaptivity	Worksheet 11, py/ipynb	1.7.2015	IPyNb solution 11 Solution Ex. 2
12	Spatial Adaptivity (Implementation), Combination Technique	Worksheet 12, py/ipynb	8.7.2015	IPyNb solution 12 Solution Ex. 2

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).

Repeat Exam

• type: written exam, duration: 90 min
• time, date, room: Thu, Sep 24, 2015, 14.00-15.45 (MW 0350)
  • note that the exam will start precisely on 14.00; please be in the exam room by 13.45, at the latest!
• please make sure that you register in TUMonline
• 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

Literature and Additional Material

Books that are labeled as "available as e-book" can be accessed as e-book vi the TUM library - see the ebooks website of the library for details 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
• 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