<< Chapter < Page | Chapter >> Page > |
A third approach to removing redundancy in an algorithm is to express the algorithm as an operator and then factor that operator into sparse factors. Thisapproach is used by Tolimieri [link] , [link] , Egner [link] , Selesnick, Elliott [link] and others. It is presented in a more general form in DFT and FFT: An Algebraic View The operators may be in the form of a matrix or a tensor operator.
The definition of the DFT in Multidimensional Index Mapping: Equation 1 can written as a matrix-vector operation by which, for is
which clearly requires complex multiplications and additions. A factorization of the DFT operator, , gives and or, expanded,
where the matrices are sparse. Note that each has 16 (or ) non-zero terms and and have 8 (or ) non-unity terms. If , then the number of factors is . In another form with the twiddle factors separated so as to count the complexmultiplications we have
which is in the form described by the index map. , , and each represents 8 additions, or, in general, additions. and each represent 4 (or ) multiplications.
This is a very interesting result showing that implementing the DFT using the factored form requires considerably less arithmetic than the single factor definition.Indeed, the form of the formula that Cooley and Tukey derived showing that the amount of arithmetic required by the FFT is on the order of can be seen from the factored operator formulation.
Much of the theory of the FFT can be developed using operator factoring and it has some advantages for implementation of parallel and vector computer architectures. The eigenspace approach is somewhat of the same type [link] .
A very general structure for all kinds of algorithms can be generalized from the approach of operators and operator decomposition. This is developed as“Algebraic Theory of Signal Processing" discussed in the module DFT and FFT: An Algebraic View by Püschel and others [link] .
Notification Switch
Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?