Seminar Schnelle Algorithmen (Seminar on fast algorithms)

Summer Term 2014
In this seminar we consider fast algorithms occurring in different fields of Numerical Mathematics.

Time: The seminar will be scheduled as a block seminar.

The seminar can be successfully completed if you give your own talk at the seminar successfully
and attend the talks of the other students in this seminar.

Preliminary meeting
The preliminary meeting to assign the topics of the seminar talks and the time schedule will be on Wednesday 23.04.2014, 12:30 at MN68.
If you would like to have your topic earlier, please come directly to my office.


Possible seminar topics are:

Talk 1: Discrete Fourier transform and circulant matrices

Talk 2: Fast Fourier transform: Radix-2 algorithm

Talk 3: Radix-4 algorithm and Split-Radix algorithm for the DFT

Talk 4: Chinese Remainder Theorem (CRT)

Talk 5: Fast polynomial multiplication and cyclic convolution with the CRT

Talk 6: The Rader algorithm for DFT(p)

Talk 7: The Bluestein algorithm for DFT(N)

Talk 8: Two-dimensional fast Fourier transform

Talk 9: Application: Fast trigonometric interpolation

Talk 10: Application: Fast numerical evaluation of Fourier transform and Fourier coefficients

(more topics if needed)

Literature:
[1] H. J. Nussbaumer: Fast Fourier transforms and convolution algorithms, Springer, 1982.
[2] R. Tolimieri, M. Ann, C. Lu: Algorithms for the discrete Fourier transform and convolution, Springer, 1989.
[3] C. van Loan: Computational frameworks for fast Fourier transform, SIAM Philadelphia, 1992.

General hints for seminar talks

1. Suitable handling of the topic:
What are the main ideas?
How to explain them by suitable examples?
What do the mathematical theorems tell us?
Organization of the talk: Introduction, organized main part, summary
A written summary of the talk (1-2 pages) should contain the main definitions, theorems and examples.
This summary should be provided to all auditors at the beginning of the talk.
Further written elaborations of the talk are not necessary.

2. Literature:
Please use the given literature. You can use further literature if needed
(for example for finding suitable examples, applications etc.)

3. Talk:
Time 75-90 minutes
clear arrangements on the blackboard
Speed and audibility of speech
possible usage of further media