Geodesic
On the efficient update of rectangular LU-factorizations subject to low rank modifications
Electronic transactions on numerical analysis, Tome 26 (2007), pp. 161-177
In this paper we introduce a new method for the computation of KKT matrices that arise from solving constrained, nonlinear optimization problems. This method requires updating of null-space factorizations after a low rank modification. The update procedure has the advantage that it is significantly cheaper than a re-factorization of the system at each new iterate. This paper focuses on the cheap update of a rectangular LU-decomposition after a rank-1 modification. Two different procedures for updating the LU-factorization are presented in detail and compared regarding their costs of computation and their stability. Moreover we will introduce an extension of these algorithms which further improves the computation time. This turns out to be an excellent alternative to algorithms based on orthogonal transformations.
Classification : 15A23, 65F05, 65F30, 65K05, 90C53, 7, 2006, 4, 2006
Keywords: KKT-system, LU-factorization, low-rank modification, quasi-Newton method AMS subject classifications 
@article{ETNA_2007__26__a17,
     author = {Stange,  Peter and Griewank,  Andreas and Bollh\"ofer,  Matthias},
     title = {On the efficient update of rectangular {LU-factorizations} subject to low rank modifications},
     journal = {Electronic transactions on numerical analysis},
     pages = {161--177},
     year = {2007},
     volume = {26},
     zbl = {1171.15309},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2007__26__a17/}
}
TY  - JOUR
AU  - Stange,  Peter
AU  - Griewank,  Andreas
AU  - Bollhöfer,  Matthias
TI  - On the efficient update of rectangular LU-factorizations subject to low rank modifications
JO  - Electronic transactions on numerical analysis
PY  - 2007
SP  - 161
EP  - 177
VL  - 26
UR  - http://geodesic.mathdoc.fr/item/ETNA_2007__26__a17/
LA  - en
ID  - ETNA_2007__26__a17
ER  - 
%0 Journal Article
%A Stange,  Peter
%A Griewank,  Andreas
%A Bollhöfer,  Matthias
%T On the efficient update of rectangular LU-factorizations subject to low rank modifications
%J Electronic transactions on numerical analysis
%D 2007
%P 161-177
%V 26
%U http://geodesic.mathdoc.fr/item/ETNA_2007__26__a17/
%G en
%F ETNA_2007__26__a17
Stange,  Peter; Griewank,  Andreas; Bollhöfer,  Matthias. On the efficient update of rectangular LU-factorizations subject to low rank modifications. Electronic transactions on numerical analysis, Tome 26 (2007), pp. 161-177. http://geodesic.mathdoc.fr/item/ETNA_2007__26__a17/