Shift-invert Arnoldi's method with preconditioned iterative solves

Melina A. Freitag, Alastair Spence

Research output: Contribution to journalArticle

16 Citations (Scopus)

Abstract

We consider the computation of a few eigenvectors and corresponding eigenvalues of a large sparse nonsymmetric matrix using shift-invert Arnoldi's method with and without implicit restarts. For the inner iterations we use preconditioned GMRES as the inexact iterative solver. The costs of the solves are measured by the number of inner iterations needed by the iterative solver at each outer step of the algorithm. We first extend the relaxation strategy developed by Simoncini [SIAM J. Numer. Anal., 43 (2005), pp. 1155-1174] to implicitly restarted Arnoldi's method, which yields an improvement in the overall costs of the method. Secondly, we apply a new preconditioning strategy to the inner solver. We show that small rank changes to the preconditioner can produce significant savings in the total number of iterations. The combination of the new preconditioner with the relaxation strategy in implicitly restarted Arnoldi produces enhancement in the overall costs of around 50 percent in the examples considered here. Numerical experiments illustrate the theory throughout the paper.
Original languageEnglish
Pages (from-to)942-969
Number of pages28
JournalSIAM Journal On Matrix Analysis and Applications (SIMAX)
Volume31
Issue number3
Early online date11 Aug 2009
DOIs
Publication statusPublished - 2010

Fingerprint

Arnoldi Method
Invert
Iterative Solver
Iteration
Preconditioner
Costs
Nonsymmetric Matrix
Arnoldi
GMRES
Restart
Sparse matrix
Preconditioning
Percent
Eigenvector
Enhancement
Numerical Experiment
Eigenvalue
Strategy

Cite this

Shift-invert Arnoldi's method with preconditioned iterative solves. / Freitag, Melina A.; Spence, Alastair.

In: SIAM Journal On Matrix Analysis and Applications (SIMAX), Vol. 31, No. 3, 2010, p. 942-969.

Research output: Contribution to journalArticle

@article{563dd899264e4ba7a035b33c73f5240e,
title = "Shift-invert Arnoldi's method with preconditioned iterative solves",
abstract = "We consider the computation of a few eigenvectors and corresponding eigenvalues of a large sparse nonsymmetric matrix using shift-invert Arnoldi's method with and without implicit restarts. For the inner iterations we use preconditioned GMRES as the inexact iterative solver. The costs of the solves are measured by the number of inner iterations needed by the iterative solver at each outer step of the algorithm. We first extend the relaxation strategy developed by Simoncini [SIAM J. Numer. Anal., 43 (2005), pp. 1155-1174] to implicitly restarted Arnoldi's method, which yields an improvement in the overall costs of the method. Secondly, we apply a new preconditioning strategy to the inner solver. We show that small rank changes to the preconditioner can produce significant savings in the total number of iterations. The combination of the new preconditioner with the relaxation strategy in implicitly restarted Arnoldi produces enhancement in the overall costs of around 50 percent in the examples considered here. Numerical experiments illustrate the theory throughout the paper.",
author = "Freitag, {Melina A.} and Alastair Spence",
year = "2010",
doi = "10.1137/080716281",
language = "English",
volume = "31",
pages = "942--969",
journal = "SIAM Journal On Matrix Analysis and Applications (SIMAX)",
issn = "0895-4798",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

TY - JOUR

T1 - Shift-invert Arnoldi's method with preconditioned iterative solves

AU - Freitag, Melina A.

AU - Spence, Alastair

PY - 2010

Y1 - 2010

N2 - We consider the computation of a few eigenvectors and corresponding eigenvalues of a large sparse nonsymmetric matrix using shift-invert Arnoldi's method with and without implicit restarts. For the inner iterations we use preconditioned GMRES as the inexact iterative solver. The costs of the solves are measured by the number of inner iterations needed by the iterative solver at each outer step of the algorithm. We first extend the relaxation strategy developed by Simoncini [SIAM J. Numer. Anal., 43 (2005), pp. 1155-1174] to implicitly restarted Arnoldi's method, which yields an improvement in the overall costs of the method. Secondly, we apply a new preconditioning strategy to the inner solver. We show that small rank changes to the preconditioner can produce significant savings in the total number of iterations. The combination of the new preconditioner with the relaxation strategy in implicitly restarted Arnoldi produces enhancement in the overall costs of around 50 percent in the examples considered here. Numerical experiments illustrate the theory throughout the paper.

AB - We consider the computation of a few eigenvectors and corresponding eigenvalues of a large sparse nonsymmetric matrix using shift-invert Arnoldi's method with and without implicit restarts. For the inner iterations we use preconditioned GMRES as the inexact iterative solver. The costs of the solves are measured by the number of inner iterations needed by the iterative solver at each outer step of the algorithm. We first extend the relaxation strategy developed by Simoncini [SIAM J. Numer. Anal., 43 (2005), pp. 1155-1174] to implicitly restarted Arnoldi's method, which yields an improvement in the overall costs of the method. Secondly, we apply a new preconditioning strategy to the inner solver. We show that small rank changes to the preconditioner can produce significant savings in the total number of iterations. The combination of the new preconditioner with the relaxation strategy in implicitly restarted Arnoldi produces enhancement in the overall costs of around 50 percent in the examples considered here. Numerical experiments illustrate the theory throughout the paper.

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

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

U2 - 10.1137/080716281

DO - 10.1137/080716281

M3 - Article

VL - 31

SP - 942

EP - 969

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

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

SN - 0895-4798

IS - 3

ER -