Parallel algorithms for the iterative solution of sparse least-squares problems (Q916307)

The authors present two algorithms for the computation of the least squares solution of a large sparse overdetermined system of linear equations, which are based on papers of \textit{J. E. Dennis} jun. and \textit{T. Steihaug} [SIAM J. Numer. Anal. 23, 717-733 (1986; Zbl 0614.65059)] and \textit{T. F. Coleman} and \textit{J. J. Moré} [ibid. 20, 187-209 (1983; Zbl 0527.65033)]. For applying a generalized Gauss-Seidel method the columns of the coefficient matrix are grouped appropriately. In a lot of applications it will be possible to get mutually orthogonal columns in each submatrix. On the other hand the problems can easily be solved in parallel. The first algorithm cycles through the groups solving in parallel the smaller (and often trivial) linear systems. The second algorithm processes the group with the smallest residuum. For solving the linear systems with successive overrelaxation (SOR) methods the normal equations can be rewritten to speed up the convergence. Numerical experiments show (a) the efficiency of the parallelization (65 to 98\% for 2 or 4 processors), (b) the superiority of the second algorithm, and (c) the acceleration of the SOR method.