×

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

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.

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)
PDF BibTeX XML Cite
Full Text: DOI