Restructuring the Tridiagonal and Bidiagonal QR Algorithms for Performance
Ver/ Abrir
Impacto
Scholar |
Otros documentos de la autoría: Van Zee, Field G.; Van de Geijn, Robert A.; Quintana-Ortí, Gregorio
Metadatos
Mostrar el registro completo del ítemcomunitat-uji-handle:10234/9
comunitat-uji-handle2:10234/7036
comunitat-uji-handle3:10234/8620
comunitat-uji-handle4:
INVESTIGACIONMetadatos
Título
Restructuring the Tridiagonal and Bidiagonal QR Algorithms for PerformanceFecha de publicación
2014-04Editor
ACM Digital LibraryCita bibliográfica
VAN 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:34Tipo de documento
info:eu-repo/semantics/articleVersión de la editorial
http://dl.acm.org/citation.cfm?id=2535371Palabras clave / Materias
Efficiency | Algorithms | Performance | Eigenvalues | Singular values | Tridiagonal | Bidiagonal | EVD | SVD | QR algorithm | Givens rotations | Linear algebra | Libraries | High-performance
Resumen
We 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-fr ... [+]
We 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. [-]
Publicado en
ACM Transactions on Mathematical Software, v. 40, issue 3 (April 2014)Derechos de acceso
http://rightsstatements.org/vocab/CNE/1.0/
info:eu-repo/semantics/openAccess
info:eu-repo/semantics/openAccess
Aparece en las colecciones
- ICC_Articles [430]