Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.14279/2012
Title: | Greedy givens algorithms for computing the rank-k updating of the qr decomposition |
Authors: | Kontoghiorghes, Erricos John |
Major Field of Science: | Natural Sciences |
Field Category: | Computer and Information Sciences |
Keywords: | Computational complexity;Algorithms |
Issue Date: | 9-Sep-2002 |
Source: | Parallel Computing, 2002, vol. 28, no. 9, pp. 1257-1273 |
Volume: | 28 |
Issue: | 9 |
Start page: | 1257 |
End page: | 1273 |
Journal: | Parallel Computing |
Abstract: | A Greedy Givens algorithm for computing the rank-1 updating of the QR decomposition is proposed. An exclusive-read exclusive-write parallel random access machine computational model is assumed. The complexity of the algorithms is calculated in two different ways. In the unlimited parallelism case a single time unit is required to apply a compound disjoint Givens rotation of any size. In the limited parallelism case all the disjoint Givens rotations can be applied simultaneously, but one time unit is required to apply a rotation to a two-element vector. The proposed Greedy algorithm requires approximately 5/8 the number of steps performed by the conventional sequential Givens rank-1 algorithm under unlimited parallelism. A parallel implementation of the sequential Givens algorithm outperforms the Greedy one under limited parallelism. An adaptation of the Greedy algorithm to compute the rank-k updating of the QR decomposition has been developed. This algorithm outperforms a recently reported parallel method for small k, but its efficiency decreases as k increases |
URI: | https://hdl.handle.net/20.500.14279/2012 |
ISSN: | 1678191 |
DOI: | 10.1016/S0167-8191(02)00132-1 |
Rights: | ©Elsevier |
Type: | Article |
Affiliation : | Université de Neuchâtel |
Publication Type: | Peer Reviewed |
Appears in Collections: | Άρθρα/Articles |
CORE Recommender
This item is licensed under a Creative Commons License