Numerical solution of saddle point problems. (English) Zbl 1115.65034

Benzi, Michele; Golub, Gene H.; Liesen, Jörg

Acta Numerica 14, 1-137 (2005).

This survey paper is a guide to applications, solution methods and software for saddle point problems which are (usually large) \(2\times2\) block linear systems of the form \[ \left[\begin{matrix} A & B_1^T\\ B_2 & -C\end{matrix}\right] \left[\begin{matrix} x\\ y\end{matrix}\right]= \left[\begin{matrix} f\\ g\end{matrix}\right],\qquad A\in{\mathbb R}^{n\times n}, \quad C\in{\mathbb R}^{m\times m},\quad n\geq m, \] with possibly one or more extra conditions on the blocks like, e.g., \(A\) is symmetric, the symmetric part of \(A\) is positive definite, \(C\) is zero or symmetric positive definite, \(B_1=B_2\), or more structure (Toeplitz, sparse, \(\ldots\)) can be assumed.
These problems occur in many diverse applications, from fluid dynamics, over image processing, to finance. Some of them are worked out in more detail.
Next, some of the properties of these methods are reviewed (solvability, spectral properties, numerical conditioning, \(\ldots\)), but most of the paper is devoted to solution algorithms, emphasizing iterative methods and preconditioning.
The paper is in the first place a survey with an exhaustive list of references. An excellent introduction for graduate students to this topic.

Reviewer: Adhemar Bultheel (Leuven)

MSC:

65F10	Iterative numerical methods for linear systems
65F50	Computational methods for sparse matrices
65F05	Direct numerical methods for linear systems and matrix inversion
65F35	Numerical computation of matrix norms, conditioning, scaling
65-02	Research exposition (monographs, survey articles) pertaining to numerical analysis
94A08	Image processing (compression, reconstruction, etc.) in information and communication theory
91G60	Numerical methods (including Monte Carlo methods)

Keywords:

saddle point problems; structured problem; preconditioning; iterative solvers; direct solvers; Krylov subspace method; fluid dynamics; interior point method; survey paper; image processing; finance

Software:

CUTEr; SOCS; LSQR; Trilinos; QMRPACK; MA47