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 Entry 4, Entry 5, Egner Entry 3,
Selesnick, Elliott Entry 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
