Graphics Programs Reference
In-Depth Information
As the notation implies, we are storing the nonzero elements of
A
in the vectors
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
d
1
d
2
.
d
n
−
1
d
n
c
1
c
2
.
c
n
−
1
e
1
e
2
.
e
n
−
1
c
=
d
=
e
=
The resulting saving of storagecan besignificant.For example, a100
×
100 tridiag-
onal matrix,containing 10,000 elements, can be storedinonly99
+
100
+
99
=
298
locations, which represents a compressionratioofabout 33:1.
We now applyLU decomposition to the coefficient matrix. We reduce row
k
by
getting rid of
c
k
−
1
with the elementary operation
row
k
←
row
k
−
(
c
k
−
1
/
d
k
−
1
)
×
row (
k
−
1),
k
=
2
,
3
,...,
n
The corresponding change in
d
k
is
d
k
←
d
k
−
(
c
k
−
1
/
d
k
−
1
)
e
k
−
1
(2.21)
whereas
e
k
is not affected. In order to finish up with Doolittle's decomposition of the
form [
L
\
U
], we store the multiplier
λ
=
c
k
−
1
/
d
k
−
1
in the locationpreviously occupied
by
c
k
−
1
:
c
k
−
1
←
c
k
−
1
/
d
k
−
1
(2.22)
Thus the decompositionalgorithmis
fork=2:n
lambda = c(k-1)/d(k-1);
d(k) = d(k) - lambda*e(k-1);
c(k-1) = lambda;
end
Next we look at the solutionphase, i.e., the solution of the
Ly
=
b
, followedby
Ux
=
y
. The equations
Ly
=
b
can be portrayedbythe augmented coefficient matrix
⎡
⎣
⎤
⎦
1
000
···
0
b
1
c
1
1
00
···
0
b
2
L
b
0
c
2
1
0
···
0
b
3
=
00
c
3
1
...
0
b
4
.
.
.
.
.
.
···
00
···
0
c
n
−
1
1
b
n
Search WWH ::
Custom Search