Arithmetic complexity of computations

Shmuel Winograd9780898711639, 0898711630

This monograph focuses on finding the minimum number of arithmetic operations needed to compute the solution to a system of bilinear forms, and on finding a better algorithm for such computations. The author concentrates on results applicable in the area of signal processing. Two reasons for this are: results applicable to signal processing are relatively new, and applications to problems of signal processing provide a good insight into complexity of computation.Included in this monograph are discussions of the complexity of computing the convolution, digital filtering and the discrete Fourier transform. A general background of basic results in the arithmetic complexity of computations is also discussed.