Parallel strategies for rank-k updating of the qr decomposition
File(s)
Journal
SIAM Journal on Matrix Analysis and Applications
Date Issued
2000
Author(s)
Abstract
arallel strategies based on Givens rotations are proposed for updating the QR decomposition of an n × n matrix after a rank-k change (k < n). The complexity analyses of the Givens algorithms are based on the total number of Givens rotations applied to a 2-element vector. The algorithms, which are extensions of the rank-1 updating method, achieve the updating using approximately 2(k + n) compound disjoint Givens rotations (CDGRs) with elements annihilated by rotations in adjacent planes. Block generalization of the serial rank-1 algorithms are also presented. The algorithms are rich in level 3 BLAS operations, making them suitable for implementation on large scale parallel systems. The performance of some of the algorithms on a 2-D SIMD (single instruction stream-multiple instruction stream) array processor is discussed.