×

A pipelined Givens method for computing the QR factorization of a sparse matrix. (English) Zbl 0587.65018

This paper discusses an extension of the pipelined Givens method for computing the QR factorization of a real \(m\times n\) matrix to the case in which the matrix is sparse. When restricted to one process, the algorithm performs the same computation as the serial sparse Givens algorithm of A. George and the first author [ibid. 34, 69-83 (1980; Zbl 0459.65025)]. Our implementation is compatible with the data structures used in SPARSPAK. The pipelined algorithm is well suited to parallel computers having globally shared memory and low-overhead synchronization primitives, such as the Denelcor HEP, for which computational results are presented. We point out certain synchronization problems that arise in the adaptation to the sparse setting and discuss the effect on parallel speedup of accessing a serial data file.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices

Citations:

Zbl 0459.65025

Software:

symrcm
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Argyris, J. H.; Brönlund, O. E., The natural factor formulation of the stiffness matrix and displacement method, Comput. Methods Appl. Mech. Engrg., 5, 97-119 (1975) · Zbl 0291.73051
[2] Babb, R. G., Parallel processing with large grain data flow techniques, IEEE Trans. Comput., 17, 7, 55-61 (July 1984)
[3] Dongarra, J. J.; Sameh, A. H.; Sorensen, D. C., Implementation of some concurrent algorithms for matrix factorization, (Argonne National Lab. Report MCS/TM-25 (Oct. 1984)) · Zbl 0591.65027
[4] Gentleman, W., Error analysis of the QR decomposition by Givens transformations, Linear Algebra Appl., 10, 189-197 (1975) · Zbl 0308.65022
[5] Gentleman, M.; Kung, H. T., Matrix triangularization by systolic arrays, Proceedings SPIE 298 Real-Time Signal Processing IV (1981), San Diego, Calif.
[6] George, A.; Heath, M. T., Solution of sparse linear least squares problems using Givens rotations, Linear Algebra Appl., 34, 69-83 (1980) · Zbl 0459.65025
[7] George, J. A.; Heath, M. T.; Plemmons, R. J., Solution of large-scale sparse least squares problems using auxiliary storage, SIAM J. Sci. Statist. Comput., 2, 416-429 (1981) · Zbl 0469.65021
[8] George, A.; Liu, J., Computer Solution of Large Sparse Positive Definite Systems (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0516.65010
[9] Givens, W., Numerical computation of the characteristic values of a real symmetric matrix, (Oak Ridge National Lab. Report ORNL-1574 (1954)), Oak Ridge, Tenn. · Zbl 0055.35005
[10] Golub, G. H.; Plemmons, R. J., Large scale geodetic least squares adjustments by dissection and orthogonal decomposition, Linear Algebra Appl., 34, 3-28 (1980) · Zbl 0468.65012
[11] Lawson, C. L.; Hanson, R. J., Solving Least Squares Problems (1974), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0185.40701
[12] Lord, R.; Kowalik, J.; Kumar, S., Solving linear algebraic equations on an MIMD computer, J. Assoc. Comput. Mach., 30, 103-117 (1983) · Zbl 0502.65017
[13] Jordan, H. F., Experience with pipelined multiple instruction streams, IEEE Proc., 72, 1, 113-123 (Jan. 1984)
[14] Sameh, A.; Kuck, D., On stable parallel linear system solvers, J. Assoc. Comput. Mach., 25, 81-91 (1978) · Zbl 0364.68051
[15] Sorensen, D. C., Buffering for vector performance on a pipelined MIMD machine, Parallel Computing, 1, 143-164 (1984) · Zbl 0547.65036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.