Information Technology Reference
In-Depth Information
Since
φ
A
(
λ
j
)=
0, when we substitute
l
for
n
−
i
it suffices to show the following for
≤
l
≤
n
−
0
1:
n
l
c
k
λ
j
(
n
−
l
)
c
l
=
(6.14)
j
=
1
k
=
0
This identity can be shown by induction using as the base case
l
=
0 and the following facts
about the derivatives of the characteristic polynomial of
A
, which are easy to establish:
n
1
)
n
c
0
=(
−
λ
j
j
=
1
x
=
0
k
d
k
φ
A
(
x
)
dx
k
1
)
k
c
0
j
1
···
j
k
j
r
1
λ
j
t
c
k
=
−
=(
t
=
1
=
j
s
The reader is asked to show that (
6.14
) follows from these identities. (See Problem
6.17
.)
Csanky's algorithm computes the traces of powers, namely the
s
r
's , and then inve r t s the
lower triangular matrix given above, thereby solving for the coefficients of the characteristic
polynomial. The coefficients are then used with a prefix computation, as mentioned earlier, to
compute the inverse. Each of the
ns
r
's can be comput ed in
O
(
n
)
steps once the powers of
A
have been formed by the prefix computation described above. The lower triangular matrix
is non-singular and can be inverted by a circuit with
M
matrix
(
n
,
K
)
operations and depth
O
(log
2
n
)
, as shown in Theorem
6.5.1
. The following theorem summarizes these results.
THEOREM
6.5.6
The matrix inverse function for non-singular
n × n
matrices over a field of
characteristic zero,
f
(
n
)
A
−
1
, has an algebraic circuit whose size and depth satisfy the following bounds:
C
f
(
n
)
A
−
1
=
O
(
nM
matrix
(
n
,
K
))
C
f
(
n
)
A
−
1
=
O
(log
2
n
)
The size bound can be improved to
O
(
√
nM
matrix
(
n
,
K
))
, as suggested in Problems
6.15
and
6.16
.
6.6 Solving Linear Systems
A general linear system with
n
n
coefficient matrix
M
,
n
-vector
x
of unknowns and
n
-vector
b
is defined in (
6.5
) and repeated below:
×
M
x
=
b
This system can be solved for
x
in terms of
M
and
b
using the following steps when
M
is not
SPD. If it is SPD, the first step is unnecessary and can be eliminated.
a) Premultiply both sides by the transpose of
M
to produce the following linear system in
which the coefficient matrix
M
T
M
is SPD:
M
T
M
x
=
M
T
b
=
b
∗
Search WWH ::
Custom Search