Heideman M.T. Multiplicative Complexity, Convolution, and the DFT

Springer, 1988. — 162.This book is intended to be a comprehensive reference to multiplicative complexity theory as applied to digital signal processing computations. Although a few algorithms are included to illustrate the theory, I concentrated more on the development 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.
I owe 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 important computational problems. These influences can be easily discerned in the present work.
I have attempted to include proofs of all the results in this book. This should make the book more self-contained, so that the reader can follow the proofs in the book itself, without needing to refer to papers from journals. On the other hand, it should be possible for a reader to skip over the proofs if the results are all that is desired.Multiplicative Complexity of Linear and Bilinear Systems
Convolution and Polynomial Multiplication
Constrained Polynomial Multiplication
Multiplicative Complexity of Discrete Fourier Transform
Restricted and Constrained DFTs
A: Cyclotomic Polynomials and Their Properties
B: Complexities of Multidimensional Cyclic Convolutions
C: Programs for Computing Multiplicative Complexity
D: Tabulated Complexities of the One-Dimensional DFT