NFFT logo

The Nonequispaced FFT
and its Applications

A mini course at Helsinki University of Technology,
23.-27.02.2009 (3 credit pts)

A part of the Special Year in Numerics 2008-2009
of the Finnish Mathematical Society

The Fast Fourier Transform (FFT) has been named one of the
"10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century''.

Despite a wealth of successful applications, one of the major disadvantages remains that the classical FFT is limited to evenly distributed nodes. It is therefore natural to ask for an efficient generalisation to arbitrary node configurations. This mini course is to introduce the NFFT algorithm which provides such a generalisation, as well as a range of related algorithms and applications.

Lecturers:

Jens Keiner (University of Lübeck), Stefan Kunis (Chemnitz University of Technology),
and Antje Vollrath (University of Lübeck).

The aim of this course is threefold:

  • to provide a comprehensive understanding of the maths behind the NFFT,
  • to explain related algorithms and various applications,
  • and to introduce the NFFT software library which is a free to download

In a series of five lectures, the following topics will be covered:

  • Classical Fourier analysis and trigonometric series
  • Discrete and fast Fourier transforms (DFT, FFT)
  • Algorithms and error estimates for the nonequispaced FFT
  • Classical orthogonal polynomials and their associated functions
  • Algorithms for fast polynomial transforms
  • Fourier analysis on the sphere S2
  • Nonequispaced fast S2 Fourier transform and applications
  • Fourier analysis on the rotation group SO(3)
  • Nonequispaced fast SO(3) Fourier transform and applications
  • High dimensional problems, sparse grids and FFTs
  • Inversion of the nonequispaced FFT and compressed sensing
The course will require a working knowledge of basics of Fourier analysis and - recommended but not required - orthogonal polynomials. It is intended for a general audience extending from undergraduate and graduate students to anybody with a general interest in applied and numerical mathematics, and in particular, Fourier analysis.


Lectures will take place at Helsinki University of Technology
on 23.2.2009 at 14:15-16:00 in room U322,
on 24.2.2009 at 12:15-14:00 in lecture hall F (that is, room U141),
on 25.2.2009 at 12:15-14:00 in room U345,
on 26.2.2009 at 14:15-16:00 in room U322,
on 27.2.2009 at 10:15-12:00 in room U322
Lecture notes can be found here or in a printer friendly version.


Computer practice sessions will be at Helsinki University of Technology
Exercise 1 on Tuesday 24.2.2009 at 14:30-16:00 in room Y339b, Solution 1,
Exercise 2 on Wednesday 25.2.2009 at 14:30-16:00 in room Y338c, Solution 2.

A bug in the NFFT library that causes problems with the second exercise has been fixed. The NFFT homepage will soon be updated.
Contact information:
Professor Timo Eirola (Timo.Eirola@tkk.fi),
Assistant Kurt Baarman (Kurt.Baarman@tkk.fi)