Information Technology Reference
In-Depth Information
SPACE-TIME LOWER BOUNDS WITH PEBBLING
10.15 Let
A
be a
γ
-nice
n
×
n
matrix over a ring
R
for some 0
<γ<
1
/
2. Show that the
matrix-vector multiplication function
f
(
n
)
n
that maps the input
n
-tuple
x
to the output
n
-tuple
A
x
is
(
1,
n
2
+
n
,
n
,
γn
)
-independent.
10.16 Use Lemma
10.12.1
and the result of the previous problem to show that for almost
all
n
n
:
R
→R
A×
x
n
matrices
A
every straight-line program for the matrix-vector multiplication
function
f
(
n
)
A
×
n
n
over the ring
:
R
→R
R
requires space
S
and time
T
satisfying
×
x
the inequality
(
S
+
1
)
T
=Ω(
n
2
)
Furthermore, show that a straight-line program for matrix-vector multiplication can be
realized with space
S
=
3 and time
T
=
n
(
2
n
−
1
)
,thatis,with
(
S
+
1
)
T
=
O
(
n
2
)
10.17 Linear systems are described in Section
6.2.2
. A linear system of
n
equations in
n
unknowns
x
is defined by an
(
n
×
n
)
-coefficient matrix
A
and an
n
-vector
b
,as
suggested below:
A
x
=
b
(10.11)
The goal is to solve this equation for
x
.If
A
is non-singular, such a solution exists for
each vector
b
.Let
f
(
n
)
A
−
1
n
2
+
n
n
denote the
linear system solver function
that maps the matrix
A
and the vector
b
onto the solution
x
when the matrix-vector
multiplication is over the ring
:
R
→R
×
b
and
A
is non-singular.
Show that every pebbling strategy for every straight-line program to compute the linear
system solver function
f
(
n
)
A
−
1
R
n
2
n
2
over the ring
:
R
→R
R
for
n
even requires space
×
b
S
and time
T
satisfying the following inequality:
n
3
/
24
(
S
+
1
)
T
≥
Hint:
Would it be possible to violate the lower bound on
(
S
+
1
)
T
for matrix inversion
given in Problem
10.25
if a DAG for the linear system solver function can be pebbled
with
S
pebbles in too few steps?
10.18 Let
f
:
n
m
have
g
:
r
s
as a subfunction. Show that if
g
is
(
α
,
r
,
s
,
p
)
-
A
→A
A
→A
independent for
r
m
,thensois
f
. Show that, as a consequence, the
space
S
and time
T
needed to pebble the graph of a straight-line program for
f
satisfy
the following inequality:
≤
n
and
s
≤
α
(
S
+
1
)
T
≥
sp/
4
10.19 Show that if a function is
(
α
,
n
,
m
,
p
)
-independent, it is also
(
α
,
n
,
m
,
q
)
-independent
for
q
p
.
Hint:
Considerthesameset
V
of outputs in the two definitions.
≤
Search WWH ::
Custom Search