A product-form Cholesky factorization method for handling dense columns in interior point methods for linear programming (Q1424285)

In solving a symmetric system of linear equations with dense columns the Cholesky factorization is not efficient. A typical approach to remedy this fact is to apply the Sherman-Morrison-Woodbury (SMW) update formula to the dense part. This approach is very efficient, but it is not numerically stable. Then the authors propose using the product-form Cholesky factorization to handle dense columns. The proposed approach is stable and nearly efficient as the SMW approach. A key part of the theoretical analysis is the proof that the elements of the Cholesky factors of the matrices that arise in interior point methods used in linear programming are uniformly bounded as the duality gap converges to zero.