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
-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