COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Iterative Methods for Large Linear Systems - 1st Edition - ISBN: 9780124074750, 9781483260204

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
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


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



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


3 ELLPACK and ITPACK as Research Tools for Solving Elliptic Problems

1 Background


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



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



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



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



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




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



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



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



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



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



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




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



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



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



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





No. of pages:
© Academic Press 1989
28th December 1989
Academic Press
eBook ISBN:

About the Editors

David R. Kincaid

Linda J. Hayes

Ratings and Reviews