Splitting dense columns in sparse linear systems

We consider systems of equations of the form AA^Tx = b, where A is a sparse matrix having a small number of columns which are much denser than the other columns. These dense columns in A cause AA^T to be very (or even completely) dense, which greatly limits the effectiveness of sparse-matrix techniques for directly solving the above system of equations. In the literature on interior-point methods for linear programming, the usual technique for dealing with this problem is to split A into a sparse part S and a dense part D, A = [S D], and to solve systems involving AA^T in terms of the solution of systems involving SS^T using either conjugate-gradient techniques or the Sherman-Morrison-Woodbury formula. This approach has the difficulty that SS^T is often rank-deficient even when AA^T has full rank. In this paper we propose an alternative method which avoids the rank-deficiency problem and at the same time allows for the effective use of sparse-matrix techniques. The resulting algorithm is both efficient and robust.