Information Technology Reference
In-Depth Information
6.14 Show that a lower triangular Toeplitz matrix
T
can be inverted by a circuit of size
O
(
n
log
n
)
and depth
O
(log
2
n
)
.
Hint:
Assume that
n
=
2
k
,write
T
as a 2
×
2matrixof
n/
2
×
n/
2 matrices, and
devise a recursive algorithm to invert
T
.
6.15 Exhibit a circuit to compute the character
ist
ic polynomial
φ
A
(
x
)
of an
n
×
n
matrix
that has
O
(max(
n
3
,
√
nM
matrix
(
n
)))
field operations and depth
A
over a field
R
O
(log
2
n
)
.
Hint:
Consider the case
n
=
k
2
. Represent the integer
i
,0
≤
i
≤
n
−
1, by the unique
pair of integers
(
r
,
s
)
,0
≤
r
,
s
≤
k
−
1, where
i
=
rk
+
s
. Represent the coefficient
c
i
+
1
,0
≤
i
≤
n
−
2, of
φ
A
(
x
)
by
c
r
,
s
.Thenwecanwrite
φ
A
(
x
)
as follows:
A
rk
k−
1
c
r
,
s
A
s
k−
1
φ
A
(
x
)=
r
=
0
s
=
0
Show that it suffices to perform
k
2
n
2
=
n
3
scalar multiplications and
k
(
k
−
1
)
n
2
≤
n
3
n
matrices, and
kn
2
scalar
additions to combine these products. In addition,
A
2
,
A
3
,
...
,
A
k−
1
and
A
k
,
A
2
k
,
...
,
A
(
k−
1
)
k
must be computed.
6.16 Show that the traces of
po
wers,
s
r
,1
additions to form the inner sums,
k
multiplications of
n
×
≤
r
≤
n
,foran
n
×
n
matrix
A
over a field can
be computed with
O
(
√
nM
matrix
(
n
))
operations.
Hint:
By definition
s
r
=
j
=
1
a
(
r
)
j
,
j
,where
a
(
r
)
j
,
j
is the
j
th diagonal term of the
ma
trix
A
r
.Let
n
be
a
square. Represent
r
u
ni
quely by a pair
(
a
,
b
)
,where1
≤
√
n
≤
a
,
b
−
1
and
r
=
a
√
n
+
b
.Th
en
A
r
=
A
a
√
n
A
b
.Thus,
a
(
r
)
j
,
j
can be computed as the product
of the
j
th r
o
w of
A
a
√
n
with the
j
th column of
A
b
.Then,for
e
ach
j
,1
≤
j
≤
n
,
form the
√
n
≤
√
n
n
ma
tr
ix
R
j
whose
a
th row is the
j
th row of
A
a
√
n
,0
×
≤
a
−
1.
×
√
n
matrix
C
j
whose
b
th column is the
j
th column of
A
b
,1
Al
so
form the
n
≤
b
≤
√
n
1. Show that the product
R
j
C
j
contains each of the terms
a
(
r
)
−
for all values
j
,
j
of
r
,0
≤
r
≤
n
−
1 and that the products
R
j
C
j
,1
≤
j
≤
n
, can be computed
efficiently.
6.17 Show that (
6.14
) holds by applying the properties of the coefficients of the characteristic
polynomial of an
n
n
matrix stated in (
6.15
).
Hint:
Use proof by induction on
l
to establish (
6.14
).
×
CONVOLUTION
6.18 Consider the convolution
f
(
n
,
m
)
:
R
n
+
m
R
n
+
m−
2
of an
n
-tuple
a
with an
m
-
→
conv
tuple
b
when
n
m
. Develop a circuit for this problem whose size is
O
(
m
log
n
)
that uses the convolution theorem multiple times.
Hint:
Represent the
m
-tuple
b
as sequence of
m/n
n
-tuples.
6.19 The
wrapped convolution
f
(
n
)
n
maps
n
-tuples
a
=(
a
0
,
a
1
,
...
,
a
n−
1
)
and
b
=(
b
0
,
b
1
,
...
,
b
n−
1
)
, denoted
a
b
,tothe
n
-tuple
c
the
j
th component
of which,
c
j
,isdefinedasfollows:
2
n
wrapped
:
R
→R
c
j
=
a
r
∗
b
s
r
+
s
=
j
mod
n
Search WWH ::
Custom Search