×

zbMATH — the first resource for mathematics

The Lanczos algorithm with partial reorthogonalization. (English) Zbl 0546.65017
The author proposes a new method to avoid the instability of the Lanczos algorithm. Starting from a symmetric matrix A and a vector \(r_ 1\) a sequence \(q_ 1,q_ 2,..\). is calculated which in exact arithmetic is orthonormal, and tridiagonal matrices \(T_ 1,T_ 2,... \). In finite precision arithmetic the orthogonality is lost. It is shown by the author that if the \(q_ j's\) are still semi-orthogonal (i.e. \(| q^*_ iq_ j|\leq \sqrt{\epsilon}\), \(1\leq i<j\), where \(\epsilon\) is the roundoff unit) then \(T_ j\) is, up to roundoff, the orthogonal projection of A onto \(span(q_ 1,...,q_ j)\). Hence a reorthogonalization is necessary only if semi-orthogonality is lost. The author discusses ways to compute or estimate the level of orthogonality without much arithmetic. It is also discussed how after semi- orthogonalization is lost a partial reorthogonalization can be computed.
The Lanczos algorithm can be used for the solution of systems of linear equations. Many numerical examples for this are given and the results compared to other methods, such as SYMMLQ, Lanczos with full reorthogonalization and cg methods without and with preconditioning. With the exception of the last method the proposed method is always better.
Reviewer: L.Elsner

MSC:
65F25 Orthogonalization in numerical linear algebra
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
PDF BibTeX XML Cite
Full Text: DOI