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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Parallel algorithms for the iterative solution of sparse least-squares problems
scientific article

    Statements

    Parallel algorithms for the iterative solution of sparse least-squares problems (English)
    0 references
    1990
    0 references
    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.
    0 references
    parallel iterative methods
    0 references
    parallel computing
    0 references
    least squares solution
    0 references
    large sparse overdetermined system
    0 references
    Gauss-Seidel method
    0 references
    successive overrelaxation
    0 references
    0 references
    0 references

    Identifiers