Page 53 - Numerical methods for chemical engineering

Matrix factorization 39

elimination on matrix A alone, without augmenting it with b,
 
a 11 a 12 a 13 ... a 1N
 a 21 a 22 a 23 ... a 2N 
 
a 31 a 32 a 33 a 3N  (1.191)
 ... 
A = 
 . . . . . 
 . . . . . . . . . . 
a N1 a N2 a N3 ... a NN
We perform the row operation 2 ← 2 − λ 21 × 1 with λ 21 = a 21 /a 11 to obtain
 
a 11 a 12 a 13 ... a 1N
 (2,1) (2,1) (2,1) 
0 a a ... a
 
22 23
 2N 
A (2,1) =  a 31 a 32 a 33 ... a 3N  (1.192)


 . . . . . . . . . . 


 . . . . . 
...
a N1 a N2 a N3 a NN
(2,1)
We know from our choice of λ 21 = a 21 /a 11 that a 21 = 0; therefore, we are free to use this
location in memory to store something else. Let us take the advantage of this free location
to store the value of λ 21 ,
 
a 11 a 12 a 13 ... a 1N
(2,1) (2,1)
 (2,1) 
 λ 21 a a ... a
22 23 2N 
A (2,1) =  a 31 a 32 a 33 ...  (1.193)


 a 3N 
 . . . . . 
 . . . . . . . . . . 
a N1 a N2 a N3 ... a NN
Next, we perform the row operation 3 ← 3 − λ 31 × 1 with λ 31 = a 31 /a 11 , and use the
(3,1)
location freed by the fact that a = 0 to store λ 31 ,
31
 
a 11 a 12 a 13 ... a 1N
 (2,1) (2,1) (2,1) 
λ 21
 a a ... a 
22 23
 2N 
A (3,1) =  λ 31 a (3,1) a (3,1) ... a (3,1)  (1.194)


32
33
 3N 
 . . . . .
 
 . . . . . . . . . . 

...
a N1 a N2 a N3 a NN
After completing Gaussian elimination, storing after each row operation k ← k − λ kj × j
the value of λ kj in the position freed by a jk = 0, we have in memory
 
...
a 11 a 12 a 13 a 14 a 1N
 (2,1) (2,1) (2,1) 
λ 21
 a a a ... a (2,1) 
 22 23 24 2N 
 
(3,2) (3,2)
 λ 32 a a ... a (3,2) 
 λ 31
A (N,N−1) 33 34 3N  (1.195)

= 
(4,3)
 (4,3) 
 λ 41 λ 42 λ 43 a 44 ... a 4N 
 . . . . . . . . . . . . 

 . . . . . . 

(N,N−1)
... a
λ N1 λ N2 λ N3 λ N4
NN