Analysis of the BiCG Method

TR Number
Journal Title
Journal ISSN
Volume Title
Virginia Tech

The Biconjugate Gradient (BiCG) method is an iterative Krylov subspace method that utilizes a 3-term recurrence.  BiCG is the basis of several very popular methods, such as BiCGStab.  The short recurrence makes BiCG preferable to other Krylov methods because of decreased memory usage and CPU time.  However, BiCG does not satisfy any optimality conditions and it has been shown that for up to n/2-1 iterations, a special choice of the left starting vector can cause BiCG to follow {em any} 3-term recurrence.  Despite this apparent sensitivity, BiCG often converges well in practice.  This paper seeks to explain why BiCG converges so well, and what conditions can cause BiCG to behave poorly.  We use tools such as the singular value decomposition and eigenvalue decomposition to establish bounds on the residuals of BiCG and make links between BiCG and optimal Krylov methods.

Krylov methods, BiCG, GMRES, FOM