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

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.