No label defined (Q4935973)

The fast Fourier transform (FFT) represents an important advancement in scientific and engineering computing. Up to now there exist some excellent monographs on FFT, e.g. those by \textit{C. F. Van Loan} [Computational frameworks for the fast Fourier transform, SIAM Philadelphia (1992; Zbl 0757.65154)] and by \textit{R. Tolimieri}, \textit{M. An} and \textit{C. Lu} [Algorithms for discrete Fourier transform and convolution, 2nd ed., Springer/New York (1997; Zbl 0894.65076)]. Hence one can not say that there is a ``gap between brief introductions in textbooks and intimidating treatments in the FFT literature''. The book under review presents an elementary approach to several sequential and parallel FFTs, but without usage of Kronecker products (i.e. tensor products of matrices) and stride permutations. It is a self-contained treatment with many figures and tables, as well as 25 algorithms in pseudo-code. This textbook is divided into 3 parts. The discrete Fourier transform is introduced briefly in Part I. Then Part II contains sequential FFTs, where their length is often a power of 2. Note that Algorithm 2.1 on p. 15 is a worse precomputation method of twiddle factors, since FFTs are very sensitive with respect to roundoff errors. But this book does not contain any hint of numerical stability. Selected applications of FFT are sketched. Part III deals with the main theme of this book, namely parallel FFTs on multiprocessor computers. Starting with data mappings to processors, distributed-memory multiprocessors are discussed next. The hypercube multiprocessor architecture is particularly considered. The authors present several parallel FFTs. Parallel versions of two-dimensional FFTs are also described. FFTs on a vector computer are not handled. This book will be useful for students as well as researchers in computer science and electrical engineering. It should be noted that this book contains several improprieties.