Inexact inverse iteration for symmetric matrices

Jorg Berns-Müller, Ivan G. Graham, Alastair Spence

Research output: Contribution to journalArticle

34 Citations (Scopus)
51 Downloads (Pure)

Abstract

In this paper we analyse inexact inverse iteration for the real symmetric eigenvalue problem Av = λv. Our analysis is designed to apply to the case when A is large and sparse and where iterative methods are used to solve the shifted linear systems (A − σI)y = x which arise. We present a convergence theory that is independent of the nature of the inexact solver used, and, though the use of the Rayleigh quotient is emphasised, our analysis also extends to quite general choices for shift and inexact solver strategies. Additionally, the convergence framework allows us to treat both standard preconditioning and to present a new analysis of the variation introduced by Simoncini and Eldén (BIT, vol. 42, pp.159–182, 2002). Also, we provide an analysis of the performance of inner iteration solves when preconditioned MINRES is used as the inexact solver. This analysis provides descriptive bounds which are shown to predict well the actual behaviour observed in practice. Also, it explains the improvement in performance of the modification introduced by Simoncini and Eldén over the standard preconditioned form. Importantly, our analysis shows that letting the shift tend to the eigenvalue, as is the case if the Rayleigh quotient is used, does not harm significantly the performance of the iterative method for the shifted systems. Throughout the paper numerical results are given to illustrate the theory.
Original languageEnglish
Pages (from-to)389-413
Number of pages25
JournalLinear Algebra and its Applications
Volume416
Issue number2-3
Early online date9 Feb 2006
DOIs
Publication statusPublished - 15 Jul 2006

Fingerprint

Inverse Iteration
Iterative methods
Symmetric matrix
Linear systems
Rayleigh quotient
Iteration
MINRES
Symmetric Eigenvalue Problem
Convergence Theory
Preconditioning
Linear Systems
Tend
Eigenvalue
Predict
Numerical Results

Keywords

  • Rayleigh quotient iteration
  • Inverse iteration
  • Preconditioned MINRES
  • Iterative methods

Cite this

Inexact inverse iteration for symmetric matrices. / Berns-Müller, Jorg; Graham, Ivan G.; Spence, Alastair.

In: Linear Algebra and its Applications, Vol. 416, No. 2-3, 15.07.2006, p. 389-413.

Research output: Contribution to journalArticle

@article{a45c550d3e544884af2439aea80ed07a,
title = "Inexact inverse iteration for symmetric matrices",
abstract = "In this paper we analyse inexact inverse iteration for the real symmetric eigenvalue problem Av = λv. Our analysis is designed to apply to the case when A is large and sparse and where iterative methods are used to solve the shifted linear systems (A − σI)y = x which arise. We present a convergence theory that is independent of the nature of the inexact solver used, and, though the use of the Rayleigh quotient is emphasised, our analysis also extends to quite general choices for shift and inexact solver strategies. Additionally, the convergence framework allows us to treat both standard preconditioning and to present a new analysis of the variation introduced by Simoncini and Eld{\'e}n (BIT, vol. 42, pp.159–182, 2002). Also, we provide an analysis of the performance of inner iteration solves when preconditioned MINRES is used as the inexact solver. This analysis provides descriptive bounds which are shown to predict well the actual behaviour observed in practice. Also, it explains the improvement in performance of the modification introduced by Simoncini and Eld{\'e}n over the standard preconditioned form. Importantly, our analysis shows that letting the shift tend to the eigenvalue, as is the case if the Rayleigh quotient is used, does not harm significantly the performance of the iterative method for the shifted systems. Throughout the paper numerical results are given to illustrate the theory.",
keywords = "Rayleigh quotient iteration, Inverse iteration, Preconditioned MINRES, Iterative methods",
author = "Jorg Berns-M{\"u}ller and Graham, {Ivan G.} and Alastair Spence",
note = "The original publication is available at www.sciencedirect.com",
year = "2006",
month = "7",
day = "15",
doi = "10.1016/j.laa.2005.11.019",
language = "English",
volume = "416",
pages = "389--413",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",
publisher = "Elsevier",
number = "2-3",

}

TY - JOUR

T1 - Inexact inverse iteration for symmetric matrices

AU - Berns-Müller, Jorg

AU - Graham, Ivan G.

AU - Spence, Alastair

N1 - The original publication is available at www.sciencedirect.com

PY - 2006/7/15

Y1 - 2006/7/15

N2 - In this paper we analyse inexact inverse iteration for the real symmetric eigenvalue problem Av = λv. Our analysis is designed to apply to the case when A is large and sparse and where iterative methods are used to solve the shifted linear systems (A − σI)y = x which arise. We present a convergence theory that is independent of the nature of the inexact solver used, and, though the use of the Rayleigh quotient is emphasised, our analysis also extends to quite general choices for shift and inexact solver strategies. Additionally, the convergence framework allows us to treat both standard preconditioning and to present a new analysis of the variation introduced by Simoncini and Eldén (BIT, vol. 42, pp.159–182, 2002). Also, we provide an analysis of the performance of inner iteration solves when preconditioned MINRES is used as the inexact solver. This analysis provides descriptive bounds which are shown to predict well the actual behaviour observed in practice. Also, it explains the improvement in performance of the modification introduced by Simoncini and Eldén over the standard preconditioned form. Importantly, our analysis shows that letting the shift tend to the eigenvalue, as is the case if the Rayleigh quotient is used, does not harm significantly the performance of the iterative method for the shifted systems. Throughout the paper numerical results are given to illustrate the theory.

AB - In this paper we analyse inexact inverse iteration for the real symmetric eigenvalue problem Av = λv. Our analysis is designed to apply to the case when A is large and sparse and where iterative methods are used to solve the shifted linear systems (A − σI)y = x which arise. We present a convergence theory that is independent of the nature of the inexact solver used, and, though the use of the Rayleigh quotient is emphasised, our analysis also extends to quite general choices for shift and inexact solver strategies. Additionally, the convergence framework allows us to treat both standard preconditioning and to present a new analysis of the variation introduced by Simoncini and Eldén (BIT, vol. 42, pp.159–182, 2002). Also, we provide an analysis of the performance of inner iteration solves when preconditioned MINRES is used as the inexact solver. This analysis provides descriptive bounds which are shown to predict well the actual behaviour observed in practice. Also, it explains the improvement in performance of the modification introduced by Simoncini and Eldén over the standard preconditioned form. Importantly, our analysis shows that letting the shift tend to the eigenvalue, as is the case if the Rayleigh quotient is used, does not harm significantly the performance of the iterative method for the shifted systems. Throughout the paper numerical results are given to illustrate the theory.

KW - Rayleigh quotient iteration

KW - Inverse iteration

KW - Preconditioned MINRES

KW - Iterative methods

UR - http://www.sciencedirect.com/science/journal/00243795

U2 - 10.1016/j.laa.2005.11.019

DO - 10.1016/j.laa.2005.11.019

M3 - Article

VL - 416

SP - 389

EP - 413

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

IS - 2-3

ER -