Information Technology Reference
In-Depth Information
constructed with
AND
and
OR
gates for it):
C
Ω
f
(
n
)
A
∗
≤
M
matrix
(
cn
,
K
)
log
2
n
D
Ω
f
(
n
)
≤
K
(log
n
)
log
2
n
A
∗
Proof
Let
k
=
2
p
be the smallest power of 2 such that
k
≥
n
−
1. Then,
p
=
log
2
(
n
−
.
Since
A
∗
=(
I
+
A
)
k
, it can be computed with a circuit that squares the matrix
I
+
Ap
times. Each squaring can be done with a circuit for the standard matrix multiplication algo-
rithm described in (
6.1
)using
M
matrix
(
cn
,
K
)=
O
(
n
3
)
operations and depth
1
)
log
2
2
n
.
The desired result follows.
The above statement says that the transitive closure function on
n
n
matrices has circuit
size and depth at most a factor
O
(log
n
)
times that of matrix multiplication. We now show
that Boolean matrix multiplication is a subfunction of the transitive closure function, which
implies that the former has a circuit size and depth no larger than the latter. We subsequently
show that the size bound can be improved to a constant multiple of the size bound for matrix
multiplication. Thus the transitive closure and Boolean matrix multiplication functions have
comparable size.
×
THEOREM
6.4.2
The
n × n
matrix multiplication function
f
(
n
)
2
n
2
n
2
A×B
:
R
→R
for Boolean
matrices is a subfunction of the transitive closure function
f
(
3
n
)
A
∗
18
n
2
9
n
2
:
R
→R
.
Proof
Observe that the following relationship holds for
n
×
n
matrices
A
and
B
,sincethe
third and higher powers of the 3
n
×
3
n
matrix on the left are 0.
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
∗
0
A
0
00
B
000
IAAB
0
IB
=
AI
0
It follows that the product
AB
of
n
×
n
matrices is a subfunction of the transitive closure
function on a 3
n
×
3
n
matrix.
COROLLARY
6.4.1
It follows that
C
Ω
f
(
n
)
A×B
C
Ω
f
(
3
n
)
≤
A
∗
D
Ω
f
(
n
)
B
D
Ω
f
(
3
n
)
≤
A
×
A
∗
over the basis
Ω=
{
}
AND
,
OR
.
Not only can a Boolean matrix multiplication algorithm be devised from one for transitive
closure, but the reverse is also true, as we show. Let
n
be a power of 2 and divide an
n
×
n
matrix
A
into four
(
n/
2
)
×
(
n/
2
)
matrices:
A
=
UV
WX
(6.3)
Search WWH ::
Custom Search