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.

Contenu

1. Introduction.- 1.1. An Overview of Multiplicative Complexity.- 1.2. Why Count Only Multiplications and Divisions?.- 1.3. Organization.- 2. Multiplicative Complexity of Linear and Bilinear Systems.- 2.1. Historical Perspective.- 2.2. Definitions and Basic Results.- 2.3. Semilinear Systems.- 2.4. Quadratic and Bilinear Systems.- 2.4.1. Properties of Quadratic Systems.- 2.4.2. Bilinear Systems and Noncommutative Algorithms.- 2.4.3. Direct Products and Direct Sums of Systems.- 2.5. Summary of Chapter 2.- 3. Convolution and Polynomial Multiplication.- 3.1. Aperiodic Convolution/Polynomial Multiplication.- 3.2. Polynomial Multiplication Modulo an Irreducible Polynomial.- 3.3. Polynomial Multiplication Modulo a General Polynomial.- 3.4. Products of a Fixed Polynomial with Several Polynomials.- 3.4.1. Equivalent Systems and Row Reduced Forms.- 3.4.2. Reduction and Inflation Mappings.- 3.4.3. Equivalence of Products with a Fixed Polynomial.- 3.4.4. Multiplicative Complexity Results.- 3.5. Products with Several Fixed Polynomials in the Same Ring.- 3.6. Products with Several Fixed Polynomials in Different Rings.- 3.7. Multivariate Polynomial Multiplication.- 3.7.1. Polynomial Products in Two Variables.- 3.7.2. Multidimensional Cyclic Convolution.- 3.8. Summary of Chapter 3.- 4. Constrained Polynomial Multiplication.- 4.1. General Input Constraints.- 4.2. Multiplication by a Symmetric Polynomial.- 4.3. Multiplication by an Antisymmetric Polynomial.- 4.4. Products of Two Symmetric Polynomials.- 4.5. Polynomial Multiplication with Restricted Outputs.- 4.5.1. Decimation of Outputs.- 4.5.2. Other Output Restrictions.- 4.6. Summary of Chapter 4.- 5. Multiplicative Complexity of Discrete Fourier Transform.- 5.1. The Discrete Fourier Transform.- 5.2. Prime Lengths.- 5.2.1. Rader's Permutation.- 5.2.2. Multiplicative Complexity.- 5.3. Powers of Prime Lengths.- 5.4. Power-of-Two Lengths.- 5.5. Arbitrary Lengths.- 5.6. DFTs with Complex-Valued Inputs.- 5.7. Multidimensional DFTs.- 5.8. Summary of Chapter 5.- 6. Restricted and Constrained DFTs.- 6.1. Restricting DFT Outputs to One Point.- 6.2. Constraining DFT Inputs to One Point.- 6.3. DFTs with Symmetric Inputs.- 6.4. Discrete Hartley Transform.- 6.5. Discrete Cosine Transform.- 6.6. Summary of Chapter 6.- Appendix A. Cyclotomic Polynomials and Their Properties.- Appendix B. Complexities of Multidimensional Cyclic Convolutions.- Appendix C. Programs for Computing Multiplicative Complexity.- Appendix D. Tabulated Complexities of the One-Dimensional DFT.- Problems.