Information Technology Reference
In-Depth Information
modulo a prime
p
, a set that forms a finite field under addition and multiplication modulo
p
.
(See Problem
6.3
.)
In the next section we describe Strassen's algorithm, a straight-line program realizable by a
logarithmic-depth circuit of size
O
(
n
2
.
807
)
. This is not the final word on matrix multiplication,
however. Winograd and Coppersmith [
81
] have improved the bound to
O
(
n
2
.
38
)
.Despite
this progress, the smallest asymptotic bound on matrix multiplication remains unknown.
Since later in this chapter we design algorithms that make use of matrix multiplication,
it behooves us to make the following definition concerning the number of ring operations to
multiply two
n
×
n
matrices over a ring
R
.
DEFINITION
6.3.1
Let
K ≥
1
.Then
M
matrix
(
n
,
K
)
is the size of the smallest circuit of depth
K
log
2
n
over a commutative ring
R
for the multiplication of two
n
×
n
matrices.
The following assumptions on the rate of growth of
M
matrix
(
n
,
K
)
with
n
make subse-
quent analysis easier. They are satisfied by Strassen's algorithm.
ASSUMPTION
6.3.1
We assume that for all
c
satisfying
0
≤ c ≤
1
and
n ≥
1
,
c
2
M
matrix
(
n
,
K
)
M
matrix
(
cn
,
K
)
≤
ASSUMPTION
6.3.2
We assume there exists an integer
n
0
>
0
such that, for
n ≥ n
0
,
2
n
2
≤
M
matrix
(
n
,
K
)
6.3.1 Strassen's Algorithm
Strassen [
319
] has developed a fast algorithm for multiplying two square matrices over a com-
mutative ring
R
. This algorithm makes use of the additive inverse of ring elements to reduce
the total number of operations performed.
Let
n
be even. Given two
n
×
n
matrices,
A
and
B
, we write them and their product
C
as 2
×
2 matrices whose components are
(
n/
2
)
×
(
n/
2
)
matrices:
C
=
uv
wx
=
A
B
=
ab
cd
ef
gh
×
×
Using the standard algorithm, we can form
C
with eight multiplications and four additions
of
(
n/
2
)
(
n/
2
)
matrices. Strassen's algorithm exchanges one of these multiplications for
10 such additions. Since one multiplication of two
(
n/
2
)
×
(
n/
2
)
matrices is much more
costly than an addition of two such matrices, a large reduction in the number of operations is
obtained. We now derive Strassen's algorithm.
Let
D
be the the 4
×
×
4 matrix shown below whose entries are
(
n/
2
)
×
(
n/
2
)
matrices.
(Thus,
D
is a 2
n
×
2
n
matrix.)
⎡
⎣
⎤
⎦
ab
00
cd
00
00
ab
00
cd
D
=
Search WWH ::
Custom Search