Algorithms for Scientific Computing - Summer 18

Term

Summer 2018

Lecturer

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)

Audience

see module description (IN2001) in TUMonline

Tutorials

Jean-Matthieu Gallard, M.Sc., Michael Obersteiner, M.Sc.

Exam

written exams (Jul 26 and, pres., Oct 4)

Semesterwochenstunden / ECTS Credits

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

TUMonline

https://campus.tum.de/tumonline/wbLv.wbShowLVDetail?pStpSpNr=950349332

---

News & Announcements

• The repeat exam review will take place on Tuesday, Oct 16 11:00 - 11:30 in room 02.05.043
• The exam review will take place on Monday, Aug 20, 10:00 am in room 02.07.023
• A Q&A session for exam preparation will be offered on Friday, Jul 20, 10.15 in lecture hall MI HS 2
• 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.

• Introduction - Apr 9

Fast Fourier Transform

• Discrete Fourier Transform (DFT) - Apr 9, 13
• Fast Fourier Transform (FFT) - Apr 13, 16
  • 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 20, 30
  • 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 23, 30
  • matlab central: jpeg compression
  • an embarrassingly simple simple JPEG-simulator (Java program)
  • The Discrete Cosine Transform by Gilbert Strang (SIAM Review 41(1), p. 135-147) - the article discusses the connection between the Discrete Cosine Transform and eigenvectors of familiar matrices in Scientific Computing
• Discrete Sine Transform - May 4
• Fast Poisson Solvers - May 4

Hierarchical Methods

• Towards Data Mining: Approximation and Classification - May 7
• Archimedes' Quadrature 1D - May 11
• Hierarchical Basis in 1D - May 14, 18
• Wavelets - May 18, 25, 28
  • Wavelet transforms versus Fourier transforms by Gilbert Strang (Bull. Amer. Math. Soc. 28 (1993) p.288-305)
• Finite Element Methods (parts I & II) - Jun 1
  • additional material: Maple worksheet for Poisson-FEM (and as PDF)

Sparse Grids

• Archimedes Quadrature in d Dimensions - Jun 4,8
  • further material (from an older course): Maple worksheet for d-Dim. archimedes (and as PDF)
• Hierarchical Basis in d Dimensions - Jun 8 (intro), 11,15,18 (parts I, II and III)
  • "separate proof" for estimating surpluses (outlook)
• Data Structures for Sparse Grids - Jun 18,22
  • Slide 18 supplement: transform to matrix form
• Finite Element Methods (part III shortly, part IV not covered) - Jun 22

Space-Filling Curves

• From Quadtrees to Space-Filling Order - Jun 25
  • Python script (for Jupyter Notebook) for Hilbert curve grammar
• Hilbert Curve (Construction, Definition, and Arithmetisation) - Jun 29, Jul 2
  • Python script (for Jupyter Notebook) for Hilbert curve arithmetization
• 2D and 3D Space-filling Curves - Jul 2,6 (parts I+II), Jul 9 (part III)
• Space-filling curves and parallelisation - Jul 9
  • Python Notebook script Hilbert curve on a quadtree

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 Worksheet 11 include files	Jun. 20	Ws11 code solution Ws11 Ex2 solution Ws11 Ex3 solution
12	Grammars for space-filling curves	Worksheet 12 Worksheet 12 code template Notebook template	Jun. 27	Ws12 solution Ws12 solution code Ws12 solution Notebook
13	Arithmetization of space-filling curves	Worksheet 13 code template Notebook template	Jul. 04	Ws13 solution Ws13 solution code Ws13 solution Notebook
14	Refinement trees and space-filling curves	Worksheet 14, Worksheet 14 Notebook template	Jul. 11	Ws14 solution Ws14 solution Notebook
-	Mock Exam	Mock exam	-	Mock exam solution

Jupyter Notebook

• If you want to use a local installation of Jupyter 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 (solutions use the python3 version).

Exams

• 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
• Exam preparation: a Q&A session will be offered on Friday, Jul 20, 10.15 in lecture hall MI HS 2

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)
• Review: Monday, Aug 20, 10:00 am in room 02.07.023

Second Exam: Thursday, Oct 4

• Time: 8.00-10.00 - Please make sure to be in the lecture hall by 7.45, as the exam will start precisely at 8.00.
• Place: Interim 1

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

• Interactive Educational Modules in Scientific Computing accompanying the book Scientific Computing, An Introductory Survey by Michael T. Heath (may be useful to repeat some fundamentals in Scientific Computing; also contains a module on the Fourier Transform)
• 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)