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