Variable Accuracy of Matrix-Vector Products in Projection Methods for Eigencomputation

We analyze the behavior of projection-type schemes, such as the Arnoldi and Lanczos methods, for the approximation of a few eigenvalues and eigenvectors of a matrix A, when A cannot be applied exactly but only with a possibly large perturbation. This occurs, for instance, in shift-and-invert procedu...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on numerical analysis 2005-01, Vol.43 (3), p.1155-1174
Main Author: Simoncini, V.
Format: Article
Language:English
Subjects:
Accuracy
Approximation
Eigenvalues
Eigenvectors
Methods
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:We analyze the behavior of projection-type schemes, such as the Arnoldi and Lanczos methods, for the approximation of a few eigenvalues and eigenvectors of a matrix A, when A cannot be applied exactly but only with a possibly large perturbation. This occurs, for instance, in shift-and-invert procedures or when dealing with large generalized eigenvalue problems. We theoretically show that the accuracy with which A is applied at each iteration can be relaxed, as convergence to specific eigenpairs takes place. We show that the size of the perturbation is allowed to be inversely proportional to the current residual norm, in a way that also depends on the sensitivity of the matrix A. This result provides a complete understanding of reported experimental evidence in the recent literature. Moreover, we adapt our theoretical results to devise a practical relaxation criterion to achieve convergence of the inexact procedure. Numerical experiments validate our analysis.
ISSN:0036-1429
1095-7170
DOI:10.1137/040605333