Change search
ReferencesLink to record
Permanent link

Direct link
Applying recursion to serial and parallel QR factorization leads to better performance
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2000 (English)In: IBM Journal of Research and Development, ISSN 0018-8646, Vol. 44, no 4, 605-624 p.Article in journal (Refereed) Published
Abstract [en]

We present new recursive serial and parallel algorithms for QR factorization of an m by n matrix. They improve performance. The recursion leads to an automatic variable blocking, and it also replaces a Level 2 part in a standard block algorithm with Level 3 operations. However, there are significant additional costs for creating and performing the updates, which prohibit the efficient use of the recursion for large n. We present a quantitative analysis of these extra costs. This analysis leads us to introduce a hybrid recursive algorithm that outperforms the LAPACK algorithm DGEQRF by about 20% for large square matrices and up to almost a factor of 3 for tall thin matrices. Uniprocessor performance results are presented for two IBM RS/6000(R) SP nodes-a 120-MHz IBM POWER2 node and one processor of a four-way 332-MHz IBM PowerPC(R) 604e SMP node. The hybrid recursive algorithm reaches more than 90% of the theoretical peak performance of the POWER2 node, Compared to standard block algorithms, the recursive approach also shows a significant advantage in the automatic tuning obtained from its automatic variable blocking. A successful parallel implementation on a four-way 332-MHz IBM PPC604e SMP node based on dynamic load balancing is presented. For two, three, and four processors it shows speedups of up to 1.97, 2.99, and 3.97.

Place, publisher, year, edition, pages
IEEE Press, 2000. Vol. 44, no 4, 605-624 p.
National Category
Computer Science
URN: urn:nbn:se:umu:diva-21923DOI: 10.1147/rd.444.0605ISI: 000088316600011ISBN: 0018-8646OAI: diva2:212178
Available from: 2009-04-21 Created: 2009-04-21 Last updated: 2012-05-14Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Elmroth, ErikGustavson, F. G.
By organisation
Department of Computing Science
In the same journal
IBM Journal of Research and Development
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 34 hits
ReferencesLink to record
Permanent link

Direct link