Multiplicative Complexity Convolution And The Dft

Multiplicative Complexity, Convolution, and the DFT

This book is intended to be a comprehensive reference to multiplicative com plexity theory as applied to digital signal processing computations. Although a few algorithms are included to illustrate the theory, I concentrated more on the develop ment of the theory itself. Howie Johnson's infectious enthusiasm for designing efficient DfT algorithms got me interested in this subject. I am grateful to Prof. Sid Burrus for encouraging and supporting me in this effort. I would also like to thank Henrik Sorensen and Doug Jones for many stimulating discussions. lowe a great debt to Shmuel Winograd, who, almost singlehandedly, provided most of the key theoretical results that led to this present work. His monograph, Arithmetic Complexity o/Computations, introduced me to the mechanism behind the proofs of theorems in multiplicative complexity. enabling me to return to his earlier papers and appreciate the elegance of his methods for deriving the theory. The second key work that influenced me was the paper by Louis Auslander and Winograd on multiplicative complexity of semilinear systems defined by polynomials. After reading this paper, it was clear to me that this theory could be applied to many impor tant computational problems. These influences can be easily discerned in the present work.

Multiplicative Complexity, Convolution, and the DFT

Algorithms for Discrete Fourier Transform and Convolution

This book is based on several courses taught during the years 1985-1989 at the City College of the City University of New York and at Fudan Univer sity, Shanghai, China, in the summer of 1986. 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. However, it was soon apparent that the scope of the course had to be greatly expanded. For researchers interested in the design of new algorithms, a deeper understanding of the basic mathematical concepts underlying algorithm design was essential. At the same time, a large gap remained between the statement of an algorithm and the implementation of the algorithm. The main goal of this text is to describe tools that can serve both of these needs. In fact, it is our belief that certain mathematical ideas provide a natural language and culture for understanding, unifying and implementing a wide range of digital signal processing (DSP) algo rithms. This belief is reinforced by the complex and time-consuming effort required to write code for recently available parallel and vector machines. A significant part of this text is devoted to establishing rules and procedures that reduce and at times automate this task.