Scientific Computing

This module shows how padding a sequence to make it have length a
power of 2 affects the resulting DFT of the sequence. An
implementation of full mixed-radix FFT can compute the DFT of a
sequence of arbitrary length. The algorithm becomes less efficient,
though, when the sequence length has large prime factors. When the
sequence length is a prime number, FFT is no better than computing the
DFT by matrix multiplication, which takes
*O*(*n*^{2})^{k} for some integer *k*, it makes sense to try
adding extra values to a shorter sequence to make a new sequence that
has length a power of 2. This module demonstrates several options for
choosing the extra padding values that extend a short sequence.

The user begins by choosing a number of basic mesh points *n*,
the length of the initial sequence. The user then selects whether
values for the basic mesh points will be taken from a source function
or generated randomly. When points come from a function, the user may
choose a specific function *f* from the menu provided; the point
values are *f*(0)*f*(1/64)*f*(2/64)*f*((*n*−1)/64)*Change Values* generates a new set of point
values, each in the range *Zeros* method gives all additional points the value 0. The
*Constant Extension* method gives all additional points the same
value as the last point in the basic sequence. *Linear to Zero*
chooses values from a linear interpolation between the last point value
and 0. *Linear Periodic* uses instead a linear interpolation
between the last point value and the first point value. For both
options that involve linear interpolation, the right endpoint of the
linear function is considered to be beyond the last point value of the
sequence, at an imagined 65*th* point. Thus, the periodic option
avoids an artificial constant interval of length 1/64 in the continuous
linear interpolation of the values on the interval

The upper graph shows the full sequence of 64 values with blue dots,
and the lower graph shows (the first half of) the power spectrum of the
DFT of that sequence with red dots. When mesh point values are taken
from a source function, green dots in the upper graph show all 64
discrete samples from the function, and green dots in the lower graph
show the power spectrum of the DFT of that sequence for comparison.
The blue and red dots may obscure the green dots, particularly in the
upper graph, where the first *n* point values always coincide.

The power spectrum of a sequence of complex values is computed by
multiplying each value by its complex conjugate. For a sequence of
real values, the power spectrum of the DFT is symmetric, so only the
first half of the power spectrum need be displayed. The power spectrum
represents the amount of energy present at each frequency. The tick
labels on the horizontal axis show the wave numbers of selected
frequencies; higher wave numbers correspond to higher frequencies. As
the tick labels on the vertical axis suggest, the values of the power
spectrum are shown on a log base 2 scale, with all values less than
2^{−6} lying on the horizontal axis.

**Reference:** Michael T. Heath, *Scientific Computing,
An Introductory Survey*, 2nd edition, McGraw-Hill, New York,
2002. See Section 12.2.1 and Computer Problem 12.4 on page 509.

**Developers:** Evan VanderZee and Michael Heath