Information Technology Reference
In-Depth Information
T
−
1
2,2
T
2,1
T
−
1
−
1,1
MULT[
n/
2]
T
−
1
2,2
MULT[
n/
2]
T
−
1
1,1
T
2,1
TRI INV
[
n/
2
]
TRI INV
[
n/
2
]
T
2,2
T
1,1
Figure 6.5
A recursive circuit TRI INV[
n
] for the inversion of a triangular matrix.
This representation for the inverse of
T
defines the recursive algorithm TRI INV[
n
]in
Fig.
6.5
.When
n
=
1 this algorithm requires one operation; on an
n
×
n
matrix it requires
two calls to TRI INV[
n/
2] and two matrix multiplications. Let
f
(
n
)
tri inv
(
n
2
+
n
)
/
2
:
R
→
(
n
2
+
n
)
/
2
be the function corresponding to the inversion of an
n
R
n
lower triangular ma-
trix. The algorithm TRI INV[
n
] provides the following bounds on the size and depth of the
smallest circuit to compute
f
(
n
)
×
tri inv
.
THEOREM
6.5.1
Let
n
be a power of 2. Then the matrix inversion function
f
(
n
)
tri inv
for
n
×
n
lower triangular matrices satisfies the following bounds:
C
f
(
n
)
tri inv
≤
M
matrix
(
n
,
K
)
D
f
(
n
)
tri inv
=
O
(log
2
n
)
Proof
From Fig.
6.5
it is clear that the following circuit size and depth bounds hold if the
matrix multiplication algorithm has circuit size
M
matrix
(
n
,
K
)
and depth
K
log
2
n
:
C
f
(
n
)
tri inv
2
C
f
(
n/
2
)
tri inv
+
2
M
matrix
(
n/
2,
K
)
≤
D
f
(
n
)
tri inv
D
f
(
n/
2
)
tri inv
+
2
K
log
n
≤
The solution to the first inequality follows by induction from the fact that
M
matrix
(
1,
K
)=
1 and the assumption that 4
M
matrix
(
n/
2,
K
)
M
matrix
(
n
,
K
)
. The second inequality
follows from the observation that
d>
0 can be chosen so that
d
log
2
(
n/
2
)+
c
log
n
≤
≤
d
log
2
n
for any
c>
0for
n
sufficiently large.
Search WWH ::
Custom Search