Information Technology Reference
In-Depth Information
This result provides a lower bound on the space and time for matrix multiplication. The
upper bound cited below is obtained by another hybrid algorithm that mixes a branching
program for the standard algorithm with one for table lookup.
THEOREM
10.13.4
There is an integer
n
0
>
0
such that for
n>n
0
the space
S
and time
T
needed to compute the matrix multiplication function
f
(
n
)
2
n
2
n
2
A×B
:
R
→R
over the ring
R
using
a general branching program satisfies the inequality:
γ
3
16
n
6
log
2
|R|
ST
2
≥
for some
0
<γ<
1
/
2
when
T
n
2
. This lower bound can be achieved up to a multiplicative
factor of
O
(log
n
)
for space in the range
Ω(log
n
+log
≥
|A|
)
≤
S
≤
O
(
n
log
|A|
)
.
Proof
The lower bound follows from Theorem
10.11.1
and Lemma
10.13.3
by letting
a
=
γ
2
n
4
/
4
T
since this value of
a
satisfies the two conditions
a
≤
τ
(
ma/
2
T
)=
,
γn
ma/
4
T
and
a
n
2
.
At the extreme of large space, namely
S
=
O
(
n
2
)
, the upper bound follows from
a branching program for table lookup that has one level for each of the 2
n
2
variables in
the matrices
A
and
B
and the fact that there are
≤
2
n
2
when
T
≥
2
n
2
|R|
pairsofsuchmatricesoverthe
2
n
2
ring
R
. Consequently, the branching program has at most
O
(
|R|
)
vertices and space
O
(
n
2
log
)
.Ituses
O
(
n
2
)
steps.
At the extreme of small space, namely
S
=Ω(log
n
+log
|R|
)
, we use a branching
program for the standard matrix multiplication algorithm that forms
n
2
inner products of
rows and columns of the two matrices. As discussed in the proof of Theorem
10.13.3
,a
branching program can be constructed to form the inner product of two
n
-tuples that has
Θ(
n
|A|
)
and time
O
(
n
)
. Concatenating
n
2
of
these programs, one for each of the
n
2
entries in the product matrix, we have a branching
program with space
Ω(log
n
+log
2
)
vertices; that is, space
Ω(log
n
+log
|R|
|A|
)
and time
O
(
n
3
)
.
To fill in the gap between these extremes, the method applied in Theorem
10.13.3
can
be used, as the reader can demonstrate. (See Problem
10.40
.)
|A|
10.13.5 Matrix Inversion
As an intermediate step to deriving a space-time product lower bound on matrix inversion, we
derive a lower bound for the product of three
n
n
matrices. This is done by first deriving
an alternate representation for this product in terms of the Kronecker product of two matrices.
Kronecker products are defined in Section
10.12
.
×
LEMMA
10.13.4
Let
A
,
B
,
C
,and
D
be
n×n
matrices over a commutative ring. The following
two equations define the same set of mappings from entries of
A
,
B
,and
C
to entries in
D
:
D
=
ABC
E
=(
A
C
T
)
B
⊗
where
B
and
E
are
n
2
1
column vectors obtained by concatenating the transposes of the rows of
the matrices
B
and
D
, respectively.
×
Search WWH ::
Custom Search