Iterative methods for solving Ax=b, GMRES/FOM versus QMR/BiCG

Jane Cullum
Mathematical Sciences Department,
IBM Research Division,
T.J. Watson Research Center,
Yorktown Heights, NY 10598, USA.
Phone: 914-945-2227
Fax: 914-945-3434
This work was supported by
NSF grant GER-9450081.

We study the convergence of
GMRES/FOM and  QMR/BiCG methods for
solving nonsymmetric Ax=b.  We prove that given the
results of a BiCG computation on Ax=b, we
can obtain a matrix B with the same eigenvalues
as A and a vector c such
that the residual norms generated by
a FOM computation on Bx=c are identical
to those generated by the BiCG computations.
Using a unitary equivalence for each of these methods,
we obtain test problems where we
can easily vary certain spectral properties of the matrices.
We  use these test problems to study the effects of nonnormality
on the convergence of GMRES and QMR, to study the effects of
eigenvalue outliers on the convergence of QMR, and
to compare the convergence of restarted GMRES, QMR,
and BiCGSTAB across a family of normal and nonnormal problems.
Our GMRES tests on nonnormal test matrices indicate that nonnormality
can have unexpected effects upon the
residual norm convergence, giving misleading indications
of superior convergence over QMR when the
error norms for GMRES are not significantly different from those for QMR.
Our QMR tests indicate that the convergence of the QMR
residual and error norms is influenced predominantly
by small and large eigenvalue outliers and by the character, real,
complex, or nearly real, of the outliers and the other eigenvalues.
In our comparison tests QMR
outperformed  GMRES(10) and GMRES(20)
on both the normal and nonnormal test matrices.