Volume 55, pp. 547-567, 2022.

When does the Lanczos algorithm compute exactly?

Dorota Šimonová and Petr Tichý

Abstract

In theory, the Lanczos algorithm generates an orthogonal basis of the corresponding Krylov subspace. However, in finite precision arithmetic the orthogonality and linear independence of the computed Lanczos vectors is usually lost quickly. In this paper we study a class of matrices and starting vectors having a special nonzero structure that guarantees exact computations of the Lanczos algorithm whenever floating point arithmetic satisfying the IEEE 754 standard is used. Analogous results are formulated also for an implementation of the conjugate gradient method called cgLanczos. This implementation then computes approximations that agree with their exact counterparts to a relative accuracy given by the machine precision and the condition number of the system matrix. The results are extended to the Arnoldi algorithm, the nonsymmetric Lanczos algorithm, the Golub-Kahan bidiagonalization, the block-Lanczos algorithm, and their counterparts for solving linear systems.

Full Text (PDF) [392 KB], BibTeX

Key words

Lanczos algorithm, exact computations, finite precision arithmetic, rounding errors

AMS subject classifications

65F10, 65F15

< Back