Information Technology Reference
In-Depth Information
6.8 Generalize Strassen's matrix multiplication algorithm to matrices that are
m
m
for
m
=
p
2
k
,
p
and
k
both integers. Derive bounds on the size and depth of a circuit
realizing this version of the algorithm.
For arbitrary
n
,showhow
n
×
m
matrices,
m
=
p
2
k
, so that this new version of the algorithm can be used. Show that upper
bounds of 4
.
77
n
log
2
7
×
n
matrices can be embedded into
m
×
and
O
(log
n
)
on the size and depth of this algorithm can be
obtained.
6.9 Show that Strassen's matrix multiplication algorithm can be used to multiply square
Boolean matrices by replacing
OR
by addition modulo
n
+
1. Derive a bound on the
size and depth of a circuit to realize this algorithm.
6.10 Show that, when one of two
n
n
Boolean matrices
A
and
B
is fixed and known in
advance,
A
and
B
can be multiplied by a circuit with
O
(
n
3
/
log
n
)
operations and
depth
O
(log
n
)
to produce the product
C
=
AB
using the information provided
below.
a) Multiplication of
A
and
B
is equivalent to
n
multiplications of
A
with an
n
×
×
1
vector
x
, a column of
B
.
b) Since
A
is a 0
1matrix,theproduct
A
x
consists of sums of variables in
x
.
c) The product
A
x
can be further decomposed into the sum
A
1
x
1
+
A
2
x
2
+
−
···
+
A
k
x
k
where
k
=
n/
log
n
,
A
j
is the
n
×
log
n
submatrix consisting of
columns
(
j
−
1
)
log
n
+
1through
j
log
n
of
A
,and
x
j
is the
j
th set of
rows (variables) in
x
.
d) There are at most
n
distinct sums of
log
n
log
n
variables each of which can be formed
in at most 2
n
addition steps, thereby saving a factor of
log
n
.
TRANSITIVE CLOSURE
6.11 Let
A
=[
a
i
,
j
]
,1
n
, be a Boolean matrix that is the adjacency matrix of
adirectedgraph
G
=(
V
,
E
)
on
n
=
≤
i
,
j
≤
|
V
|
vertices. Give a proof by induction that
the entry in the
r
th row and
s
th column of
A
k
=
A
k−
1
×
A
is 1 if there is a path
containing
k
edges from vertex
r
to vertex
s
and 0 otherwise.
6.12 Consider a directed graph
G
=(
V
,
E
)
in which each edge carries a label drawn from
a semiring. Let the entry in the
i
th row and
j
th column of the adjacency matrix of
G
contain the label of the edge between vertices
i
and
j
if there is such an edge and the
empty set otherwise. Assume that the labels of edges in
G
are drawn from a semiring.
Show that Theorems
6.4.1
,
6.4.2
,and
6.4.3
hold for such labeled graphs.
MATRIX INVERSION
6.13 Show that over fields the following properties hold for matrix inversion:
a) The inverse of a 2
×
2 upper (lower) triangular matrix is the matrix with the off-
diagonal term negated.
b) The inverse of a 2
2 diagonal matrix is a diagonal matrix in which the
i
th diagonal
element is the multiplicative inverse of the
i
th diagonal element of the original
matrix.
×
Search WWH ::
Custom Search