SPARSE MATRICES REGINALD P. TE WARSON Department of Applied Mathematics and Statistics State University of N e w York St...
88 downloads
934 Views
5MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
SPARSE MATRICES REGINALD P. TE WARSON Department of Applied Mathematics and Statistics State University of N e w York Stony Brook, N e w York
A C A D E M I C P R E S S New York and London
1973
0 1973, OF
OR F O R M OR
OR
OR
York,
111
York 10003
United Kingdom Edition published by 24/28
OF
(MOS) 1970 OF
To HEIDI, ANITA, A N D MONIQUE
Preface
book
book
xi
xii
Preface
1962-1964, I ;
on. on on
1968, on
1969
1970. on
1969,
1970 book on on 1970 book book
book.
book.
xiii
Preface
1,
2,
3,
do 2.
4. ;
2
3
5,
by
6.
7 7
xiv
Preface
8,
EFI, on
8.
Acknowledgments
L.
I book book
I.
K.
xu
CHAPTER
I
Preliminary Considerations
1.I.
Introduction
A
I .2. Sparse Matrices A a
nx n
I
2
1 Preliminary Considerations
n n.
i
;
on
1.3. Packed Form of Storage
pucked form;
1.3.
3
Packed Form of Storage
(for
by
for ;
n
A z << n2,
z
A
by aij.
A aij # 0, for
aij.
32 A.
n2 A
A
3r
4
1 Prelimioary Comiderstioas
UTILIZATION OF LINKED LISTS IN PACKING
by
linked lists as item
aij
an
1.3.1).
r
Address the item Of
1 Value of the element
Row index
Next item in column if any
Address of next item ( Z e r o if last i t e m )
Fig. 1.3.1. The item corresponding to aij.
(i, p),
i
p
aij
p
address)
SI (Storagefor Items).
BC (Beginning of Column BC n BC
SI(a) 1.3.2). SI, z
BC
SI Fig. 1.3.2. Linked lists packed storage.
1.3.
5
Packed Form of Storage
SI n
32
+ 32 no
SI ;
SI by 3. a I 3 = u33 = 0, a23 = 0.5, 101, 200 203 2.5), 300, :
BC a43 = 1.5;
BC ~
2
3
a43
on u33 as Location
103
200
201
202
203
204
300
301
302
Present contents New contents
200 200
2 2
0.5 0.5
203 300
4 4
1.5 1.5
3
2.5
203
-
202 3.5) 300,
u 3 3 ,a,
Location
103
200
201
202
203
204
300
Present contents New contents
200 300
2 2
0.5 0.5
203 203
4 4
1.5 1.5
by
301
302
-
-
1
3.5
200
6
1 Preliminary Considerations
by
101
201,
50
301
50
101
102
103
201
201
203
301
~~
101
301
~
-
-
201 201
-
302
303
~~
-
101
-
~
301,302,
303,
do by
by
A,,
u z l ,u 4 1 ,u 5 2 ,u I 3 ,u 3 3 ,u z4 , by by
u45,
1.3.
7
Packed Form of Storage
SCHEME I
A
of
n+z + 1 of A , 1
t
n
As
+z +
a
A. A,
7
t =
2,Uz1;
n
5,U5,;
=
5
1,U13;
0,5;
3 , ~ ~ ~ ;
SCHEME I1
t, =
t,.
n
t
2t
+n
~
u
A, =
=
~
'
~
~
~
u
~
4,
5,
1,
3,
4,
6,
~
3,
~
~
r
u
~
~
2,
a33 =
4, 3.
~
u
3
3
~
u
~
~
8
1 Preliminary Considerations
4,
a33 # 0.
3
RI(5)
=
3,
aS3.
SCHEME III
:
A(i,j) A(i,j ) = i
+ ( j - l)n,
aij # 0. A(i,j)
z = 1,2,. . . ,z.
aij
to
A, = (a21 9 a41 3 a52r a 1 3 , a331 a24,
4,
=
10, 11, 13, 17,
:
A(iJ
2 A(i,~)/n
i = A(i,j) - ( j - 1)n. i, J) =
i = A(i,j) - ( j -
= 13,
i, j)/n =
3,
A(i,j)/n = 13 - 10 = 3.
=
3
SCHEME ZV i 2j, aij = 0,
Oi i,
i - j > Oi,
n symmetric band matrix
locally variable
9
Packed Form of Storage
1.3.
3.8.
on
up
8, + 1
(8, + i
- j < Oi
,
full,
,8, =
>j,
+
-
on a 3 3 ,~
4 2 a44, , a,*,
n 8, + 2n aij # 0,
a,
,,a, ,,a,,,
a3,,
a 5 3 ,a 5 5 .
a43
a54
:
aij -
- (i
-j)>
-j ) -
aij aij
aij = 0
a53
- (5
-
=
12 - 2 = 10 > 8
=
a53
:
:
10
1 Preliminary Considerations
SOME REMARKS ON PACKING SCHEMES
by
1 by by by by
no
1.4. Scaling
A x = b,
x xi
bi
b
n. x
b,
6,
6,
A bz.
b,
by
1.5.
11
Bibliography and Comments
A
A
of
x
Ax = b
by by A by
Ax
=
b
:
ej
I,.
(f.4.2)
D2AD1D;'x = D2b,
D1
D,
(2.4.2) ejlD,ej =
e;D2ei
j
by
(1.4.1) (2.4.3)
Ie,'AD,ejl]-'.
=
i
x = Dl(D2AD1)-'D2b,
A-', D2AD,. (2.4.4)
D,
=
I,,
(1.4.3)
x = (D2A)-'D2b.
1.5. Bibliography and Comments
(1963), (1968),
: (1957), (1962), (1963), (1963a, (1965), (1966, 1967a), et (1969), (1969), (1969),
12
1 Preliminary Considerations
:
:
:
et al.
: : : :
Weil(1969),
by by equilibration.
1.5.
Bibliography and Comments
book
:
13
CHAPTER
2
The Gaussian Elimination
2.1. Introduction
2.2.
(2.2.2)
The Basic Method
AX = b
15
16
2 The Gaussian Elimination
1, x n) forwardcourse
U U n A(k)
A")
=
A("+')
E
U.
u$)
ui:) = e ; k k ) e j ,
A(k);
1.3 A(k'
I,. k-1
-Row
k
t
Column k
Fig. 2.2.1. The matrix at the beginning of the kth step.
A'k'
by by A ( k +I).
A'k+ ') = LkA"',
k = 1,2,. . . ,n, Lk
2.2.
17
The Basic Method
I
I
I
-
I
X X I X I
*
klh row
*
0
X
I
kth column
Fig. 2.2.2. The elementary matrix at the kth stage.
q(,)
on
Lk
qlk's on
(2.2.2), A("+1)
(2.2.5)
=
L,. . . L,L,A'",
L = L, . . . L,L, ,
(2.2.6)
A(') = (2.2.7)
A("+
= U,
U =
U.
LkS
18
2 'zbe Gaussian Elimination
(2.2.8)
U X = Lb.
:
xi
x.
x,
U x,,-~
x, x, x,-~
(n -
x,-
on. U
(i.j)
a$+ ').
k A"+ l )
= i
U :
(2.2.9)
(2.2.10)
U2.s-
uk
=
1,
u,-,u,u
+ ('k)ek',
k
=
n, n - 1,. . . ,2,
=
Column k
1 I
X X
I
I
X I X I
-
0
Row k
0
I I
Fig. 2.2.3. The elementary matrix at the kth stage of back substitution.
19
2.3. Pivoting and Round-oli Errors
t(k) (2.2.12)
tik)=
-a$+
'),
by
tik)= 0,
i
on
U,
uk
i 2 k
t;"s on
(2.2.12)
u 2 . . .Un-IUn,
(2.2.13)
x = U-'Lb =
U , ". U n - U n L , .. ' L2Llb.
2.3. Pivoting and Round-ofl Errors a::)
pivot
by
on
partial pivoting
on
A") (2.3.2)
:
la#,
lu$)l = i
k
< i < n, A(,)
pivoting,
k,
20
n-k
2
+1
The Gaussian Elimination
A'"),
(2.3.2)
k
la$)l,
= i,i
k
t
< i,j < n,
k
E,
pivot tolerance E
9
E =
A
drop tolerance), by
2.4. A
The Elimination Form of Inverse Ab
2.2 : by x = A - ' b . by
Elimination Form of Inverse (EFI). n n-1 EFI by
A-
21
2.4. The Elimination Form of Inverse
pi
p.
(2.4.2)
by
u k
((k).
(2.4.3)
i #
(p’Uk)ei = pi,
(P”/k)ek
p’(‘k’
=
+ pkr
p‘ by Uk
p’
p’
<‘k)
ei’(Lkp) =
(2.4.4)
ek’(Lkp)
=
i <
pi?
qik)Pk,
ei‘(Lkp)= qlk)pk+ pi,
> k.
p by
Lkp
by
p,q(,) (2.4.5)
(p‘Lk)f?i= pi(, i #
(p’Lk)f?k =
/3’q(,),
by by A-’n,
q(k).
n
by
A-’
n-1
n
:
A - ln
nA-
’
=
U , ( . . . (U,(L, * f . (L2(L1n)). . .).
by :
nA-
’ = (. . .((nU,)U,). . . U,)L,). . . L1).
22
2 Tbe Gaussian Elimiiation
<(k)s.
tjJk)s EFI
<(k)s
v(~)s
2.5.
Minimizing the Total Number of Nonzero Elements in EFI 2.2
ai;), a;;),
( k + 1)
(2.5.2)
aij
a!:)
i, > k,
a$) = 0,
= -
(k) (k) (k) (%k l a k k b k j 3
A(k)
A ( k +'). A(k)
$//-in.
A ( k +')
a&) a$), 2 k, t 2 k
A(k)
(2.5.2)
A ( k +')
k
=
A(k) =
(2.5.3) Pk
=
. . ,n
pkA(k)Qk ?
I,
Qk
by Lks
~ ( ~ ) s
2.5.
Minimizing the Total Number of Nonzero Elements in EFI
a$)
23
A(,).
(i,j)
2.3,
> E,
E
IuLf)] > E
DEFINITION n -k + 1 by
(2.5.5)
i 2 k, 2 k,
B, A") by
ujyk-
by (2.5.6)
G,
=
(i, j )
BkBk'B,,
B,' B, Proof (i
bti
A(,), + k - 1, q + k + k - 1, q + k + k - 1, + k + k - 1, q + k A'k")
Bk,
q)
g:;)
24
2 me Gaussian Elimination
C C b{t)(l - bfJ)bf’, p # i, q # j = C C ei‘B,eq(l - eplBkeq)ep‘Bkej,
(2.5.7)
=
p
=
P
4
P
4
1 - b!: M
b$) = 0 b$ = 0.
i
1 - bfJ = 0
=
1 - e,’B,e, = e i M e , - e,‘B,e,
(2.5.8)
=
-
e,’B,e,
=
0,
p # i, q # j , q= (n - k
=
e,’(M - B,)eq
+
-
eq’B,’ep, e,’B,e,
(2.5.8), P
4
eqeq’Bk’C e,e,’B,ej
= e;B,
P
4
= ei’BkBLBkej,
1,eqeq‘ = 1,ePe,,’ = I , -, +
by
2.5.5. (2.5.9)
COROLLARY s=
u:!)
p (2.5.20)
+k-1 g$
cc,p
=
lc$+!k-l,j+k.-ll
i,j
(E
ct
+ k - 1, t =
by
> E,
25
2.5. Minimizing the Total Number of Nonzero Elements in EFI
by
(ik)s
U
n-k A(k)
')
tjJk)s
((k)s,
((k)s,
rfk)s
so by
2.5.9,
sub( ( k ) ~
a:!)
no
A("+1)= L,Pn...L,P,LlP,AQlQ2...Q,,
(2.5.22)
L = L,P,. . . L,P2LlPl,
(2.5.12)
Q1Q2...Qn
(2.5.13)
A("+')=
=Q
A-' =
Q
Pks
on
THEOREM
0,
Qfr-lE.
n'),
(2.5.24)
v(~)s.
a~~k-,,j+k-l
n
26
2 The Gaussian Elimination
by
Gk, (2.5.25)
Gk
= (Bk
-
I n - k + l)M(Bk
- In-k+
l)?
M
2:;’
Proof
2.5.5,
2;:)
(2.5.16)
1bi:)b$),
= P
=
p #
q # j,
4
(ei’BkC.‘,- ei’C.‘,)(Vk’Bkej - b‘ej), n-k
Vk 8 j
=
ei’(Bk
- In-,+
l)GC.‘,’(Bk
= ei’(Bk - zn-k+l)‘(Bk
- In-k+
- In-,+
+ 1.
I k j
l k j ?
VkVk’ =
(2.5.10)]
EL’$
(2.5.1
~ u ~ ~ k ~ l ,>j E,+ k - l ~
= i.j
u
a$)
Bk = Bk’
+k - 1 =s
B+k -1=
(2.5.17)
27
2.5. Minimizing the Total Number of Nonzero Elements in EFI
(2.5.16),
k::)
-
= i
c1
(ei’Bk&
-
ei’Bkl/k,
ei’BkV,2 1. (2.5.18)
i
ei’Bkh = e,’Bkh,
/‘Lkik-
I.a+k-
11
’
E,
+k -
ei’B,V, A‘k’.
do,
A
A
v(,)s
(2.5.29)
THEOREM
A
k
=
1,2,. . . ,n - 1,
n -k A‘”’) (2.5.4), qlk), i > k (2.5.20)
qjk) = -a::+
by =
> k.
28
2 The Gaussian Elimination
Proof
u $ + ' ) = u$")
> k,
= a$), i, j uij) =
by
As
(2.5.3),Qk = pk' (2.5.4), (2.2.3),
=
a$), i , j > k.
( k + 1)
=
(k + 1) =
'ji
-
&k)a(k)/$p, rk k J
-
a(k)a(k)/*(k), Jk k i ukk
JI
' i (j k + l )
= a$+1),
a!k) =
a(?),
JJ
?Ik)
= d:!)/&)
=
=
a:!),
i, j > k,
i, j 2 k.
JI
(2.5.2),(2.2.3), l)
(2.5.2),
j > k,
'ij
a:!+
i,,j > k on k
i > k, (2.2.11)
(2.5.4),
- d$)/li$), ;
(2.5.10)
(i,j ) ,
by by (2.5.16)
(2.5.15), (2.5.21)
G k
= BkMkBk
&!k-
1, j + k -
ei'Gkej is
2.5.14 (2.5.2), (2.5.3), l/uiyk- l , j + k - 1 , arik-
(2.5.4) &'Bkej - 1 1, j + k -
ek'BkVk- 1 q(k) eLA(k+'). # 0, p # i, (e:Bk& - l)(&'&ej - 1)
29
2.5. Minimizing the Total Number of Nonzero Elements in EFI
(2.5.22)
;:2
ei’G,ej
=
la$!k-
l,j+k-
> E,
1.J
k
Gk
G,
G,
B,(M - 6Bk‘)Bk 6 1-6 6 on
by Lks
ck,
O
< 6 < 1,
Bk
by
n-k A(,+’)
A^(,)
30
2
The Gaussian Elimination
2.6. Storage and Use of the Elimination Form of Inverse q(k)s
i?$) # 0,
>k
0, > k, ali") qik' # 0, > k ti$) # 0, i > q(kk) no a;\+ ') = 1 U Pk Qk (2.5.3) k a$+
(2.5.4), a;:+
l),
t
=
Pk
2n (2.2.12), (2.2.10), ((k)s by U
QkS
Pks
i?@ =
1.
Qk, (2.5.12).
(2.2.11) uks
by
((k)~
U.
A(k)
q(k)
((k)
k
1.3.
A(k'
by (2.1.1)
(2.2.1),
b 1969 ;
2.5,
A
2.7.
31
Bibliography a d Comments
2.7. Bibliography and Comments
by
al. by
on
by do no
3
CHAPTER
3
Additional Methods for Minimizing the Storage for EFI
3.1. Introduction
do ;
2. ;
33
34
3 Additional Methods for Minimizing the Storage for EFI
no
3.2. Methods Based on A Priori Column Permutations Q, P
(3.2.1)
PAQ
=
A,
A^ P
Q.
by
;
on
P,
Q A
Q
A. A
so DEFINITION B,,
rik’
cy)
2.5.
B,
(3.2.2) n-k
n -k + 1.
+ 1,
ei
35
3.2. Methods Based on A Priori Column Permutations
i;;)= (
(3.2.3)
p-
-
by
j,
(3.2.4) y y )
=
i
2:;)
=
( c y )-
i
(rlk)bl;) = 1,
i =
bL5) = 1.
(cik)- l)(rLk)-
2.5.14,
(j
A'k),
+k (a + k
-
A A
y$')s.
k n, on A
yj')
by
A - ',
on
5; p
ylip's,
A
is
j,
cy)
is
(3.2.3), by (3.2.5)
for =
(3.2.6)
dy) =
(d'jk' -
1i I l k ) ,
i
b$) = 1,
-
i
=
1.
36
3 Additional Methods for Mininlizing the Storage for EFI
A
A$%, A cjl)s.
yy's
AT)
$)
:
2.5.14,
(3.2.7)
ei)Gkej,
= i
ei'B,ej
i
=
1.
1 ej'B,'eiei) = ej'B,' C eiei) = ej)Bk'ln-,+ i i
=
ei'B,ej = 1,
(3.2.8)
=
X i e;,
(ej'B,'G,ej)/b'B,ej,
e,'B,ej
i
=
1, e j B, .
A by
,
I
c(jl)s, y y ' s
2,
A = AQ.
(3.2.9) A Ae, e,,
2
=
=
-
Ae,
2, =
AQe,,
I,
Qe,,
Q.
A
I,
Q. 2 by
cJ1)s, yJ1)s,
AJ1)s, by
37
3.2. Methods Based on A Priori Column Permutations
A(') = 2
(2.5.3), A^(k)
by = p A(k)
A(k)
(3.2.20)
k
3
1, by
Pk a
Fik)=
(3.2.12)
(a
Flk),
i
+k -
by
Idlyk,- 1,kl > E ,
i
Flk)
(3.2.2).
rlk)
(2.5.10).
E
F!k)
by
rik)
1966). n-k
(3.2.12)
A^(k) (i
+k -
+1
pik)
A^(k),
> 1, 7{k_+,'),
by
A(k+l ) (3.2.13)
by (2.5.2),(3.2.10),
A(k+')
Proof
A^(k) by 8,
8,
n -k by
(i
+1 8,
Bk+ (i -
6$),
(2.5.4).
Bk+
+ k - 1, + k - 1) A^(k) &. a!"!,- = 0, 6:;) = 0 a(k) A('+') (3.2.13) = Pi? ', rl!''') = I,k
i, j ,
38
3 Additional Methods for Mihh&z&e the Storage for EFI
1.k
&$!k-
hik) = 1
,Z o
= 1,
T(o)
b$) = 0. o
Bk A(k’ = 1
(3.2.25)
b!k) = 13
0) =
= 0)
= P(k)
- 1
plk’ - 1
3).
=
n -k
Bk
of
(Pik)-
-
hik! = hi:) = 1.
k)
(Pik)
Q)
-
-
k),
Fll)
=
8,
f‘k’ - 1 4) ( n - k ) n ( - lk ) ( 1 - n - k
’
Plk)
al7kk)I.k = 0,
on
r:”
ril),
=
B,
ei’B, Vl
A‘”
=
A’
k, Plk) Pi.4) = p
jz(k). k i
(3.2.26) n
-k
1
Pik)
+1 rik)
k. k
Bk.
<
39
3.2. Methods Based on A Priori Column Permutatiom
by (3.2.13)
7ik)s
(3.2.14)
rik)s. good
k, k
rik)s Bk
rik)'s
A(k)
1.3
(2.5.2) rik), :
cy)s,yy's, 7:'' = rill,
(2.5.4) 7ik)s
Ay)s
(3.2.2),(3.2.4), (3.2.5), Q (3.2.9). A'') = B, A(') ri') (3.2.2). k = 1,2,. . . , n (3.2.11),(3.2.10), (2.5.2), (22.3), A(k) A ( k + ' ) ; (3.2.16),(3.2.13), (3.2.14) ?Ik+ l)s. A A("+') = fi
0 = A("+'1
=
L,P,. . . L,P,A('),
(3.2.10) =
L,P,.
* *
(2.5.2),
LlPlAQ,
(3.2.9),
& = LnPn L I P l .
= LAQ,
A-'
A^
by (2.5.13). P Q
(3.2.1) no
A^.
40
3 Additional Methods for Minimidag the Storage for EFI
3.3. Desirable Forms for Gaussian Elimination
A
Ii - jl > p Ii - jl < /? bandwidth A.
aij = 0,
A aij # 0
band matrix. full band matrix.
B
1.3, B = A
on
full band matrix
2.55,
no b$) = b$) = 1,
Oi.
;
B, b$) = 1.
A A
A^
A^ by (3.2.1), All
A12
0
A22
0
0
0
0
A
(3.3.2)
A
* * .
A1.p- 1
A l p
A2.p-1
A2P
=
4
1
AP2
A,-
AP*P-
on Aii,
1,p- 1
A,-
1
Aii, i
1.p
APP
=
1,2,. . . ,p,
A,,
(3.3.1)
Aji,j
-= i, i # p.
3.10, no
3.4.
41
Matrices and Graphs
A^
P
(3.2.1)
(3.3.1).
A^ on 2.5.19,
(3.2.1), (3.3.2)
=
i #
(3.3.1), Aij = 0,
P
i
(3.21)
=
p
=
p.
(3.3.2) by (3.3.1).
A^ (1965),
et al.
(1969),
(1970).
Matrices and Graphs
3.4.
bij
by
(i,j)
by labeled graph 0,a labeled digraph bipartite graph R,, labeled row graph R,, R,
labeled graph
labeled
DEFINITIONS
n vertices edge [p,q]
labeled graph z0 edges.
q T,,
b,,,
b,,
1,2,. . . , n p
+
42
3 Additional Methods for Miaimiang the Storage for EFI
labeled digraph (directed graph) R, 1,2,. . .,n T, arcs. p q b,, = 1.
n vertices arc [p, q ] T,
labeled bigraph (bipartite graph) RE C, n z edges edge [p, 41 p
1,2,. . . ,n,
b,, = 1.
C
4
z
labeled
graph R, labeled graphs
*
1 0 1 = 1.
0,)
B
labeled
*
*
graph R,
*
0
*
zR
0,)
T,
* B, R, R,, RE,R,,
3.4.1
R,
pond
0
Fig. 3.4.1. Labeled graphs associated with a matrix.
on (3.4.2)
R
PBP
R,
=
B ;
*
3.4.
43
Matrices and Graphs
(3.4.2) (P
PBQ
=
B RE
Q
P on B Q
R,
(3.4.2)
(3.4.3) (3.4.2)
P B * B'P'
no
=
8 * B'
Q ' B * BQ
R, on RR R,, R, R,, RE,RR, R,
labeled bigraph, rowgraph,
column graph.
=
B' * 8,
R,
B
Q
P
graph, digraph, (3.4.1)
B
(3.4.2)
R, R,
RE.
R, ,
RB
DEFINITIONS p q by R, R, , Q C , R,, adjacent uertices. ul, u 2 , . . . ,u,, u,+ I i = 1,2,. . . ,cr, ui ui+ u1 u,+ connected by path [ u l , u 2 , . . . ,u,+ 1] R, R,) length cr. [ul, u 2 , . . . ,u,+ 1 ] starting vertex u1 terminating vertex u,+ 1 , cycle R, R,, R, directed cycle R, length 0.
44
3 Additional Metbods for M!himiz@j tbe Storage for EFI
R, R,, R,,
R,,
n,
n. R(R,, a,, 0,)
cr
R(R,, RR,R,) R(R,, R,, RB) R, R
B. B@
0, i
B.
0,
on. (3.4.4)
W=B@B@I,
(3.4.5)
W"+'
(3.4.6)
=
w = * w,
cr = 1,2,. . . , n - 1,
e:W"ej
=
1, by
cr.
Proof
cr =
e;Wej
=
cr,
cr
+ 1.
(3.4.7)
(3.4.8)
w;"
=1
w& = 1 cr
1,
wij = 1
wyp = 1
wpj = 1
p.
by
p
wpj= 1
p
3.5.
45
'The Block Diagonal Form
p # j.
by (3.4.5).
p
w,, = 1
=
i
(3.4.8) by
0
n
+ 1.
n
A
3.4.4
(3.410)
W=B@O,
pa+1 = pa * p
(3.4.11) 0
= 1,2,. . . ,n
e;W"e, = 1,
0.
Proof
3.5.
by
(3.4.4),
w.
The Block Diagonal Form
A
(BDF). BDF
by (3.3.1)
# j,
A^
=
0
BDF
(3.2.1) QR
B
(Aiis) (3.4.2),B
B
R,
QR
Q,)
B
P
Q,
1962 :
1967~).
(3.2.1)
46
3 Additional Methods for Minimizing the Storage for EFI
(3.5.2) (3.5.2)
W=B*B'
W Z h += ' W Z h* W Z h ,
(3.5.3)
h
=
0,1,2,...,
h, WZh1+'= - WZhl = F
(3.5.4) e;Fej
=
1
j
B. Proof
3.4.4,
by
*
*
W = ( B * B') @ ( B * B'), @ 1 = B * B',
R,
3.4.4
ei'WZhej= 1, v
8,
v
v
R,
< n.
h
2h > v, W z h
h, ei'WZh1ej = 1
8.
2h' 2 n,
v
< n.
do =
v
WZh1.
1962 ;
1962 ;
A
W
by
j, w,,wPj p= 1
i
j
3.5.
47
The Block Dingod Form
+
+ 2,. . . by
q. n p= 1
WlPWW.
no Jj
F,
=
ei'Fej = 1
J 1=
1
F
8,
B
8
on.
3.5.1 3.5.1
(3.5.5) (3.5.6)
F*B=F Jj
= e,'Fej = 1,
8. (3.5.6)
Proof
Jj = 1,
J p=
bpj = 1,
3.5.1,
Jp =
p. i
1
8,
p
p,
i.
Aj = 1
p
48
3 Additional Methods for Minimizing the Storage for EFI
B
3.5.1,
Jj
=
1.
F, B
3.5.1,
(3.5.2)
=
8.
on.
* B,
3.5.1
(3.5.7)
3.5.1, e,’(B‘* F
(3.5.8)
B
i
B.
* B)ej = 1,
(3.5.2), (3.5.3),
Proof B’ * F * B
(3.5.4)
- * ( B * B’)]* B
=
B’ * [ ( B * B’) * ( B * B’) * * *
=
(B’ * B ) * (B’ * B) * . . . * (B’ * B)
=
(B’*B)b,
Q
> v. Q,,
3.5.1, ei’(B’
* F * B)ej = ei‘(B’* B y e j = 1 by
i
(3.5.8) 3.5.5
(3.5.6), 3.5.7 3.5.1
3.5.5
3.5.
49
The Block Diagonal Form
B. 0 1
1
0
1 0 0 1
B=[ 1 0 0 1
0 1 1 0
1 0 0 0
0
0 1
1 0 0 1
1
0
1
1
0
1
1 0 0 1 0
1
1 01. 0
1 0 0 1
W 2 -= W ,
F=
F*B=
1
0
1
1
0
3.5.1 =
w I 1 = f41= wdl = 1)
3.5.5
/Iy
1 0 0 0
0 0 1 0
0 O 1 O0
011,
0
1 O
0 O 01, 0
0
0
0
0
0
0
1
1
50
3 Additional Methods for Minimizhg the Storage for EFI
-
8 = PBQ
1 1
0 0
1 1
0 0
-
=
i :I
0 0
0 0
The Block Triangular Form
3.6.
by(3.3.1),Apj=O,j#pandAi,,i=1,2,~~~,pare A^ Triangular Form
(3.6.1)
PBQ
=
B
(3.6.2)
PBP
=
8,
B (3.6.3)
8 PBQ
=
8, P
P
=
Pb,
=
Q
no
of n
bii = 1,
QP.
i = 1,2,. . . ,n
of 1962,
51
3.6. ’zbe Black Trinngulu Form
(3.6.4)
ALGORITHM n
B
V,
=
U , = V,’,
= i= 1
P,
=
Q,
=
k
I,
1.
=
STEP 1 i, (3.6.5)
bij = 1,
(3.6.6)
eikB&
=
+
1,
= 1,
+
=
no i
go
(3.6.5) ak
Uk
/?k
Pk Qk.
k by k
+ 1.
k
=n
+ 1 go
2,
k
Remarks
(ak,B k )
B”
(3.6.1).
Pk
ak
B’,
B (3.6.5)
(3.6.6)
B
B’. B
STEP 2
(3.6.7)
B’.
k =n
+1
52
3 Additional Methods for Minimizing the Storage for EFI
If k
=
n
+1
B=
3: B(")
go
3.6.1 on on
B("+l)
Remarks on Fig. 3.6.1 12,
-
k
box do
1
SR =
-
=
SC.
SR in
on
Qk by using
B(k)
& El(')
pk.
k by k
f
1.
k C n?
3
Fig. 3.6.1.
3.6.4.
Flow chart for creating a diagonal of all ones in
@').
53
3.6. The Block Triangular Form
box 12,
B("+
a
on B'k'
B'k' e;B'k'ej = 0 B(k+')
i,j 2 k. B(k) LICC.
3.6.2.
Fig. 3.6.2. Chain from northeast to southwest comer.
k
+j
,
+j z +j , + k
by 11
10
3.6.1 no LICC B(k'
box 11 to
54
3 Additional Methods for MhMzing the Storage for EFl
STEP 3
Qk= 8.
Pk = P
on
0
21
R, R
C A
by
maximal transversal n,
n.
P
(3.6.8)
B T F 8,
on
THEOREM BZhf1= B2" * BZh
(3.6.9)
hl BZhl+'= BZhl = F ,
(3.6.20) e,'Fej
=
1
R, Proof ei(B"ej = 1
3.4.9 v
@I =
0,.
i
v
R,, 2h 2 v ,
BZh
hl e,'Fej j.
=
1
v ,< n,
55
3.6. The Block Triangular Form
B
3.6.8 3.6.4, (3.6.10) by 3.5.1,
(3.6.9)
e.'Fe. = e.'Fe. = 1 1 1 I 1 i
Q,
e,'Fej
=
B
8
F
B, 1962) :
ej(Fe, = 1,
B
B.
F.
on.
B =
B
F'
BDF. 3.5.)
B by F
E
F
labeled condensation digraph Q,
F
B.
by emitter isolated
(B
0,
no Q,
P
as,
56
3 Additional Methods for Minimizing the Storage for EFI
a,
F)
B"
on. by
B
p, B
BTF on by
B
B" B,
B
no
B STEP I
B no
B". STEP 2
B"
B:
1
on.
57
3.6. ”be Block Triangular Form
by collapsing
Boolean
1 0 1 = 1.
sum of vectors by
1
2
-
2
I
X
X
T
X
X
3
-
4
-
5
.
6
-
7
3
4
5
6 X
.
X
Ij 7
.
X
X
x
X
L
Fig. 3.6.3
by
3.6.3
by
1. 1
2.
3.6.4. by x , by +.
by -,
by
3 3
a
3
7 7
7
2
3.
58
3 Additional Methods for M i-;
Order into
-
1
2
3
4
5
.
X
I
X
X
.
2
X
X
.
.
.
I
3
.
X
.
X
5
4
.
.
4
5
...
X
X
X
3 1
1
7
.
t
X
X
.
6
2
.
-
.
a
.
.
.
.
the Storage for EFI
6
.
. .
X .
7
.
X .
. X
.
.
. .
X
Fig. 3.6.4
no
3.
by 1,
[l, 2,1]
1 2 1 by 1 2
2 1
+’s
2 1,
2
2.
1
2 1. 4.
[l,6,1] 1.
1
1
6 6 5.
1
6
1 3
6
6
of
1
1. 5
6.
4
5.
5
4
7.
4
5
no off
4.
3.6.
me Block Triangular Form
59
B,
(3,3) (7,7) (6,6)
P
(2,2),
B
(5,5)
(4,4)
(3.6.2)
by
P = ( e 3 ,e7, e l , e 2 , e6, e , , e4) B by
3.6.5.
,.
B=
. .
H
X
.B
Fig. 3.6.5
B.
B
B
3.6.6.
Fig. 3.6.6
3.6.3
60
3 Additional Methods for M i r ~ h h h gthe Storage for EFI
no
1
3
7 2
no 1, 2,
6
5,
3, 4, 6
5
4
7.
P = ( e 3 ,e7,e l , e 2 , e6, e5, e4) 3.7.
3.7.
The Band Triangular Form
A
b b
B
0 c /? << n
bij = 0,
-j
by
on
B be
pi = i - qi,
(3.7.1)
= 0, =
qi < i, qi >
P,
+ 1 is 3.5.
no loss
FIRST METHOD FOR PERMUTING B TO BNTF P (3.7.2)
Q
be
B = PBQ,
> b,
61
3.7. The Band Triangular Form
B
8. P
4,
i
4,
4, = 0, pi 8.
B. B
a = 1,2,.
no
.. ,
B. pi
B
pjis, p i. - p j.i s =
pji,
4.
2
1
Pjisj
pi - pjim<
on
r#Ii 2 0,
pjit
< pjit;
- pjit < 0, - pjia
<
a.
bij = 1,
pi,pj,
(3.7.3)
(3.7.4) (3.7.5)
(3.7.6)
pj
- pjie - 4, < 0; # pi,
# pj
a = 1,2,. . . , r i
#
62
3 Additional Methods for Minimizing the Storage for EFI
SECOND METHOD FOR PERMUTING B TO BNTF on on by
B,
(3.7.3)
4')
(3.7.6).
B
ri
c;')
by (3.2.2)
=
dl), cj = c;'), i
=
bij = 1,
hi (3.7.7)
2
-
B
p 8,
E(8)
as i
E(ri)s
n
1
E(cj)s E Ai
cjs
i,
(3.7.7),
E(d,/ri)s
dJri.
i
ni
i,
cis,
by
E Ai
(3.7.7) (3.7.8)
xis
as
E(ri)s
E(rJdi)s
Mi by
ri, ni,
ri/di
63
3.7. The Band Triangular Form
by (3.7.9)
Mi
=
ri
(4
+ 6 2 + $xi
$
6 6(ri/di),
ri, E(Mi)s
$xi i
Mjs Mis (3.7.10)
M j = cj
(01
+ 6 2 + $nj
dj (3.7.22 )
di dj =
xii
bij = 1,
i
i
by
nj
(3.7.8),
C Ti2 (3.7.22)
:~7
=
(2) 2
2-
bij = 1.
i
Cj
as j
E(Mj)s
i
E(Mi)s
j
E(Mj)s
B
Mis
Mjs Mis
Mi s,
B Ic/
6
B
of 6 A
=
7’/n2
$
=
2
(7
6
I)
64
3 Additional Methods for Minimizing the Storage for EFI
B, E(ri) z E(cj) % r/n, E(di) z E(dj) x E(ri)E(cj)z r2/n2,
2ni
=
E(cj) -
bij = 1
cj,
r
r
2xi x 11
$=2
r2
a = - n2’ triangular
corners q , < p1 < p z q , < q2 < p 2 q1 < < q 2 , i > p2 ( p l , q l ) , ( p 2 ,q l ) , ( p 2 ,q2)
as hij = 0
B,
i 2p,
triangular corner
Fig. 3.7.1. Triangular corner.
3.7.
65
The Band Triangular Form
p , = q,
p,
=
q,,
pi
pi 2 p B
A,,,
pi = B.
i, (3.7.23)
by (3.7.1) B by
Biz - pi, > i, - i,
B
i, > i , ,
A,,,
i,
A,,,
Proof
pi, by Si1
pi, I
Bi1
(3.7.24)
=
Pi2
i,
Biz,
i,
- ill i, > i, ,
- (i2
< Biz.
Bit
Biz = pi, + (iz pi, - pi, > i, (3.7.25)
- i,,
c Biz.
Biz
A,,, ,
i,
(3.7.14)
(3.7.19, A,,, A,,,
i,
/3
B i, > i , ,
pi, - pi, < i,
i , c i, (3.7.26)
p 12. - p . 11= i
2
- 4,
-
i,.
66
3 Additional Methods for Minimizing the Storage for EFI
i,
< i < i,, pi, - pi = i, p,
p,
- i.
i, ,
i,
p,
+1
q, + 1, ( p , , q,)
q1 ( p l , q,), ( p , ,q l )
B p, p,
=
q,,
B
3.7.2.
Fig. 3.7.2.
Block triangular form.
B
3.7.13,
3.8.
The Band Form A
on
=
q,
67
3.8. The Band Form
2.5.19, on A
a (3.3.2)
A.
(3.8.2)
PBP
B.
=
qi < i,
pi = i - q i ,
(3.8.2)
biqi (3.8.3)
i
p
p
B,
= P
i
pi. B
Band Form no
p.
pi,
a
FIRST METHOD
A by 3.8.1.
fi
0
B
B
68
3 Additional Methods for Minimizing the Storage for EFI B
B X X X . .
X X . X . X . X . X
...
. X . X X X
X
Fig. 3.8.1.
8,
by 4
1,2, . . . , n
1.
p
2.
Vertex List B
n
pi = /jp,
p - p,
(Pi+ ( p -
go
x 's,
8
< p,
i < p),
7.
2. If
go
7.
3.
go 6.
4. go 6.
3
:
4
so 1 5. =
1,2,. . . , n,evL(j)
A^
= PAP'.
69
3.8. The Band Form
6.
4
3
go 5.
7. go
1.
SECOND METHOD
1969).
1.
i pi,
R pi
i,
pi, =
pi
3.8.2 1.
2.
2*m 2
B
7*
3*
5*
8*
Fig. 3.8.2. Example of a vertex renumbering scheme.
1*
70
3 Additio~lMethods for Minimizing the Storage for EFI
3.8.2
2*, 4*,
2, 3,
9*
4,
3.
2, 3*,
on.
3,
2 5;
3.8.2 4*)
3 6*
6*, 5*, 5* 8,
6, 7,
5,6,7,
8
1
4.
R
n
R
as 2, 3 , 4 5.
B
B
A^).
3.8.3, 3.8.2. 8
5.
B
B I * X X x 2 * x x x x x x 3* x x x 4* x x x x x 5* x x 6* x 7* x 8* 9* x x x x x x x x 10*
\
X X
x x x x x x x x x x
X
x x x x x x x x
I x x x x 2 x x x x 3 x x x x x x 4 x x x x x 5 x x x x 6 x x x x x 7 x x x 0 x x X X X X 9 x X X
.\
10
Fig. 3.8.3. Matrix B and its permuted form 8.
X
X
X
)
)
) )
71
3.8. The Band Form
by Pmin
pmin pi,
i,
d pi,
Pmin
1
+ tpmax,
p,,,
B
B.
THIRD METHOD An
Pi
on
(3.8.2) 1968).
1.
B
B
B B. Row Interchange
RI
1,2,. . . ,n,
2.
by n-1 1 (1,2), (n,n - l), (2,3), ( n - 1, n - 2), . . . , up
72
3 Additional Methods for Minimizing the Storage for EFI
no
3.
no
B
P,
RI(j)
+
j = 1,2,. . . ,n,e,,(,)
FOURTH METHOD FOR REDUCING THE BANDWIDTH
length of their intersection i
vi
p vi
3.8.4
3.8.4.
1 < i,
i’s.
< fl +
i, i, ; i, , 2p
i,
+1
i, n
- 2p.
i,
i, i,.
1
28 + 1
vis
i i
n
- 2p. ui
73
Band Form
3.8.
n - 28
28
+1 +1
n.
@
B (i, j )
i
vi
B
by
(3.8.4)
vi = e i ' i W ,
V
by @
1. (3.8.4).
vi
2.
p,,, :
z
n)/2n (p,,, - 1)/2 on
(t-
8
on
no
3.8.4
vis
3.
28
3.8.5). vp ep)@ei # 0 ei'vej# 0
vp = p.
vis by by
vir
p j
no q $ NW
e;Weq = 0,
NW
74
3 Additional Methods for M-
the Storage for EFI
NW
SE
Fig. 3.8.5.
a
a
vis on on 3.8.5. 4.
3.8.5) :
ei'V = 1,
V
ie
0, p
j~
=
NW.
: E
3.8.5. 5.
3 4
P
B=
75
3.9. Other Desirable Forms
3.5, 3.6, 3.7,
3.8
3.9. Other Desirable Forms 3.9.1 1971). Singly Bordered Block Diagonal Form Doubly Bordered Block Diagonal Form Bordered Block Triangular Band Triangular Forms Singly Bordered Band Form Bordered Band Form 3.9.1 SBBDF
DBBDF
BBTF
BBNTF
SBBF
DBBF
Bordered Doubly
Fig. 3.9.1. Some simple desirable forms.
3.9.2
B
1966, 1968).
by
76
3 Additional Methods for Minimizing the Storage for EFI
Fig. 3.9.2. Two other desirable forms.
on ;
attachment set
1965). 1971, p. 125). B.
vi
vi
(3.8.4),
vi B).
vis et al., 1970).
3.9.3). 3.6 3.9.3.
3.7
77
3.9. Other Desirable Forms
I
I
Fig. 3.9.3. Modified forms of BTF and BNTF.
3.9.3. by
3.7.13 3.9.3
no
3.5
3.6) 1971b),
(1969)
3.6). by
[l,4,3,6,5,1].
3.9.4. no
parallel 3.9.4,
no
b, c,
d.
order
78
3 Additional Methods for Minimizing the Stornge.for EFI
1
I
2
3
X
5
6
X X
2
X
x
x
X
x
x
X
3
x
4
5
4
x
X
x x
6
x
Fig. 3.9.4.
;
c
2 - 1 = 1.
3.9.5,
Order
I
4
3
6
!
5
0
B-2-E
I
B-E
i
I
E
IB-c
3
E
a
~
b
B
d
Fig. 3.9.5.
3.9.4
E [6,5]
d
3.9.4, 5
1
79
3.10. Inverses of BTF and BBTF
on. 3.9.6. 5
I Fig. 3.9.6.
1
X/Torn
4
3
element
2
6
m x El
The matrix associated with the relabeled digraph.
3.9.6
3.10. Inverses of BTF and BBTF A,,, i
by (3.3.1). 1972; 1.
=
1,2,. . . ,p
1972).
i = p - 1, p - 2,. . . , 2 , 1
A,,
by
elimination
A,,
Uii APi Gaussian A,,.
U,, A,,
< i.
Ajps,
< i.
80
3 Additional Metbods for MinimMog tbe Storage for EFI
2. Up, Aj$,j # p
I
Up,
no ji,
j
i # p.
i, i = p, p - 1,. . . ,2,1, :
Uii.
A,,
Uii
I
Aji
0
< i. A j i , j # i.
no
U,,,
3.11. Bibliography and Comments
1,4,
3.7
Q, 3.8 to
et
good 3.9.2
by
3.11.
81
Bibliography a d Comments
1961;
CHAPTER
4
Direct Triangular Decomposition
4.1.
Introduction
z
A U, (4.2.2)
A
=
ZU.
1968 ; (4.2.2)
A - 1 = U-1z-1
U-'
t-' 83
84
4
Direct Triangular Decomposition
2 =
x
b
(4.1.3)
Ly
=
(4.1.4)
ux
=y
y
b
no by
x,
2. 2
Ag)
4.2.
The Crout Method
2
(i,]]
by lij
U
U
k = 1,2,. .. ,n. L U
k
k- 1
=
1,
+ p = 1 lipUpkr
i
> k,
> k,
k- 1
(4.2.1)
Iik = aik
-
1l i p U p k ,
p= 1
lkp = 0
p > k, k- 1
ukk =
-1
> i, upk =
lip = 0
uij,
il k.
1,
ukk = 1,
4.2.
85
The Crout Method
U
k-1
k-1
U U
E
E
?I
by
(4.2.3)
i = 1,2,... , n ;
1.11 = a.11,
U
(4.1.1)
U
(4.1.1)
Z ll1el’, (4.2.4)
ulj = alj/lll,
j > 1.
k = 1, (. . .) = 0, (4.2.1) 4.2.2),
E
L2>
(4.2.3) In
(4.2.4)
U
Okk
7
Fig. 4.2.1.
4
2
Storage for the Crout method.
4.2.1
k
- 1
el.
86
4
+ U, , U,,
U
k
U,]
-
Direct Triangular Decomposition
z
1
I,,
U, (4.2.1)
a,,
E,
[?] [
(4.2.5)
A,
lkk = a,,
li+,,,
A, "k]1 -
=
1
[;:]., by (4.2.2)
= ei'Az1.
U, (4.2.6)
A12 =
(A12 - L Z u 3 ) / a k k ,
1
ukJ+,= Al,ej.
U
z,
:
E, (4.2.7)
U, (4.1.3)
(4.1.4) lkk,
yk =
(4.2.8)
X,
f
= y, -
U, U
ukpxp?
k
y
k
=
:
x
1,2,. . . ,n
= n, n -
1,... , I ,
p=k+ 1 0
n
p= 1
p=n+ 1
1 (..-) (4.2.7)
1
(
-
0
.
)
y
(4.2.2) by (Alb)
(4.2.2) =
b,
up,"+ = y,,.
by
1965). (4.2.1),
(4.2.9)
llskl
=
11ik1 3 I
i 2 k,
li,
87
4.3. Minimiziig the Fill-in for the Crout Method
by
i
E
>k
of A
P =
O (4.2.ZO)
lkk = 0 lsk
2, =
4.3.
U
L-
Minimizing the Fill-infor the Crout Method
n-k Bk
+1
88
4 Direct Triallgulu Decomposition
4.2.1 (i,j]
by b!:). b$), i < k, 2
Bk b$),i 2 k, <
(4.3.1)
I\k =
by Nk b$), i, 2 k.
4,
sk,
sk * 4,
* 1
+ 1 = 1.
iik
Ak by
Ak = & @ Nk,
(4.3.2) @
n -k
1 @ 1 = 1.
+1 =
YA
(4.3.3)
E(k)
(4.3.4)
F(k) = Ak I/'
I/
k
E(k),
F(k)
Cf)
:
(4.3.5)
Pik)
+ E:k) =
+ E$)), (4.2.1)
(4.2.2)
as+k-l,r+k-l
(k, Proof earAke_B
ea'Akep= 1, e,'Nkefl
l\k
ea'(Sk* q ) e p = 1 ea'Akep= 1.
(4.3.2) I\k
by (4.3.1),
ea'Nkep= 0 (/.?
+k-
4.2.1 sk,
Tk,
Nk
4.3.
89
Minimizing the Fill-infor the Crout Method
k- 1
1
lipupk
z 0 * ea’(Sk* q ) e a = 1,
p= 1
o!
+ k - 1 = i,
(i, ea‘Nke,= 0.
ea‘Nke, = 0 ea‘(Sk* Tk)e, = 1 (4.2.1), (i,
/?
ea‘Akep= 1,
+k - 1
k
no (i,
no
V‘A,es
Cr’.
(4.3.3), T:k)
no
o!
+k -
+k Ck)+ C!k) = E
=
+k - 1
(TLk)
+ CF)).
uSi,
+ k - 1,
i
=
+k -1
E
k- 1
(4.3.6)
2.3.
E
(4.3.6)
4.3.5,
90
4
Direct Triangular Decomposition
(4.3.6) 4.3.5 by by
B,
by (4.2.1)
(4.2.2)
on E.
1967;
al., 1970).
4.5.
4.4.
The Doolittle (Black) Method
z
U
1967).
1968; by
t
by i- 1
(4.4.2)
U
by
E,
(4.2.2).
E, U,
4.3.5,
Sk
U,
4.5.
91
The Cholesky (Square-Root, Banachiewicz) Method
2, U
by
by
(4.2.1)
i 2 k.
lik,
by
ZU
4.5.
The Cholesky (Square-Root, Banachiewicz) Method
=
,?p
U'U,
2
U
=
(4.5.1) p= 1
U (4.5.2)
ukk =
(
by k-1
akk
-
1
p= 1
k- 1
(4.5.3)
' k i = ('kj
- p=
1/2
u;k)
1 upkupj)
(. . .) = 0
/
Ukk,
k = 1.
U. uM 1965).
j > k,
U'U,
92
4 Direct Triangular Decomposition
1967). 4.3.5. (4.5.4)
Sk
=
&’, A,
(4.3.1),(4.3.2), (4.3.3) (4.3.4), ij(k) =
(4.5.5)
(F(k))’. 4.3.5
(4.5.6)
?kk)
COROLLARY
=
(?ik)), (4.5.3)
(k,k)
as+k-l,s+k-l
Proof A 4.3.5
+ $,)
~ik)
a = =
(fik)
p,
(4.53,
+ ~ ; k ) > F:”) o
@.
=
on 4.3.5
I,,
by up,).
by by
by (4.5.3)
4.6.
93
Desirable Form for Triangular Decomposition
no
(4.5.2) (4.5.3)
no
A^
on 2.
4.6.
P =
Desirable Forms for Triangular Decomposition 3,
t=
’
4.2,
E
by (2.2.6),
.. . (2.2.3) L,- . .
-
- = I,,
(2.2.4) e,
1
94
4
Direct Triangular Decomposition
=
4.7. Bibliography and Comments
by
(1963), (1969),
(1969), (1971). 1967;
1972).
al. (1969).
k,
ukk
=1
Ikk
(1963), (1969),
=
1.
al., 1970).
(1963, 1968), (1971),
CHAPTER
5
The Gauss-Jordan Elimination
5.1.
Introduction
Gauss-Jordan elimination.
U
A-' Product Form
Inverse
95
96
5 The GnussJordan Elimination
5.2.
The Basic Method
b = b,
1963;
x
1965).
of A(') = A(k)
A(,)
k
= 1,2,. . . ,n,
A(k).
(i,j)
A("+') =
k-1 e, by
u$)
A(k) A @ +1 ) = T A ( k )
(5.2.1)
k
(5.2.2)
= 1,
3
+ ( [ ( k ) - ek)e;, by
((k)
(5.2.3)
[lk) = -&)/ui?,
[ik)= l/ui\).
i#k A(') =
(5.2.1)
A("+')= I , ,
T, - * . TZTlA = I , ,
of A
Product Form oflnuerse A-' = T, * * * TZT1.
(5.2.4)
((k) ')
by
1963 ; 1968 ;
1954; 1963 ; et ul., 1969 ;
1962; 1966,1967a; et ul., 1969).
97
5.3. The Relationship between the PFI and the EFI
5.4. =b
no
& A(k) (5.2.1). A(k)
A(k+')
(5.2.1),
PFI.
2.4
5.3. The Relationship between the PFI and the EFI 2.2
U
by
by no
U
by
U U-
U
U -'
by
k
k,
k
U
U
U -' U-' U -')
U -' by
98
5 The G a d o r d a n Elimination
U :
U k + '= ) Ok Uk), k
(5.3.2)
~ ( 1= )
(5.3.2)
u, U ( n + l )= I n
8, = I n
(5.3.3)
= 1,2,. . . , n,
+ t(k)eL by
f(k)
(5.3.4)
t!k)= 0,
[ui:)
(i,j)
i2k
-@,
i
U(k)].
0, = In
u - ' = 0, . . . O 3 02 .
(5.3.5)
GE
=
f!k)
GJE
n -k
(5.3.6)
& . .. T2TlA
Lk'"L,L,A k = 1,2,. . . ,n.
k
=
1,
GJE
e l by u\'/
k,
GE
(k +
by
+1
Proof
GE
0,
Lk, Tk,
et al.,
GJE,
+
(k +
;
n -k
on n -k Lk+1...L2L1A by
&+l...T2TlA
5.3.
99
The Relationship between the PFI and the EFI
(5.3.7)
LEMMA n -k = 1,2,..., n.
+1
Proof
.- -
Lk -
L,
+ +
n -k 1 n -k 1 L,L A & - . . T, TlA , 5.3.6, n -k
,
Lk
+1
L,
(5.3.8)
LEMMA
U(k)
A',' k = 2,3,. . . ,n
e l ' L I A= e l ' U , 5.3.6 0, = e l ' L I A = el'U = e , ' 8 , U = e,'U('); k = 2. 5.3.6,
by
k-1
Proof
el'"''
=
e l ' T I A=
k, e,lL,
L,L,A
=
e,l U , ek'A(k+l)= ek'T,,. . . T2TlA =
e,'Lk... L 2 L l A = e,'U
- ekru(k+l).
k-1 (5.3.9)
on
k
A(k+l )
U(k+l )
k-1
LEMMA
-
1
A','
on k
0,
T
Proof
k-1 k-1 U(k)
A(k),
8,
100
k
5.3.8,
(5.3.20) LEMMA
Proof
0k
U-
(5.3.3)
Ope, = ( I ,
-
it,
1
'
by (5.3.3)
&
(5.3.5),
(5.3.4)
+ t(P)e,')e, = e4,
p # q,
Opep= ep + P),
5.3.7,5.3.9,
5.3.10, :
(5.3.22)
e i q e , = eiOkek= eiU-'e,,
(5.3.22)
e/&ek = ei'Lkek,
i
i 2 k.
(5.3.11)
U-',
U (5.3.12),
on on U-'
5.4.
101
Minimizing the Total Number of Nollzeros in the PFI
U. PFI
EFI U
5.4.
U-'
EFI.
Minimizing the Total Number of Nonzeros in the PFI PFI
EFI, 2.3
PFI PFI 2.5 1963; 1966,
1963;
1965;
;
2.5,
PFI.
kk)
GJE as GE) GJE
k
s
sit),
k,
a:!)
1a:f)I E.
Pk
(5.4.1) a!!)
by
Qk
A(k) =
pk A(k)Qk
102
5 The Gauss-Jordan Elimination
(5.4.1)
(5.4.4)
(5.4.2)
A-'
=
QlQ2.**QnT,Pn.-.T2P~TlP1.
+1
n-k
Bk A(k) by A(k)
by
Bk 1967b)
2.5.5. (5.4.5)
THEOREM
i 3 k,
1,
@+k-
by (i, j )
Gk
(5.4.6)
Gk
= BkBk'Bk,
Bk'
Bk Proof (i, q
A(k) q + k - 1) + k - 1) j + k - 1) (5.4.1), (5.4.2), (5.2.2), q + k - 1) A('+
(5.4.3),
')
on 2.5.5, by
GE
n x (n - k
+ 1)
M
GJE
5.4.5,
(5.4.7)
COROLLARY s
2 k, t
=
p
+ k - 1,
as
GJE ut!) s
/3
by (5.4.8) 1.J
I@;+k-ll
> E,
i 3 k,
Zj
(E I n - k + 1),
5.4.
103
Minimizing the Total Number of Nonzeros in the PFI
&s A("s
LI(~)s,
on A
on
(5.4.9)
i 2 k,
a!S+k- 1 ,
by
g!;'
(5.4.20) (5.4.22)
= (rjk)
-
rik) = ei'Bk&,
c y ) = V'Bk
n -k
V Zj
jr
+1
n
In-k+l.
rik)
Proof
+k-1
cy)
A").
+k (rik)-
A(k)
-
g$)
e k
ei'V = &'Zj #)
=
(eiBk& -
= ei'(Bk&
(5.4.22)
e k =
-
- V)(V'Bk -
K')f?j,
(BkG - V ) (V'Bk - &').
5.4.9, (5.4.23)
)2;:
=
ei(ekf?j,
laifj+k- > E.
=
1,
104
5 The C a d o r d a n Elimination
(5.4.13),
a!fh+k-l
on 3.2, k = 1, (5.4.11)
(3.2.2)
C$')S,
+ n- k r(,)s
n-k
;
by n - k
n by n
+1
-
k
+1
n
k+1 3.2.12.
n -k
(5.4.24)
2 k, ?!k)
a(k),
A(k- l),
+1
=- k, Flk+l),
by
Proof
3.2.12.
cy)s, yy's,
(5.4.15) 1967a ;
(5.4.16)
P
A
(3.2.1l), (3.2.13) 1968).
3.3, Q
-
A^
=
PAQ
P(k)
(3.2.14)
lj')s, by 1966,
5.6.
105
Bibliography and Comments
5.5.
Desirable Forms for the GJE on
A :
3 A
3.
2,
lo
Q
I
=
A
=
0 A,,
0 A42
A,,
0
0
. A43
A44
A,,
A,, A,, ,A,, , on A , , , A,, ,
A,, , A,, .
A,, by
5.4.
5.6. Bibliography and Comments on
106
5 The G a d o r d m Elimination
(1963), Wolfe and Cutler (1963), Dickson (1965), Baumann (1965), Tewarson (1966, 1967a), Orchard-Hays (1968), Dantzig et (1969), Brayton et (1969), Beale (1971), and de Buchet (1971). A comparison of the EFI and the PFI in terms of fill-in for randomly generated sparse matrices is given by Brayton et (1969).
CHAPTER
6
Orthogonalization Methods
6.1. Introduction
Gram-Schmidt, the Householder, and the Givens methods
6.2.
The Gram-Schmidt Method m x n
n
Schmidt method
I07
m
n.
Gram-
108
6 OrthogodizationMetbods
0
1962,
A0
Q
0
AQ0
Revised Gram-Schmidt (RGS) method k = 1,. . . ,n, A(k) A(') = n A(k),
n
A("+')
k-1 n-k by (i,
A'" ;
a$)
').
a?)
A(k), :
,kth
column
I
I
x x - - - x x -
. kth row
I
I I
Fig. 6.2.1. The elementary matrix
0,at the kth stage.
0k by (6.2.2)
0, = I,,
+ e k ( P - e;)
109
6.3. Minimizing the Nonzeros in the RGS Method
)(!'
(6.2.3)
Ok !("s
on
on
o k
(6.2.1),(6.2.2),
(6.2.3),
RGS
m = n,
(6.2.1)
A-'.
RGS
6.3. Minimizing the Nonzeros in the RGS Method (6.2.4), aQ),
n -k
+1
up)
by
RGS A(k),
Qk
by
110
6 Orthogonalization Methods
I,. A(,+ 1)
(6.3.2)
a?) by
a$)
a(,),
=
p O ,,
k
=
1,2,..., n, (i,
0,
by
)'$c
(6.3.3)
by) n -k
B,
+1
A"' by
by
+k -
(6.3.4)
kk) by G,,
Gk = (B,' * B,)B,'B,,
(6.3.5)
*
B, by
Proof
+k-
by
+k -
6y)'bjk', 6y) b$" * by' = 0,
B,. no by
111
6.3. Minimizingthe Nonzeros io the RGS Method
6jk)'bjk)= 0, by (6.3.6)
= e','(Bk' * Bk)Ek'Bkgl, n-k+l
1 Zjz/ =
+ 1,
i= 1
=
z;Gks?,,
b',k)'bp)= 1 A(')
6ik)'bik),
by)
RGS gj:)
;
gl:).
gk!)
1
k - 1, A(k). B,' * Bk
[e','G,i?,]
gi:) =
=
(6.3.1),(6.3.2),(6.2.2),
I
') 3
&'Bk
k. (B{ * B1)B,'B1
s=3
RGS (6.3.3)
RGS
+ k.
112
6 Orthogonalization Methods
A(k) 6.3.4.
k by
6.3.4
(6.3.6). (6.3.9)
COROLLARY Proof bjk”by)= 1
(6.3.20) THEOREM aZ.ki+ = 0 Proof
bjk)‘bjk)= 1, =
gj:)
=
0.
bjk)’ * b y ) = 1
1,
g$) = 0.
6.3.8,
a$)
=
=- k.
(6.2.4), a$+ 1) = =
1
a!:) = 0
(k)
(k)
i # p,
> k,
-
a$
=
2
0,
kpk
113
6.3. Minimizing the Nonzeros in the RGS Method
2,
ei
(6.3.2Z)
n -k
rn
V,
$)
+ 1,
c y ) = V’BkZj.
= ei’B,T/,
A
B,
(6.3.22) A L G O R I T H M
A.
R,
n k 1.
cy)
=
1.
c:,) =
b$ by
2. (t + k k = n, go
2.
cy),
> 1, go
j =
0
b:) = 1
R,. 3,
k
k
go
G,
n -k
+1
R, G,
,
R,, . 3.
A R, +
,
,
R,, ,
A.
Remarks
1 A
6.3.
2,
A
1. on A ,
RGS
,
In-,+ ,
I,
+ 1.
114
6 Orthogonalization Methods
A^ A^
3.
6.4.
(6.4.2)
=
:
The Householder Triangularization Method n A(k+' )= HkA(k),
(6.4.2)
Hk=lm-uk
k -1
=
1,2,. . . , n
9( k )9W',
qck)
by
m
(6.4.4)
fikZ
=
1
c(k
= f i k 2 f fik&)
i=k
A(') =
flk
&).
n n
by rn 2 n). rn = n. (6.4.5)
Householder Triangularization A("+') m -n n-1
H,H,,-,**.H1
=
n
H H
by I?,
6.4.
I15
The Householder Triangularhation Method
(6.4.1)
H A ( ” + 1= ) H A =.A =
fiv
A D - ‘ = 8’.
(6.4.6)
8‘
O-’ (6.4.6),
1965). (6.4.5);
H
qck)s
aks
1968a). :
(6.4.7)
by (6.4.1) (6.4.4),
k a,+’)
Proof
=
- 1
T
Ack+’)
A(k)
a!:+” = 0, i > k.
Bk
(6.4.2)
k
(6.4.3),
Hk I, ; (6.4.3)
q(k)’aik) = (aii) f Sk)ai7+ =
a$+ l ) = 0, > k.
& Bk&)
+
(6.4.1), (6.4.4),
rn
1
i=k+ 1
Bk2 =
ak,
(6.4.1)
(6.4.2),
- .ik) - qCk)
aj;kk+
1)
=
- 1
-+ Bk
116
6 Orthogonalizatiot~Methods
n A(k).
n
-
k
k
-
+1
+1
by
n-k B, A ( k )by bjk) = BkZj Z;BkZj = bj?)
In-k+
Zj
bikl = 1,
(6.4.8)
by (6.3.5).
Gk
(6.4.1), (6.4.2), (6.4.3),
Proof 1)
4
=,
(6.4.4),
4 > k,
- a; I ( #k)"af))Q(k),
m
C a$)a$) ~f:flkaiy,
9W' a,, (k) =
i=k
ag) # 0,
bikI = 1 i=k
=4 -k
A(k),
bik)by
A(k)
no
+ 1.
by)' * by) = 1, (bik)'* by))6y)'bik) hik)
bikY* by) = 1
q(k)af)# 0, as
6ik)'bik)= 0, by n-k+
1
(6.3.6)
c
=
1.
117
6.5. ”he Fill-infor the RCS wrsus the HT Metbod
u& = 0, u~k”u= ~ k0, )
fiCk)‘uik) # 0
u,
by
u
u$) # 0.
A(k)
(6.4.9)
Bk
Gk Bk
on G k . Proof In-k+
Pk by
Qk Bk by
PkBkQk,
(6.3.5) (QklBk’pk’
* PkBkQk)
= Qk’(Bk’
Qk‘gk(Pk‘PkBkQk
= Pi*Pk
=Q
(6.4.8)
k Q i
QklGkQk,
= Qk* Q i = PLPk =
In-k+,,
(6.4.9),
s 2 k, +k -
3 @d+k-
* Bk)B,’BkQk
#
A(‘+ ‘). B, do
on
6.5.
on
The Fill-in for the RGS versus the HT Method
fi’
no
118
6 Orthogonaliiation Methods
fi'
by H , ' H , ' . . . H,'
A
fi'
n
rfk)s
fi' fi'
uks
no
fi' by 6.3.4, 6.4.8,
RGS
6.4.9,
RGS
by
Gk
RGS
(n - k
+
Bk
(n - k
x
RGS
+
m x (n - k
+1
n-k A(k)
ffk)
RGS
A(k)
fi' RGS
by
6.6. The Jacobi Method
by
A("+'),
n-1
A(k) k-1 a$) (i, j ) a$) # 0, i > k u$) #
,i > k
$2
a{;), i
A(k) A(k),
by
> k. k
+
119
6.6. The Jacobi Method
A‘,’, (6.6.2)
R,,
= 1,
:
+ (t - l)(f?kek’+ e,e,‘) + w(eke;
(6.6.2)
Z = a&)/(&)z
0=
R,, p ) , (p,
+ abkk)Z)1/2
a$)/(ag
+
a$q1/2.
k),
by by 5, w , - w, r, A‘,’ R,,A(,)
(p,
RpkA(,) p,
i # k
- e,,ek’),
e / e j = 0, i # j ,
(6.6.1)
(6.6.3)
ei’RpkA(,)= ei’A(,).
+ (Z - 1)ek’ + We,’)A‘k’ = 7ek’A(,)+ oe,’A(k!
(6.6.4)
ek‘R,kA‘k’ = (ek’
(6.6.5)
f?p’RpkA(k) = (ed
+ (Z - l)ep’- wf?k’)A‘k’
- ze ‘A(,) - oe,’A(k).
A(k’.
(6.6.6)
(6.6.5)
(6.6.2)
f?,‘R,kA‘k’C?k = 7 4 2 - W U i i ) = 0.
(6.6.4)
(6.6.5), A(,).
R,kA(k’ q > p,
a$)
k q.
a$ = 0.
q.
# 0,
a$) = 0, a:
second order interaction third higher order interactions
k
p
120
6 OrthogoaalizatioaMethods
As
n -k by
Bk
+1
A , by
(s
+ k - 1, + k -
A(,)
(6.6.4)
on
i
(6.6.5),
on bl:)
bj:) = 1,
Bk
=
s B, e,'Bke,.
bf) = 1, bf)
=
1
by (3.2.6),
rp,
=
bf)
i
=
1
i
1bl:'ei'Bk&,
=
(3.2.2)
i
(6.6.7)
dik) = e,'BLBk&.
djk)=
(6.6.8)
j
:
e), bi:)
=
rjk)s (6.6.9)
rjk),
=
i
i
s
(s,j)
by
Bk f?,'Bk'* Bkej = 1,
bl:) = 1.
1
6.7.
I21
Bibliography and Comments
s (6.6.10)
yit) = =
1e,’Bk’* Bkej - rtk) et’(Bk’* Bk)& - es’Bk&, s
t
:
(6.6.11)
6.7. Bibliography and Comments
(1965). (1966)
(1967).
by
(1962).
by
CHAPTER
7
Eigenvalues and Eigenvectors
7.1.
Introduction
:
Method
Householder Method 6. 1965 ;
I23
124
7 Eigenvalues and Eigenvectors
aij = 0, i > j
+1 (Fox,
7.4, by
no
by by
The Givens Method
7.2.
by k-1
n -k-1 k
. . . ,n 6.6,
(7.2.2)
=In
+ (T -
lei+ 1
+
-
epe;+
1)
+
a$
k.
(7.2.2)
+
= pk
pk*
+ 2, k + 3,
7.2.
125
The Givens Method
ei‘Rpk= ei’ i # k
+
+ 1, A\k)
e;+ lRpkA‘k’= (ei+ 1
(7.2.3)
=
re; +
A(k’
+ (z - l)ei+ + oe,’)A(k’ A(k’+ we,’Atk), 1
eP ‘ Rp k A(k)= 7e ’A(k)- we;+ lA(k).
(7.2.4)
k
+1
p A(k’.
RpkA(k’ RpkA(k’R>k,
p
k+1 RpkA(k’.
e>Ay’ek = e,’RpkA‘k’R>kek =
( T ~ , ’ A( ~we;+ ) lA‘k’)ek
- 7 4 2 - wa(kk!1 . k = 0
7 = a (kk+) l , k . / [ ( a $ ) ) z
0
(k,
= a$)/[(a$))’
Aik)
-k
(aik!l . k ) z l l ’ z
+ (aiki
1,k)2]1’z-
e,’A‘:)e, = 0. by k + 2, k + 3,. . . ,n
(7.2.2),
A(k)
by A(k+l )
aiyk,t+k- # 0, s # t - 1,
+ 1,
by do 6.6
6.6,
k
126
k
7 Eigenvalues and Eigenvectors
k
+1
+1 A(k),A\k)
n
n -k
-
k
+1
Bk
A(k) by
by
(k + 1, k)
A(k)
# t - 1 by by
by
by
r
X X
Fig. 7.2.1.
Rotations for a band matrix.
X
127
7.3. The Householder Method
1
1
1
n = 10, 1 = 3,
7.2.1,
udl
on (6.6.1),
w
t
7.2.1, (7,3)
u41
R34
(10,6)
R9,10
(10,6) by
(3,l)
(4,l)
The Householder Method
7.3.
by 1965).
k-1
A(k)
k
. . . ,n
(7.3.1)
n
6.4.
[ A ( ' )=
A("-') A(k+1) = H k A(k)Hk ,
k
H - I - cck-
(7.3.2)
k -
n
=
1,2,..., n - 2,
lq(k)q(k)r,
q(k) fj!k) = 0, i
(7.3.3)
vk+ A(k)
=
a (kk +) l,k
by
<
f Bk, ij!k)= u!,k),. i > k
+1
+ 2, k + 3,
128
7 Eigenvalues and Eigenvectors
n
8,'
(7.3.4)
1
=
uk
(&))'3
= 8,'
f 8k'ikl
1, k
i=k+l
ukklI , , . n -k
n -k
Bk
A',) by
+1
by 6.4.8,
(7.3.5)
THEOREM
1
=
-
AW =
(7.3.6)
H k A(,)r
by
Hk
by Gk
Proof A(,)
by
Bk
n
-
k
n -k 6.4.8.
+1
6.4.8,
G,,
6.4.9
B, s# 3
3
(s
+ k, 3 + k A(,+') 3
-1 A(,)
+ 1,
= 1
A(,) A(,)
H,dk)
+ 1,
(s
by
+ k, 3 + k -
by H , , by H , . A")
7.4.
129
Reduction to the Hessenberg Form
A
S
Bk
es'(Bk'* Bk)v =
(7.3.7)
i
ej'(B,'
* Bk)v.
(6.3.7).
by
7.4. Reduction to the Hessenberg Form k
A(k) i >j
a$) = 0
Lk
k
-
(7.4.1)
-
1 j < k.
2.2)
+ 2, k + 3,. . . ,n
. . . ,n
+1
k = 1,2,
2
A("- ')
A('+') = L k + l A'k'L-' k+l,
=
1 ? 2 , . * . , n - 2,
(7.4.2)
9"' (7.4.3)
(7.4.2) (7.4.4)
(7.4.3),
Lk;ll = I ,
-
q(k+l)ei+l
by
130
7 Eigenvalues and Eigenvectors
A',) by
A(,+')
ui:) # 0, i > k
(k +
+ 1, a$) # 0 , j
n-k -1
>k
+ 1, (k +
n -k-1
A',).
(k +
:
by
Lk+l,
k
by
(k +
j
(k +
+1 I,;:,.
n
-
Lk+l.
n-k
n -k
k-1 Bk
+1
A',) by
by (7.4.5)
THEOREM
(s
(k + 1, k)
+ k, t + k -
A',)
by
# t - 1,
by
by L,+ G,
(s,t )
by # t -1
Proof
(k + 1, k)
A(k)
by (i
+ k,j + k -
E,
(i, j ) A',',
2.5.5,
no
(k +
Lk;ll
A',',
7.4.5
(k +
Lk;ll,
(k + by Lk;ll. n -k +1
A'k)
by
by
B",
N,
A','
7.4.
I31
Reduction to the Hessenberg Form
n -k
+1
I@'
N,. II -
by
k
+1
by
(7.4.6)
THEOREM
(p
+ k - 1,q + k -
(k + 1, k)
A',)
by
(k
Lk;ll,
by
+
by (7.4.7)
yb",' = e,'N,(N,
* Z'4)Bk)e,.
Proof A',)
k
6);:
=
e,'mk'(N,
Bk,
+k-1
I*
Bk
(i,q)
N, p
+k-1 k + 1,
q
* I'4'B&,,
7.4.5
7.4.6, (i + 1,j) aL2k,t+k-
Bk (7.4.8)
gi:)
+ y$
=
+ yly
i,j
(i,j)
Bk,
# j
1, j ) ,
+ 1,
G',).
A
on s
t.
s
7.4.5,
V,
(3.2.2)
t
:
B, n -k
132
7 Eigenvalues and Eigenvectors
(3.2.2)
(3.2.3),
(7.4.9) s
t.
7.5. Eigenvectors x A x = Ax (7.5.2)
( A - AZ)x = 0. x # 0,
A - II
(n Fox
7.6. Bibliography and Comments
x.
CHAPTER
a
Change of Basis and Miscellaneous Topics
8.1. Introduction
by
by
al., 8.2, by 133
134
8 Change of Basis and MiscellaneousTopics
A'). 8.3. A 8.4.
A
U 2.2.
8.2.
The Result of Changes in a Column of A on A-' A
A A
(5.2.4),
by (2.4.1) A by 8,.
A- '
A-
'.
FIRST METHOD A-
'
A,
A-
I,,
A-'A
(8.2.1)
+ ( ~ - ' d ,- e,)e,' = I , + (a:+ - e,)e,', =
I,
')
a:+')
A-' = [ I , + ( a ,
(8.2.2)
=
=
A-'a,.
- e ) e 'l-lA-1 4
4
EA-',
5.2, (8.2.3)
(8.2.4)
=
@)
=
-di:'')/dr
I, + ($4)
'),
- e,)e,'
i#q
tp) =
'A
135
8.2. The Result of Changes in a Column of A on A -
A-'
A-'. %(4)
3. A
3)
a A AA
SECOND METHOD
a,
a4 U,
(2.4.1) by
(8.2.5)
by (8.2.3),
c$q)= -6$y/d::, a:)
(8.2.6)
=
# q
[$)
L,..-L,A
L, . . . L , A (2.2.5).
,
L, . . L A
on U , , . I . U,L,. . . L,A
U , , . . U,L,.
. . LIA
2.2, by L, . L , A^ (2.2.10),
3
(8.2.3),(8.2.5), (8.2.6) U,, . . . U,L,. . .L,A e4 < U q , * * U,L,. . . L , A
,
;
44
by
L;.. L,A
by (8.2.6).
=
u,,, . . . U,L, . . .~ ~ 6 , . A("+')
(2.2.1
by
t(4)
,
136
8 Change of Basis and Miscellaneous Topics
UqUq+
. . . U,L,. . . L,A I,
U , . . . U,L,-..L,A
=
= u,..'U,-,$u,,,.'A^-,
(8.2.7)
u, . . . uq-1 $ U q i
=
1
U,L,."L,A^
* . ' U,L,
* *.
L,.
q
q1 :
< q, $, U,, a;! = u4,+,... uq_,$uq,,...u,~,...~,aq,.
1.
4,
2.
q , > 4,
$,
$,
a:!
=
fpq+ . . . u,L,. . . L,aq,,
U,,
ul., 1969).
THIRD METHOD
1972). As
al., 1969;
A^("+ = L, . . L , A A("+') U
OqA^('+')
by (8.2.8)
0, n-q eq
U(q)
(2.2.9), (2.2.10), U,
A^-'
uq,
by dq A^ U = L, . . . L,A,
$
Uq)= $OqA^(n+l).
U by eq, by eq' (2.2.1l), U ( ¶ ) - ' CJ, . . . U , = 0, k > 4 , (2.2.11). = @?-'q+0 L q q n***L,.
8.2.
137
The Result of Changes in a Column of A on A -
$
0,
k'.
0, = I ,
(8.2.9)
e4 ' +
+
e,$q),
.. U ,
e,'U,+
& I = )
'
A("+')ej= U e1 .7 1' # q,
e , ' O 4 P + ' ) e j = (eq' + @)Uej
.. U,Uej
= e,'U,+ =
'
e4 ' eJ . = 0,
U,+ ',. . . , U , e j ) o , = ej), j # q,
n
0,
a;)
')
=
6;:.
0 , ~. . L,a,, ~ . ',
6,ACn+l)
$
2-1 =
A,
iqr,
dql
f+0 L q n***L1,
~(,*l?l)-l~10
q1 q
U(q)by
U(q*ql)
by ebl $%L,,. . . L 1 2 , L,A. e,, 1972).
by (8.2.5)
(8.2.3)
(8.2.10).
(8.2.11)
2.2).
A("+') 6;) =
eq'oq#''+
U
-q
I, by (8.2.9)
(8.2.10 )
on
j # q9
oql
$I
f+,
L, . . .
0,
o,$"+
4
cI
U(,.ql)
q
(8.2.11); 4'
')
')
138
8 Change of Basis and Miscellaneous Topics
8.3. Kron's Method of Tearing C
n x
x n,
A
=
A
+ KEC,
by
A-'
(8.3.2)
=
[ I , - A-'KE(I,
+ CA-'KE)-'C]A-'. k'
A-' :
1.
n x
Y
2.
+ CY)'Z' = Y',
3.
A-'
a,
A-'KE. I
x n
- ZC)A-'.
=
k', =
=
Z, C, - a,,
A-'
A-'
=
1
C = ei,
A-'.
r x r,
8.4.
139
Bifactorization
8.4. Bifactorization U
I , by
2.2
u8102...8, -1 = I ,
(8.4.1) = 1,.
. . ,n
- 1,
8,
~0~. . . 8k-
U D l ... O k - l ,
ek' by ek,
U U 1 ... 8 k - l
ii
8,
U.
8,= I , + eke(')
(8.4.2)
(8.4.3)
-k
by
=
@)
0, j
< k, (Ol . . . 0,- ,)U
(8.4.1), (2.2.6) (2.2.7),
= -ukj,
&)
=
I,,
by (2.2.2),(2.2.3),
A(k+') (2.2.7),
k (8.4.2)
(2.2.4),
8,
(8.4.3),
Lks
A(k+')
Ll no
9
0 1 9
L2
9
02 . . . L,- 1 0,- 1 L, 9
I
> k.
7
9
2.2.
U by (2.2.6)
0k.s
140
8 Change of Basis and MiscellaneousTopics
8.5. Bibliography and Comments 8.2
by
by et
by
;
8.2,
et by
8.2
7,
7,
Lr,
by PI-’.
by
References
S. (1968). AIAA
6,728-730.
(1971).
pp. 17-24. (1965).
Comput.
8 , 264-272.
(1971).
I F I P Conf. Ljubljana, Yugoslavia. In
V. (1971). pp. 57-74. (1962).
Comm. ACM 5, 102.
on (1969).
Comm. ACM 12. 266-268. (1971).
pp. 169-190.
In (1965).
Trans. Power
Apparatus and Systems 85, 1 1 6 4 1 176.
141
142
References
(1971).
In pp. 105-126. Numer. Math. 5, 73-87. In pp. 1-16.
L. (1963). (1971).
(1970). (1962).
Numer. Math. 4, 238-252. (1971).
Trans. Circuit Theory (3-18, 4&50. (1971).
Math.
Anal. Appl. 35.48-57. (1967). by Nordisk Tidskr. Inlormations-Behandling ( B I T ) 7 , 1-21. (1959). 2), 1-29. (1967).
Proc.
55, 1787-
1801. (1969).
(1965).
on (A
2332, 1970 Math.
24,937-954.)
on
(1971). 25,285-294.
Math. (1971).
In pp. 21 1-218.
R.(1969). (1965). (1971).
Internt.
Numer. Methods
Eng. 3,379-388. (1963). (1965).
Proc. Power Systems Comput. Con$. London.
pp. 63-71. (1971).
pp. 191-210.
In (1966). 9.84-97.
143
In pp. I M A J . 10, Computing (Arch. Elektron. Rechnen) 9, Computing 9 SIAM Rev.
pp.
In
Comm. ACM 9,802. A
11. Comm. ACM 7 , 13.
on 6844,
444, 450,
476,
In
pp.
P.,
R. In
pp.
Math. Comput. 8,6467. G. Econometrica
144
References
(1962).
In
pp. 347-379. (1965). (1971).
Computing 8, 382-394. (1972). S. (1962).
Math. Comput. 16,494496. S. (1963).
SIAM J . Appl. Math. 11, 183-194. S. (1967). pp. 167-277. (1963).
In Proc. Power Systems
Comput. Conf, London.
H.(1968). Elektron. Rechenanlagen 10, 118-123.
nung (1972).
In
pp. 3140. (1970).
Reine Angewandte Math. 245,208-220. A., (1968). An In pp. 118-128. (1972).
In
pp. 89-100. (1963). (1972).
Math. Programming 2, 263268. (1967).
Rev. 9,
489-5 15. (1967). (1965).
0.
(1965).
Pacific J . Math. 15, 835-855. (1962). 142-146.
SIAM Reo. 4,
145
References (1958).
:
C. (1971). IEEE Trans. Circuit Theory CT 18, 89-95. (1971). (1972).
In pp. 101-1 14. York.
(1969). (1972).
72-260. (1972).
In pp. 135-146.
York.
(1972).
In pp. 41-52. (1970).
ACM
17,87-109.
(1972).
In pp. 115-120.
York.
(1971).
IEEE Trans. Circuit Theory CT-18, 101-1 13. (1969). Proc. Cornell Con$ Computerized Electron. (1962). (1959).
Math. Phys. 38, 104-11 1. Assoc. Comput. Mach. 7 ,
(1960). O n 255-259. (1962). Numer. Math. 4, 128-135. (1967). (1969). (1971a).
by SIAM Rev. 9.83-90.
In pp. 139-150.
(1971b). : IFIP Con$, Ljubljana, Yugoslavia. (1966). (1956). (1958). 5, 339-342.
Numer. Math. 8, 114122.
ACM
146
References
S. (1971a). 400-213. S. (1971b). 400-214. 141. Comm. A C M 5, 556.
(1962). (1970). Methods Eng. 2, 5-32. (1966).
Int.
Compt. J . 9, 28 1-285. (1968). Internat. Comput. Math. 2, 1-21. (1971). In pp. 97-104. (1967). Proc. IEEE 55, 1997-2000. (1970). Struct. Diu. Proc. Amer. SOC.Civil Eng. 96, 4 9 4 4 . (1969).
Numer.
00.1873.
(1969). ( # 11707),
pp. 11-24. 1. (1970). Internat.
V. V., by
Numer. Methods Eng. 2, 523-533. (1965).
CS-24.
(1963). (1962). Comm. A C M 5, 382-383. (1969). In
1 ( # 11707), pp. 75-84. (1971). J P L Quart. Tech. Rev. 1, 61-70. P., (1966). von Appl. Mat. 11, 1-9. (1969). SIAM Numer. Anal. 7 , 4 7 4 6 . (1960-1961). (1972). 2-483.
Comput.
3,3439.
147
References
(1959). J . Assoc. Comput. Mach. 6, 164171. (1960). SIAM Rev. 2, 259-268. (1969). 31,255-274. M. (1957). Management Sci. 3, 255-269. D. (1968).
Bull. Math. Biophys.
Math. Comput. 19,
(1965). 644-645. (1969). ( # I1707), pp. 155-158.
408. Comm. ACM 14.
(1971). 265-273. (1964).
(1967-1968). by Comput. 10, 19C194. R. S., (1971). Trans. Circuit Theory CT-18,139-145. (1970). Computing 6, 1-8. E. (1970). Trans. Power Apparatus Systems PAS 89, 15C155. (1971). In pp. 219-230.
on
(1970). Trans. Power Apparatus Systems
89,141-155. (1968). (1969). (11707). pp. 5 9 6 4 .
In R A l (11707). pp. 101-106.
(1969).
(1960). 376388. S. (1961). 130.
SIAM 8,
of
H A M Rev. 3, 119-
148
References
K.(1971). 468475.
Comm. ACM 14, (1972).
(1968). SIAM Rev. 10, 121-159. (1965). (1971). Inst. Math. Appl., April 1970. (1966). on 20,325-328. (1970).
Proc. Oxford Con5 Math. Comput.
X-58037, A. (1971).
on
(1970a).
Murh. Anal.
(1970b). Appl. 32, 597609. (1972).
(1972). In
pp. 177-190. (1972). Proc. IBM Con5 Sept. 1970. York. (1968). Proc. 23rd Nat. Conf: ACM Publ. pp. 585-595. (1959). Sociometry 22, 139-147. (1959). Kron’s Quart. Appl. Math. 17, 1-24. (1967). by Proc. J . Struct. Div. ASCE 93. 231-235. (1963). Proc. Symposia Appl. Math. 15, pp. 219-240. (1963). IEEE Trans. Power Apparatus Systems, PAS-82,944-950. K.(1970). Math. Comput. 25, 27-30. (1968). a Numer. Math. 12, 23 1-24 1.
149
References
In pp.
In pp. Struct. Div. ASCE 94 Quart. Appl. Math. 26,425432. G.
V. SIAM Rev.
V.
SIAM
Numer.
Anal.
V. In pp.
On
SIAM Rev. 8,
On SIAM Rev.
by
Nordisk. Tidskr. Informations
Behandling ( B I T ) Comput.
On
10,
Computing (Arch.
Elektron. Rechnen) Nordisk. Tidskr. Informations Behandling ( B I T ) 8,
R.
Comput.
Internat. J . Comput. Math.
P.
SIAM Rev.
On Internat. J . Comput. Math. 2,
In pp.
59. In pp. 3542.
150
References
(1972). Computing (Arch. Elektron. Rechnen) 9, 1-7. (1972).
Computing 9 (1969).
on
In (1 1707),
pp. 25-34. (1970).
:
1970 (1967).
Proc. IEEE 55, 1801-1809. Proc. Struct. Diu. ASCE 92,
by (1966). 75-88. (1970).
70-15.
(1972).
In pp. 77-85. (1972b). IMA J A. (1969). 14. 1623. (1962).
Numer. Math.
S. (1962). (1967).
ACM 9, 11-12.
on
(1968).
Econornetrica
36,260-278. (1964). mensforschung 8, 3346. (1968).
Unterneh-
(1965). (1969).
(11707).
(1965).
In 2, pp. 271-284.
(1969).
In (11707). pp. 107-112. (1963).
pp. 211-218.
References
151
Ziewkiewin, 0. C. (1967). “The Finite Element Method in Structural and Continuum Mechanics.” McGraw-Hill, New York. Zollenkopf, K. (1971). Bi-Factorization : Basic computational algorithm and programming techniques. In “Large SparseSets Linear Equations” (J. K. Reid, ed.),pp. 75-96. Academic Press. New York.
Author Index on
A
121, 142 12, 142 31, 94, 98, 106, 133, 136, 140,142,145 142 140, 142 81,142,148 G., 12,41, 142
71,80,141 12, 30, 141 G. G., 12,80,141 141 12,94,141
B 46,141 133, 140,141 12, 81, 141 12, 106,141, 142 13,142 12, 106,142 R.,12,41,142 81, 142 12, 13,31, 142 31, 142 31,142
C
13,81, 142 31, 94, 142 12,31,142 12,94,143 W. 143 Y. 61,143 M. 12, 27, 30, 31, 143 20, 143 153
154
Author Index
46, 143 12,41, 142 13, 143 12, 69, 143 11, 96, 101, 106, 150
145 12, 144 12, 13, 31, 90, 94, 96, 98, 106, 133, 136, 140, 142, 145 12, 145 0.
H 11, 13, 31, 61, 81, 96, 105, 106, 133,140, 143 J., 107, 108, 121, 144 12, 13, 106, 140, 142 C., 11, 13, 101, 106, 144 A., 144 50, 79, 144 A. 12, 50, 54, 144-
E 12, 31,94, 144 A. 149 A. 94, 144 80, 144 12,144 147
F
J. J . 140, 144
96, 105, 144 96, 105, 144 12, 13, 31, 133, 136, 137,
12, 31, 144 31, 105, 123, 124, 132, 144 12, 13,144
G 105, 145 C. 12, 145 J. 12, 81, 145 S., 146 145 G. 12, 145 133, 140, 141
145 105, 145 148 12, 41, 45, 50, 55, 77, 80, 145, 148
11, 13,96, 106, 140, 143 145 27, 31, 149 105, 145 S., 114, 145 146 1 46, 146 146
J A,, 80, 144 A., 12, 13, 75. 80, 94, 146 12, 81, 146 A. 12, 146
K 12, 147 12, 50, 146 12, 145, 146 146 I., 146 12, 133, 140, 146 1 11,96, 101, 105, 146
155
H.
13, 146 146 146 12, 13, 30, 90, 94, 145, 146 12, 13, 146 A,, 12,41, 142 146
M 12,94,147 12, 69, 143 1 1 , 13,96, 106, 140, 143 147 12, 80, 147 11, 25, 31, 101, 103, 140,147 12, 80, 141 12, 147 76, 147 12, 50, 54, 144 12, 31, 144 147
N A,, 147 S., 147 12, 147
0 12, 30, 31, 76, 80, 147 11, 13, 35, 36, 96, 101, 104, 105, 106, 133, 143, 147,149
P 12, 147 G. A., 12, 81, 146 S., 80, 147 148 A. 148 147 143
R 61, 148 A., 105, 148 13, 31, 76, 143, 148 108, 121, 148 148 A., 2, 148 80, 81, 148 12,68,80, 148 1. 148 12, 140, 148 148 132, 148
5 12, 41, 142 12, 31, 148 140, 148 126, 132, 148 146 149 1 1 , 13, 96, 101, 105, 106, 140, 149 11, 13, 96, 106, 140, 143 141 27, 31, 149 G. 149 12,50, 56, 77. 149 12, 81, 141 141
T 11,20, 23, 31, 35, 36, 37, 45,73,75,79,80,87,96,101, 102, 104, 106, 107, 108, 115,123, 124, 132,143, 149,150 12, 27, 31, 76, 80, 90, 92, 94,147,148, 150 150 A., 12,13,31,133,136,137,140, 144, 150 A. 12,94, 146
156
Author Index
U Utku, S., 71, 80, 141
Wenke, V. K., 80, 144,150 Westlake, J. R., 12, 83, 90, 105, 150 Wilkinson, J. H., 12, 16, 19, 31, 83, 86, 87, 89,91,115,118,121,123,124,127,132,
V van der Sluis, A., 13, 150 Varga, R. A., 12, 13, 150
W Walker, J. W., 76, 80, 147 Warshall, S., 46, 150 Weaver, W., Jr., 150 Weil, R. L., Jr., 12, 50, 146,150
150 Willoughby, R. A., 12, 13, 30, 31, 90, 94, 96, 98, 106, 133, 136, 140, 142, 145, 146,148,150 Wolfe, P., 1 1 , 12, 13, 20, 81, 96, 101, 106, 143,144,150 Z
Ziewkiewicz, 0. C., I51 Zollenkopf, K., 138, 150
Subject Index
40
A
see
43
67- 74 see
see see
see
139
see
43 42
6&74
71 67
see
45-50 50-60 79-80
8.40, see of,126427
40
see
8-9 60-66
44, 45, 88
62
72 42, 44,46,48, 54, 88, 117, 129, 131
62
64 157
158
Subject Index 75-77 75-77
by by
79-80
21 21
30 see
C 91-93 92-93 92-93 43
404I , 45-80 22 87-90
42 23-27
84-87 89
109-1 13
8687 87 117-1 18
90
see see
G
43 42 42
1619 16, 18-19 19-20
55 43
20 57
27-28
see 77-78
1618 28-29
77-78
see
43
19 43
19
see
20
9G91
GE, see
75-78
95-97 105
75-78
96 101
E
101
41 see
97-101 2G22 134-138 by
(I
priori
123-125 126127 4144
34-39
43 4142
22-29, 33-39
107-109
159 R
H 129
108-109
131-132 129-132
114 14
see
123, 127-129 128-129
see
91-92 19-20
114-1 17 115-117
101 43 42
see
J 118-121 see
119 118-119, 124-125
see
1&11
K
row, 1 1 see
138
75
L
75-76
see
2 1-2
0
see
see
9-10 4
P
4-6, 10 2-10
see
7-10
43 43 77
44 8, 6 6 6 7 , 91-93, 123-
see
6U7.91 95-96 134-138
123-129
T
101-104 97-
101
124, see
77-79, 138 54
160
Subject Index
Triangular decomposition, definition, 83 desirable forms 93-94
V Vertex, 41 degree of, 44 ernmiter, 55 in-degree of, 44 isolated, 55 out-degree 44 attachment set. 76
