Information Technology Reference
In-Depth Information
Proof
Let
C
=
AB
be the product of
n
n
matrices
A
and
B
. Consider any set
X
0
of
input variables (entries of
A
and
B
)andanyset
Y
1
of output variables (entries of
C
)such
that
×
|
X
0
|
+
|
Y
1
|
=
n
.Theoutputsin
Y
1
fall into at most
|
Y
1
|
columns of
C
and the inputs
in
X
0
fall into at most
columns of
A
contain only variables in
X
1
. Fix the entries in
B
so that it forms a permutation matrix that
permutes the columns of
A
containing only elements in
X
1
onto columns of
C
containing
elements of
Y
1
. (We are free to make the best assignment of variables in
B
,whetherin
X
0
or
X
1
.) It follows that each output variable in
Y
1
is assigned to an input variable of
A
in
X
1
by this permutation. Thus these output variables are free to assume
|
X
0
|
columns of
A
. It follows that at least
n
−|
X
0
|
|R|
|Y
1
|
different values.
|R|
|Y
1
|−
1
, it follows that
f
(
n
)
A×B
is
(
1, 2
n
2
,
n
2
,
n
)
-independent.
Since this is more than
As this result illustrates, for any set of
y
1
outputs of the matrix multiplication function and
any set of
x
0
of its inputs satisfying
x
0
+
y
1
p
, there is some assignment to these inputs such
that there is a large flow of information from the complementary set of inputs,
X
1
,toanyset
y
1
of its outputs.
≤
10.4.2 The Lower-Bound Method in the Basic Pebble Game
The following theorem provides a lower bound on the exchange of space for time. Its proof
uses a variant of the pigeonhole principle. Since the pebbling of vertices is assumed to occur
sequentially, time is divided into intervals in which the number of output vertices pebbled,
b
,is
chosen to be a small multiple of the number of pebbles,
S
, used in pebbling. The pigeonhole
principle is used to show that a large number of inputs must be pebbled in each interval.
In particular, we show that if the number of inputs pebbled inside an interval is small, the
number of inputs outside the interval is large enough that there is a large flow from the inputs
outside the interval to the outputs inside it. However, the flow cannot be any larger than can
be supported by the number,
S
, of vertices carrying pebbles just before the interval. Thus, the
number of input variables outside the interval is small, which implies that the number inside is
large. That is, many inputs must be pebbled within each interval. Multiplying by the number
of intervals in which
b
outputs are pebbled provides the lower bound.
THEOREM
10.4.1
Let
f
:
A
n
m
have an
w
(
u
,
v
)
-flow and let it be realized by a straight-
→A
r
s
line program over a basis
{
h
:
A
→A
|
r
,
s
≥
1
}
. For arbitrary
b
≤
m
, every pebbling of
every DAG for
f
requires space
S
and time
T
satisfying the inequality
T
≥
m/b
(
n
−
d
)
where
d
is the largest integer such that
w
(
d
,
b
)
S
.
Proof
Assume that
G
=(
V
,
E
)
is pebbled with
S
≤
≥
1 pebbles in
T
≥
1steps. Let
T
I
≤
T
be the number of times that input vertices are pebbled. (This is generally more
than the number of input variables.)
Given a pebbling of
G
with
S
pebbles, group the consecutive pebbling steps into in-
tervals, the first
m/b
of which contain
b
pebbled outputs and one of which contains
m
−
)
pebbled outputs.
Consider an arbitrary interval
b
(
m/b
in which
b
outputs are pebbled. Let
Y
1
be these outputs
and let
x
0
and
x
1
be the number of inputs pebbled inside and outside the interval, respec-
tively. By definition, there is an assignment to the
x
0
inputs such that that the
b
=
I
|
Y
1
|
Search WWH ::
Custom Search