Multiplicative Complexity, Convolution, and the DFT - Heideman, Michael T.

. .

Résumé :
This book introduces multiplicative complexity theory and applies it to the computation of discrete convolutions and the discrete Fourier transform. A mathematical framework is established that enables the multiplicative complexity of many common bilinear systems to be determined. Semilinear systems are introduced as a means of determining the multiplicative complexity of the discrete Fourier transform. Complexity results are derived for other discrete transforms such as the cosine and Hartley transforms. Complete proofs of all the major results are included - the book is essentially self-contained. Many examples are provided to demonstrate the application of the theory.

Sommaire:
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.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.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.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.6. Summary of Chapter 4.- 5. Multiplicative Complexity of Discrete Fourier Transform.- 5.1. The Discrete Fourier Transform.- 5.2. Prime Lengths.- 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. Complexitiesof Multidimensional Cyclic Convolutions.- Appendix C. Programs for Computing Multiplicative Complexity.- Appendix D. Tabulated Complexities of the One-Dimensional DFT.- Problems.