Look-ahead in bi-cgstab and other methods for linear systems

The Lanczos method for solving Ax = b consists in constructing the sequence of vectors x(k) such that r(k) = b - Ax(k) = P-k(A)r(0) where P-k is the orthogonal polynomial of degree at most k with respect to the linear functional c whose moments are c(xi(i)) = c(i) = (y, A(i)r(0)). In this paper we discuss how to avoid breakdown and near-breakdown in a whole class of methods defined by r(k) = Q(k)(A)P-k(A)r(0), Q(k) being a given polynomial. In particular, the case of the Bi-CGSTAB algorithm is treated in detail. Some other choices of the polynomials Q(k) are also studied.