Please use this identifier to cite or link to this item:
Title: Greedy givens algorithms for computing the rank-k updating of the qr decomposition
Authors: Kontoghiorghes, Erricos John 
Keywords: Computational complexity;Algorithms
Issue Date: 2002
Publisher: Elsevier
Source: Parallel Computing, 2002, Volume 28, Issue 9, Pages 1257-1273
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
ISSN: 01678191
Rights: © 2002 Elsevier Science B.V. All rights reserved.
Type: Article
Appears in Collections:Άρθρα/Articles

Show full item record


checked on Feb 13, 2018

Page view(s) 50

Last Week
Last month
checked on Aug 17, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.