Algorithms for Discrete Fourier Transform and Convolution

The main goal of this graduate-level textis 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.