A breakdown-free Lanczos type algorithm for solving linear systems

Lanczos type algorithms for solving systems of linear equations have their foundations in the theory of formal orthogonal polynomials and the method of moments which leads to a determinantal formula for their iterates. The various Lanczos type algorithms mainly differ by the way of computing the coefficients entering into the recurrence formulae. If the denominator in the formula for one of these coefficients is zero, then a breakdown occurs in the algorithm, and it must be stopped. Such a breakdown is in fact due to the non-existence of some orthogonal polynomial. In this paper we show how to jump over such a singularity by computing the next existing orthogonal polynomial by the block bordering method. The resulting algorithm, called MRZ, is equivalent to the nongeneric BIODIR algorithm (which is a look-ahead Lanczos type algorithm), but our derivation is much simpler.