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
|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
checked on Dec 6, 2016
checked on Jan 23, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.