Seminar Schnelle Algorithmen (Seminar on fast algorithms)

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.

The preliminary meeting to assign the topics of the seminar talks and the time schedule will be on Wednesday

If you would like to have your topic earlier, please come directly to my office.

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.

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

Research Group for Mathematical Signal and Image Processing

Institute for Numerical and Applied Mathematics

Lotzestr. 16-18

37083 Göttingen