Spectral analysis of inexact constraint preconditioning for symmetric saddle point matrices (Q1938586)

A matrix with saddlepoint structure has the form \[ \mathcal{A}= \left[\begin{matrix} A&B^T\cr B&-C \end{matrix}\right],~~ 0\leq A\in\mathbb{R}^{n\times n}, ~~ 0<C\in\mathbb{R}^{m\times m},~~ m\leq n. \] A preconditioned form is \(\mathcal{AP}^{-1}\) with \[ \mathcal{P}=\left[\begin{matrix} I_n&B^T\cr B&-C\end{matrix}\right]= \left[\begin{matrix} I_n&0\cr B&I_m\end{matrix}\right]\left[\begin{matrix} I_n&0\cr 0&H\end{matrix}\right]\left[\begin{matrix} I_n&B^T\cr 0&I_m\end{matrix}\right],~~ H=BB^T+C. \] The convergence of an iterative solver for \(\mathcal{AP}^{-1}\) will depend on its spectrum. This paper gives an analysis of this spectrum by constructing the Weyr canonical form of the problem [\textit{H. Shapiro}, Am.\ Math.\ Mon.\ 106, No.~10, 919--929 (1999; Zbl 0981.15008)] taking into account its saddlepoint structure. That is a sparse representation that already reflects the structure of the eventual Jordan form. This is analysed first for the case \(C=0\) and \(\mathcal{P}\) exact. Since in large scale computations, it is often only feasible to use an approximate form of \(\mathcal{P}\), also the perturbation caused by this inexact preconditioner is analysed and illustrated with numerical examples. Finally, also the case \(C\neq0\) is considered which complicates the structure of the result. Explicit descriptions expose the linear and nonlinear influence of the perturbations. The spectral properties of the approximation of the core matrix \(H\) play a prominent role in predicting the distribution of the spectrum of the perturbed problem.