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