PHYSICAL MATHEMATICS SEMINAR

TOPIC:	STRETCHING THE BOUNDARIES OF COMPUTATION:
	SELF-OPTIMIZING FFTS AND SEMI-ANALYTICAL
	APPROACHES IN ELECTROMAGNETISM

SPEAKER:  STEVEN G. JOHNSON
	  Division of Engineering and Applied Sciences
	  Harvard University

ABSTRACT:

The recent surge of interest in the electromagnetism of nanostructured
media, such as the periodic metamaterials known as photonic crystals, has
invalidated many classical analytic approaches and led to increasing
demands for computing power.  In this talk, we discuss developments in two
approaches to meeting such demands: semi-analytical methods, which dodge
the bullet of brute force, and self-optimizing codes, which attack the
speed problem head-on.

Some of the most challenging computational problems for brute-force
methods involve the study of small effects in complex systems, such as the
consequences of imperfections in a waveguide.  The classical approach to
such questions involves perturbation theory: given the solution for an
idealized system, compute an analytical correction for small
perturbations.  Unfortunately, existing perturbative approaches,
originally developed for the simple systems that were solvable decades
ago, can fail completely in nano-structured media, due to the field
discontinuities and rapid material variations in even the ideal system.
Thus, it turns out that there are simple, general analytical questions in
classical electromagnetism whose answer was unknown.  We answer them, and
in doing so extend many classical approaches, from perturbation theory to
coupled-mode equations, to cover the new nano-structured regimes.

The other approach to large-scale computation demands has been the
development of optimized software that extracts every ounce of speed from
the available hardware.  In particular, we focus on the case of the fast
Fourier transform (FFT), an algorithm of particular importance in
electromagnetism as well as in many other fields.  We describe the
development of FFTW, an FFT library that solves the problem of portable
near-optimal performance by a combination of self-optimization, generation
of computational kernels by a domain-specific "compiler", and
"cache-oblivious" recursive algorithms.  Unfortunately, we found that the
approach that was prevalent until the early 1990's, that of minimizing the
number of arithmetic operations, turns out to be largely irrelevant.
Instead, we show how, in the latest release of FFTW, a wide variety of FFT
algorithms can be expressed by a small number of composable recursive
steps, allowing the FFTW runtime system to pick the algorithm that is
fastest on any given hardware; the chosen algorithms are apparently
unpredictable by simple heuristics.

DATE:		TUESDAY, FEBRUARY 17, 2004

TIME:		2:30 PM

LOCATION:	Building 2, Room 338


Refreshments at 3:30 PM in Building 2, Room 349.

Massachusetts Institute of Technology, Department of Mathematics
Cambridge, MA  02139