QR factorization of a dense matrix on a shared-memory multiprocessor
Eleanor Chu, Alan D. George · 1987
A new algorithm for computing an orthogonal decomposition of a rectangular m x n matrix A on a shared-memory parallel computer is described. The algorithm uses Givens rotations, and has the feature that its synchronization cost is low. In particular, for a multiprocessor having p processors, an analysis of the algorithm shows that this cost is O (n/sup 2//p) if m/p greater than or equal to n, and O (mn/p/sup 2/) if m/p > n. Analysis and experiments show that the algorithm is effective in balancing the load and producing high efficiency (speed-up). 13 refs.