Following an introduction to the basis of the fast Fourier transform
(FFT), this book focuses on the implementation details on FFT for
parallel computers. FFT is an efficient implementation of the discrete
Fourier transform (DFT), and is widely used for many applications in
engineering, science, and mathematics. Presenting many algorithms in
pseudo-code and a complexity analysis, this book offers a valuable
reference guide for graduate students, engineers, and scientists in the
field who wish to apply FFT to large-scale problems.
Parallel computation is becoming indispensable in solving the
large-scale problems increasingly arising in a wide range of
applications. The performance of parallel supercomputers is steadily
improving, and it is expected that a massively parallel system with
hundreds of thousands of compute nodes equipped with multi-core
processors and accelerators will be available in the near future.
Accordingly, the book also provides up-to-date computational techniques
relevant to the FFT in state-of-the-art parallel computers.
Following the introductory chapter, Chapter 2 introduces readers to the
DFT and the basic idea of the FFT. Chapter 3 explains mixed-radix FFT
algorithms, while Chapter 4 describes split-radix FFT algorithms.
Chapter 5 explains multi-dimensional FFT algorithms, Chapter 6 presents
high-performance FFT algorithms, and Chapter 7 addresses parallel FFT
algorithms for shared-memory parallel computers. In closing, Chapter 8
describes parallel FFT algorithms for distributed-memory parallel
computers.