A COARSE-GRAINED PARALLEL QR-FACTORIZATION ALGORITHM FOR SPARSE LEAST-SQUARES PROBLEMS

A sparse QR-factorization algorithm SPARQR for coarse-grained parallel computations is described. The coefficient matrix, which is assumed t o be general sparse, is reordered in an attempt to bring as many zero elements in the lower left corner as possible. The reordered matrix is then partitioned into block rows, and Givens plane rotations are appl ied in each block-row. These are independent tasks and can be done in parallel. Row and column permutations are carried out within the diago nal blocks in an attempt to preserve better the sparsity of the matrix . The algorithm can be used for solving least squares problems either directly or combined with an iterative method (preconditioned conjugat e gradients are used). Small non-zero elements can optionally be dropp ed in the latter case. This leads to a better preservation of the spar sity and, therefore, to a faster factorization, The price which has to be paid is some loss of accuracy. The iterative method is used to reg ain the accuracy lost during the factorization. Numerical results from several experiments with matrices from the well-known Harwell-Boeing collection as well as with some larger sparse matrices are presented i n this work. An SGI Power Challenge computer with 16 processors has be en used in the experiments. (C) 1998 Elsevier Science B.V. All rights reserved.