Information Technology Reference
In-Depth Information
Compute
X
∗
recursively and use it to form
Y
=
U
+
VX
∗
W
by performing two multiplica-
tions of
(
n/
2
)
(
n/
2
)
matrices and one addition of such matrices. Recursively form
Y
∗
and
then assemble the matrix
B
shown below with four further multiplications and one addition
of
(
n/
2
)
×
×
(
n/
2
)
matrices.
B
=
Y
∗
Y
∗
VX
∗
(6.4)
X
∗
WY
∗
X
∗
+
X
∗
WY
∗
VX
∗
We now show that
B
=
A
∗
.
THEOREM
6.4.3
Under Assumptions
6.3.1
and
6.3.2
,acircuitofsize
O
(
M
matrix
(
n
,
K
))
and
depth
O
(
n
)
exists to form the transitive closure of
n
n
matrices.
Proof
We assume that
n
is a power of 2 and use the representation for the matrix
A
given
in (
6.3
). If
n
is not a power of 2, we augment the matrix
A
by embedding it in a larger
matrix in which all the new entries, are 0 except for the new diagonal entries, which are 1.
Given that 4
M
(
n
)
×
M
(
2
n
)
, the bound applies.
We beg in by showing tha t
B
=
A
∗
.Let
F
≤
V
be the first and second
sets of
n/
2 vertices, respectively, corresponding to the first and second halves of the rows
and columns of the matrix
A
.Then,
F
⊂
V
and
S
⊂
.Observethat
X
∗
is
the adjacency matrix for those paths originating on and terminating with vertices in
F
and
visiting no other vertices. Similarly,
Y
=
U
+
VX
∗
W
is the adjacency matrix for those
paths consisting of an edge from a vertex in
F
to a vertex in
F
or paths of length more
than 1 consisting of an edge from vertices in
F
to vertices in
S
, a path of length 0 or more
within vertices in
S
, and an edge from vertices in
S
to vertices in
F
. It follows that
Y
∗
is
the adjacency matrix for all paths between vertices in
F
that may visit any vertices in
V
.A
similar line of reasoning demonstrates that the other entries of
A
∗
are correct.
The size of a circuit realizing this algorithm,
T
(
n
)
, satisfies
∪
S
=
V
and
F
∩
S
=
∅
T
(
n
)=
2
T
(
n/
2
)+
6
M
matrix
(
n/
2,
K
)+
2
(
n/
2
)
2
because the above algorithm (see Fig.
6.4
)usestwocircuitsfortransitiveclosureon
(
n/
2
)
×
(
n/
2
)
matrices, six circuits for multiplying, and two for adding two such matrices.
Because we assume that
n
2
≤
M
matrix
(
n
,
K
)
, it follows that
T
(
n
)
≤
2
T
(
n/
2
)+
8
M
matrix
(
n/
2,
K
)
.Let
T
(
m
)
≤
cM
matrix
(
cm
,
K
)
for
m
≤
n/
2 be the inductive hy-
pothesis. Then we have the inequalities
T
(
n
)
≤
(
2
c
+
8
)
M
matrix
(
n/
2,
K
)
≤
(
c/
2
+
2
)
M
matrix
(
n
,
K
)
which follow from
M
matrix
(
n/
2,
K
)
≤
M
matrix
(
n
,
K
)
/
4 (see Assumption
6.3.2
). Because
(
c/
2
+
2
)
4, for
c
=
4 we have the desired bound on circuit size.
The depth
D
(
n
)
of the above circuit satisfies
D
(
n
)=
2
D
(
n/
2
)+
6
K
log
2
n
,from
which we conclude that
D
(
n
)=
O
(
n
)
.
≤
c
for
c
≥
A
semiring
(
S
,
+
,
·
,0,1
)
is a set
S
,twooperations
+
and
·
∈
S
with
and elements 0, 1
the following properties:
a)
S
is closed under
+
and
·
;
b)
+
and
·
are associative;
Search WWH ::
Custom Search