Information Technology Reference
In-Depth Information
Proof
The lower bound follows from Theorem
11.3.1
and Theorem
10.5.5
. We show that
the upper bounds can be achieved on
F
(
d
)
under the I/O limitation simultaneously for
1
L
.
The pebbling strategy meeting the lower bounds is based on that used in the proof of
Theorem
10.5.5
to pebble
F
(
d
)
using
S
≤
l
≤
2
d
+
1 pebbles in the red pebble game. The
number of level-1 pebble placements used in that pebbling is given in the statement of
Theorem
10.5.5
. A level-2 I/O operation occurs once on each of the 2
d
outputs and 2
d−e
times on each of the 2
d
≤
inputs of the bottom FFT subgraphs, for a total of 2
d
(
2
d−e
+
1
)
times.
The pebbling for the
L
-level MHG is patterned after the aforementioned pebbling for
the red pebble game, which is based on the decomposition of Lemma
6.7.4
.(SeeFig.
11.9
.)
Let
e
be the largest integer such that
S
2
e
+
d
≥
−
e
. Pebble the binary subtrees on
inputs in the 2
e
bottom subgraphs
F
(
d−e
)
2
d−e
b
,
m
as follows: On an input vertex level-
L
pebbles are replaced by pebbles at all levels down to and including the first level. Then level-
1 pebbles are advanced on the subtrees in the order that minimizes the number of level-1
pebbles in the red pebble game. It may be necessary to use pebbles at all levels to make these
advances; however, each vertex in a subtree (of which there are 2
d−e
+
1
1) experiences at
most two transitions at each level in the hierarchy. In addition, each vertex in a bottom
tree is pebbled once with a level-1 pebble in a computation step. Therefore, the number of
level-
l
transitions on vertices in the subtrees is at most 2
d
+
1
(
2
d−e
+
1
−
−
1
)
for 2
≤
l
≤
L
,
since this pebbling of 2
e
subtrees is repeated 2
d−e
times.
Once the inputs to a given subgraph
F
(
e
)
t
,
p
have been pebbled, the subgraph itself is
pebbled in the manner indicated in Theorem
11.5.5
,using
O
(
e
2
e
/
log
s
l−
1
)
pebbles at
each level
l
for 2
subgraphs
F
(
e
)
L
. Since this is done for each of the 2
d−e
t
,
p
,it
follows that on the top FFT subgraphs a total of
O
(
e
2
d
/
log
s
l−
1
)
level-
l
transitions occur,
2
≤
l
≤
L
.Inaddition,eachvertexinagraph
F
(
e
)
≤
l
≤
is pebbled once with a level-1 pebble
t
,
p
in a computation step.
It follows that at most
)=
O
2
d
(
2
d−e
+
1
e
2
d
log
s
l−
1
T
(
L
)
l
(
p
,
F
(
d
)
,
P
−
1
)+
level-
l
I/O operations occur for 2
≤
l
≤
L
,aswellas
T
(
L
)
1
(
p
,
F
(
d
)
,
)=
O
(
2
d
(
2
d−e
+
1
1
)+
e
2
d
)
P
−
computation steps. It is left to the reader to verify that 2
e
<
2
e
+
d
−
e
≤
S<
2
e
+
1
+
d
−
e
−
≤
42
e
when
e
+
1
≥
log
d
(this is implied by
S
≥
2
d
), from which the result follows.
1
11.5.4 Convolution
The convolution function
f
(
n
,
m
)
:
R
n
+
m
R
n
+
m−
1
over a commutative ring
→
R
(see
conv
Section
6.7.4
)mapsan
n
-tuple
a
and an
m
-tuple
b
onto an
(
n
+
m
−
1
)
-tuple
c
and is
denoted
c
=
a
b
. An efficient straight-line program for the convolution is described in
Section
6.7.4
that uses the convolution theorem (Theorem
6.7.2
) and the FFT algorithm.
The convolution theorem in terms of the 2
n
-point DFT and its inverse is
⊗
b
=
F
−
1
a
⊗
2
n
(
F
2
n
(
a
)
×
F
2
n
(
b
))
Search WWH ::
Custom Search