Convergence of a direct-iterative method for large-scale least-squares problems

AbstractIn 1975 Chen and Gentleman suggested a 3-block SOR method for solving least-squares problems, based on a partitioning scheme for the observation matrix A intoA=A1A2 where A1 is square and nonsingular. In many cases A1 is obvious from the nature of the problem. This combined direct-iterative method was discussed further and applied to angle adjustment problems in geodesy, where A1 is easily formed and is large and sparse, by Plemmons in 1979. Recently, Niethammer, de Pillis, and Varga have rekindled interest in this method by correcting and extending the SOR convergence interval. The purpose of our paper is to discuss an alternative formulation of the problem leading to a 2-block SOR method. For this formulation it is shown that the resulting direct-iterative method always converges for sufficiently small SOR parameter, in contrast to the 3-block formulation. Formulas for the optimum SOR parameter and the resulting asymptotic convergence factor, based upon ‖A2A-11‖2, are given. Furthermore, it is shown that this 2-cyclic block SOR method always gives better convergence results than the 3-cyclic one for the same amount of work per iteration. The direct part of the algorithm requires only a sparse-matrix factorization of A1. Our purpose here is to establish theoretical convergence results, in line with the purpose of the recent paper by Niethammer, de Pillis, and Varga. Practical considerations of choosing A1 in certain applications and of estimating the resulting ‖A2A-11‖2 will be addressed elsewhere