Parallel strategies for rank-k updating of the QR decomposition

Parallel strategies based on Givens rotations are proposed for updating the QR decomposition of an n x n matrix after a rank-k change (k< n). The comp lexity analyses of the Givens algorithms are based on the total number of G ivens rotations applied to a 2-element vector. The algorithms, which are ex tensions of the rank-1 updating method, achieve the updating using approxim ately 2(k + n) compound disjoint Givens rotations (CDGRs) with elements ann ihilated by rotations in adjacent planes. Block generalization of the seria l rank-1 algorithms are also presented. The algorithms are rich in level 3 BLAS operations, making them suitable for implementation on large scale par allel systems. The performance of some of the algorithms on a 2-D SIMD (sin gle instruction stream multiple instruction stream) array processor is disc ussed.