Show simple item record

dc.contributor.authorVan Zee, Field G.
dc.contributor.authorVan de Geijn, Robert A.
dc.contributor.authorQuintana Ortí, Gregorio
dc.date.accessioned2015-06-17T10:14:08Z
dc.date.available2015-06-17T10:14:08Z
dc.date.issued2014-04
dc.identifier.citationVAN ZEE, F. G.; VAN DE GEIJN, R. A.; QUINTANA ORTÍ, G. Restructuring the Tridiagonal and Bidiagonal QR Algorithms for Performance. ACM Transactions on Mathematical Software, v. 40, issue 3 (April 2014) , pp. 18:2-18:34ca_CA
dc.identifier.urihttp://hdl.handle.net/10234/123806
dc.description.abstractWe show how both the tridiagonal and bidiagonal QR algorithms can be restructured so that they be- come rich in operations that can achieve near-peak performance on a modern processor. The key is a novel, cache-friendly algorithm for applying multiple sets of Givens rotations to the eigenvector/singular vector matrix. This algorithm is then implemented with optimizations that (1) leverage vector instruction units to increase floating-point throughput, and (2) fuse multiple rotations to decrease the total number of memory operations. We demonstrate the merits of these new QR algorithms for computing the Hermitian eigenvalue decomposition (EVD) and singular value decomposition (SVD) of dense matrices when all eigen- vectors/singular vectors are computed. The approach yields vastly improved performance relative to the traditional QR algorithms for these problems and is competitive with two commonly used alternatives— Cuppen’s Divide and Conquer algorithm and the Method of Multiple Relatively Robust Representations— while inheriting the more modest O(n) workspace requirements of the original QR algorithms. Since the computations performed by the restructured algorithms remain essentially identical to those performed by the original methods, robust numerical properties are preserved.ca_CA
dc.format.extent47 p.ca_CA
dc.format.mimetypeapplication/pdfca_CA
dc.language.isoengca_CA
dc.publisherACM Digital Libraryca_CA
dc.relation.isPartOfACM Transactions on Mathematical Software, v. 40, issue 3 (April 2014)ca_CA
dc.subjectEfficiencyca_CA
dc.subjectAlgorithmsca_CA
dc.subjectPerformanceca_CA
dc.subjectEigenvaluesca_CA
dc.subjectSingular valuesca_CA
dc.subjectTridiagonalca_CA
dc.subjectBidiagonalca_CA
dc.subjectEVDca_CA
dc.subjectSVDca_CA
dc.subjectQR algorithmca_CA
dc.subjectGivens rotationsca_CA
dc.subjectLinear algebraca_CA
dc.subjectLibrariesca_CA
dc.subjectHigh-performanceca_CA
dc.titleRestructuring the Tridiagonal and Bidiagonal QR Algorithms for Performanceca_CA
dc.typeinfo:eu-repo/semantics/articleca_CA
dc.identifier.doihttp://dx.doi.org/10.1145/2535371
dc.rights.accessRightsinfo:eu-repo/semantics/openAccessca_CA
dc.relation.publisherVersionhttp://dl.acm.org/citation.cfm?id=2535371ca_CA


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record