Multiplicative complexity, convolution, and the DFT
Author(s)
Bibliographic Information
Multiplicative complexity, convolution, and the DFT
Springer, c1988
- : us
- : gw
Available at 14 libraries
  Aomori
  Iwate
  Miyagi
  Akita
  Yamagata
  Fukushima
  Ibaraki
  Tochigi
  Gunma
  Saitama
  Chiba
  Tokyo
  Kanagawa
  Niigata
  Toyama
  Ishikawa
  Fukui
  Yamanashi
  Nagano
  Gifu
  Shizuoka
  Aichi
  Mie
  Shiga
  Kyoto
  Osaka
  Hyogo
  Nara
  Wakayama
  Tottori
  Shimane
  Okayama
  Hiroshima
  Yamaguchi
  Tokushima
  Kagawa
  Ehime
  Kochi
  Fukuoka
  Saga
  Nagasaki
  Kumamoto
  Oita
  Miyazaki
  Kagoshima
  Okinawa
  Korea
  China
  Thailand
  United Kingdom
  Germany
  Switzerland
  France
  Belgium
  Netherlands
  Sweden
  Norway
  United States of America
-
Library, Research Institute for Mathematical Sciences, Kyoto University数研
: usHEI||21||188053668
Note
Originally presented as the author's thesis (Ph. D.)--Rice University, under title: Applications of multiplicative complexity theory to convolution and the discrete Fourier transform
Bibliography: p. 147-150
Includes index
Description and Table of Contents
Description
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.
Table of Contents
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.
by "Nielsen BookData"