Breakdown and near-breakdown control in the CGS algorithm using stochastic arithmetic (Q1911443)

The aim of this paper is to show how using stochastic arithmetic the problem with near-breakdown can be eliminated. In the conjugate gradient squared (CGS) method (which is a variant of the Lanczos method), a sequence of residuals \(r_k= P^2_k (A) r_0\) has to be computed. The coefficients of the orthogonal matrix polynomials \(P_k (A)\) are given by ratios of scalar products. However, when some of the scalar products appearing in the demoninators are badly computed, then rounding errors can affect all the computations -- a typical situation of near-breakdown. In specific computations, due to the finite precision one cannot distinguish between breakdown and near-breakdown. Recurrence formulas for orthogonal polynomials in order to avoid near-breakdown in CGS algorithm have been proposed by C. Brezinski and M. Redivo-Zagaria, but some choices have to be made: when to jump and what is the size of the jump. In this paper, the authors present an algorithm using stochastic arithmetic where the computer decides whether to jump or not and how far. Some numerical results showing the good numerical properties of the proposed algorithm are given. This techniques can be applied to different algorithms involving recurrence relations for orthogonal polynomials and can be useful in detecting and controlling numerical instabilities.