A tuned preconditioner for inexact inverse iteration applied to Hermitian eigenvalue problems

Melina A Freitag, Alastair Spence

Research output: Contribution to journalArticle

27 Citations (Scopus)

Abstract

In this paper, we consider the computation of an eigenvalue and the corresponding eigenvector of a large sparse Hermitian positive-definite matrix using inexact inverse iteration with a fixed shift. For such problems, the large sparse linear systems arising at each iteration are often solved approximately by means of symmetrically preconditioned MINRES. We consider preconditioners based on the incomplete Cholesky factorization and derive a new tuned Cholesky preconditioner which shows considerable improvement over the standard preconditioner. This improvement is analysed using the convergence theory for MINRES. We also compare the spectral properties of the tuned preconditioned matrix with those of the standard preconditioned matrix. In particular, we provide both a perturbation result and an interlacing result, and these results show that the spectral properties of the tuned preconditioner are similar to those of the standard preconditioner. For Rayleigh quotient shifts, comparison is also made with a technique introduced by Simoncini & Eldén (2002, BIT, 42, 159–182) which involves changing the right-hand side of the inverse iteration step. Several numerical examples are given to illustrate the theory described in the paper.
Original languageEnglish
Pages (from-to)522-551
Number of pages30
JournalIMA Journal of Numerical Analysis
Volume28
Issue number3
DOIs
Publication statusPublished - 2008

Fingerprint

Inverse Iteration
Preconditioner
Eigenvalue Problem
MINRES
Spectral Properties
Factorization
Eigenvalues and eigenfunctions
Linear systems
Rayleigh quotient
Cholesky
Interlacing
Cholesky factorisation
Sparse Linear Systems
Convergence Theory
Positive definite matrix
Eigenvector
Eigenvalue
Perturbation
Iteration
Numerical Examples

Cite this

A tuned preconditioner for inexact inverse iteration applied to Hermitian eigenvalue problems. / Freitag, Melina A; Spence, Alastair.

In: IMA Journal of Numerical Analysis, Vol. 28, No. 3, 2008, p. 522-551.

Research output: Contribution to journalArticle

@article{dde65ab5486042759e2d6cec14068142,
title = "A tuned preconditioner for inexact inverse iteration applied to Hermitian eigenvalue problems",
abstract = "In this paper, we consider the computation of an eigenvalue and the corresponding eigenvector of a large sparse Hermitian positive-definite matrix using inexact inverse iteration with a fixed shift. For such problems, the large sparse linear systems arising at each iteration are often solved approximately by means of symmetrically preconditioned MINRES. We consider preconditioners based on the incomplete Cholesky factorization and derive a new tuned Cholesky preconditioner which shows considerable improvement over the standard preconditioner. This improvement is analysed using the convergence theory for MINRES. We also compare the spectral properties of the tuned preconditioned matrix with those of the standard preconditioned matrix. In particular, we provide both a perturbation result and an interlacing result, and these results show that the spectral properties of the tuned preconditioner are similar to those of the standard preconditioner. For Rayleigh quotient shifts, comparison is also made with a technique introduced by Simoncini & Eld{\'e}n (2002, BIT, 42, 159–182) which involves changing the right-hand side of the inverse iteration step. Several numerical examples are given to illustrate the theory described in the paper.",
author = "Freitag, {Melina A} and Alastair Spence",
year = "2008",
doi = "10.1093/imanum/drm036",
language = "English",
volume = "28",
pages = "522--551",
journal = "IMA Journal of Numerical Analysis",
issn = "0272-4979",
publisher = "Oxford University Press",
number = "3",

}

TY - JOUR

T1 - A tuned preconditioner for inexact inverse iteration applied to Hermitian eigenvalue problems

AU - Freitag, Melina A

AU - Spence, Alastair

PY - 2008

Y1 - 2008

N2 - In this paper, we consider the computation of an eigenvalue and the corresponding eigenvector of a large sparse Hermitian positive-definite matrix using inexact inverse iteration with a fixed shift. For such problems, the large sparse linear systems arising at each iteration are often solved approximately by means of symmetrically preconditioned MINRES. We consider preconditioners based on the incomplete Cholesky factorization and derive a new tuned Cholesky preconditioner which shows considerable improvement over the standard preconditioner. This improvement is analysed using the convergence theory for MINRES. We also compare the spectral properties of the tuned preconditioned matrix with those of the standard preconditioned matrix. In particular, we provide both a perturbation result and an interlacing result, and these results show that the spectral properties of the tuned preconditioner are similar to those of the standard preconditioner. For Rayleigh quotient shifts, comparison is also made with a technique introduced by Simoncini & Eldén (2002, BIT, 42, 159–182) which involves changing the right-hand side of the inverse iteration step. Several numerical examples are given to illustrate the theory described in the paper.

AB - In this paper, we consider the computation of an eigenvalue and the corresponding eigenvector of a large sparse Hermitian positive-definite matrix using inexact inverse iteration with a fixed shift. For such problems, the large sparse linear systems arising at each iteration are often solved approximately by means of symmetrically preconditioned MINRES. We consider preconditioners based on the incomplete Cholesky factorization and derive a new tuned Cholesky preconditioner which shows considerable improvement over the standard preconditioner. This improvement is analysed using the convergence theory for MINRES. We also compare the spectral properties of the tuned preconditioned matrix with those of the standard preconditioned matrix. In particular, we provide both a perturbation result and an interlacing result, and these results show that the spectral properties of the tuned preconditioner are similar to those of the standard preconditioner. For Rayleigh quotient shifts, comparison is also made with a technique introduced by Simoncini & Eldén (2002, BIT, 42, 159–182) which involves changing the right-hand side of the inverse iteration step. Several numerical examples are given to illustrate the theory described in the paper.

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

UR - http://dx.doi.org/10.1093/imanum/drm036

U2 - 10.1093/imanum/drm036

DO - 10.1093/imanum/drm036

M3 - Article

VL - 28

SP - 522

EP - 551

JO - IMA Journal of Numerical Analysis

JF - IMA Journal of Numerical Analysis

SN - 0272-4979

IS - 3

ER -