# Algorithms for Scientific Computing - Summer 16

Term
Summer 2016
Lecturer
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

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

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.

## Worksheets and Solutions

Number Topic Worksheet Tutorial Solution
1 Discrete Fourier Transform I Worksheet 1Python Introduction Apr. 13 Ws1 solution Ws1 solution Notebook
2 Discrete Fourier Transform II Worksheet 2 Worksheet 2 Notebook template Apr. 20 Ws2 solution Ws2 solution Notebook Ws2 Ex2 solution code
- - - Apr. 27 tutorial cancelled due to student assembly
3 Discrete Cosine Transform Worksheet 3 Worksheet 3 Notebook template Template Exercise 1 May 4 Ws3 solution Ws3 solution code
4 Discrete Fourier Transform III Worksheet 4 May 11 Ws4 solution Ws4 solution Notebook
5 Numerical Quadrature 1D Worksheet 5 Worksheet 5 Notebook template May 18 Ws5 solution Notebook (no ex4) Lecture Ex solution Notebook
6 Haar Wavelet Worksheet 6 Worksheet 6 Notebook template May 25 Ws5 Ex4 solution Notebook Ws6 solution Notebook Ws6 Ex2 Solution
7 Function Approximation and Wavelet Worksheet 7 Jun. 1
8 Multi-dimensional Quadrature Worksheet 8 Worksheet 8 template Jun. 8
9 Multi-dimensional hierarchization and adaptive sparse grids Worksheet 9 Worksheet 9 code template Jun. 15 Ws9 code solution Ws9 Ex2 solution
10 Grammars for space-filling curves Worksheet 10 Worksheet 10 code template Notebook template Jun. 22 Ws10 solution Ws10 solution code Ws10 solution Notebook
11 Arithmetization of space-filling curves Worksheet 11 code template Notebook template Jun. 29 Ws11 solution Ws11 solution code Ws11 solution Notebook
12 Refinement trees and space-filling curves Worksheet 12, Worksheet 12 Notebook template Jul. 6 Ws12 solution Ws12 solution Notebook
13 Q&A session (exercises) Jul. 13
14 Q&A session (lecture) Jul. 20

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

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: