Geodesic
An analysis of low-rank modifications of preconditioners for saddle point systems
Electronic transactions on numerical analysis, Tome 37 (2010), pp. 307-320
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.
Classification : 65F08, 65F10, 90C22
Keywords: saddle point systems, preconditioners, Schur complement, semidefinite programming 
@article{ETNA_2010__37__a6,
     author = {Greif,  Chen and Overton,  Michael L.},
     title = {An analysis of low-rank modifications of preconditioners for saddle point systems},
     journal = {Electronic transactions on numerical analysis},
     pages = {307--320},
     year = {2010},
     volume = {37},
     zbl = {1205.65142},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2010__37__a6/}
}
TY  - JOUR
AU  - Greif,  Chen
AU  - Overton,  Michael L.
TI  - An analysis of low-rank modifications of preconditioners for saddle point systems
JO  - Electronic transactions on numerical analysis
PY  - 2010
SP  - 307
EP  - 320
VL  - 37
UR  - http://geodesic.mathdoc.fr/item/ETNA_2010__37__a6/
LA  - en
ID  - ETNA_2010__37__a6
ER  - 
%0 Journal Article
%A Greif,  Chen
%A Overton,  Michael L.
%T An analysis of low-rank modifications of preconditioners for saddle point systems
%J Electronic transactions on numerical analysis
%D 2010
%P 307-320
%V 37
%U http://geodesic.mathdoc.fr/item/ETNA_2010__37__a6/
%G en
%F ETNA_2010__37__a6
Greif,  Chen; Overton,  Michael L. An analysis of low-rank modifications of preconditioners for saddle point systems. Electronic transactions on numerical analysis, Tome 37 (2010), pp. 307-320. http://geodesic.mathdoc.fr/item/ETNA_2010__37__a6/