A preconditioner for generalized saddle point problems. (English) Zbl 1082.65034

Benzi, Michele; Golub, Gene H.

SIAM J. Matrix Anal. Appl. 26, No. 1, 20-41 (2004).

The authors consider the solution of large scale sparse systems of linear algebraic equations of a generalized saddle point type, i.e., of systems of a block \(2 \times 2\) structure \[ \left ( \begin{matrix} A & B^T \\ B & -C \end{matrix}\right) \left (\begin{matrix} u \\ p \end{matrix}\right) = \left (\begin{matrix} f \\ g \end{matrix}\right) , \] where \(A \in {\mathbb{R}}^{n \times n}\), \(B \in {\mathbb{R}}^{ m \times n}\), \(C \in {\mathbb{R}}^{m \times m}\), \(f \in {\mathbb{R}}^n\), \(g \in {\mathbb{R}}^m\), and \(m \leq n\) with the assumptions: \(A\) has a positive semidefinite part \(H =\frac{1}{2} (A+A^T)\); \(rank(B) = m\); \(\mathcal{N}(H) \cap \mathcal{N}(B) = \{0\}\); \(C\) is symmetric positive semidefinite. The existence and uniqueness of the solution is proved. The authors propose an alternating splitting iteration for the solution of such systems and show that this iteration can be efficiently used as a preconditioner for Krylov subspace methods like GMRES or its restarted version rather than as a stand-alone solver.
Numerical experiments with matrices from several different applications illustrate that the method is not overly sensitive to the choice of an optimization parameter \(\alpha\) which has been introduced into the alternating splitting iteration similar to the classical alternating direction method. The numerical examples also show that diagonal scaling additionally improves the convergence of the outer iteration.

Reviewer: Georg Hebermehl (Berlin)

MSC:

65F10	Iterative numerical methods for linear systems
65F35	Numerical computation of matrix norms, conditioning, scaling
65F50	Computational methods for sparse matrices
65N22	Numerical solution of discretized equations for boundary value problems involving PDEs

Keywords:

saddle point problem; matrix splittings; iterative methods; preconditioning; large scale sparse systems; Krylov subspace methods; GMRES; numerical experiments; alternating direction method; diagonal scaling; convergence