Iterative Methods for Large Linear Systems

Iterative Methods for Large Linear Systems

1st Edition - December 28, 1989

Write a review

  • Editors: David R. Kincaid, Linda J. Hayes
  • eBook ISBN: 9781483260204

Purchase options

Purchase options
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

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




Product details

  • No. of pages: 350
  • Language: English
  • Copyright: © Academic Press 1989
  • Published: December 28, 1989
  • Imprint: Academic Press
  • eBook ISBN: 9781483260204

About the Editors

David R. Kincaid

Linda J. Hayes

Ratings and Reviews

Write a review

There are currently no reviews for "Iterative Methods for Large Linear Systems"