Spectral analysis of inexact constraint preconditioning for symmetric saddle point matrices
type: Item
instance of: scholarly article
title: Spectral analysis of inexact constraint preconditioning for symmetric saddle point matrices
zbMATH Open document ID: 1263.65029
author: Debora Sesana
author: Valeria Simoncini
published in: Linear Algebra and its Applications
publication date: 2013-02-21T00:00:00Z
review text: 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.
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F08
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65F50
zbMATH DE Number: 6138283
zbMATH Keywords: saddle point matrices
zbMATH Keywords: symmetric linear systems
zbMATH Keywords: Weyr canonical form
zbMATH Keywords: Jordan blocks
zbMATH Keywords: nonlinear perturbation
zbMATH Keywords: preconditioning
zbMATH Keywords: iterative method
zbMATH Keywords: convergence
zbMATH Keywords: numerical examples
describes a project that uses: HSL_MI20
MaRDI profile type: Publication
full work available at URL: j.laa.2012.11.022
OpenAlex ID: W1977745351
cites work: Krylov sequences of maximal length and convergence of GMRES
cites work: Constraint Preconditioners for Symmetric Indefinite Matrices
cites work: Numerical solution of saddle point problems
cites work: On the eigenvalues of a class of saddle point matrices
cites work: Inexact constraint preconditioners for linear systems arising in interior point methods
cites work: HSL_MI20 : An efficient AMG preconditioner for finite element problems in 3D
cites work: Using constraint preconditioners with regularized saddle-point problems
cites work: Constraint-Style Preconditioners for Regularized Saddle Point Problems
cites work: Implicit-Factorization Preconditioning and Iterative Solvers for Regularized Saddle-Point Systems
cites work: Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems
cites work: Q5702543
cites work: Q5751853
cites work: Q4328442
cites work: Constraint Preconditioning for Indefinite Linear Systems
cites work: Q5552491
cites work: Preconditioning discretizations of systems of partial differential equations.
cites work: On the Lidskii--Vishik--Lyusternik Perturbation Theory for Eigenvalues of Matrices with Arbitrary Jordan Structure
cites work: Q3102765
cites work: Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations
cites work: Krylov Subspace Methods for Saddle Point Problems with Indefinite Preconditioning
cites work: Parallel iterative methods for sparse linear systems
cites work: Symmetric Indefinite Preconditioners for Saddle Point Problems with Applications to PDE-Constrained Optimization Problems
cites work: The Weyr Characteristic
cites work: Recent computational developments in Krylov subspace methods for linear systems
cites work: Q3998482
DOI: 10.1016/J.LAA.2012.11.022
description: scientific article; zbMATH DE number 6138283