Information Technology Reference
In-Depth Information
LEMMA
10.5.3
The matrix multiplication function
f
(
n
)
2
n
2
n
2
over the ring
A×B
:
R
→R
R
has
a
w
(
u
,
v
)
-flow, where
w
(
u
,
v
)
satisfies the following lower bound:
(
2
n
2
u
)
2
/
4
n
2
)
/
2
w
(
u
,
v
)
≥
(
v
−
−
Proof
Let
C
=
AB
be the product of
n
n
matrices
A
and
B
. We establish this result by
using characteristic functions to identify the outputs in
C
in
Y
1
and the inputs in
A
and
B
in
X
1
, as indicated below. Here the indices
i
and
j
range over 0
×
≤
i
,
j
≤
n
−
1:
σ
i
,
j
=
1
α
i
,
j
=
1
Y
1
0ot er ise
c
i
,
j
∈
X
1
0ot er ise
a
i
,
j
∈
β
i
,
j
=
1
X
1
0ot er ise
b
i
,
j
∈
Let
A
,
B
,and
C
denote the matrices
[
α
i
,
j
]
,
[
β
i
,
j
]
,and
[
σ
i
,
j
]
, respectively. Denote by
|
A
|
,
|
B
|
|
C
|
|
A
|
+
|
B
|
=
,and
the number of 1s in the three corresponding matrices. Note that
|
X
1
|
|
C
|
=
|
Y
1
|
and
.
The
k
th
n
×
n
cyclic permutation matrix
P
(
k
)
is the
n
×
n
identity matrix in which
the rows are rotated cyclically
k
−
×
3matrixis
P
(
3
)
.
1 times. For example, the following 3
⎡
⎣
⎤
⎦
010
001
100
Let
D
be an
n
×
n
matrix. The matrix
P
(
k
)
D
consists of the rows of
D
shifted cyclically
down
k
1 places. Similarly, the matrix
DP
(
k
)
consists of the columns of
D
shifted
cyclically left
k
−
1places.
Let
B
(
k
)
be the matrix
B
obtained by multiplication on the left by
A
=
P
(
k
)
. Sim-
ilarly, let
A
(
k
)
be the matrix
A
obtained by multiplication on the right by
B
=
P
(
k
)
.
Then, a 1 value for the
(
i
,
j
)
entry in
A
(
k
)
and
B
(
k
)
identifies a variable in
X
1
that is
mapped to an output variable of
C
through its multiplication by
P
(
k
)
.
Let
D
and
E
be
n
−
×
n
matrices whose entries are drawn from the set
{
0, 1
}
.Wedenote
by
D
∩
E
the
n
×
n
matrix whose
(
i
,
j
)
entry is 1 if
d
i
,
j
=
e
i
,
j
=
1. Similarly, let
D
∪
E
be the
n
n
matrix whose
(
i
,
j
)
entry is 1 if either
d
i
,
j
=
1or
e
i
,
j
=
1. The following
identity applies:
×
|
D
∪
E
|
+
|
D
∩
E
|
=
|
D
|
+
|
E
|
(10.3)
|
D
∪
E
|≤
n
2
for
n
×
n
matrices, the following inequality holds:
Since
n
2
|
D
∩
E
|≥|
D
|
|
E
|−
+
(10.4)
Also, since
|
D
∩
E
|≥
0wehave
|
D
|
+
|
E
|≥|
D
∪
E
|
(10.5)
The
w
(
u
,
v
)
-flow of matrix multiplication is large if for some choice of
r
or
s
|
C
∩
A
(
r
)
|
or
|
C
∩
B
(
s
)
|
is large. This follows because choosing
A
to be the
r
th cyclic permutation
Search WWH ::
Custom Search