The definition of the DFT in Multidimensional Index Mapping: Equation 1 can written as a matrixvector
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(N1)N(N1) 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) nonzero terms
and F2F2 and F3F3 have 8 (or NN) nonunity 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].
"The Fast Fourier Transform (FFT) is a landmark algorithm used in fields ranging from signal processing to highperformance computing. First popularized by two American scientists in 1965, the […]"