GMRES convergence bounds for eigenvalue problems

Melina A. Freitag, Patrick Kürschner, Jennifer Pestana

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

The convergence of GMRES for solving linear systems can be influenced heavily by the structure of the right hand side. Within the solution of eigenvalue problems via inverse iteration or subspace iteration, the right hand side is generally related to an approximate invariant subspace of the linear system. We give detailed and new bounds on (block) GMRES that take the special behavior of the right hand side into account and explain the initial sharp decrease of the GMRES residual. The bounds motivate the use of specific preconditioners for these eigenvalue problems, e.g. tuned and polynomial preconditioners, as we describe. The numerical results show that the new (block) GMRES bounds are much sharper than conventional bounds and that preconditioned subspace iteration with either a tuned or polynomial preconditioner should be used in practice.
LanguageEnglish
Pages203-222
Number of pages20
JournalComputational Methods in Applied Mathematics
Volume18
Issue number2
Early online date7 Jun 2017
DOIs
Publication statusPublished - 30 Apr 2018

Fingerprint

GMRES
Eigenvalue Problem
Linear systems
Polynomials
Preconditioner
Linear Systems
Subspace
Inverse Iteration
Iteration
Polynomial
Invariant Subspace
Numerical Results
Decrease

Keywords

  • GMRES
  • convergence analysis
  • inexact inverse iteration
  • inexact subspace iteration
  • Krylov subspace methods
  • block Krylov methods
  • preconditioning

Cite this

Freitag, Melina A. ; Kürschner, Patrick ; Pestana, Jennifer. / GMRES convergence bounds for eigenvalue problems. In: Computational Methods in Applied Mathematics. 2018 ; Vol. 18, No. 2. pp. 203-222.
@article{560baee15a1c441d824efc4accd07ca5,
title = "GMRES convergence bounds for eigenvalue problems",
abstract = "The convergence of GMRES for solving linear systems can be influenced heavily by the structure of the right hand side. Within the solution of eigenvalue problems via inverse iteration or subspace iteration, the right hand side is generally related to an approximate invariant subspace of the linear system. We give detailed and new bounds on (block) GMRES that take the special behavior of the right hand side into account and explain the initial sharp decrease of the GMRES residual. The bounds motivate the use of specific preconditioners for these eigenvalue problems, e.g. tuned and polynomial preconditioners, as we describe. The numerical results show that the new (block) GMRES bounds are much sharper than conventional bounds and that preconditioned subspace iteration with either a tuned or polynomial preconditioner should be used in practice.",
keywords = "GMRES, convergence analysis, inexact inverse iteration, inexact subspace iteration, Krylov subspace methods, block Krylov methods, preconditioning",
author = "Freitag, {Melina A.} and Patrick K{\"u}rschner and Jennifer Pestana",
year = "2018",
month = "4",
day = "30",
doi = "10.1515/cmam-2017-0017",
language = "English",
volume = "18",
pages = "203--222",
journal = "Computational Methods in Applied Mathematics",
issn = "1609-9389",
number = "2",

}

GMRES convergence bounds for eigenvalue problems. / Freitag, Melina A.; Kürschner, Patrick; Pestana, Jennifer.

In: Computational Methods in Applied Mathematics, Vol. 18, No. 2, 30.04.2018, p. 203-222.

Research output: Contribution to journalArticle

TY - JOUR

T1 - GMRES convergence bounds for eigenvalue problems

AU - Freitag, Melina A.

AU - Kürschner, Patrick

AU - Pestana, Jennifer

PY - 2018/4/30

Y1 - 2018/4/30

N2 - The convergence of GMRES for solving linear systems can be influenced heavily by the structure of the right hand side. Within the solution of eigenvalue problems via inverse iteration or subspace iteration, the right hand side is generally related to an approximate invariant subspace of the linear system. We give detailed and new bounds on (block) GMRES that take the special behavior of the right hand side into account and explain the initial sharp decrease of the GMRES residual. The bounds motivate the use of specific preconditioners for these eigenvalue problems, e.g. tuned and polynomial preconditioners, as we describe. The numerical results show that the new (block) GMRES bounds are much sharper than conventional bounds and that preconditioned subspace iteration with either a tuned or polynomial preconditioner should be used in practice.

AB - The convergence of GMRES for solving linear systems can be influenced heavily by the structure of the right hand side. Within the solution of eigenvalue problems via inverse iteration or subspace iteration, the right hand side is generally related to an approximate invariant subspace of the linear system. We give detailed and new bounds on (block) GMRES that take the special behavior of the right hand side into account and explain the initial sharp decrease of the GMRES residual. The bounds motivate the use of specific preconditioners for these eigenvalue problems, e.g. tuned and polynomial preconditioners, as we describe. The numerical results show that the new (block) GMRES bounds are much sharper than conventional bounds and that preconditioned subspace iteration with either a tuned or polynomial preconditioner should be used in practice.

KW - GMRES

KW - convergence analysis

KW - inexact inverse iteration

KW - inexact subspace iteration

KW - Krylov subspace methods

KW - block Krylov methods

KW - preconditioning

UR - https://www.degruyter.com/view/j/cmam

U2 - 10.1515/cmam-2017-0017

DO - 10.1515/cmam-2017-0017

M3 - Article

VL - 18

SP - 203

EP - 222

JO - Computational Methods in Applied Mathematics

T2 - Computational Methods in Applied Mathematics

JF - Computational Methods in Applied Mathematics

SN - 1609-9389

IS - 2

ER -