Difference between revisions of "Algorithms for Scientific Computing - Summer 18"

From Sccswiki
Jump to navigation Jump to search
Line 79: Line 79:
=== Space-Filling Curves ===
=== Space-Filling Curves ===
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss18/sfc_orders.pdf From Quadtrees to Space-Filling Order] - July 7 (octrees), 14
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss18/sfc_orders.pdf From Quadtrees to Space-Filling Order] - Jun 25
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss14/Hilbert_Plotter.ipynb Python Notebook script for Hilbert curve grammar]
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss14/Hilbert_Plotter.ipynb Python Notebook script for Hilbert curve grammar]
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sfc_mapping.pdf Hilbert Curve (Construction, Definition, and Arithmetisation)] - July 14, 17
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sfc_mapping.pdf Hilbert Curve (Construction, Definition, and Arithmetisation)] - Jun 25, 29
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss14/sfc_hilbert_arith.ipynb Python Notebook script for Hilbert curve arithmetization]
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss14/sfc_hilbert_arith.ipynb Python Notebook script for Hilbert curve arithmetization]
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sfc_3Dcurves.pdf 2D and 3D Space-filling Curves] - Jul 17, 21
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sfc_3Dcurves.pdf 2D and 3D Space-filling Curves] - Jul  
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sfc_parallel.pdf Space-filling curves and parallelisation] - Jul 24
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sfc_parallel.pdf Space-filling curves and parallelisation] - Jul  
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss14/sfc_hilbert_plotter_adp.ipynb Python Notebook script Hilbert curve on a quadtree]
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss14/sfc_hilbert_plotter_adp.ipynb Python Notebook script Hilbert curve on a quadtree]

Revision as of 10:56, 25 June 2018

Summer 2018
Univ.-Prof. Dr. Michael Bader
Time and Place
Lecture: Mon 14-16 and Fri 10-12, MI HS 2 (first lecture on Mon, Apr 9)
Tutorial: Wed 10-12 MI 00.13.009A (first tutorial on Wed, Apr 11)
see module description (IN2001) in TUMonline
Jean-Matthieu Gallard, M.Sc., Michael Obersteiner, M.Sc.
written exams (Jul 26 and, pres., Oct 4)
Semesterwochenstunden / ECTS Credits
6 SWS (4V + 2Ü) / 8 Credits

News & Announcements

  • No tutorial on Wednesday 25.04, the tutorial will take place on Friday 27.04 in the usual lecture room (MI HS 2).

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 2017 will be linked.

Fast Fourier Transform

Hierarchical Methods

Sparse Grids

Space-Filling Curves

Worksheets and Solutions

Number Topic Worksheet Tutorial Solution
1 Discrete Fourier Transform I Python Introduction Worksheet 1 Worksheet 1 Notebook template Apr. 11

Ws1 solution Ws1 solution Notebook

2 Discrete Fourier Transform II Worksheet 2 Worksheet 2 Notebook template Apr. 18

Ws2 solution Ws2 solution Notebook Ws2 Ex2 solution code

3 Discrete Cosine Transform

Worksheet 3 Worksheet 3 Notebook template Template Exercise 2

Apr. 27

Ws3 solution Ws3 solution code

4 Discrete Fourier Transform III Worksheet 4 May 02

Ws4 solution

5 1D Classification Worksheet 5 Worksheet 5 Notebook template May 09

Ws5 solution Notebook

6 Quadrature Worksheet 6 Worksheet 6 Notebook template May 16 Ws6 solution Notebook
7 Hierarchical Basis Worksheet 7 May 23

Ws7 Ex1-2 solution Notebook Ws7 Ex3 solution

8 + 9 Wavelets Worksheet 8 Worksheet 8 Notebook template May 30

Ws8 solution

10 Multi-dimensional Quadrature Worksheet 10Worksheet 10 notebook Worksheet 10 spreadsheet Jun. 13

Ws10 solution

11 Multi-dimensional hierarchization and adaptive sparse grids Worksheet 11 Worksheet 11 code template Jun. 20

Jupyter Notebook


  • type: written exam, working time: 120 min
  • 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

First Exam: Thursday, Jul 26

  • Time: 16.00-18.00 - Please make sure to be in the lecture hall by 15.45, as the exam will start precisely at 16.00.
  • Place: MW 1801 (Ernst-Schmidt-Hörsaal)

Second Exam

  • currently scheduled for Thursday, Oct 4 (preliminary!)

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:

Hierarchical Methods and Sparse Grids


Space-filling Curves:

Background Material Concerning Scientific and High Performance Computing