The influence of orthogonality on the Arnoldi method

Many algorithms for solving eigenproblems need to compute an orthonormal basis. The computation is commonly performed using a QR factorization computed using the classical or the modified Gram–Schmidt algorithm, the Householder algorithm, the Givens algorithm or the Gram–Schmidt algorithm with itera...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2000-04, Vol.309 (1), p.307-323
Main Authors: Braconnier, T., Langlois, P., Rioual, J.C.
Format: Article
Language:English
Subjects:
Arnoldi method
Backward error
Eigenvalues
QR factorization
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Many algorithms for solving eigenproblems need to compute an orthonormal basis. The computation is commonly performed using a QR factorization computed using the classical or the modified Gram–Schmidt algorithm, the Householder algorithm, the Givens algorithm or the Gram–Schmidt algorithm with iterative reorthogonalization. For the eigenproblem, although textbooks warn users about the possible instability of eigensolvers due to loss of orthonormality, few theoretical results exist. In this paper we prove that the loss of orthonormality of the computed basis can affect the reliability of the computed eigenpair when we use the Arnoldi method. We also show that the stopping criterion based on the backward error and the value computed using the Arnoldi method can differ because of the loss of orthonormality of the computed basis of the Krylov subspace. We also give a bound which quantifies this difference in terms of the loss of orthonormality.
ISSN:0024-3795
1873-1856
DOI:10.1016/S0024-3795(99)00100-7