Inexact inverse subspace iteration with preconditioning applied to non-Hermitian eigenvalue problems

M Robbé, M Sadkane, Alastair Spence

Research output: Contribution to journalArticle

17 Citations (Scopus)
51 Downloads (Pure)

Abstract

Convergence results are provided for inexact inverse subspace iteration applied to the problem of finding the invariant subspace associated with a small number of eigenvalues of a large sparse matrix. These results are illustrated by the use of block-GMRES as the iterative solver. The costs of the inexact solves are measured by the number of inner iterations needed by the iterative solver at each outer step of the algorithm. It is shown that for a decreasing tolerance the number of inner iterations should not increase as the outer iteration proceeds, but it may increase for preconditioned iterative solves. However, it is also shown that an appropriate small rank change to the preconditioner can produce significant savings in costs and, in particular, can produce a situation where there is no increase in the costs of the iterative solves even though the solve tolerances are reducing. Numerical examples are provided to illustrate the theory.
Original languageEnglish
Pages (from-to)92-113
Number of pages22
JournalSIAM Journal On Matrix Analysis and Applications (SIMAX)
Volume31
Issue number1
Early online date27 Feb 2009
DOIs
Publication statusPublished - 2009

Fingerprint

Preconditioning
Eigenvalue Problem
Subspace
Iteration
Iterative Solver
Tolerance
Costs
GMRES
Sparse matrix
Invariant Subspace
Preconditioner
Convergence Results
Eigenvalue
Numerical Examples

Keywords

  • Eigenvalue approximation
  • Inverse subspace iteration
  • Preconditioning
  • Iterative methods

Cite this

@article{14ba67154aba45cf8a25a895b528d829,
title = "Inexact inverse subspace iteration with preconditioning applied to non-Hermitian eigenvalue problems",
abstract = "Convergence results are provided for inexact inverse subspace iteration applied to the problem of finding the invariant subspace associated with a small number of eigenvalues of a large sparse matrix. These results are illustrated by the use of block-GMRES as the iterative solver. The costs of the inexact solves are measured by the number of inner iterations needed by the iterative solver at each outer step of the algorithm. It is shown that for a decreasing tolerance the number of inner iterations should not increase as the outer iteration proceeds, but it may increase for preconditioned iterative solves. However, it is also shown that an appropriate small rank change to the preconditioner can produce significant savings in costs and, in particular, can produce a situation where there is no increase in the costs of the iterative solves even though the solve tolerances are reducing. Numerical examples are provided to illustrate the theory.",
keywords = "Eigenvalue approximation, Inverse subspace iteration, Preconditioning, Iterative methods",
author = "M Robb{\'e} and M Sadkane and Alastair Spence",
year = "2009",
doi = "10.1137/060673795",
language = "English",
volume = "31",
pages = "92--113",
journal = "SIAM Journal On Matrix Analysis and Applications (SIMAX)",
issn = "0895-4798",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "1",

}

TY - JOUR

T1 - Inexact inverse subspace iteration with preconditioning applied to non-Hermitian eigenvalue problems

AU - Robbé, M

AU - Sadkane, M

AU - Spence, Alastair

PY - 2009

Y1 - 2009

N2 - Convergence results are provided for inexact inverse subspace iteration applied to the problem of finding the invariant subspace associated with a small number of eigenvalues of a large sparse matrix. These results are illustrated by the use of block-GMRES as the iterative solver. The costs of the inexact solves are measured by the number of inner iterations needed by the iterative solver at each outer step of the algorithm. It is shown that for a decreasing tolerance the number of inner iterations should not increase as the outer iteration proceeds, but it may increase for preconditioned iterative solves. However, it is also shown that an appropriate small rank change to the preconditioner can produce significant savings in costs and, in particular, can produce a situation where there is no increase in the costs of the iterative solves even though the solve tolerances are reducing. Numerical examples are provided to illustrate the theory.

AB - Convergence results are provided for inexact inverse subspace iteration applied to the problem of finding the invariant subspace associated with a small number of eigenvalues of a large sparse matrix. These results are illustrated by the use of block-GMRES as the iterative solver. The costs of the inexact solves are measured by the number of inner iterations needed by the iterative solver at each outer step of the algorithm. It is shown that for a decreasing tolerance the number of inner iterations should not increase as the outer iteration proceeds, but it may increase for preconditioned iterative solves. However, it is also shown that an appropriate small rank change to the preconditioner can produce significant savings in costs and, in particular, can produce a situation where there is no increase in the costs of the iterative solves even though the solve tolerances are reducing. Numerical examples are provided to illustrate the theory.

KW - Eigenvalue approximation

KW - Inverse subspace iteration

KW - Preconditioning

KW - Iterative methods

UR - http://www.scopus.com/inward/record.url?scp=72449138426&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1137/060673795

U2 - 10.1137/060673795

DO - 10.1137/060673795

M3 - Article

VL - 31

SP - 92

EP - 113

JO - SIAM Journal On Matrix Analysis and Applications (SIMAX)

JF - SIAM Journal On Matrix Analysis and Applications (SIMAX)

SN - 0895-4798

IS - 1

ER -