Iterative Methods for Large Linear Systems

1 Fourier Analysis of Two-Level Hierarchical Basis Preconditioners


1 Introduction


2 ID, Linear S


3 2D, Bilinear S, Bilinear A


4 2D, Bilinear, 5-Point A


5 3D, Trilinear S, 7-Point A


6 Concluding Remarks

Acknowledgements

References


2 An Algebraic Framework for Hierarchical Basis Functions Multilevel Methods or the Search for 'Optimal' Preconditioners


1 Introduction


2 The Algebraic Framework for Two-Level Hierarchical Basis Function Methods

Basic Assumptions


3 Recursive Definition of Preconditioner

Forward Substitution

Backward Substitution

Computational Complexity

Domain Decomposition


4 The Relative Condition Number of M(ℓ) with Respect to A(ℓ)

Fixed-Point Analysis


5 Concluding Remarks

References


3 ELLPACK and ITPACK as Research Tools for Solving Elliptic Problems


1 Background


2 ELLPACK and ITPACK


3 Some Basic Question


4 Direct vs. Iterative Methods


5 Different Elliptic Problems


6 Symmetry?


7 Extended Network Analogy


8 Orders of Accuracy


9 Choice of Mesh


10 Computational Complexity


11 3D Problems

Acknowledgement

References


4 Preconditioned Iterative Methods for Indefinite Symmetric Toeplitz Systems


1 Introduction


2 Toeplitz and Circulant Matrices


3 Solution Methods


4 Test Matrix Preconditioners


5 Test Matrices


6 Computed Spectra

Acknowlegements

References


5 A Local Relaxation Scheme (Ad-Hoc SOR) Applied to Nine Point and Block Difference Equations


1 History


2 The Method


3 Nine Point Application: Cross Derivatives


4 Block Iteration

Acknowledgements

References


6 Block Iterative Methods for Cyclically Reduced Non-Self-Adjoint Elliptic Problems


1 Introduction


2 The Reduced System for the Convection-Diffusion Equation


3 Bounds for Solving the Convection-Diffusion Equation


4 Numerical Experiments

Acknowledgements

References


7 Toward an Effective Two-Parameter SOR Method


1 Background


2 Singular Value Decomposition and Orthogonal Similarities


3 Two-Parameter SOR


4 A Numerical Example

Acknowledgements

References

Appendix


8 Relaxation Parameters for the IQE Iterative Procedure for Solving Semi-Implicit Navier-Stokes Difference Equations


1 Introduction


2 The Continuous and Discrete Problems


3 The IQE Iterative Method


4 The Calculation of ω


5 Numerical Results

Acknowledgements

References


9 Hodie Approximation of Boundary Conditions


1 Introduction


2 Approximation 'Away from the Boundary'


3 Hodie as Interpolation


4 Boundary Conditions


5 Extension of Ui,j to Ω


6 Indexing of Unknowns


7 Eigenproblems

Acknowledgements

References


10 Iterative Methods for Nonsymmetric Linear Systems


1 Introduction


2 Projection Methods

Balanced Projection Methods


3 Krylov Projection Methods


3.1 Computational Schemes for Krylov Projection Methods


3.2 Examples of Krylov Projection Method


4 Semi-Krylov Projection Methods


4.1 Balanced SKPM's: Truncated/Restarted Methods


4.2 Balanced SKPM's: Generalized Minimal Error Methods


5 Non-polynomial Projection Methods


6 Non-projection Polynomial Methods


7 Conclusion

Acknowledgements

References


11 Solution of Three-Dimensional Generalized Poisson Equations on Vector Computers


1 Introduction


2 Discretization


3 The SSOR Preconditioned Conjugate Gradient Method


4 Numerical Results


5 Summary and Conclusions

Acknowledgements

References


12 Multi-Level Asynchronous Iteration for PDEs


1 Introduction


2 Multiple Level Asynchronous PDE Algorithms


3 A Unified Model of Parallel Computation


4 Model of Multi-Level Iteration On a Hypercube Machine


5 Mapping Multi-Level Structures Onto a Hypercube


6 Analysis of the Iteration and its Performance

Acknowledgements

References


13 An Adaptive Algorithm for Richardson's Method


1 Introduction


1.1 Outline


1.2 The Convex Hull of σ(A)


1.3 Motivation


1.4 Conventions and Notation


2 The Numerical Framework


2.1 Richardson's Method


2.2 Eigenvalue Least Squares Problem


2.3 Optimal Residual Polynomial LS Problem


2.4 The Minimum Residual LS Problem


3 The Power Method for Eigenvalues


3.1 A Linear Combination of Krylov Vectors


3.2 The Eigenvalue LS Problem


3.3 Solution of the Eigenvalue LS Problem


4 Finding the Optimal Richardson Parameters


4.1 Residual Polynomials


4.2 Inner Products, Norms, and Optimal Residual Polynomials


4.3 Solving the Optimal Residual Polynomial LS Problem


4.4 The Optimal Residual Polynomial


5 The Minimum Residual Method


5.1 The Minimum Residual Krylov Subspace


5.2 The Minimum Residual LS Problem


5.3 Complementary LS Problems


5.4 Matrix Form


6 Algorithm


6.1 The Convex Hull


6.2 Ordering the Parameters


6.3 Richardson's Method Variant


6.4 An Algorithm

Summary

Acknowledgements

References


14 A Note on the SSOR and USSOR Iterative Methods Applied to p-Cyclic Matrices


1 Introduction


2 Statement of Main Result and Discussion


3 Proof of the Theorem

Acknowledgements

References


15 The ADI Minimax Problem for Complex Spectra


1 Introduction and Review of Results for Real Spectra


2 Early Analysis of Complex Spectra


3 The Family of Elliptic Function Domains


4 Spectral Boundary


5 Spectrum Partitioning

A. Region II: The Asymptotic Region

B. Region III: The Right End

C. Region I: The Left End


6 Subspace Refinement

A. Excluded Subspaces

B. Direct Solution Over a Subspace

Acknowledgements

References


16 Some Domain Decomposition Algorithms for Elliptic Problems


1 Introduction


2 Substructures, Subspaces and Projections


3 Schwarz Methods


4 Analysis of an Additive Schwarz Method


5 Iterative Substructuring Methods

Acknowledgements

References


17 The Search for Omega


1 Introduction


2 Iterative Algorithms and Iteration Parameters]


3 A Priori Techniques

Analytic Techniques

Spectral Methods

Use of Differential Equations


4 Adaptive Techniques

The Search for Omega for the SOR Method

Adaptive Chebyshev Acceleration

Adaptive SSOR with Chebyshev CG Acceleration

Variational-Based Adaptive Methods: The Composite Adaptive Procedure


5 The Nonsymmetric Case

The SOR Method

Chebyshev Acceleration

Generalized CG Methods and Lanczos Methods

Acknowlegements

References

Index