Iterative Methods for Solving Nonsymmetric Linear Systems

Center for Numerical Analysis

University of Texas at Austin

Austin, Texas 78713-8510

Abstract

A less than satisfactory situation may arise when one is solving large linear systems involving nonsymmetric matrices. Krylov subspace methods, which can be regarded as generalized conjugate gradient methods, are often used. However, for nonsymmetric problems, the amount of work per iteration often increases as the number of iterations increases. Frequently, this disadvantage can be overcome by the use of Lanczos-type methods, such as the biconjugate method. On the other hand, the Lanczos-type methods may suffer from numerical instability. Numerical instability in matrix algorithms can often be avoided by the use of orthogonal matrix operations or rotations. Such operations are used in the GMRES method of Saad and Schultz. Orthogonal rotations are also used by Paige and Saunders in the SYMMQR method for solving linear systems with symmetric but not necessarily positive definite matrices.

The research of David M. Young, Jen-Yuan Chen, and David R. Kincaid involves the iterative solution of large sparse linear systems using Krylov subspace methods. The matrices of the systems are not assumed to be symmetric. First, we replace a given system with a related system with a symmetric matrix of twice the size, as is done in deriving the Lanczos methods. We then apply Krylov subspace techniques involving orthogonal rotations, such as generalized GMRES-type procedures. Also, we employ techniques such as are used in the SYMMQR and MINRES procedures of Paige and Saunders. The goal is to develop procedures where the work per iteration does not increase as the number of iterations increases and where the numerical stability and overall convergence are not adversely affected.