Information Technology Reference
In-Depth Information
Then the product of the vector
[
e
,
g
,
f
,
h
]
T
with
D
is the following sum of seven column
vectors.
⎡
⎤
⎡
⎤
⎡
⎤
⎡
⎤
⎡
⎤
⎡
⎤
⎡
⎤
⎡
⎤
u
w
v
x
P
1
0
0
P
1
0
P
2
0
−
0
0
P
3
P
3
P
4
P
4
0
0
−
P
5
0
P
5
0
0
0
0
P
6
P
7
0
0
0
⎣
⎦
⎣
⎦
⎣
⎦
⎣
⎦
⎣
⎦
⎣
⎦
⎣
⎦
⎣
⎦
=
+
+
+
+
+
+
P
2
It follows that
u
,
v
,
w
,and
x
are given by the following equations:
u
=
P
1
+
P
4
−
P
5
+
P
7
v
=
P
3
+
P
5
w
=
P
2
+
P
4
x
=
P
1
−
P
2
+
P
3
+
P
6
Associativity and commutativity under addition and distributivity of multiplication over ad-
dition are used to obtain this result. In particular, commutativity of the ring multiplication
operator is not assumed. This is important because it allows this algorithm to be used when
the entries in the original 2
×
2 matrices are themselves matrices, since matrix multiplication
is not commutative.
Thus, an algorithm exists to form the product of two
n
×
n
matrices with seven multi-
plications of
(
n/
2
)
×
(
n/
2
)
matrices and 18 additions or subtractions of such matrices. Let
n
=
2
k
and
M
(
k
)
be the number of operations over the ring
R
used by this algorithm to
multiply
n
×
n
matrices. Then,
M
(
k
)
satisfies
1
)+
18
2
k−
1
2
=
7
M
(
k
1
)+(
18
)
4
k−
1
M
(
k
)=
7
M
(
k
−
−
If the standard algorithm is used to multiply 2
×
2matrices,
M
(
1
)=
12 and
M
(
k
)
satisfies
the following recurrence:
M
(
k
)=(
36
/
7
)
7
k
(
18
/
3
)
4
k
−
The depth (number of operations on the longest path),
D
(
k
)
, of this straight-line algo-
rithm for the product of two
n
n
matrices when
n
=
2
k
×
satisfies the following bound:
D
(
k
)=
D
(
k
−
1
)+
3
because one level of addition or subtraction is used before products are formed and one or two
levels are used after they are formed. Since
D
(
1
)=
2 if the standard algorithm is used to
multiply 2
×
2matrices,
D
(
k
)=
3
k
−
1
=
3
log
n
−
1.
These size and depth bounds can be improved to those in the following theorem by using
the standard matrix multiplication algorithm on small matrices. (See Problem
6.8
.)
THEOREM
6.3.1
The matrix multiplication function for
n × n
matrices over a commutative ring
R
,
f
(
n
)
A×B
, has circuit size and depth satisfying the following bounds over the basis
Ω
containing
addition, multiplication, and additive inverse over
R
:
C
Ω
f
(
n
)
A×B
4
.
77
n
log
2
7
≤
D
Ω
f
(
n
)
A×B
=
O
(log
n
)
Search WWH ::
Custom Search