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. This
approach is used by Tolimieri [4], [5], Egner [3],
Selesnick, Elliott [2] 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 C=WXC=WX which, for N=8N=8 is
C
(
0
)
C
(
1
)
C
(
2
)
C
(
3
)
C
(
4
)
C
(
5
)
C
(
6
)
C
(
7
)
=
W
0
W
0
W
0
W
0
W
0
W
0
W
0
W
0
W
0
W
1
W
2
W
3
W
4
W
5
W
6
W
7
W
0
W
2
W
4
W
6
W
8
W
10
W
12
W
14
W
0
W
3
W
6
W
9
W
12
W
15
W
18
W
21
W
0
W
4
W
8
W
12
W
16
W
20
W
24
W
28
W
0
W
5
W
10
W
15
W
20
W
25
W
30
W
35
W
0
W
6
W
12
W
18
W
24
W
30
W
36
W
42
W
0
W
7
W
14
W
21
W
28
W
35
W
42
W
49
x
(
0
)
x
(
1
)
x
(
2
)
x
(
3
)
x
(
4
)
x
(
5
)
x
(
6
)
x
(
7
)
C
(
0
)
C
(
1
)
C
(
2
)
C
(
3
)
C
(
4
)
C
(
5
)
C
(
6
)
C
(
7
)
=
W
0
W
0
W
0
W
0
W
0
W
0
W
0
W
0
W
0
W
1
W
2
W
3
W
4
W
5
W
6
W
7
W
0
W
2
W
4
W
6
W
8
W
10
W
12
W
14
W
0
W
3
W
6
W
9
W
12
W
15
W
18
W
21
W
0
W
4
W
8
W
12
W
16
W
20
W
24
W
28
W
0
W
5
W
10
W
15
W
20
W
25
W
30
W
35
W
0
W
6
W
12
W
18
W
24
W
30
W
36
W
42
W
0
W
7
W
14
W
21
W
28
W
35
W
42
W
49
x
(
0
)
x
(
1
)
x
(
2
)
x
(
3
)
x
(
4
)
x
(
5
)
x
(
6
)
x
(
7
)
(1)
which clearly requires N2=64N2=64 complex multiplications and N(N-1)N(N-1) additions.
A factorization of the DFT operator, WW, gives W=F1F2F3W=F1F2F3 and
C=F1F2F3XC=F1F2F3X or, expanded,
C
(
0
)
C
(
4
)
C
(
2
)
C
(
6
)
C
(
1
)
C
(
5
)
C
(
3
)
C
(
7
)
=
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
W
0
0
-
W
2
0
0
0
0
0
0
W
0
0
-
W
2
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
W
0
0
-
W
0
0
0
0
0
0
0
W
2
0
-
W
2
C
(
0
)
C
(
4
)
C
(
2
)
C
(
6
)
C
(
1
)
C
(
5
)
C
(
3
)
C
(
7
)
=
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
W
0
0
-
W
2
0
0
0
0
0
0
W
0
0
-
W
2
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
W
0
0
-
W
0
0
0
0
0
0
0
W
2
0
-
W
2
(2)
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
W
0
0
0
0
-
W
0
0
0
0
0
W
1
0
0
0
-
W
1
0
0
0
0
W
2
0
0
0
-
W
2
0
0
0
0
W
3
0
0
0
-
W
3
x
(
0
)
x
(
1
)
x
(
2
)
x
(
3
)
x
(
4
)
x
(
5
)
x
(
6
)
x
(
7
)
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
W
0
0
0
0
-
W
0
0
0
0
0
W
1
0
0
0
-
W
1
0
0
0
0
W
2
0
0
0
-
W
2
0
0
0
0
W
3
0
0
0
-
W
3
x
(
0
)
x
(
1
)
x
(
2
)
x
(
3
)
x
(
4
)
x
(
5
)
x
(
6
)
x
(
7
)
(3)
where the FiFi matrices are sparse. Note that each has 16 (or 2N2N) non-zero terms
and F2F2 and F3F3 have 8 (or NN) non-unity terms. If N=2MN=2M, then the number
of factors is log(N)=Mlog(N)=M.
In another form with the twiddle factors separated so as to count the complex
multiplications we have
C
(
0
)
C
(
4
)
C
(
2
)
C
(
6
)
C
(
1
)
C
(
5
)
C
(
3
)
C
(
7
)
=
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
C
(
0
)
C
(
4
)
C
(
2
)
C
(
6
)
C
(
1
)
C
(
5
)
C
(
3
)
C
(
7
)
=
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
-
1
(4)
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
W
0
0
0
0
0
0
0
0
0
W
2
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
W
0
0
0
0
0
0
0
0
0
W
2
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
-
1
0
0
0
0
0
0
1
0
-
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
-
1
0
0
0
0
0
0
1
0
-
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
W
0
0
0
0
0
0
0
0
0
W
2
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
W
0
0
0
0
0
0
0
0
0
W
2
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
-
1
0
0
0
0
0
0
1
0
-
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
-
1
0
0
0
0
0
0
1
0
-
1
(5)
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
W
0
0
0
0
0
0
0
0
0
W
1
0
0
0
0
0
0
0
0
W
2
0
0
0
0
0
0
0
0
W
3
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
1
0
0
0
-
1
0
0
0
0
1
0
0
0
-
1
0
0
0
0
1
0
0
0
-
1
0
0
0
0
1
0
0
0
-
1
x
(
0
)
x
(
1
)
x
(
2
)
x
(
3
)
x
(
4
)
x
(
5
)
x
(
6
)
x
(
7
)
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
W
0
0
0
0
0
0
0
0
0
W
1
0
0
0
0
0
0
0
0
W
2
0
0
0
0
0
0
0
0
W
3
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
1
0
0
0
-
1
0
0
0
0
1
0
0
0
-
1
0
0
0
0
1
0
0
0
-
1
0
0
0
0
1
0
0
0
-
1
x
(
0
)
x
(
1
)
x
(
2
)
x
(
3
)
x
(
4
)
x
(
5
)
x
(
6
)
x
(
7
)
(6)
which is in the form C=A1M1A2M2A3XC=A1M1A2M2A3X described by the index map.
A1A1, A2A2, and A3A3 each represents 8 additions, or, in general, NN additions.
M1M1 and M2M2 each represent 4 (or N/2N/2) 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 Nlog(N)Nlog(N) 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 [1].
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 [3].
-
Beard, James K. (2003). The FFT in the 21st Century: Eigenspace Processing. Boston: Kluwer.
-
Elliott, Douglas F. (Ed.). (1987). Handbook of Digital Signal Processing. [Chapter 7 on FFT by Elliott]. San Diego, CA: Academic Press.
-
Egner, Sebastian and Püschel, Markus. (2001). Automatic Generation of Fast Discrete Signal Transforms. IEEE Transactions on Signal Processing, 49(9), 1992–202.
-
Tolimieri, Richard and An, Myoung and Lu, Chao. (1989, 1997). Algorithms for Discrete Fourier Transform and Convolution. (second). New York: Springer-Verlag.
-
Tolimieri, Richard and An, Myoung and Lu, Chao. (1993, 1997). Mathematics of Multidimensional Fourier Transform Algorithms. (second). New York: Springer-Verlag.
"The Fast Fourier Transform (FFT) is a landmark algorithm used in fields ranging from signal processing to high-performance computing. First popularized by two American scientists in 1965, the […]"