# Algorithms for Scientific Computing - Summer 16

**Term**- Summer 2016
**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 11)
- Tutorial: Wed 10:15-11:45, MI 00.09.013A
**Audience**- see module description (IN2001) in TUMonline
**Tutorials**- Emily Mo-Hellenbrand, M.Sc., Angelika Schwarz, M.Sc.
**Exam**- written exam at the end of the semester
**Semesterwochenstunden / ECTS Credits**- 6 SWS (4V + 2Ü) / 8 Credits
**TUMonline**- https://campus.tum.de/tumonline/wblv.wbShowLvDetail?pStpSpNr=950238554

## Contents

## News & Announcements

**Repetition Exam review**(opportunity to take a look at your graded exam):**Friday, Oct 28, 10AM-12PM**, MI 02.05.057 (Student ID required)**Exam review**(opportunity to take a look at your graded exam): Wednesday, Aug 24, 10AM-12PM, MI 02.05.057 (Student ID required)- Extra session for questions: on Wednesday, July 20, in the tutorial slot (10-12 in room MI 02.07.023); opportunity to ask questions on all exam topics covered in the lectures
- 6.7.2016: On Wednesday, July 13, the last tutorial session will take place in the form of a Q&A session for the exercise sheets.
- 6.5.2016: Worksheet 2 Exercise 3 has been corrected. The problem description was erroneous.
- 5.5.2016: Worksheet 4 has been reuploaded.
- 4.5.2016: Worksheet 3 Exercise 2 has been updated. The input dataset is now explicitly real-valued.
- 24.5.2016: Worksheet 6 has been updated.
- 31.5.2016: Worksheet 7 has been updated.

## 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

## Lecture Slides and Supplementary Materials

Lecture slides will be published here as soon as they become available. For future lectures, the respective slides from summer 2015 will be linked.

- Introduction - Apr 11

### Fast Fourier Transform

- Discrete Fourier Transform (DFT) - Apr 15
- Fast Fourier Transform (FFT) - Apr 15, 18
- 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, 25
- 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 25, 29
- matlab central: jpeg compression
- an embarrassingly simple simple JPEG-simulator (Java program)

- Discrete Sine Transform - May 2
- Fast Poisson Solvers - May 6

### Hierarchical Methods

- Towards Data Mining: Approximation and Classification - May 9, 13
- Archimedes' Quadrature 1D - May 13
- Hierarchical Basis in 1D - May 20, 23
- Wavelets - May 23, 27, 30
- Finite Element Methods (parts I & II) - Jun 3
- additional material: Maple worksheet for Poisson-FEM (and as PDF)

### Sparse Grids

- Archimedes Quadrature in d Dimensions - Jun 6
- further material (from lecture in 2012): Maple worksheet for d-Dim. archimedes (and as PDF)

- Hierarchical Basis in d Dimensions - Jun 10, 13
- "separate proof" for estimating surpluses (outlook)

- Data Structures for Sparse Grids - Jun 13 (part I), 17 (part II)
- Finite Element Methods (part III and slight outlook on part IV) - Jul 8

### Space-Filling Curves

- From Quadtrees to Space-Filling Order - June 17, 20, 27
- Hilbert Curve (Construction, Definition, and Arithmetisation) - Jun 20 (part I), 24, 27
- Space-filling curves and parallelisation - Jul 1, 4
- 2D and 3D Space-filling Curves - Jul 4 (intro and part I), Jul 8 (part III)

## Worksheets and Solutions

### Jupyter Notebook (formerly known as the IPython Notebook)

- If you want to use a local installation of IPython 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
- If you install Jupyter 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 Jupyter 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
- time, date, room:
**Wed, Oct 12**, 2016,**16.00-17.40**(**2501**, Physics Department, Rudolf-Mößbauer-Hörsaal)- note that the exam will start precisely on 16.00; please be in the exam room
**by 15.45**, at the latest!

- note that the exam will start precisely on 16.00; please be in the exam room
**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

- you may use one

## 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

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