Information Technology Reference
In-Depth Information
Obviously, when
n
=
2
d
the 2
n
-point DFT can be realized by the 2
n
-point FFT. The DAG
associated with this algorithm, shown in Fig.
11.11
for
d
=
4, contains three copies of the
FFT graph
F
(
2
d
)
.
We derive bounds on the computation and I/O time in the standard and I/O-limited
memory-hierarchy game needed for the convolution function using this straight-line program.
For the standard MHG, we invoke the lower bounds and an efficient algorithm for the FFT.
For the I/O-limited MHG, we derive new lower bounds based on those for two back-to-back
FFT graphs as well as upper bounds based on the I/O-limited pebbling algorithm given in
Theorem
11.5.4
for FFT graphs.
THEOREM
11.5.7
Let
G
(
n
)
convolve
be the graph of a straight-line program for the convolution of
two
n
-tuples using the convolution theorem,
n
=
2
d
.Let
G
(
n
)
convolve
be pebbled in the standard
MHG with the resource vector
p
.Let
s
l
=
j
=
1
p
j
and let
k
be the largest integer such that
s
k
≤
3
there is a pebbling of
G
(
n
)
convolve
n
.When
p
1
≥
for which the following bounds hold
simultaneously:
⎧
⎨
Θ(
n
log
n
)
l
=
1
Θ
n
log
n
log
s
l
−
1
2
T
(
L
)
l
(
p
,
F
(
d
)
)=
≤
l
≤
k
+
1
⎩
Θ(
n
)
k
+
2
≤
l
≤
L
Proof
The lower bound follows from Lemma
11.3.2
and Theorem
11.5.5
.Fromthefor-
mer, it is sufficient to derive lower bounds for a subgraph of a graph. Since
F
(
d
)
is contained
in
G
(
n
)
convolve
, the lower bound follows.
Figure 11.11
A DAG for the graph of the convolution theorem on
n
=
8inputs.
Search WWH ::
Custom Search