  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 a variant of
the conjugate gradient method that produces then almost exact results. 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.
