Information Technology Reference
In-Depth Information
10.13.4 Matrix Multiplication*
The space-time lower-bound argument for matrix multiplication in the branching program
model uses ideas similar to those used for matrix-vector multiplication.
LEMMA
10.13.3
The matrix multiplication function
f
(
n
)
2
n
2
n
2
A×B
:
R
→R
R
over the ring
is
(
1, 1, 1,
γ/
4,
τ
)
-distinguishable for some
0
<γ<
1
/
2
,where
τ
(
b
)=
γn
b/
2
.
Proof
Consider the subfunction of
f
(
n
)
A×B
obtained by choosing
A
and
B
from the set of
n
nγ
-nice matrices. By Lemma
10.11.2
, a lower bound on the space-time product for
this subfunction provides a lower bound to the matrix multiplication function.
Consider some
a
×
2
n
2
n
2
≤
selected inputs and some
b
≤
selected outputs such that
τ
(
b
)
;thatis,
(
a/γn
)
2
a
≤
≤
b/
2. The outputs correspond to entries of the product matrix
C
=
A
B
.Letrow
i
of
C
be a
heavy row
if at least
γn
of the
a
selected inputs are in
row
i
of
A
. Similarly, let column
j
of
C
be a
heavy column
if at least
γn
of the
a
selected
inputs are in column
j
of
B
. A row or column of
C
is
light
otherwise. (See Fig.
10.21
.)
There are at most
a/γn
heavy rows and
a/γn
heavy columns of
C
. We now show that
either a) at least
b/
4 of the selected outputs fall into light rows of
C
or b) at least
b/
4of
the selected outputs fall into light columns of
C
. Suppose not. Then both statements are
false and less than
b/
4 of the selected outputs fall into light rows and less than
b/
4ofthe
selected outputs fall into light columns of
C
. It follows that at least 3
b/
4oftheselected
outputs fall into heavy rows. Of these at most
(
a/γn
)
2
fall into heavy columns, since this is
the maximum number of entries of
C
that could be in both heavy rows and columns. The
remaining selected outputs in these rows (of which there are less than
b/
4) fall into light
columns. However, because the entries in each row fall into either heavy or light columns,
the number of selected outputs that are i
n he
avy rows is less than
(
a/γn
)
2
+
b/
4. But this
is less than 3
b/
4since
a
×
τ
(
b
)=
γn
b/
2, contradicting the stated hypothesis.
Without loss of generality, assume that b holds. (If not, a holds and at least
b/
4 selected
outputs fall into light rows of
C
or into light columns of the transpose
C
T
.) Represent the
≤
C
A
=
B
=
Figure 10.21
Identification of heavy rows and columns of matrices.
Search WWH ::
Custom Search