tailieunhanh - Digital Signal Processing Handbook P9

Complexity theory of computation attempts to determine how “inherently” difficult are certain tasks. For example, how inherently complex is the task of computing an inner product of two vectors of length N? Certainly one can compute the inner product N=1 xj yj by computing the j N products xj yj and then summing them. But can one compute this inner product with fewer than N multiplications? The answer is no, but the proof of this assertion is no trivial matter. One first abstracts | Feig E. Complexity Theory of Transforms in Signal Processing Digital Signal Processing Handbook Ed. Vijay K. Madisetti and Douglas B. Williams Boca Raton CRC Press LLC 1999 1999 by CRC Press LLC Complexity Theory of Transforms in Signal Processing Ephraim Feig IBM Corporation . Watson Research Center Introduction One-Dimensional DFTs Multidimensional DFTs One-Dimensional DCTs Multidimensional DCTs Nonstandard Models and Problems References Introduction Complexity theory of computation attempts to determine how inherently difficult are certain tasks. For example how inherently complex is the task of computing an inner product of two vectors of length N Certainly one can compute the inner product j i xjyj by computing the N products xjyj and then summing them. But can one compute this inner product with fewer than N multiplications The answer is no but the proof of this assertion is no trivial matter. One first abstracts and defines the notions of the algorithm and its components such as addition and multiplication then a theorem is proven that any algorithm for computing a bilinear form which uses K multiplications can be transformed to a quadratic algorithm some algorithm of a very special form which uses no divisions and whose multiplications only compute quadratic forms which uses at most K multiplications 20 and finally a proof by induction on the length N of the summands in the inner product is made to obtain the lower bound result 6 13 22 25 . We will not present the details here we just want to let the reader know that the process for even proving what seems to be an intuitive result is quite complex. Consider next the more complex task of computing the product of an N point vector by an M x N matrix. This corresponds to the task of computing M separate inner products of N-point vectors. It is tempting to jump to the conclusion that this task requires MN multiplications. But we should not jump to fast conclusions. First the M .