Information Technology Reference
In-Depth Information
|
Y
1
|
/
2
|R|
|Y
1
|/
2
values, or
F
n
is
of these columns are set to zero, the
outputs have
(
2,
n
,
n
,
n/
2
)
-independent.
The space-time lower bound stated below follows from Corollary
10.4.1
.
THEOREM
10.5.5
To pebble any straight-line program for the
n
-point DFT over a commutative
ring
R
requires space
S
and time
T
satisfying the following:
n
2
/
16
(
S
+
1
)
T
≥
when
n
is even. The FFT graph on
n
=
2
d
inputs can be pebbled with space
S
and time
T
satisfying the upper bound
4
n
2
/
(
S
T
≤
−
log
2
n
)+
n
log
2
S
Thus,
(
S
+
1
)
T
=
O
(
n
2
)
when
2
log
2
n
(
n/
log
2
n
)+log
2
n
.
Proof
This lower bound can be achieved up to a constant factor by a pebbling strategy
for the FFT algorithm, as we now show. Denote with
F
(
d
)
the
n
-point FFT graph (it has
n
inputs),
n
=
2
d
.(Figure .
6.1
,
6.7
,and
10.8
show 4-point, 16-point, and 32-point
FFT graphs.) Inputs are at level 0 and outputs are at level
d
. WeinvokeLemma
6.7.4
to decompose
F
(
d
)
≤
S
≤
e
into a set of top 2
d−e
2
e
-point FFT graphs above the
at level
d
−
F
(
e
)
t
,
j
{
|
≤
j
≤
2
e
}
,andasetof2
e
2
d−e
-point FFT graphs below the split,
split,
1
F
(
d−e
)
b
,
j
2
e
{
|
≤
j
≤
}
, as suggested in Fig.
10.8
. In this figure the vertices and edges have
been grouped together as recognizable FFT graphs and surrounded by shaded boxes. The
edges between boxes identify vertices that are common to pairs of FFT subgraphs.
1
F
(
2
)
t
,1
F
(
2
)
t
,2
F
(
2
)
t
,3
F
(
2
)
t
,4
F
(
2
)
t
,5
F
(
2
)
t
,6
F
(
2
)
t
,7
F
(
2
)
t
,8
F
(
3
)
b
,1
F
(
3
)
b
,2
F
(
3
)
b
,3
F
(
3
)
b
,4
Figure 10.8
Decomposition of the FFT graph
F
(
5
)
into four copies of
F
(
3
)
and eight copies
of
F
(
2
)
. Edges between bottom and top sub-FFT graphs are fictitious; they identify overlapping
vertices between sub-FFT graphs.
Search WWH ::
Custom Search