umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:umu:diva-21923DOI: 10.1147/rd.444.0605ISI: 000088316600011ISBN: 0018-8646 OAI: oai:DiVA.org:umu-21923DiVA: 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

Authority records BETA

Elmroth, ErikGustavson, F. G.

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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 48 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf