第1页 / 共107页
第2页 / 共107页
第3页 / 共107页
第4页 / 共107页
第5页 / 共107页
第6页 / 共107页
第7页 / 共107页
第8页 / 共107页
computational linear algebra.pdf
Iterative Methods
for Sparse
Linear Systems
Yousef Saad
6
15
4
11
2
13
1
12
9
14
10
7
5
8
3
Copyright c 2000 by Yousef Saad.
SECOND EDITION WITH CORRECTIONS. JANUARY 3RD, 2000.
PREFACE
Acknowledgments . . . .
. . . .
Suggestions for Teaching . . . .
. . . .
. . . .
. . . .
. . . .
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. .
. .
. . .
. . . .
. . . .
. . . .
. . . .
1.1 Matrices . .
. . . .
1.2 Square Matrices and Eigenvalues . . . .
1.3 Types of Matrices . . . .
. . . .
1.4 Vector Inner Products and Norms . . . .
. . . .
1.5 Matrix Norms . .
. . . .
1.6 Subspaces, Range, and Kernel . .
. . . .
1.7 Orthogonal Vectors and Subspaces . . .
. . . .
1.8 Canonical Forms of Matrices . .
1 BACKGROUNDINLINEARALGEBRA
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
1.8.1 Reduction to the Diagonal Form . . . .
1.8.2 The Jordan Canonical Form . . .
. . . .
1.8.3 The Schur Canonical Form . . .
. . . .
1.8.4 Application to Powers of Matrices . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
1.12.1 Range and Null Space of a Projector . .
1.12.2 Matrix Representations .
. . . .
1.12.3 Orthogonal and Oblique Projectors . . .
1.12.4 Properties of Orthogonal Projectors . . .
. . . .
. . . .
. . . .
. . . .
1.13 Basic Concepts in Linear Systems . . . .
. . . .
. . . .
. . . .
1.9 Normal and Hermitian Matrices .
1.9.1 Normal Matrices
. . . .
1.9.2 Hermitian Matrices . . .
. . . .
. . . .
. . . .
1.10 Nonnegative Matrices, M-Matrices . . .
. . . .
1.11 Positive-Definite Matrices . . . .
1.12 Projection Operators . . .
. . . .
. . . .
1.13.1 Existence of a Solution .
1.13.2 Perturbation Analysis . .
. . . .
Exercises and Notes . .
. . . .
. . . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
xiii
xiv
xv
1
1
3
4
6
8
9
10
15
15
16
17
19
21
21
24
26
30
33
33
35
35
37
38
38
39
41
44
44
45
47
2 DISCRETIZATIONOFPDES
. . . .
2.1 Partial Differential Equations . .
2.1.1 Elliptic Operators . . . .
. . . .
2.1.2 The Convection Diffusion Equation . .
. . . .
. . . .
. . .
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. .
. .
. .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . .
2.2 Finite Difference Methods . . .
2.2.1 Basic Approximations .
. . .
2.2.2 Difference Schemes for the Laplacean Operator . .
. . .
2.2.3
. . .
2.2.4 Upwind Schemes . . .
2.2.5
. . .
. . .
. . .
. . .
. . .
Finite Differences for 1-D Problems .
. . . .
Finite Differences for 2-D Problems .
. . . .
. . . .
. . . .
. . . .
2.3 The Finite Element Method . .
. . . .
2.4 Mesh Generation and Refinement . . .
. . . .
2.5 Finite Volume Method .
Exercises and Notes . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
3 SPARSEMATRICES
. . . .
. . . .
. . . .
. . . .
Introduction . . .
. . .
. . . .
. . . .
3.1
. . .
3.2 Graph Representations .
. . . .
. . . .
3.2.1 Graphs and Adjacency Graphs . . . .
. . . .
3.2.2 Graphs of PDE Matrices
. . . .
3.3 Permutations and Reorderings .
3.3.1 Basic Concepts
. . . .
. . . .
3.3.2 Relations with the Adjacency Graph .
. . . .
3.3.3 Common Reorderings .
. . . .
. . . .
3.3.4
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
3.4 Storage Schemes .
3.5 Basic Sparse Matrix Operations . . . .
3.6 Sparse Direct Solution Methods . . . .
. . . .
3.7 Test Problems . .
Exercises and Notes . .
. . . .
Irreducibility .
. . .
. . . .
. . . .
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
4 BASICITERATIVEMETHODS
4.1
. . .
. . . .
4.2 Convergence . . .
. . . .
. . . .
Jacobi, Gauss-Seidel, and SOR . . . .
4.1.1 Block Relaxation Schemes . .
4.1.2
. . . .
. . . .
Iteration Matrices and Preconditioning . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
4.2.1 General Convergence Result
. . . .
4.2.2 Regular Splittings . . .
4.2.3 Diagonally Dominant Matrices . . . .
Symmetric Positive Definite Matrices
4.2.4
Property A and Consistent Orderings .
4.2.5
. . . .
. . . .
. . . .
.
. . . .
. . . .
. . . .
4.3 Alternating Direction Methods
. . . .
Exercises and Notes . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
5 PROJECTIONMETHODS
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
47
48
49
51
51
54
55
61
63
66
68
68
70
70
72
72
72
75
75
83
84
87
88
88
91
95
95
. . .
98
. . .
. . . 102
. . . 104
. . . 104
. . . 107
. . . 108
. . . 112
. . . 112
. . . 116
. . . 119
122
5.1 Basic Definitions and Algorithms . . .
.
. . . .
. . . .
5.2.1 Two Optimality Results . . . .
5.1.1 General Projection Methods
5.1.2 Matrix Representation .
. . . .
5.2 General Theory .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . .
. . .
. . .
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . 122
. . . 123
. . . 124
. . . 126
. . . 126
5.2.2
5.2.3 General Error Bound . .
. . . .
5.3 One-Dimensional Projection Processes .
. . . .
Interpretation in Terms of Projectors . .
. . . .
. . . .
5.3.1
. . . .
5.3.2 Minimal Residual (MR) Iteration . . . .
5.3.3 Residual Norm Steepest Descent
. . . .
. . . .
5.4 Additive and Multiplicative Processes . .
Exercises and Notes . .
. . . .
. . . .
Steepest Descent
. . . .
. . . .
. . . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . 127
. . 129
. . 131
. . 132
. . 134
. . 136
. . 136
. . 139
6 KRYLOVSUBSPACEMETHODS–PARTI
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
144
. . 144
. . 145
. . 147
. . 147
. . 149
. . 152
. . 154
. . 155
. . 158
. . 158
. . 159
. . 161
. . 165
. . 165
. . 168
. . 169
. . 174
. . 174
. . 175
. . 176
. . 176
. . 180
. . 181
. . 183
. . 183
. . 186
. . 188
. . 188
. . 189
. . 193
. . 194
. . 197
. . 202
205
. . 205
. . .
. . . .
. . . .
Introduction . . .
6.5 GMRES . .
. . . .
. . . .
. . . .
6.3.1 The Basic Algorithm . .
6.3.2
. . . .
. . . .
. . . .
. . . .
Practical Implementations . . . .
6.1
. . . .
6.2 Krylov Subspaces . . . .
6.3 Arnoldi’s Method . . . .
. . .
. . . .
. . .
. . . .
. . .
. . . .
. . .
. . . .
. . .
. . . .
. . .
6.4 Arnoldi’s Method for Linear Systems (FOM) . .
. . .
. . . .
6.4.1 Variation 1: Restarted FOM . . .
. . .
. . . .
6.4.2 Variation 2: IOM and DIOM . .
. . .
. . . .
. . . .
. . .
. . . .
6.5.1 The Basic GMRES Algorithm .
. . .
. . . .
6.5.2 The Householder Version . . . .
. . .
. . . .
6.5.3
Practical Implementation Issues
. . .
6.5.4 Breakdown of GMRES .
. . . .
. . . .
. . .
6.5.5 Relations between FOM and GMRES .
6.5.6 Variation 1: Restarting .
. . .
. . . .
6.5.7 Variation 2: Truncated GMRES Versions . . .
. . .
. . .
. . .
. . .
6.7 The Conjugate Gradient Algorithm . . .
. . .
6.7.1 Derivation and Theory .
. . . .
6.7.2 Alternative Formulations . . . .
. . .
6.7.3 Eigenvalue Estimates from the CG Coefficients
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . . .
6.8 The Conjugate Residual Method . . . .
. . . .
6.9 GCR, ORTHOMIN, and ORTHODIR . .
. . . .
. . . .
6.10 The Faber-Manteuffel Theorem .
. . . .
6.11 Convergence Analysis . .
. . . .
. . . .
. . . .
6.11.1 Real Chebyshev Polynomials . .
6.11.2 Complex Chebyshev Polynomials
. . .
6.11.3 Convergence of the CG Algorithm . . .
. . . .
6.11.4 Convergence of GMRES . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
6.6.1 The Algorithm . .
. . . .
6.6.2 Relation with Orthogonal Polynomials .
. . . .
. . . .
. . . .
6.6 The Symmetric Lanczos Algorithm . . .
. . . .
6.12 Block Krylov Methods
Exercises and Notes . .
. . . .
. . . .
.
. . . .
. . . .
. . . .
7 KRYLOVSUBSPACEMETHODS–PARTII
. . .
7.1 Lanczos Biorthogonalization . .
. . . .
. . . .
. . . .
7.1.1 The Algorithm .
7.1.2
. . . .
Practical Implementations . . .
. . . .
. . . .
7.2 The Lanczos Algorithm for Linear Systems . .
7.3 The BCG and QMR Algorithms . . . .
. . . .
7.3.1 The Biconjugate Gradient Algorithm .
7.3.2 Quasi-Minimal Residual Algorithm .
. . . .
. . . .
. . . .
7.4.1 Conjugate Gradient Squared .
7.4.2 BICGSTAB . .
. . . .
. . . .
7.4.3 Transpose-Free QMR (TFQMR) . . .
. . . .
7.4 Transpose-Free Variants . . . .
Exercises and Notes . .
. . . .
. . . .
. . . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . 205
. . . 208
. . . 210
. . . 210
. . . 211
. . . 212
. . . 214
. . . 215
. . . 217
. . . 221
. . . 227
8 METHODSRELATEDTOTHENORMALEQUATIONS
230
. . . .
. . . .
. . . .
. . . .
. . . .
. . .
8.1 The Normal Equations .
8.2 Row Projection Methods
. . . .
. . . .
8.2.1 Gauss-Seidel on the Normal Equations . . . .
. . . .
8.2.2 Cimmino’s Method . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
8.3 Conjugate Gradient and Normal Equations . .
. . . .
. . . .
. . . .
. . . .
. . .
. . .
8.4 Saddle-Point Problems .
Exercises and Notes . .
. . .
8.3.1 CGNR . .
8.3.2 CGNE . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . 230
. . . 232
. . . 232
. . . 234
. . . 237
. . . 237
. . . 238
. . . 240
. . . 243
9 PRECONDITIONEDITERATIONS
. . .
. . . .
Introduction . . .
Preserving Symmetry .
9.3 Preconditioned GMRES . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . .
. . . .
9.1
. . . .
. . .
. . . .
9.2 Preconditioned Conjugate Gradient . .
. . .
. . . .
9.2.1
. . . .
. . .
. . . .
9.2.2 Efficient Implementations . . .
. . .
. . . .
. . . .
. . .
. . . .
9.3.1 Left-Preconditioned GMRES .
. . .
9.3.2 Right-Preconditioned GMRES . . . .
9.3.3
. . .
. . . .
9.3.4 Comparison of Right and Left Preconditioning . . .
. . .
. . .
. . .
. . .
. . .
. . .
. . . .
. . . .
. . . .
9.5 Preconditioned CG for the Normal Equations .
9.6 The CGW Algorithm .
. . . .
. . . .
. . .
Exercises and Notes . .
. . . .
Flexible GMRES . . .
. . . .
9.4.1
9.4.2 DQGMRES . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
9.4 Flexible Variants .
Split Preconditioning .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . .
10 PRECONDITIONINGTECHNIQUES
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
245
. . . 245
. . . 246
. . . 246
. . . 249
. . . 251
. . . 251
. . . 253
. . . 254
. . . 255
. . . 256
. . . 256
. . . 259
. . . 260
. . . 261
. . . 263
265
. . .
. . . .
. . . .
10.1 Introduction . . .
10.2 Jacobi, SOR, and SSOR Preconditioners . . .
. . . .
10.3 ILU Factorization Preconditioners
. . . .
. . . .
. .
10.3.1 Incomplete LU Factorizations .
10.3.2 Zero Fill-in ILU (ILU(0)) . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . .
. . .
. . .
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . 265
. . . 266
. . . 269
. . . 270
. . . 275
. . . .
. . . .
) .
. . . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
.
10.4 Threshold Strategies and ILUT .
10.4.1 The ILUT Approach . .
10.4.2 Analysis .
. . . .
10.4.3 Implementation Details .
10.4.4 The ILUTP Approach . .
10.4.5 The ILUS Approach . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
10.5 Approximate Inverse Preconditioners . .
. . . .
10.3.3 Level of Fill and ILU(
10.3.4 Matrices with Regular Structure . . . .
. . . .
10.3.5 Modified ILU (MILU)
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
10.5.1 Approximating the Inverse of a Sparse Matrix . . . .
. . . .
10.5.2 Global Iteration .
. . . .
. . .
. . . .
10.5.3 Column-Oriented Algorithms . .
. . .
10.5.4 Theoretical Considerations . . .
. . . .
. . .
. . . .
10.5.5 Convergence of Self Preconditioned MR . . .
. . . .
. . . .
. . .
10.5.6 Factored Approximate Inverses .
. . . .
. . . .
. . .
10.5.7 Improving a Preconditioner . . .
. . . .
. . . .
. . .
. . . .
. . . .
. . . .
. . .
10.6.1 Block-Tridiagonal Matrices . . .
. . . .
. . . .
. . .
10.6.2 General Matrices
. . . .
. . .
. . . .
. . .
10.7 Preconditioners for the Normal Equations
. . . .
10.7.1 Jacobi, SOR, and Variants . . . .
. . .
. . . .
. . . .
. . .
10.7.2 IC(0) for the Normal Equations .
. . . .
. . . .
. . .
10.7.3 Incomplete Gram-Schmidt and ILQ . .
. . . .
. . .
. . . .
10.6 Block Preconditioners . .
Exercises and Notes . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
11.3 Types of Parallel Architectures
11.1 Introduction . . .
. . . .
11.2 Forms of Parallelism . . .
11 PARALLELIMPLEMENTATIONS
. . .
. . . .
. . .
. . . .
. . .
11.2.1 Multiple Functional Units . . . .
. . .
. . . .
11.2.2 Pipelining . . . .
. . . .
11.2.3 Vector Processors . . . .
. . .
. . . .
11.2.4 Multiprocessing and Distributed Computing .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . . .
. . . .
11.3.1 Shared Memory Computers . . .
. . . .
11.3.2 Distributed Memory Architectures . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
11.4.1 Preconditioned CG . . .
. . . .
11.4.2 GMRES .
. . . .
11.4.3 Vector Operations . . . .
. . . .
11.4.4 Reverse Communication . . . .
. . . .
11.5.1 The Case of Dense Matrices
. .
11.5.2 The CSR and CSC Formats . . .
11.5.3 Matvecs in the Diagonal Format
11.5.4 The Ellpack-Itpack Format
. . .
11.5 Matrix-by-Vector Products
11.4 Types of Operations . . .
. . . .
. . .
.
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . 278
. . 281
. . 286
. . 287
. . 288
. . 289
. . 292
. . 294
. . 296
. . 298
. . 299
. . 299
. . 301
. . 303
. . 305
. . 307
. . 310
. . 310
. . 311
. . 312
. . 313
. . 313
. . 314
. . 316
. . 319
324
. . 324
. . 325
. . 325
. . 326
. . 326
. . 326
. . 327
. . 327
. . 329
. . 331
. . 332
. . 332
. . 333
. . 334
. . 335
. . 335
. . 336
. . 339
. . 340
11.6 Standard Preconditioning Operations .
.
. . . .
. . . .
11.5.5 The Jagged Diagonal Format
11.5.6 The Case of Distributed Sparse Matrices . . .
. . . .
. . . .
. . .
. . .
. . .
. . . .
11.6.1 Parallelism in Forward Sweeps . . . .
. . .
11.6.2 Level Scheduling: the Case of 5-Point Matrices . .
11.6.3 Level Scheduling for Irregular Graphs . . . .
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . 341
. . . 342
. . . 345
. . . 346
. . . 346
. . . 347
. . . 350
Exercises and Notes . .
12 PARALLELPRECONDITIONERS
. . .
. . .
12.4 Multicoloring . .
. . . .
12.1 Introduction . . .
. . . .
. . . .
12.2 Block-Jacobi Preconditioners .
. . . .
12.3 Polynomial Preconditioners . .
12.3.1 Neumann Polynomials
. . . .
12.3.2 Chebyshev Polynomials . . . .
12.3.3 Least-Squares Polynomials . .
12.3.4 The Nonsymmetric Case . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
12.4.1 Red-Black Ordering . .
. . . .
12.4.2 Solution of Red-Black Systems . . . .
. . . .
12.4.3 Multicoloring for General Sparse Matrices . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
12.7.1 Approximate Inverses .
. . . .
12.7.2 Element-by-Element Techniques . . .
. . . .
12.7.3 Parallel Row Projection Preconditioners . . .
. . . .
. . . .
. . . .
. . . .
. . . .
12.6.1 Distributed Sparse Matrices . .
. . . .
. . . .
. . . .
12.5.1 Multi-Elimination . . .
. . . .
12.5.2 ILUM . .
12.6 Distributed ILU and SSOR . .
12.5 Multi-Elimination ILU .
Exercises and Notes . .
12.7 Other Techniques
. . . .
. . . .
. . . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
13 DOMAINDECOMPOSITIONMETHODS
. . .
. . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
13.1 Introduction . . .
. . . .
13.1.1 Notation .
13.1.2 Types of Partitionings .
13.1.3 Types of Techniques . .
. . . .
. . . .
. . . .
. . . .
13.2 Direct Solution and the Schur Complement . .
. . . .
.
. . . .
. . .
. . . .
. . .
. . . .
. . .
. . . .
. . .
. . . .
. . .
. . . .
. . .
13.2.1 Block Gaussian Elimination .
. . . .
13.2.2 Properties of the Schur Complement
. . .
13.2.3 Schur Complement for Vertex-Based Partitionings .
. . . .
13.2.4 Schur Complement for Finite-Element Partitionings . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
13.3.1 Multiplicative Schwarz Procedure . .
. . . .
13.3.2 Multiplicative Schwarz Preconditioning . . .
. . . .
13.3.3 Additive Schwarz Procedure .
13.3.4 Convergence . .
. . . .
. . . .
13.3 Schwarz Alternating Procedures . . . .
. . .
. . .
. . .
. . .
. . .
. . . .
. . . .
. . . .
353
. . . 353
. . . 354
. . . 356
. . . 356
. . . 357
. . . 360
. . . 363
. . . 365
. . . 366
. . . 367
. . . 368
. . . 369
. . . 370
. . . 371
. . . 374
. . . 374
. . . 376
. . . 377
. . . 377
. . . 379
. . . 380
383
. . . 383
. . . 384
. . . 385
. . . 386
. . . 388
. . . 388
. . . 389
. . . 390
. . . 393
. . . 395
. . . 395
. . . 400
. . . 402
. . . 404
. . .
. . .
. . .
. . . .
. . . .
. . . .
.
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . 408
. . 408
. . 410
. . 411
. . 412
. . 414
. . 414
. . 415
. . 417
. . 418
. . 422
425
439
13.4 Schur Complement Approaches .
13.4.1 Induced Preconditioners .
13.4.2 Probing .
. . . .
13.4.3 Preconditioning Vertex-Based Schur Complements
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
13.5 Full Matrix Methods . . .
. . . .
. . . .
13.6 Graph Partitioning . . . .
. . . .
13.6.1 Basic Definitions
. . . .
. . . .
13.6.2 Geometric Approach . .
13.6.3 Spectral Techniques . . .
. . . .
13.6.4 Graph Theory Techniques . . . .
. . . .
Exercises and Notes . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
REFERENCES
INDEX
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
