Please use this identifier to cite or link to this item: http://ktisis.cut.ac.cy/handle/10488/6791
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
URI: http://ktisis.cut.ac.cy/handle/10488/6791
ISSN: 01678191
DOI: 10.1016/S0167-8191(02)00132-1
Rights: © 2002 Elsevier Science B.V. All rights reserved.
Appears in Collections:Άρθρα/Articles

Show full item record

SCOPUSTM   
Citations 50

3
checked on Dec 6, 2016

Page view(s)

1
checked on Jan 23, 2017

Google ScholarTM

Check

Altmetric


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