Transforms1
The development of fast algorithms usually consists of using spe-
cial properties of the algorithm of interest to remove redundant or
unnecessary operations of a direct implementation. Because of the
periodicity, symmetries, and orthogonality of the basis functions
and the special relationship with convolution, the discrete Fourier
transform (DFT) has enormous capacity for improvement of its
arithmetic efficiency.
There are four main approaches to formulating efficient DFT [50]
algorithms. The first two break a DFT into multiple shorter ones.
This is done in Multidimensional Index Mapping (Chapter 3) by
using an index map and in Polynomial Description of Signals
(Chapter 4) by polynomial reduction. The third is Factoring the
Signal Processing Operators (Chapter 6) which factors the DFT
operator (matrix) into sparse factors. The DFT as Convolution or
Filtering (Chapter 5) develops a method which converts a prime-
length DFT into cyclic convolution. Still another approach is in-
teresting where, for certain cases, the evaluation of the DFT can be
1This content is available online at <http://cnx.org/content/m16325/1.10/>.
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
5
CHAPTER 2. INTRODUCTION: FAST
6
FOURIER TRANSFORMS
posed recursively as evaluating a DFT in terms of two half-length
DFTs which are each in turn evaluated by a quarter-length DFT
and so on.
The very important computational complexity theorems of Wino-
grad are stated and briefly discussed in Winograd’s Short DFT
Algorithms (Chapter 7). The specific details and evaluations of
the Cooley-Tukey FFT and Split-Radix FFT are given in The
Cooley-Tukey Fast Fourier Transform Algorithm (Chapter 9), and
PFA and WFTA are covered in The Prime Factor and Winograd
Fourier Transform Algorithms (Chapter 10). A short discussion of
high speed convolution is given in Convolution Algorithms (Chap-
ter 13), both for its own importance, and its theoretical connection
to the DFT. We also present the chirp, Goertzel, QFT, NTT, SR-
FFT, Approx FFT, Autogen, and programs to implement some of
these.
Ivan Selesnick gives a short introduction in Winograd’s Short DFT
Algorithms (Chapter 7) to using Winograd’s techniques to give
a highly structured development of short prime length FFTs and
describes a program that will automaticlly write these programs.
Markus Pueschel presents his “Algebraic Signal Processing" in
DFT and FFT: An Algebraic View (Chapter 8) on describing the
various FFT algorithms. And Steven Johnson describes the FFTW
(Fastest Fourier Transform in the West) in Implementing FFTs in
Practice (Chapter 11)
The organization of the book represents the various approaches to
understanding the FFT and to obtaining efficient computer pro-
grams. It also shows the intimate relationship between theory and
implementation that can be used to real advantage. The disparity
in material devoted to the various approaches represent the tastes
of this author, not any intrinsic differences in value.
A fairly long list of references is given but it is impossible to be
truly complete. I have referenced the work that I have used and
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
7
that I am aware of. The collection of computer programs is also
somewhat idiosyncratic. They are in Matlab and Fortran because
that is what I have used over the years. They also are written pri-
marily for their educational value although some are quite efficient.
There is excellent content in the Connexions book by Doug Jones
[206].
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
CHAPTER 2. INTRODUCTION: FAST
8
FOURIER TRANSFORMS
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>