Fast Fourier Transform: Why? How? and the Course 842

The Discrete Fourier Transform (DFT) is one of the most important operators in computational mathematics.The DFT operator acts on the n-dimenional Hilbert Space of complex valued functions on the group of integers modulo-n. It becames very useful in the last century due to the Cooley–Tukey algorithm that computes this transform in order of nlog(n) operations. In the lecture we will elaborate on an idea–due to Auslander and Tolimieri–which establishes this algorithm as a logical consequence of the Stone–von Neumann theorem in the representation theory of the Heisenberg group.

Another, silent, goal of the lecture is to let you know about the course 842 that I will give for Math/CS/EE/Biology/Chemistry…. undergrad/grad students in the 2011 Spring semester. The main topic that I will describe in the course is Group Symmetry Theory (known also as Representation Theory) from the point of view of concrete applications to Signal Processing, Communication, Structuring of Molecules, and Diagonalization of natural operators that appear in various applied problems.

An important feature of the course 842 will be active participation of students via reading and presenting scientific problems and solutions, programing several of the algorithms that we will talk about, etc.

I will assume familiarity with basic notions of linear algebra.