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

Chen Greif, Michael L. Overton

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)307-320
Number of pages14
JournalElectronic Transactions on Numerical Analysis
Volume37
StatePublished - 2010

Keywords

  • Preconditioners
  • Saddle point systems
  • Schur complement
  • Semidefinite programming

ASJC Scopus subject areas

  • Analysis

Fingerprint Dive into the research topics of 'An analysis of low-rank modifications of preconditioners for saddle point systems'. Together they form a unique fingerprint.

  • Cite this