A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows (Q1625762)

To solve a large linear least squares problem \(Ax=b\), \(A\in\mathbb{R}^{m\times n}\), \(m\geq n\), in which \(A\) consists of sparse rows \(A_s\) and nearly dense rows \(A_d\), it is worthwhile to treat these separately. In their previous paper [SIAM J. Sci. Comput. 39, No. 6, A2422--A2437 (2017; Zbl 1377.65050)], the authors have considered preconditioned iterative methods to deal with the dense part. In this paper, they use a Schur complement method instead. After eliminating \(r_s\), the sparse part of the residual, the reduced augmented normal equations have a \(2\times 2\) block matrix \(K\). The Schur complement method gives a block \(LDL^T\) factorization of \(K\). An incomplete Cholesky factor of \(\tilde{C}_s=C_s+\alpha I\) is used to approximate the Cholesky factor of \(C_s=A_s^TA_s\) (Tikhonov regularization). These replace the true factors in the Schur complement method which serves as a preconditioner. After solving the approximate system, only a few iterative steps are needed to solve the original problem. It is efficient to explicitly separate the zero columns in \(A_s\) from those that are not. If the size of \(\tilde{C}_s\) (the number of dense rows) becomes too large for a direct method, an iterative method can be used instead. Both the direct and the iterative methods are tested on a number of realistic problems.