0.6 Winograd's short dft algorithms  (Page 5/11)

An important characteristic of the $D$ operator in the calculation of the DFT is its entries are either purely real orimaginary. The reduction of the $W$ vector by $(s^{(N-1)/2}-1)$ and $(s^{(N-1)/2}+1)$ separates the real and the imaginary constants. This is discussed in [link] , [link] . The number of multiplications for complex data is only twice those necessary forreal data, not four times.

Although this discussion has been on the calculation of the DFT, very similar results are true for the calculation ofconvolution and correlation, and these will be further developed in Algorithms for Data with Restrictions . The $A^{T}DA$ structure and the picture in [link] are the same for convolution. Algorithms and operation counts can be found in [link] , [link] , [link] .

The bilinear structure

The bilinear form introduced in [link] and the related linear form in [link] are very powerful descriptions of both the DFT and convolution.

Since [link] is a bilinear operation defined in terms of a second bilinear operator o , this formulation can be nested. Forexample if o is itself defined in terms of a second bilinear operator @, by

then [link] becomes

For convolution, if A represents the polynomial residue reduction modulo the cyclotomic polynomials, then $A$ is square (e.g. [link] and o represents multiplication of the residue polynomials modulo the cyclotomic polynomials. If $A$ represents the reduction modulo the cyclotomic polynomials plus the Toom-Cookreduction as was the case in the example of [link] , then $A$ is NxM and o is term-by- term simple scalar multiplication. In thiscase $AX$ can be thought of as a transform of $X$ and $C$ is the inverse transform. This is called a rectangular transform [link] because $A$ is rectangular. The transform requires only additions and convolution is done with $M$ multiplications. The other extreme is when $A$ represents reduction over the $N$ complex roots of $s^N-1$ . In this case $A$ is the DFT itself, as in the example of (43), and o is point by point complex multiplicationand C is the inverse DFT. A trivial case is where $A$ , $B$ and $C$ are identity operators and o is the cyclic convolution.

This very general and flexible bilinear formulation coupled with the idea of nesting in [link] gives a description of most forms of convolution.

Winograd's complexity theorems

Because Winograd's work [link] , [link] , [link] , [link] , [link] , [link] has been the foundation of the modern results in efficient convolution and DFT algorithms, it is worthwhile to look at histheoretical conclusions on optimal algorithms. Most of his results are stated in terms of polynomial multiplication as Polynomial Description of Signals: Equation 3 or [link] . The measure of computational complexity is usually the number of multiplications, and only certain multiplications arecounted. This must be understood in order not to misinterpret the results.

This section will simply give a statement of the pertinent results and will not attempt to derive or prove anything. A shortinterpretation of each theorem will be given to relate the result to the algorithms developed in this chapter. The indicated referencesshould be consulted for background and detail.