Scientific Computing

This module illustrates a recursive fast Fourier transform (FFT) algorithm for computing the discrete Fourier transform of a complex vector. Although an iterative implementation of the FFT algorithm is usually more efficient than a recursive implementation, the latter more clearly illustrates the divide-and-conquer nature of the algorithm.

The user chooses the size of the input vector from the menu of small
powers of 2. For each size, a default input vector is provided, but
the user can type in different initial values by clicking *Edit Input
Vector*. Input values may be scaled to guarantee that intermediate
steps and results of the algorithm will fit in the display boxes.
Clicking *OK* in the input editor returns to the main display.
With the initial vector selected, the user then steps through the
recursive FFT algorithm by repeatedly clicking either *Next* or
the currently highlighted step. Each step of the algorithm is
graphically depicted in the main display, with corresponding values of
the indices and twiddle factors displayed at the lower right. Red
lines indicate copying of entries from one vector to another. Blue
lines indicate a multiplication/addition step, where the second of two
numbers is multiplied by the appropriate twiddle factor and the numbers
are added together. At any point during or after the execution of the
algorithm, the user may click *Reset* to start over from the first
step of the FFT.

The arguments passed to the FFT procedure are ** x**,

**Reference:** Michael T. Heath, *Scientific Computing,
An Introductory Survey*, 2nd edition, McGraw-Hill, New York,
2002. See Section 12.2, especially Algorithm 12.1.

**Developers:** Evan VanderZee and Michael Heath