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
SCOPUSTM
Citations
3
checked on Nov 9, 2023
WEB OF SCIENCETM
Citations
50
3
Last Week
0
0
Last month
0
0
checked on Oct 29, 2023
Page view(s) 10
509
Last Week
1
1
Last month
12
12
checked on Aug 30, 2024
Google ScholarTM
Check
Altmetric
This item is licensed under a Creative Commons License