Treatment of near-breakdown in the CGS algorithm (Q1334209)

The authors consider the system of linear algebraic equations (1) \(Ax = b\) with nonsingular matrix \(A\). They define the linear functional \(c\) on the space of polynomials by the relation \[ c(\xi^ i) = (y, A^ i r_ 0), \] where \(y\) is a given nonzero vector, \(r_ 0 = b - Ax_ 0\), and \(x_ 0\) is an initial approximation, by using Lanczos' method for solving (1). The residue \(r_ k = b - Ax_ k = P_ k(A)r_ 0\) and Lanczos' method imply orthogonality relations for the polynomials \(P_ k\), \(k = 0,1,\dots\) with respect to \(c\). The behaviour and form of the \(P_ k\) are studied in detail. The coefficients appearing in the recurrence relations for \(P_ k\) are given as ratios of scalar products. When a denominator is close to zero then a ``near-breakdown'' situation occurs. The stopping of the algorithm can be avoided by jumping over non-existing polynomials. In this sense the conjugate gradient squared (CGS) algorithm, i.e. \(r_ k = P^ 2_ k(A)r_ 0\), is investigated and a pseudocode of the corresponding BSMRZS algorithm (modification of the method of recursive zoom algorithm) and informations about this code in FORTRAN 77 are presented. Five illustrative examples complete this paper.