A pipelined givens method for computing the QR factorization of a sparse matrix

AbstractThis paper discusses an extension of the pipelined Givens method for computing the QR factorization of a real m×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 George and Heath. 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