Algorithms of Scientific Computing - Summer 10

From Sccswiki
Jump to navigation Jump to search
Term
Summer 10
Lecturer
Tobias Neckel, Dirk Pflüger
Time and Place
Tuesdays 10:15-11:45 and Thursdays 10:15-11:45, room MI 02.07.023, starting 20/04/2010
Tutorial: Wednesdays 10:15-11:45, room MI 02.07.023, starting 28/04/2010
Audience
Modul IN2001
Informatik Diplom: Wahlpflichtfach im Bereich theoretische Informatik
Informatik Master: Wahlfach im Fachgebiet "Algorithmen und Wissenschaftliches Rechnen"
Informatik Master: Elective topic, subject area "Algorithms and Scientific Computing"
Informatik/Wirtschaftsinformatik Bachelor: Wahlfach
Studierende der Mathematik/Technomathematik, Natur- und Ingenieurwissenschaften
Tutorials
Kristof Unterweger, Gerrit Buse
Exam
2nd exam (~90 minutes), Monday, October 11, 9:00, MI HS 02; auxiliary material: 2 pages (=1 sheet) DIN A4 (handwritten, no photocopies, no printed versions)
Semesterwochenstunden / ECTS Credits
6 SWS (4V + 2Ü) / 8 Credits
TUMonline
{{{tumonline}}}


What's ASC (former AWR) 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.

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

News

  • On Thursday, July 8, we have our chair's annual excursion. You are invited (or should we say urged? ;-) ) to come and join!
  • Practicals in winter term 2010/11
    • Bachelor-Praktikum (PSE) Molekulardynamik (Meeting Friday, 16. July, 10.00 Uhr)
    • Masterpraktikum Scientific Computing - High Performance Computing (Meeting: Friday, 16. July, 10:45 Uhr)
    • Masterpraktikum Scientific Computing - Advanced C++ Programming (Meeting: Wednesday, 14. July, 16:00 Uhr)
  • Exam review, see above

Material

Introduction

Fast Fourier Transform

Hierarchical Methods


Space-Filling Curves


Worksheets and Solutions

Number Topic Worksheet Date Solution
1 Discrete Fourier Transform Worksheet 1 28.4. Solution 1 pallas1.mws

( also in html: pallas1.html) pallas2.mws ( also in html: pallas2.html)

2 Discrete Fourier Transform Worksheet 2 5.5. Solution 2

uebung2.mw ( also in html: uebung2.html)

3 Fast Poisson Solver Worksheet 3a 7.5. Solution 3a
3 Discrete Cosine Transform Worksheet 3 12.5. Solution 3
4 Hierarchical Surplus Worksheet 4 26.5. Solution 4

solution4.mw ( also in html: solution4.html)

5 Hierarchical Basis/Norms of Functions Worksheet 5 2.6. Solution 5

solution5.mw ( also in html: solution5.html)

6 Multidimensional Quadrature Worksheet 6 9.6.

Solution 6, empty template as spreadsheet document

7 Combination Technique Worksheet 7 22.6.

Solution 7 solution7.mw ( also in html: solution7.html)

8 Generating Systems Worksheet 8 24.6.

Solution 8 solution8_gensys.mw ( also in html: solution8.html)

9 Orthogonality Worksheet 9 30.6.

Solution 9

10 Grammars for Space-filling Curves Worksheet 10 6.7. Solution 10

regularPeano.mw ( also in html: regularPeano.html) meanderPeano.mw ( also in html: meanderPeano.html) realturtle_hilbert.mw ( also in html: realturtle_hilbert.html) realturtle_hilbert1.mw ( also in html: realturtle_hilbert1.html) realturtle_hilbert2.mw ( also in html: realturtle_hilbert2.html)

11 Arithmetization of Space-filling Curves Worksheet 11 14.7.

Solution 11 peano_switch.mws ( also in html: peano_switch.html) kochturtle.mw ( also in html: kochturtle.html)


Literature

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

Hierarchical Methods and Sparse Grids

Space-filling Curves:

Retrieved from "https://www5.in.tum.de/wiki/index.php?title=Algorithms_of_Scientific_Computing_-_Summer_10&oldid=7238"