MORE: talk by Miroslav Tůma

The efficient solution of large linear least squares problems in which the system matrix A contains rows with very different densities is challenging. There have been many classical contributions to solving this problem that focus on direct methods; they can be found in the monograph by Ake Bjorck. Such solvers typically perform a splitting of the rows of A into two row blocks, As and Ad. The block As is such that the sparse factorization of the normal matrix A^T_s As is feasible, while the rows in the block Ad have a relatively large number of nonzero entries. These dense rows are initially ignored, a factorization of the sparse part is computed using a sparse direct solver and then the solution updated to take account of the omitted dense rows.

There are two potential weaknesses of this approach. First, in practical applications the number of rows that contain a significant number of entries may not be small. Processing some of the denser rows separately may improve performance. Furthermore, large-scale problems require the use of preconditioned iterative solvers. A straightforward proposal to precondition the iterative solver using only an incomplete factorization of the sparse block while discarding the dense block may not lead to any success. In this presentation, we propose processing As separately within a conjugate gradient method using an incomplete factorization preconditioner combined with the factorization of a dense matrix of size equal to the number of rows in Ad. Problems arising from practical applications are used to demonstrate the potential of the new approach.