Time: October 8, 2009, 1100-1125 hours
Place: Erskine 415
Speaker: Thomas Steinke

Title:
Long multiplication is too long, but complex numbers are too complex

Abstract:
Multiplying 1000-digit numbers takes a long time, even on a
computer. However, if you take the Fourier transform of the numbers,
then it becomes much easier. This is the basis of the fastest
multiplication algorithms.

Unfortunately, computers cannot represent complex numbers exactly;
doing a Fourier transform introduces small errors into the
calculation. How can we recover an exact answer in the face of these
errors?

By working with sets rather than individual complex numbers, rounding
errors can be kept in check. The Sch\"onhage-Strassen algorithm and
the fast Fourier transform will be explained.  A novel approach to the
Sch\"onhage-Strassen algorithm using containment sets will be
discussed. This 20-minute talk is aimed at a general mathematical
audience with a basic understanding of algorithms.