BREAKDOWNS IN THE IMPLEMENTATION OF THE LANCZOS METHOD FOR SOLVING LINEAR-SYSTEMS

The Lanczos method for solving systems of linear equations is based on formal orthogonal polynomials. Its implementation is realized via som e recurrence relationships between polynomials of a family of orthogon al polynomials or between those of two adjacent families of orthogonal polynomials. A division by zero can occur in such recurrence relation s, thus causing a breakdown in the algorithm which has to be stopped. In this paper, two types of breakdowns are discussed. The true breakdo wns which are due to the nonexistence of some polynomials and the ghos t breakdowns which are due to the recurrence relationship used. Among all the recurrence relationships which can be used and all the algorit hms for implementing the Lanczos method which came out from them, the only reliable algorithm is Lanczos/Orthodir which can only suffer from true breakdowns. It is shown how to avoid true breakdowns in this alg orithm. Other algorithms are also discussed and the case of near-break down is treated. The same treatment applies to other methods related t o Lanczos'.