Constraint-style preconditioners for regularized saddle point problems

Sue Dollar
Dept. of Mathematics, University of Reading
Whiteknights, P.O.Box 220, Reading, Berkshire, RG6 6AX, UK
h.s.dollar@reading.ac.uk

The problem of finding good preconditioners for the numerical solution of a certain important class of indefinite linear systems is considered. These systems are of a saddle point structure

$\displaystyle \left( \begin{array}{cc} A & B^T \\ B & -C \end{array}\right) \l... ... \\ y \end{array}\right) = \left( \begin{array}{c} c \\ d \end{array}\right) , $

where $ A\in\mathbb{R}^{n\times n}$, $ C\in\mathbb{R}^{m\times m}$ are symmetric, and $ B\in\mathbb{R}^{m\times n}$ has full rank.

In Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl. 21 (2000), Keller, Gould and Wathen analyzed the idea of using constraint preconditioners that have a specific 2 by 2 block structure for the case of $ C$ being zero. We shall extend this idea by allowing the (2,2) block to be non-zero. Results concerning the spectrum and form of the eigenvectors are presented, as are numerical results to validate our conclusions. We will also introduce the idea of implicit-factorization constraint preconditioners which allow us to efficiently carry out the required preconditioning steps.