Abstract
A sparse QR-factorization algorithm for coarse-grain parallel computations is described. Initially the coefficient matrix, which is assumed to be general sparse, is reordered properly in an attempt to bring as many zero elements in the lower left corner as possible. Then the matrix is partitioned into large blocks of rows and Givens rotations are applied in each block. These are independent tasks and can be done in parallel. Row and column permutations are carried out within the blocks to exploit the sparsity of the matrix.
The algorithm can be used for solving least squares problems either directly or combined with an appropriate iterative method (for example, the preconditioned conjugate gradients). In the latter case, dropping of numerically small elements is performed during the factorization stage, which often leads to a better preservation of sparsity and a faster factorization, but this also leads to a loss of accuracy. The iterative method is used to regain the accuracy lost during the factorization.
An SGI Power Challenge computer with 16 processors has been used in the experiments. Results from experiments with matrices from the Harwell-Boeing collection as well as with automatically generated large sparse matrices are presented in this work.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. R. Amestoy, I. S. Duff and C. Puglisi, Multifrontal QR-factorization in a multiprocessor environment, TR/PA/94/09, CERFACS, 1994.
A. Björck, Stability analysis of the method of semi-normal equations for least squares problems, Linear Algebra Appl. 1988/89, pp. 31–48.
A. Björck, Least squares methods, in P. G. Ciarlet and J. L. Lions editors/, Handbook of Numerical Analysis, vol.1: Finite Difference Methods — Solution of Equations in R n, Elsevier/North-Holland, Amsterdam, 1990.
A. Björck, R. J. Plemmons and H. Schneider, Large-Scale Matrix Problems, North-Holland, New York, 1981.
I. S. Duff, A. M. Erisman and J. K. Reid, Direct Methods for Sparse Matrices, Oxford University Press, Oxford-London, 1986.
I. S. Duff, R. G. Grimes and J. G. Lewis, Sparse matrix test problems, ACM Trans. Math. Software, 15 (1989), pp. 1–14.
A. C. N. van Duin, P. C. Hansen, Tz. Ostromsky, H. Wijshoff and Z. Zlatev, Improving the numerical stability and the performance of a parallel sparse solver, Computers and Mathematics with Applications (to appear).
K. A. Gallivan, P. C. Hansen, Tz. Ostromsky and Z. Zlatev, A locally optimal reordering algorithm and its application to a parallel sparse linear system solver, Computing, vol.54 No.1, bf 1995, pp. 39–67.
W. M. Gentleman, Least squares computations by Givens transformations without square roots, J. Inst. Math. Appl. 12, 1973, pp. 329–336.
J. A. George and M. T. Heath, Solution of sparse linear least squares problems using Givens rotations, Linear Algebra Applications 34, 1980, pp. 69–73.
J. A. George, M. T. Heath and E. G. Y. Ng, A comparison of some methods for solving sparse linear least squares problems, SIAM J. Sci. Stat. Comput. 4, 1983, pp. 177–187.
J. A. George and E. G. Y. Ng, SPARSPAK: Waterloo sparse matrix package user's guide for SPARSPAK-B, Research Report CS-84-47, Department of Computer Science, University of Waterloo, Ontario, 1984.
J. W. Givens, Computation of plane unitary rotations transforming a general matrix to a triangular form, J. Soc. Ind. Appl. Math. 6, 1958, pp. 26–50.
A. S. Householder, Unitary triangularization of a nonsymmetric matrix, J. Assoc. Comput. Mach. 5, 1958, pp. 339–342.
P. Matstoms, The Multifrontal Solution of Sparse Linear Least Suares Problems, Thesis No.293, LIU-TEK-LIC-1991:33, Linköping, Sweden, 1991.
C. Puglisi, QR-factorization of large sparse overdetermined and square matrices using the multifrontal method in a multiprocessor environment, TR/PA/93/33, CERFACS, 1993.
J. R. Rice, PARVEC workshop on very large least squares problems and supercomputers, Report CSD-TR 464, Purdue University, West Lafayette, IN, 1983.
Xi. Wang, Incomplete Factorization Preconditioning for Linear Least Squares Problems, Ph.D. thesis, UIUC, Urbana, Illinois, 1993.
Z. Zlatev, Computational Methods for General Sparse Matrices, Kluwer Academic Publishers, Dordrecht-Toronto-London, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ostromsky, T., Hansen, P.C., Zlatev, Z. (1996). A parallel sparse QR-factorization algorithm. In: Dongarra, J., Madsen, K., Waśniewski, J. (eds) Applied Parallel Computing Computations in Physics, Chemistry and Engineering Science. PARA 1995. Lecture Notes in Computer Science, vol 1041. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60902-4_49
Download citation
DOI: https://doi.org/10.1007/3-540-60902-4_49
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60902-5
Online ISBN: 978-3-540-49670-0
eBook Packages: Springer Book Archive