Algorithms for Discrete Fourier Transform and Convolution

It was originally our intention to present to a mixed audience of electrical engineers, mathematicians and computer scientists at the graduate level a collection of algorithms that would serve to represent the vast array of algorithms designed over the last twenty years for computing the finite Fourier transform (FFT) and finite convolution. The main goal of this graduate-level text is to provide a language for understanding, unifying , and implementing a wide variety of algorithms for dgital signal processing -- in particular, to provide ruls and procedures that can simplify or even automate the task of writing code for the newest parallel and vector machines. It thus bridges the gap between digital signal processing algorithms and their implementation on a variety of computing platforms. The mathematical concept of tensor product is a recurring theme throughout the book: tensor product factors have a direct interpretation on on many vector and parallel computers and tensor product idetities can be matched to machine implementation. These formulations also highlight the data flow, which is is especially important on supercomputers, where data flow may be the factor limiting the efficiency of a computation. Because of its importance in many appications, much of the discussion centers on algorithms related to the finite Fourier transform and to multiplicative FFT algorithms; other topics covered include convolution algorithms and prime-factor algorithms. This second edition has been revised and brought up to date throughout.