# Iterative Methods for Large Linear Systems

## 1st Edition

**Editors:**David R. Kincaid Linda J. Hayes

**eBook ISBN:**9781483260204

**Imprint:**Academic Press

**Published Date:**28th December 1989

**Page Count:**350

## Description

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.

## Table of Contents

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

## Details

- No. of pages:
- 350

- Language:
- English

- Copyright:
- © Academic Press 1989

- Published:
- 28th December 1989

- Imprint:
- Academic Press

- eBook ISBN:
- 9781483260204