Natural preconditioning and iterative methods for saddle point systems

Jennifer Pestana, Andrew J. Wathen

Research output: Contribution to journalArticle

24 Citations (Scopus)

Abstract

The solution of quadratic or locally quadratic extremum problems subject to linear(ized) constraints gives rise to linear systems in saddle point form. This is true whether in the continuous or the discrete setting, so saddle point systems arising from the discretization of partial differential equation problems, such as those describing electromagnetic problems or incompressible flow, lead to equations with this structure, as do, for example, interior point methods and the sequential quadratic programming approach to nonlinear optimization. This survey concerns iterative solution methods for these problems and, in particular, shows how the problem formulation leads to natural preconditioners which guarantee a fast rate of convergence of the relevant iterative methods. These preconditioners are related to the original extremum problem and their effectiveness---in terms of rapidity of convergence---is established here via a proof of general bounds on the eigenvalues of the preconditioned saddle point matrix on which iteration convergence depends.
LanguageEnglish
Pages71–91
Number of pages21
JournalSIAM Review
Volume57
Issue number1
DOIs
Publication statusPublished - 2015

Fingerprint

Saddle Point Systems
Incompressible flow
Quadratic programming
Preconditioning
Iterative methods
Partial differential equations
Linear systems
Extremum Problem
Iteration
Saddlepoint
Preconditioner
Interior Point Method
Iterative Solution
Nonlinear Optimization
Incompressible Flow
Quadratic Programming
Rate of Convergence
Partial differential equation
Discretization
Linear Systems

Keywords

  • inf-sup constant
  • iterative solvers
  • preconditioning
  • saddle point problems

Cite this

Pestana, Jennifer ; Wathen, Andrew J. / Natural preconditioning and iterative methods for saddle point systems. In: SIAM Review. 2015 ; Vol. 57, No. 1. pp. 71–91.
@article{f9eb23cdfa0d48098de2b3e0c3a3284d,
title = "Natural preconditioning and iterative methods for saddle point systems",
abstract = "The solution of quadratic or locally quadratic extremum problems subject to linear(ized) constraints gives rise to linear systems in saddle point form. This is true whether in the continuous or the discrete setting, so saddle point systems arising from the discretization of partial differential equation problems, such as those describing electromagnetic problems or incompressible flow, lead to equations with this structure, as do, for example, interior point methods and the sequential quadratic programming approach to nonlinear optimization. This survey concerns iterative solution methods for these problems and, in particular, shows how the problem formulation leads to natural preconditioners which guarantee a fast rate of convergence of the relevant iterative methods. These preconditioners are related to the original extremum problem and their effectiveness---in terms of rapidity of convergence---is established here via a proof of general bounds on the eigenvalues of the preconditioned saddle point matrix on which iteration convergence depends.",
keywords = "inf-sup constant, iterative solvers, preconditioning, saddle point problems",
author = "Jennifer Pestana and Wathen, {Andrew J.}",
year = "2015",
doi = "10.1137/130934921",
language = "English",
volume = "57",
pages = "71–91",
journal = "SIAM Review",
issn = "0036-1445",
number = "1",

}

Natural preconditioning and iterative methods for saddle point systems. / Pestana, Jennifer; Wathen, Andrew J.

In: SIAM Review, Vol. 57, No. 1, 2015, p. 71–91.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Natural preconditioning and iterative methods for saddle point systems

AU - Pestana, Jennifer

AU - Wathen, Andrew J.

PY - 2015

Y1 - 2015

N2 - The solution of quadratic or locally quadratic extremum problems subject to linear(ized) constraints gives rise to linear systems in saddle point form. This is true whether in the continuous or the discrete setting, so saddle point systems arising from the discretization of partial differential equation problems, such as those describing electromagnetic problems or incompressible flow, lead to equations with this structure, as do, for example, interior point methods and the sequential quadratic programming approach to nonlinear optimization. This survey concerns iterative solution methods for these problems and, in particular, shows how the problem formulation leads to natural preconditioners which guarantee a fast rate of convergence of the relevant iterative methods. These preconditioners are related to the original extremum problem and their effectiveness---in terms of rapidity of convergence---is established here via a proof of general bounds on the eigenvalues of the preconditioned saddle point matrix on which iteration convergence depends.

AB - The solution of quadratic or locally quadratic extremum problems subject to linear(ized) constraints gives rise to linear systems in saddle point form. This is true whether in the continuous or the discrete setting, so saddle point systems arising from the discretization of partial differential equation problems, such as those describing electromagnetic problems or incompressible flow, lead to equations with this structure, as do, for example, interior point methods and the sequential quadratic programming approach to nonlinear optimization. This survey concerns iterative solution methods for these problems and, in particular, shows how the problem formulation leads to natural preconditioners which guarantee a fast rate of convergence of the relevant iterative methods. These preconditioners are related to the original extremum problem and their effectiveness---in terms of rapidity of convergence---is established here via a proof of general bounds on the eigenvalues of the preconditioned saddle point matrix on which iteration convergence depends.

KW - inf-sup constant

KW - iterative solvers

KW - preconditioning

KW - saddle point problems

UR - http://epubs.siam.org/doi/abs/10.1137/130934921

U2 - 10.1137/130934921

DO - 10.1137/130934921

M3 - Article

VL - 57

SP - 71

EP - 91

JO - SIAM Review

T2 - SIAM Review

JF - SIAM Review

SN - 0036-1445

IS - 1

ER -