Iterative Methods for Solving Linear Systems and Other Problems

####

The numerical solution of partial differential equations and
integral equations in modeling various physical phenomena often requires
the solution of large sparse or structured systems of linear algebraic
equations. The direct solution of these linear systems using Gaussian
elimination is prohibitively expensive in terms of both time and
storage, so iterative methods are used. These do not require storage of
the matrix but only the ability to perform matrix-vector
multiplications. An important area of research is to find efficient
iterative methods that require only a small number of matrix-vector
multiplications and a small amount of additional work to compute a good
approximate solution to the linear system. Sometimes the techniques
used in solving linear systems are applicable in other areas as well,
such as computing eigenvalues and computing various matrix functions
such as the resolvent and the matrix exponential.

Recent progress has been made in understanding the behavior of the
conjugate gradient method and the minimal residual method for symmetric
linear systems in finite precision arithmetic. It is shown that these
methods behave like the exact algorithms applied to a larger linear
system whose eigenvalues all lie in tiny intervals about the eigenvalues
of the given matrix. This same analysis shows why the Lanczos
algorithm can be used effectively to compute the matrix exponential.

Current work deals with nonsymmetric problems. One interesting
problem is to describe the behavior of iterative methods for
nonsymmetric linear systems in terms of some characteristic properties
of the coefficient matrix. Eigenvalues are not the answer in the
nonnormal case. Another open problem is to find an iterative method
using a short recurrence that generates a near optimal approximate
solution to the linear system at each step. The conjugate gradient and
minimal residual methods do this for symmetric problems, but it is not
known if such a method exists for nonsymmetric matrices.

For more details, see the references:

* Iterative Methods for Solving Linear Systems *

** SIAM, Philadelphia, 1997 **,

by Anne Greenbaum.

* Predicting the Behavior of Finite Precision Lanczos and Conjugate
Gradient Computations *

** SIAM J. Matrix Anal. Appl., 13 (1992), pp. 121-137 **,

** by A. Greenbaum and Z. Strakos.
**

* Relations Between Galerkin and Norm-Minimizing Iterative Methods for
Solving Linear Systems *

** SIAM J. Matrix Anal. Appl., 17 (1996), pp. 223-247 **,

by J. Cullum and A. Greenbaum.

* Any Nonincreasing Convergence Curve is Possible for GMRES *

** SIAM J. Matrix Anal. Appl., 17 (1996), pp. 465-469. **,

by A. Greenbaum, V. Ptak, and Z. Strakos.