Volume 37, pp. 307-320, 2010.

An analysis of low-rank modifications of preconditioners for saddle point systems

Chen Greif and Michael L. Overton

Abstract

We characterize the spectral behavior of a primal Schur-complement-based block diagonal preconditioner for saddle point systems, subject to low-rank modifications. This is motivated by a desire to reduce as much as possible the computational cost of matrix-vector products with the (1,1) block, while keeping the eigenvalues of the preconditioned matrix reasonably clustered. The formulation leads to a perturbed hyperbolic quadratic eigenvalue problem. We derive interlacing results, highlighting the differences between this problem and perturbed linear eigenvalue problems. As an example, we consider primal-dual interior point methods for semidefinite programs, and express the eigenvalues of the preconditioned matrix in terms of the centering parameter.

Full Text (PDF) [195 KB], BibTeX

Key words

saddle point systems, preconditioners, Schur complement, semidefinite programming

AMS subject classifications

65F08, 65F10, 90C22

Links to the cited ETNA articles

[14]	Vol. 22 (2006), pp. 114-121 Chen Greif and Dominik Schötzau: Preconditioners for saddle point linear systems with highly singular (1,1) blocks

< Back