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||URI:||http://ktisis.cut.ac.cy/handle/10488/6791||ISSN:||01678191||DOI:||http://dx.doi.org/10.1016/S0167-8191(02)00132-1||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) 50104
checked on Aug 17, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.