Kincaid / Hayes Iterative Methods for Large Linear Systems

1. Auflage 2014
ISBN: 978-1-4832-6020-4
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 350 Seiten, Web PDF

Iterative Methods for Large Linear Systems contains a wide spectrum of research topics related to iterative methods, such as searching for optimum parameters, using hierarchical basis preconditioners, utilizing software as a research tool, and developing algorithms for vector and parallel computers. This book provides an overview of the use of iterative methods for solving sparse linear systems, identifying future research directions in the mainstream of modern scientific computing with an eye to contributions of the past, present, and future. Different iterative algorithms that include the successive overrelaxation (SOR) method, symmetric and unsymmetric SOR methods, local (ad-hoc) SOR scheme, and alternating direction implicit (ADI) method are also discussed. This text likewise covers the block iterative methods, asynchronous iterative procedures, multilevel methods, adaptive algorithms, and domain decomposition algorithms. This publication is a good source for mathematicians and computer scientists interested in iterative methods for large linear systems.

Autoren/Hrsg.

Kincaid, David R.

Hayes, Linda J.

Inhaltsverzeichnis

1;Front Cover
;1
2;Iterative Methods for Large Linear Systems
;4
3;Copyright Page
;5
4;Table of
Contents;26
5;Preface;6
6;Authors of Chapters;8
7;Papers Presented at Conference;10
8;Professor David M. Young, Jr.;16
9;Photographs from Conference;20
10;Chapter
1. Fourier Analysis of Two-Level Hierarchical Basis Preconditioners;32
10.1;1 Introduction;32
10.2;2
1D, Linear S;35
10.3;3 2D, Bilinear S, Bilinear A;38
10.4;4 2D, Bilinear, 5-Point A;42
10.5;5 3D, Trilinear S, 7-Point A;45
10.6;6 Concluding Remarks;46
10.7;Acknowledgements;47
10.8;References;47
11;Chapter 2. An Algebraic Framework for Hierarchical Basis Functions Multilevel Methods or the Search for 'Optimal'
Preconditioners;48
11.1;1 Introduction;48
11.2;2 The Algebraic Framework for Two-Level Hierarchical Basis Function
Methods;54
11.3;3 Recursive Definition of Preconditioner;60
11.4;4 The Relative Condition Number of M
with Respect to A;64
11.5;5 Concluding Remarks;69
11.6;References;70
12;Chapter 3.
ELLPACK and ITPACK as Research Tools for Solving Elliptic Problems;72
12.1;1 Background;72
12.2;2 ELLPACK and
ITPACK;74
12.3;3 Some Basic Questions;75
12.4;4 Direct vs. Iterative Methods;77
12.5;5 Different Elliptic Problems;78
12.6;6
Symmetry;80
12.7;7 Extended Network Analogy;81
12.8;8 Orders of Accuracy;83
12.9;9 Choice of Mesh;87
12.10;10 Computational Complexity;89
12.11;11 3D Problems;91
12.12;Acknowledgement;92
12.13;References;92
13;Chapter 4. Preconditioned Iterative Methods for Indefinite Symmetric Toeplitz
Systems;96
13.1;1 Introduction;96
13.2;2 Toeplitz and Circulant Matrices;97
13.3;3 Solution Methods;98
13.4;4 Test Matrix Preconditioners;99
13.5;5 Test Matrices;100
13.6;6 Computed Spectra;101
13.7;Acknowlegements;109
13.8;References;109
14;Chapter 5.
A Local Relaxation Scheme (Ad-Hoc SOR) Applied to Nine Pointand Block Difference Equations;112
14.1;1 History;112
14.2;2 The Method;113
14.3;3 Nine Point Application: Cross Derivatives;114
14.4;4 Block Iteration;119
14.5;Acknowledgements;121
14.6;References;121
15;Chapter 6. Block Iterative Methods for Cyclically Reduced Non-Self-Adjoint
Elliptic Problems;122
15.1;1 Introduction;123
15.2;2 The Reduced System for the Convection-Diffusion Equation;124
15.3;3 Bounds for Solving the Convection-Diffusion Equation;129
15.4;4 Numerical Expe;132
15.5;Acknowledgements;135
15.6;References;135
16;Chapter 7.
Toward an Effective Two-Parameter SOR Method;138
16.1;1 Background;138
16.2;2 Singular Value Decomposition and Orthogonal Similarities;141
16.3;3 Two-Parameter SOR;146
16.4;4 A Numerical Example;147
16.5;Acknowledgements;148
16.6;References;150
16.7;Appendix;150
17;Chapter 8. Relaxation Parameters for the IQE Iterative Procedure for Solving Semi-Implicit Navier-Stokes
Difference Equations;152
17.1;1 Introduction;153
17.2;2 The Continuous and Discrete Problems;153
17.3;3 The IQE Iterative Method;156
17.4;4 The Calculation of
w;158
17.5;5 Numerical Results;162
17.6;Acknowledgements;165
17.7;References;165
18;Chapter 9.
Hodie Approximation of Boundary Conditions;166
18.1;1 Introduction;166
18.2;2 Approximation 'A
way from the Boundary' ;167
18.3;3 Hodie as Interpolation;171
18.4;4 Boundary Conditions;172
18.5;5 Extension of Ui,j to
O;175
18.6;6 Indexing of Unknowns;175
18.7;7 Eigenproblems;175
18.8;Acknowledgements;176
18.9;References;177
19;Chapter 10.
Iterative Methods for Nonsymmetric Linear Systems;180
19.1;1 Introduction;180
19.2;2 Projection Methods;182
19.3;3 Krylov Projection Methods;187
19.4;4 Semi-Krylov Projection Methods;195
19.5;5 Non-polynomial Projection Methods;198
19.6;6 Non-projection Polynomial Methods;199
19.7;7 Conclusion;200
19.8;Acknowledgements;200
19.9;References;201
20;Chapter 11. Solution of Three-Dimensional Generalized Poisson Equations on
Vector Computers;204
20.1;1 Introduction;204
20.2;2 Discretization;205
20.3;3 The SSOR Preconditioned Conjugate Gradient Method;207
20.4;4 Numerical Results;210
20.5;5 Summary and Conclusions;219
20.6;Acknowledgements;220
20.7;References;220
21;Chapter 12.
Multi-Level Asynchronous Iteration for PDEs;224
21.1;1 Introduction;224
21.2;2 Multiple Level Asynchronous PDE Algorithms;225
21.3;3 A Unified Model of Parallel Computation;227
21.4;4 Model of Multi-Level IterationOn a Hypercube Machine;228
21.5;5 Mapping Multi-Level Structures
Onto a Hypercube;231
21.6;6 Analysis of the Iteration and its Performance;237
21.7;Acknowledgements;243
21.8;References;243
22;Chapter 13.
An Adaptive Algorithm for Richardson's Method;246
22.1;1 Introduction;246
22.2;2 The Numerical Framework;249
22.3;3 The Power Method for Eigenvalues;250
22.4;4 Finding the Optimal Richardson Parameters;253
22.5;5 The Minimum Residual Method;256
22.6;6 Algorithm;258
22.7;Summary;261
22.8;Acknowledgements;262
22.9;References;262
23;Chapter 14. A Note on the SSOR and USSOR Iterative Methods Applied to
p-Cyclic Matrices;266
23.1;1 Introduction;266
23.2;2 Statement of Main Result and Discussion;270
23.3;3 Proof of the Theorem;274
23.4;Acknowledgements;279
23.5;References;279
24;Chapter 15.
The ADI Minimax Problem for Complex Spectra;282
24.1;1 Introduction and Review of Results for Real Spectra;283
24.2;2 Early Analysis of Complex Spectra;284
24.3;3 The Family of Elliptic Function Domains;286
24.4;4 Spectral Boundary;293
24.5;5 Spectrum Partitioning;295
24.6;6 Subspace Refinement;298
24.7;Acknowledgements;302
24.8;References;302
25;Chapter 16.
Some Domain Decomposition Algorithms for Elliptic Problems;304
25.1;1 Introduction;305
25.2;2 Substructures, Subspaces and Projection;307
25.3;3 Schwarz Methods;312
25.4;4 Analysis of an Additive Schwarz Method;314
25.5;5 Iterative Substructuring Methods;315
25.6;Acknowledgements;318
25.7;References;319
26;Chapter 17.
The Search for Omega;324
26.1;1 Introduction;325
26.2;2 Iterative Algorithms and Iteration Parameters;326
26.3;3 A Priori Techniques;329
26.4;4 Adaptive Techniques;332
26.5;5 The Nonsymmetric Case;336
26.6;Acknowlegements;338
26.7;References;338
27;Index;344