Information Technology Reference
In-Depth Information
property that
S
+
1 or more inputs cannot remain unpebbled since
S
+
1outputsare
pebbled?
10.28 Use the result of the previous problem to show that to pebble an
n
-superconcentrator
with
S
pebbles in time
T
requires
S
and
T
to satisfy the following inequality:
n
2
2
Hint:
As in the proof of Theorem
10.4.1
, divide time up into consecutive intervals.
Choose the intervals so that each has the same number of outputs pebbled during it.
Apply the results of the previous problem to obtain a lower bound on the sum of the
number of input and output vertices that are pebbled during the interval.
(
S
+
1
)
T
≥
10.29 Show that the pebbling of two
n
-input back-to-back FFT graphs requires space and
time that satisfy
S
2
T
=Ω(
n
3
)
and that this lower bound can be achieved up to a
multiplicative factor.
Hint:
From the proof of Lemma
10.5.4
it follows that to pebble any 2
S
outputs with
S
pebbles at least
n
S
+
1 inputs must be pebbled because if fewer inputs need be
pebbled the outputs can have more values than is possible for the FFT.
−
APPLICATIONS OF THE GRIGORIEV LOWER BOUND
10.30 Show that there is a pebbling for a straight-line program for the cyclic shift func-
tion
f
(
n
)
cyclic
n
+
log
n
→B
n
examined in Section
10.5.2
for which
(
S
+
1
)
T
=
:
B
O
(
n
2
log
n
)
.
Hint:
Pebble the graph of the circuit described in Section
2.5.1
. Construct a circuit for
f
(
n
)
cyclic
that produces each output with
O
(
n
log
n
)
gates.
10.31 Show that the binary addition function
f
(
n
)
add
(see Section
2.7
) can be realized by a
straight-line program using space and time satisfying
ST
=
O
(
n
)
.
10.32 Derive upper and lower bounds on the product
(
S
+
1
)
T
for pebblings of circuits for
the squaring function
f
(
n
)
square
that are within a factor of
O
(log
2
n
)
of one another.
10.33 Derive good upper and lower bounds on the product
(
S
+
1
)
T
for pebblings of circuits
for the reciprocal function
f
(
n
)
recip
.
10.34 In Section
6.5.3
a straight-line algorithm is given to invert an
n
n
triangular matrix.
Construct another straight-line algorithm based on it that can be pebbled with
O
(
n
)
pebbles to produce outputs by columns in
O
(
n
3
)
steps under the assumption that the
standard matrix multiplication algorithm is used for the matrix multiplication steps.
Hint:
To produce outputs of a triangular matrix
T
by columns using the algorithm of
Fig.
6.5
, it is necessary to read the elements of
T
2,1
by rows and produce the outputs of
T
−
1
×
2,2
by rows. Consider modifying this algorithm to generate the elements of the latter
matrix first by rows and then by columns.
Search WWH ::
Custom Search