The Convergence of BiCG

Eric de Sturler

Swiss Center for Scientific Computing - ETH Zurich
Swiss Federal Institute of Technology Zurich
ETH Zentrum, RZ F-11
CH-8092 Zurich, Switzerland


Abstract

Although BiCG is at the basis of some of the most popular iterative linear solvers, our understanding of its convergence is still very poor. Or, to quote Anne Greenbaum [Numerical Analysis, Dundee'97, draft]: "Despite the lack of theory, numerical examples demonstrate that the convergence of iterative linear system solvers based on the two­sided Lanczos algorithm is not very sensitive to the choice of the left starting vector, if that vector is chosen randomly. A theoretical explanation for this remains an open problem." This is one of the important questions that we try to answer.

To gain a better understanding of the convergence of the BiCG iteration we derive a related BiCG iteration that takes place in eigenspace. We decompose the left and right Lanczos vectors generated by BiCG along the left and right eigenvectors respectively. The standard BiCG iteration then corresponds to an eigenspace BiCG iteration with the eigenvalue matrix and its conjugate transpose, using a special inner product derived from the left and right (normalized) eigenvector matrices. The eigenspace BiCG then generates the same tridiagonal as the original BiCG. Moreover, we can use the standard inner product instead of the special inner product if we make an appropriate change in the left starting vector. The convergence of this eigenspace BiCG is related to the convergence of BiCG by a norm derived from the right (normalized) eigenvector matrix.

We will show that this BiCG iteration taking place in (left- and right) eigenspace has special properties that help understand the behaviour of the standard BiCG iteration. For the eigenspace BiCG iteration we will show that if certain mild conditions are fulfilled the left Lanczos space approaches the right Lanczos space, in a way that can be exactly quantified. The BiCG condition that the new residual (right Lanczos vector) be orthogonal to the left Lanczos space therefore can be related to the FOM condition that the new residual be orthogonal to the right Lanczos space (Krylov space), for a FOM iteration solving the same equation. It was shown by Cullum & Greenbaum [SIMAX 17(2)] that FOM behaves more or less like GMRES, which is an optimal method and much better understood. >From the relations between the left Lanczos space and the right Lanczos space from the eigenspace BiCG iteration and the FOM residual(s) we can derive bounds for the residual (norm) of the eigenspace BiCG. We will also discuss under what conditions the convergence of BiCG can be very poor. All this information on the eigenspace BiCG iteration can be related back to the standard BiCG iteration. -- ============================================================================= = Dr. Eric de Sturler = = Research Scientist, Advanced Numerical Algorithms Group = = Swiss Center for Scientific Computing (SCSC-ETH Zurich) = = = =---------------------------------------------------------------------------= = = = Swiss Federal Institute of Technology phone : +41-1-632 5566 = = Clausiusstrasse 59, RZ F-11 fax : +41-1-632 1104 = = ETH-Zentrum, CH-8092 Zurich, Switzerland email : sturler@scsc.ethz.ch = =============================================================================