Arnoldi decomposition, GMRES, and preconditioning for linear discrete ill-posed problems

Silvia Gazzola, Silvia Noschese, Paolo Novati, Lothar Reichel

Research output: Contribution to journalArticle

13 Downloads (Pure)

Abstract

GMRES is one of the most popular iterative methods for the solution of large linear systems of equations that arise from the discretization of linear well-posed problems, such as boundary value problems for elliptic partial differential equations. The method is also applied to the iterative solution of linear systems of equations that are obtained by discretizing linear ill-posed problems, such as many inverse problems. However, GMRES does not always perform well when applied to the latter kind of problems. This paper seeks to shed some light on reasons for the poor performance of GMRES in certain situations, and discusses some remedies based on specific kinds of preconditioning. The standard implementation of GMRES is based on the Arnoldi process, which also can be used to define a solution subspace for Tikhonov or TSVD regularization, giving rise to the Arnoldi–Tikhonov and Arnoldi-TSVD methods, respectively. The performance of the GMRES, the Arnoldi–Tikhonov, and the Arnoldi-TSVD methods is discussed. Numerical examples illustrate properties of these methods.
Original languageEnglish
Pages (from-to)102-121
Number of pages20
JournalApplied Numerical Mathematics
Volume142
Early online date6 Mar 2019
DOIs
Publication statusPublished - 1 Aug 2019

Keywords

  • Arnoldi process
  • GMRES
  • Linear discrete ill-posed problem
  • Tikhonov regularization
  • Truncated iteration
  • Truncated singular value decomposition

ASJC Scopus subject areas

  • Numerical Analysis
  • Computational Mathematics
  • Applied Mathematics

Cite this

Arnoldi decomposition, GMRES, and preconditioning for linear discrete ill-posed problems. / Gazzola, Silvia; Noschese, Silvia; Novati, Paolo; Reichel, Lothar.

In: Applied Numerical Mathematics, Vol. 142, 01.08.2019, p. 102-121.

Research output: Contribution to journalArticle

Gazzola, Silvia ; Noschese, Silvia ; Novati, Paolo ; Reichel, Lothar. / Arnoldi decomposition, GMRES, and preconditioning for linear discrete ill-posed problems. In: Applied Numerical Mathematics. 2019 ; Vol. 142. pp. 102-121.
@article{712429b4795f4d908cf3c609e790db12,
title = "Arnoldi decomposition, GMRES, and preconditioning for linear discrete ill-posed problems",
abstract = "GMRES is one of the most popular iterative methods for the solution of large linear systems of equations that arise from the discretization of linear well-posed problems, such as boundary value problems for elliptic partial differential equations. The method is also applied to the iterative solution of linear systems of equations that are obtained by discretizing linear ill-posed problems, such as many inverse problems. However, GMRES does not always perform well when applied to the latter kind of problems. This paper seeks to shed some light on reasons for the poor performance of GMRES in certain situations, and discusses some remedies based on specific kinds of preconditioning. The standard implementation of GMRES is based on the Arnoldi process, which also can be used to define a solution subspace for Tikhonov or TSVD regularization, giving rise to the Arnoldi–Tikhonov and Arnoldi-TSVD methods, respectively. The performance of the GMRES, the Arnoldi–Tikhonov, and the Arnoldi-TSVD methods is discussed. Numerical examples illustrate properties of these methods.",
keywords = "Arnoldi process, GMRES, Linear discrete ill-posed problem, Tikhonov regularization, Truncated iteration, Truncated singular value decomposition",
author = "Silvia Gazzola and Silvia Noschese and Paolo Novati and Lothar Reichel",
year = "2019",
month = "8",
day = "1",
doi = "10.1016/j.apnum.2019.02.010",
language = "English",
volume = "142",
pages = "102--121",
journal = "Applied Numerical Mathematics",
issn = "0168-9274",
publisher = "Elsevier",

}

TY - JOUR

T1 - Arnoldi decomposition, GMRES, and preconditioning for linear discrete ill-posed problems

AU - Gazzola, Silvia

AU - Noschese, Silvia

AU - Novati, Paolo

AU - Reichel, Lothar

PY - 2019/8/1

Y1 - 2019/8/1

N2 - GMRES is one of the most popular iterative methods for the solution of large linear systems of equations that arise from the discretization of linear well-posed problems, such as boundary value problems for elliptic partial differential equations. The method is also applied to the iterative solution of linear systems of equations that are obtained by discretizing linear ill-posed problems, such as many inverse problems. However, GMRES does not always perform well when applied to the latter kind of problems. This paper seeks to shed some light on reasons for the poor performance of GMRES in certain situations, and discusses some remedies based on specific kinds of preconditioning. The standard implementation of GMRES is based on the Arnoldi process, which also can be used to define a solution subspace for Tikhonov or TSVD regularization, giving rise to the Arnoldi–Tikhonov and Arnoldi-TSVD methods, respectively. The performance of the GMRES, the Arnoldi–Tikhonov, and the Arnoldi-TSVD methods is discussed. Numerical examples illustrate properties of these methods.

AB - GMRES is one of the most popular iterative methods for the solution of large linear systems of equations that arise from the discretization of linear well-posed problems, such as boundary value problems for elliptic partial differential equations. The method is also applied to the iterative solution of linear systems of equations that are obtained by discretizing linear ill-posed problems, such as many inverse problems. However, GMRES does not always perform well when applied to the latter kind of problems. This paper seeks to shed some light on reasons for the poor performance of GMRES in certain situations, and discusses some remedies based on specific kinds of preconditioning. The standard implementation of GMRES is based on the Arnoldi process, which also can be used to define a solution subspace for Tikhonov or TSVD regularization, giving rise to the Arnoldi–Tikhonov and Arnoldi-TSVD methods, respectively. The performance of the GMRES, the Arnoldi–Tikhonov, and the Arnoldi-TSVD methods is discussed. Numerical examples illustrate properties of these methods.

KW - Arnoldi process

KW - GMRES

KW - Linear discrete ill-posed problem

KW - Tikhonov regularization

KW - Truncated iteration

KW - Truncated singular value decomposition

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

U2 - 10.1016/j.apnum.2019.02.010

DO - 10.1016/j.apnum.2019.02.010

M3 - Article

VL - 142

SP - 102

EP - 121

JO - Applied Numerical Mathematics

JF - Applied Numerical Mathematics

SN - 0168-9274

ER -