Arithmetic Complexity of Computations

✍ Scribed by Shmuel Winograd

• Publisher: Society for Industrial Mathematics
• Year: 1987
• Tongue: English
• Leaves: 100
• Series: CBMS-NSF Regional Conference Series in Applied Mathematics
• Category: Library

✦ Synopsis

Focuses on finding the minimum number of arithmetic operations needed to perform the computation and on finding a better algorithm when improvement is possible. The author concentrates on that class of problems concerned with computing a system of bilinear forms.

Results that lead to applications in the area of signal processing are emphasized, since (1) even a modest reduction in the execution time of signal processing problems could have practical significance; (2) results in this area are relatively new and are scattered in journal articles; and (3) this emphasis indicates the flavor of complexity of computation.

✦ Table of Contents

Arithmetic Complexity of Computations......Page 1
Contents......Page 4
CHAPTER I Introduction......Page 7
CHAPTER II Three Examples......Page 9
CHAPTER III General Background......Page 13
CHAPTER IV Product of Polynomials......Page 31
CHAPTER V FIR Filters......Page 45
CHAPTER VI Product of Polynomials Modulo a Polynomial......Page 63
CHAPTER VII Cyclic Convolution and Discrete Fourier Transform......Page 77
Bibliography......Page 99