Treatment of near-breakdown in the CGS algorithm

Lanczos' method for solving the system of linear equations Ax = b consists in constructing a sequence of vectors (x_k) such that r_k = b - A x_k = P_k(A)ro where r_0 = b - A x_0. P_k is an orthogonal polynomial which is computed recursively. The conjugate gradient squared algorithm (CGS) consists in taking r_k = P^2_k(A) r_0. In the recurrence relation for P_k, the coefficients are given as ratios of scalar products. When a scalar product in a denominator is zero, then a breakdown occurs in the algorithm. When such a scalar product is close to zero, then rounding errors can seriously affect the algorithm, a situation known as near-breakdown. In this paper it is shown how to avoid near-breakdown in the CGS algorithm in order to obtain a more stable method.